南京邮电大学 编译原理 课后习题答案和讲解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如下所示：

５

＃∈FOLLOW(E) FOLLOW(E)={#}

规则二

)∈FOLLOW(E) FOLLOE(E)={ )，#}

FIRST(E’)-{ε}FIRST(T’)-{ε}FIRST(F’)-{ε}规则三 FOLLOW(E) FOLLOW(E) FOLLOW(T) FOLLOW(T) FOLLOW(F) FOLLOW(F) 最后结果为：

FIRST(E’)={+, ε} FIRST(F’)={*, ε}

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧} FIRST(T’)={ (，a，b, ε，∧) FOLLOE(E)={ ), ＃} FOLLOW(E’)={＃，)} FOLLOW(T)={＋，＃，）} FOLLOW(T’)= {＋，＃，）}

FOLLOW(F)={ (，)，a，b，＋，＃，∧} FOLLOW(F’)={ (，)，a，b，＋，＃，∧} FOLLOW(P)= { (，)，a，b，＋，＃，∧,*} （2）证明该文法是LL（1）文法：

FOLLOW(E’) FOLLOW(E’)={# ，)} FOLLOW(T) FOLLOW(T)={＋，＃，）} FOLLOW(T’) FOLLOW(T’)= {＋，＃，）}

FOLLOW(F) FOLLOW(F)={ (，)，a，b，＋，＃，∧} FOLLOW(F’) FOLLOW(F’)= { (，)，a，b，＋，＃，∧} FOLLOW(P) FOLLOW(P)= { (，)，a，b，＋，＃，∧,*} FOLLOW(T) FOLLOW(T)={+}

FOLLOW(F) FOLLOW(F)={ (，a，b，∧} FOLLOW(P) FOLLOW(P)={*}

１１

证明：对于规则E’::=+E |ε，T’::=T |ε，F’::=*F’ |ε （仅有一边能推出空串） 有FIRST(+E)={+}∩FIRST(ε)= ?，FIRST(T)={(, a, b, ∧}∩FIRST(ε)= ? FIRST(*F’)={*}∩FIRST(ε)= ?，FIRST(+E)={+}∩FOLLOW(E’)= {#, )}=? FIRST(T)={(, a, b, ∧}∩FOLLOW(T’)= {+, #, )}=?

FIRST(*F’)={*}∩FOLLOW(F’)= { (，)，a，b，＋，＃，∧}=? 所以该文法是LL（1）文法。 （3）构造文法分析表 E E’ T T’ F F’ P

下面分析符号串a*b+b

步骤 分析栈 余留输入串 所用的产生式 1 #E a*b+b# E→TE’ 2 #E’T a*b+b# T→FT’ 3 #E’T’F a*b+b# F→PF’ 4 #E’T’F’P a*b+b# P →a 5 #E’T’F’a a*b+b#

6 # E’T’F’ *b+b# F’→*F’ 7 # E’T’F’* *b+b#

8 # E’T’F’ b+b# F’ →ε 9 # E’T’ b+b# T’ →T 10 # E’T b+b# T→FT’ 11 # E’T’F b+b# F→PF’ a E→TE’ T→FT’ T’ →T F→PF’ F’ →ε P →a b + * ( E→TE’ T→FT’ T’ →T F→PF’ F’ →ε P →(E) ) E’→ε T’ →ε F’ →ε ∧ # E→TE’ T→FT’ T’ →T F→PF’ E’→+E E→TE’ E’→ε T→FT’ T’ →T F→PF’ T’ →ε T’ →ε F’ →ε F’ →ε F’→*F’ P →b F’ →ε F’ →ε P →∧ １２

12 # E’T’F’P b+b# P →b 13 #E’T’F’b b+b#

14 #E’T’F’ +b# F’ →ε 15 #E’T’ +b# T’ →ε 16 #E’ +b# E’→+E 17 #E+ +b# 18 #E b# E→TE’ 19 #E’T b# T→FT’ 20 #E’T’F b# F→PF’ 21 # E’T’F’P b# P →b 22 # E’T’F’b b# 23 # E’T’F’ # F’ →ε 24 # E’T’ # T’ →ε 25 #E’ # E’→ε 26 # # 成功 所以符号串a*b+b是该文法的句子；

P145 13. 利用表4.6文法G[E]的优先关系矩阵，来分析符号串#b(((aa)a)a)b#和#((aa)a)#。 (1) 是文法的句子

步骤 1 2 3 4 5 6 7 # #b #b( #b(( #b((( #b(((a #b(((M < < < < < > = 符号栈 关系 输入串 规则 b(((aa)a)a)b# (((aa)a)a)b# ((aa)a)a)b# (aa)a)a)b# aa)a)a)b# a)a)a)b# a)a)a)b# M∷=a １３

8 9 10 11 12 13 14 15 16 17 18 19 20 21

#b(((Ma #b(((Ma) #b(((L #b((M #b((Ma #b((Ma) #b((L #b(M #b(Ma #b(Ma) #b(L #bM #bMb #Z = > > = = > > = = > > = > > )a)a)b# a)a)b# a)a)b# L∷=Ma) a)a)b# M∷=(L )a)b# a)b# a)b# L∷=Ma) a)b# M∷=(L )b# b# b# L∷=Ma) b# M∷=(L # # Z∷=bMb (2) 不是文法的句子

步骤 1 2 3 4 5 6 7 8 9 10 11

符号栈 关系 输入串 规则 # #( #(( #((a #((M #((Ma #((Ma) #((L #(M #(Ma #(Ma) < < < > = = > > = = > １４

((aa)a)# (aa)a)# aa)a)# a)a)# a)a)# M∷=a )a)# a)# a)# L∷=Ma) a)# M∷=(L )# # 12 13

#(L #M > > # L∷=Ma) # M∷=(L P146 17. 设已给文法G[S]: E∷＝E+T | T

T∷＝T*F | F F∷＝P↑F | P

P∷＝(E) | i

（1） 用迭代法构造优先函数； （2） 用优先函数表分析符号串i+i*i↑i

解：

( i * + ) ↑

( ·< ·< ·< ·< i ·< ·< ·< ·< * ·< >· >· ·< >· >· + ·< >· >· >· >· >· ) = >· >· >· >· >· ↑ ·< >· ·< ·< >· ·< （1）用迭代法构造优先函数 若R=S则f(R）=g(S) 若R··S则f(R）>g(S)

1 初始值 ○ f g ＋ 1 1 * 1 1 ↑ 1 1 ( 1 1 ) 1 1 i 1 1 2根据·<的优先关系修改f和g值 ○

１５

f g ＋ 1 2 * 1 2 ↑ 1 2 ( 1 2 ) 1 1 i 1 2 3根据>·的优先关系修改f和g值 ○ f g ＋ 3 2 * 3 2 ↑ 3 2 ( 1 2 ) 3 1 i 3 2 4根据=的优先关系修改f和g值 ○ f g ＋ 3 2 * 3 4 ↑ 3 4 ( 1 4 ) 3 1 i 3 4 重复○2―○4 f g f g f g 最终结果： f g

＋ 3 2 * 5 4 ↑ 5 4 ( 1 4 ) 5 1 i 5 4 ＋ 3 2 * 5 4 ↑ 5 6 ( 1 6 ) 5 1 i 5 6 ＋ 3 2 * 5 4 ↑ 5 6 ( 1 6 ) 7 1 i 7 6 ＋ 3 2 * 5 4 ↑ 5 6 ( 1 6 １６

) 7 1 i 7 6

（2）用优先函数表分析字符串i+i*i↑i

符号栈 ＃ ＃i ＃∨ ＃∨＋ ＃∨＋i ＃∨＋∨ ＃∨＋∨* ＃∨＋∨*i ＃∨＋∨*∨ ＃∨＋∨*∨↑ ＃∨＋∨*∨↑i ＃∨＋∨*∨↑∨ ＃∨＋∨*∨ ＃∨＋∨ ＃∨

关系 f(#)·< g(i) f(i) >·g(+) f(#)·< g(+) f(+)·< g(i) f(i) >·g(*) f(+)·< g(*) f(*)·< g(i) f(i) >·g(↑) f(*)·< g(↑) f(↑)·< g(i) f(i) >·g(#) f(↑) >·g(#) f(*) >·g#) f(+) >·g(#) 输入串 i+i*i↑i# +i*i↑i# +i*i↑i# i*i↑i# *i↑i# *i↑i# i↑i# ↑i# ↑i# i# # # # # # 最左素短语 i i i i ∨↑∨ ∨*∨ ∨＋∨ 成功 P146 19. 证明下面文法不是算符优先文法: S∷＝A[ ] | [

A∷＝aA | B] B∷＝a

证明： S→A[ ] A→aA

∵A →aA A→ B]

１７

S

A [ ]

a A

∴a ·< ]

∵A→B] B→a ∴ a >· ]

a

B ]

a >· ] 和a ·< ]矛盾，所以该文法非算符优先文法

