《编译原理》习题解答
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如下所示：
５