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

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 ２０

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