编译原理第三章答案

第1题 

文法G＝({A,B,S},{a,b,c},P,S)其中P为： 

S→Ac|aB 

A→ab 

B→bc 

写出L(G[S])的全部元素。 

答案： 

L(G[S])={abc} 

第2题 

文法G[N]为： 

N→D|ND 

D→0|1|2|3|4|5|6|7|8|9 

G[N]的语言是什么？ 

答案: 

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} 

N=>ND=>NDD.... =>NDDDD...D=>D......D

或者：允许0开头的非负整数？ 

第３题 

为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。 

答案： 

G[S]: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9

第4题 

已知文法G[Z]： 

Z→aZb|ab 

写出L(G[Z])的全部元素。

答案： 

Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb

L(G[Z])={anbn|n>=1}

第5题 

写一文法，使其语言是偶正整数的集合。 要求： 

(1) 允许0打头； 

(2)不允许0打头。 

答案： 

(1)允许0开头的偶正整数集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 

(2)不允许0开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 

第6题 

已知文法G： 

<表达式>::=<项>｜<表达式>＋<项>

<项>::=<因子>｜<项>*<因子>

<因子>::=（<表达式>）｜i 

试给出下述表达式的推导及语法树。 

（５）i+(i+i) 

（６）i+i*i

第8题 

文法G[S]为： 

S→Ac|aB 

A→ab 

B→bc 

该文法是否为二义的？为什么？ 

答案： 

对于串abc 

(1)S=>Ac=>abc (2)S=>aB=>abc

即存在两不同的最右推导。所以，该文法是二义的。 

或者：

第10题 

文法S→S(S)S|ε 

(1) 生成的语言是什么？ 

(2) 该文法是二义的吗？说明理由。 

答案： 

（１） 嵌套的括号 

（２） 是二义的，因为对于（）（）可以构造两棵不同的语法树。 

第11题 

令文法G[E]为： 

E→T|E+T|E-T 

T→F|T*F|T/F 

F→(E)|i 

证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

第14题 

给出生成下述语言的上下文无关文法： （1）{ anbnambm| n，m>=0} （2）{ 1n0m 1m0n| n，m>=0}

（3）{WaWr|W属于{0|a}*，Wr表示W的逆} 

答案： 

（１） S→AA A→aAb|ε （２） S→1S0|A A→0A1|ε （３） 

S→0S0|1S1|ε

第16题 给出生成下述语言的三型文法： 

(1){an|n >=0 }

(2) { anbm|n,m>=1 }

(3){anbmck|n,m,k>=0 }

答案： 

(1) S→aS|ε 

(2) S→aA A→aA|B B→bB|b 

(3) A→aA|B B→bB|C C→cC|ε

第18题 

解释下列术语和概念： 

（１） 字母表 

（２） 串、字和句子 

（３） 语言、语法和语义 

答案： 

（1）字母表：是一个非空有穷集合。

（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所 

有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。 

语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 

语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。

附加题

问题1： 

给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0 

答案： 

R = (01 | 10) ( 01 | 10 )* 

问题2： 

已知文法G[A]，写出它定义的语言描述 G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 

答案: 

G[A]定义的语言由0、1符号串组成，串中0和1的个数相同. 

问题3： 

给出语言描述，构造文法. 构造一文法,其定义的语言是由算符+, *, (,)和运算对象a构成的算术表达式的集合. 

答案一： 

G[E] E→E+T|T T→T* F|F F→(E)|a 

答案二： 

G[E] E→E+E|E* E|(E)|a 

问题4： 

已知文法G[S]: 

S→dAB

A→aA|a 

B→ε|bB 

相应的正规式是什么？G[S]能否改写成为等价的正规文法？ 

答案： 

正规式是daa*b*； 

相应的正规文法为(由自动机化简来)： 

G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 

也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε

问题5： 

已知文法G： 

E→E+T|E-T|T 

T→T*F|T/F|F 

F→(E)|i 

试给出下述表达式的推导及语法树 

(1) i; 

(2) i*i+i 

(3) i+i*i 

(4) i+(i+i) 

答案： 

(1)E=>T=>F=>i

(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i

(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i)