P146 21. 利用表4.8文法G[E]优先关系矩阵分析下列句子: i, i+i, i*i+i, i*(i*i)以及i*(i+i*i)+((i+i)*i 解：以i*i+i为例，其余类似：

符号栈 ＃ ＃i ＃∨ ＃∨* ＃∨*i ＃∨*∨ ＃∨ ＃∨+ ＃∨+i ＃∨+∨ ＃∨ ∴i*i+i是文法G[E]的句子； 再以i*(i*i)为例：

符号栈 ＃ ＃i ＃∨ ＃∨*

关系 ·< >· ·< ·< >· >· ·< ·< >· >· 输入串 i*i+i# *i+i# *i+i# i+i# +i# +i# +i# i# # # # 最左素短语 i i ∨*∨ i ∨+∨ 成功 关系 ·< >· ·< ·< １８

输入串 i*(i*i)# *(i*i)# *(i*i)# (i*i)# 最左素短语 i ＃∨*( ＃∨*(i ＃∨*(∨ ＃∨*(∨* ＃∨*(∨*i ＃∨*(∨*∨ ＃∨*(∨ ＃∨*(∨) ＃∨*∨ ＃∨ ∴i*（i*i）是文法G[E]的句子；

·< >· ·< ·< >· >· >· >· i*i)# *i)# *i)# i)# )# )# )# # # # i i ∨*∨ (∨) ∨*∨ 成功 P146 22. 设有文法G[Z]: Z∷＝A | B

