编译原理 形式语言题+答案_编译原理形式语言

编译原理 形式语言题+答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“编译原理形式语言”。

第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 所以，本文法具有二义性。