南京邮电大学 编译原理 课后习题答案和讲解2

《编译原理》习题解答

P38-39 8、设有文法G[S]：

S∷＝aAb A∷＝BcA | B B∷＝idt |ε

试问下列符号串（1）aidtcBcAb （3）ab （5）aidtcidtcidtb 是否为该文法的句型或句子。 （1）S?aAb?aBcAb?aidtcAb?aidtcBcAb 句型但不是句子； （3）S?aAb?aBb?aεb?ab 是句型也是句子；

（5）S?aAb?aBcAb?aidtcAb?aidtcBcAb?aidtcidtcBb?aidtcidtcidtb句型也是句子。

P39 10、给定文法：

S∷＝aB | bA A∷＝aS | bAA | a

B∷＝bS | aBB|b 该文法所描述的语言是什么？

L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。

P39 11、试分别描述下列文法所产生的语言（文法开始符号为S）：

（1） S∷＝0S | 01 （2） S∷＝aaS | bc （3） S:: =aSd | aAd

A:: =aAc | bc （4） S:: =AB

A:: =aAb | ab B:: =cBd | ε

（1） L(G)＝{0n1| n≥1}； （2） L(G)＝{a2nbc | n≥0}；

１

（3） L(G)＝{aibcjdk | i, j, k≥1, i=j+k-1}；或者 L(G)＝{aj+k-1bcjdk | j, k≥1}； （4） L(G)＝{anbncmdm | m≥0, n≥1}。

P39 15. 设文法G规则为：

S：：=AB B：：=a|Sb A：：=Aa|bB

对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。 （2）baabaab

（2） S A B A a S b

b B A B

a b B a

a

句型baabaab的短语a, ba, baa, baab, baabaab，简单短语a，句柄 a

P40 19. 证明下述文法是二义的 1) S::=iSeS|iS|i 3) S::=A|B

A::=aCbA|a B::=BCC|a

２

C::=ba (最简单的就是a为句型)

1) 对于句子iiieii可构造两棵不同的语法树，所以证明该文法是二义的。

P41 24. 下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？

1.S::=aB B::= cB B::=b C::=c 2.S::=aB B::=bC C::=c C::=ε

3.S::=aAb aA::=aB aA::=aaA B::=b A::=a 4.S::=aCd aC::=B aC::=aaA B::=b 5.S::=AB A::=a B::=bC B::=b C::=c 6. S::=AB A::=a B::=bC C::=c C::=ε 7. S::=aA S::= ε A::=aA A::=aB A::=a B::=b 8. S::=aA S::= ε A::=bAb A::=a 正规文法 1 2 7 上下文无关文法 5 6 8 上下文有关文法 3 短语结构文法 4

P42 29. 用扩充的BNF表示以下文法规则：

1． 2． 3．

Z::=AB|AC|A

A::=BC|BCD|AXZ|AXY S::=aABb|ab

３

4． 解:

A::=Aab|ε

1．Z::=A（B|C|ε）::=A[B|C]

2．A::=BC（ε|D）{X（Z|Y）}::= BC[D] {X（Z|Y）} 3．A::=a((AB|ε)b) ::= a[AB]b 4．A::={ab}

P74 4. 画出下列文法的状态图：

Z：：=Be B：：=Af

A：：=e|Ae 并使用该状态图检查下列句子是否该文法的合法句子：f, eeff, eefe。

由状态图可知只有eefe是该文法的合法句子。

P74 5. 设右线性文法G=({S, A, B}, {a, b}, S, P)，其中P组成如下：

S：：=bA A：：=bB A：：=aA A：：=b B：：=a 画出该文法的状态转换图。

４

P74 8. 设 (NFA) M = ( {A, B}, {a, b}, M, {A}, {B} )，其中M定义如下：

M (A, a) = {A, B} M (A, b) = {B} M (B, a) = ? M (B, b) = {A, B}

请构造相应确定有穷自动机(DFA) M’。

解：构造一个如下的自动机(DFA) M’， (DFA) M’={K’, {a, b}, M’, S’, Z’} K’的元素是[A] [B] [A, B]

由于M（A, a）={A, B}，故有M’（[A], a）=[A, B] 同样 M’（[A]，b）=[B]

M’（[B]，a）= ? M’（[B]，b）=[A，B]

由于M（{A，B}，a）= M（A，a）U M（B，a）= {A，B}U ?= {A，B} 故 M’（[A，B]，a）= [A，B]

由于M（{A，B}，b）= M（A，b）U M（B，b）={B}U {A，B} = {A，B} 故 M’（[A，B]，b）= [A，B] S’=[A]，终态集Z’={[A，B]，[B]}

重新定义：令0=[A] 1=[B] 2=[A, B]，则DFA如下所示：

５

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新经管营销南京邮电大学 编译原理 课后习题答案和讲解2 全文阅读和word下载服务。