A∷＝aAb | c B∷＝aBb | d

（1） 试构造能识别此文法的全部活前缀DFA； （2） 试构造LR(0)分析表；

（3） 试分析符号串aacbb是否为此文法的句子。

解：在上述文法中引入新的开始符号Z’，并将Z’::=Z作为第0个规则，从而得到所谓的拓广文法G’，则其LR（0）项目有：

1Z’ ::= ·Z ○2 Z’ ::= Z· ○3 Z::= ·A ○4 Z::= A· ○

5 Z ::= ·B ○6 Z ::= B· ○7 A ::= ·aAb ○8 A ::= a·Ab ○

9 A::= aA ·b ○10 A ::=aAb· ○11 B ::= ·aBb ○12 B ::= a·Bb ○

13 B ::=aB ·b ○14 B ::= aBb· ○15 B::= ·d ○16 B::= d· ○

17 A::=·c ⒅A::= c· ○(1)

１９

Z I1: Z’ ::= Z· I0: Z’ ::= ·Z Z::= ·A Z ::= ·B A ::= ·aAb A::=·c B ::= ·aBb B::= ·d d c a A I2: Z::= A· a I3: Z ::= B· A I7: A::= aA·b I9: b A::= aAb· B I4: A ::= a·Ab A ::= ·aAb A::=·c B ::= a·Bb B ::= ·aBb B::= ·d I5: A::= c· c B I8: B ::=aB·b b I6: B::= d· d I10: B::= aBb·

