编译原理 形式语言题+答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“编译原理形式语言”。
第2章 形式语言
1．试分别构造产生下列语言的文法：（1）{an#bn|n≥0}∪{cn#dn|n≥0}；
（2）任何不是以0打头的所有奇整数所组成的集合。
答：(1)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X, S→Y, X→aXb|#, Y→cYd|# },S)
(2)G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9}, {S→J|IBJ, B→0B|IB|ε, I→J|2|4|6|8, J→1|3|5|7|9},S)
2．对于下列的文法
S→AB|c
A→bA|a
B→aSb|c
试给出句子bbaacb的最右推导。
答：S=>AB=>AaSb=> Aacb=>bAacb=>bbAacb=>bbaacb
3．已知文法G[S]:
S->(AS)|(b)
A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。答：
因为S 不能 (a), 所以(a)不是文法的句型。没有短语、直接短语和句柄。
因为S (AS)(A(AS))(A((SaA)S))(A((SaA)(b))),所以(A((SaA)(b)))是文法的句型。短语：(A((SaA)(b)))，((SaA)(b))，(SaA)，(b)直接短语：(SaA)，(b)句柄：(SaA)S
（A
S)
（A
S)
（S a A)（b)
4．试描述由下列文法所产生的语言的特点：（1）S→10S0
S→aA
A→bA
A→a（2）S→aSS
S→a
答：(1)本文法构成的语言集为：L(G)={(10)nabma0n|n,m≥0}。(2)由L(G)={a2n-1|n≥1}可知，该语言特点是：产生的句子是奇数个a。
附加题：试证明文法
S→AB|DC
A→aA|a
B→bBc|bc
C→cC|c
D→aDb|ab 为二义性文法。
答：因为存在句子：abc，它对应两个最右推导：
S AB Abc abc S DC Dc abc 所以，本文法具有二义性。
编译原理心得体会编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法，在计算机本科教学中占有十分重要的地位。该课程理论性与实践性都很强，我们......
编译原理实验报告报告完成日期 2018.5.30 一． 组内分工与贡献介绍二． 系统功能概述；我们使用了自动生成系统来完成我们的实验内容。我们设计的系统在完成了实验基本要求的前提......
国际学院 0802 杨良燕 200819100227《编译原理》课程学习心得《编译原理》是计算机专业的一门重要课程，正如教材第一章的引论所述，“编译程序是现代计算机系统的基本组成部分......
编译原理教学大纲一、课程的性质、地位本课程是计算机专业的重要专业课之一，是一门理论性和实践性较强的课程。主要介绍程序设计语言编译程序构造的基本原理和基本实现方法。......
《编译原理》试题A 1．名词解释短语LL（1）文法 语法分析无环路有向图(DAG) 语法制导翻译 2． Pascal语言无符号数的正规定义如下：num digit+ (.digit+)? (E(+|-)? digit+)? 其中dig......