(2)构造LR（0）分析表

状态 ACTION a b c d # 0 1 2 3 4 5 6 7 8 9 S4 r1 r2 S4 r4 r6 r3 r1 r2 r4 r6 S9 S10 r3 S5 r1 r2 S5 r4 r6 r3 S6 r1 r2 S6 r4 r6 r3 acc r1 r2 r4 r6 r3 7 8

GOTO Z A B 1 2 3 ２０

10 r5 r5 r5 r5 r5 规则顺序：r1：Z→A r2：Z→B r3: A→aAb r4: A→C r5: B→aBb r6: B→d

(3)分析符号串aacbb是否为该文法的句子

步骤 1 2 3 4 5 6 7 8 9 10

状态栈 0 04 044 0445 0447 04479 047 0479 02 01 符号栈 ＃ ＃a ＃aa ＃aac ＃aaA ＃aaAb ＃aA ＃aAb ＃A ＃Z 输入串 aacbb＃ acbb＃ cbb＃ bb＃ bb＃ b＃ b＃ ＃ ＃ ＃ 分析动作 S4 S4 S5 r4 S9 r3 S9 r3 r1 acc 下一状态 4 4 5 GOTO[4,A]=7 9 GOTO[4,A]=7 9 GOTO[0,A]=2 GOTO[0,Z]=1 成功 P147 24. 给定文法： E∷＝EE+ | EE* | a

（1） 构造它的LR(0)项目集规范族；

（2） 它是SLR(1)文法吗？若是，构造它的SLR(1)分析表； 解：

(1) 在上述文法中引入新的开始符号E’,并将E’作为第0个规则 r1:E∷=EE+ r2: E∷=EE* r3: E∷=a 则基本LR(0)项目集为： ⑴E’∷=?E ⑸E∷=EE?+ ⑼E∷=EE?*

⑵E’∷=E?

⑶E∷=?EE+

⑷E∷=E?E+

⑻E∷=E?E*

⑹E∷=EE+? ⑽E∷=EE*?

⑺E∷=?EE* ⑾E∷=?a

⑿E∷=a?

２１

I0: E’∷=?E E∷=?EE+ E∷=?EE* E∷=?a

a E I1: E’∷=E? E∷=E?E+ E∷=?EE+ E∷=E?E* E∷=?EE* E∷=?a E I3: E∷=?a E∷=EE?+ E∷=E?E+ E∷=?EE+ E∷=EE?* E∷=E?E* E∷=?EE* a E + I4: E∷=EE+? * I5: E∷=EE*? I2: E∷=a? a

(2) 在I1中存在“移进E->?a”和“归约：E’->E?”冲突，因此该文法不是LR(0)文法，但有FOLLOW(E’)={#}∩{a}=Ф，而该动作冲突可用SLR(1)方法解决，该文法是SLR(1)文法，其分析表如下：

ACTION 状态 + 0 1 2 3 4 5

r3 S4 r1 r2 * r3 S5 r1 r2 a S2 S2 r3 S2 r1 r2 # acc r3 r1 r2 E 1 3 3 GOTO

P194 2. 给出下面表达式的后缀式表示： 解： (2) ┐a∨┐(c∨┐d) : a┐cd┐∨┐∨

(3) a+b*(c+d/e) : abcde/+*+ (4) (a∧b)∨(┐c∨d) : ab∧c┐d∨∨ (5) –a+b*(-c+d) : a-bc-d+*+

(6) (a∨b) ∧(c∨┐d∧e) : ab∨cd┐e∧∨∧

P195 4. 将下列中缀式改写为后缀式表示：

２２

解： (2) ((a*d+c)*d+e)*f+g : ad*c+d*e+f*g+

(3) a+x*(b+x*(c+x*(d+x*(e+x*f)))) : axbxcxdxexf*+*+*+*+*+ (4) x?-5∨x?5 : x5-?x5?∨

２３

本文来源：https://www.bwwdw.com/article/3gyd.html