编译原理教程课后习题答案——第三章(6)

S→;·A↑,# I9: A→a·,↑ A→·a,↑ B→a·,d B→·a,d 根据LR(1)项目集族，将同心集合并(即去掉向前搜索符后两个项目的产生式相同)。经检查，只有I6与I9同心，即将I6和I9合并为I69： I69：A→a·,↑/d B→a·,↑/d 此时出现了“归约”/“归约”冲突，即对“↑”或“d”不知是用A→a·归约，还是用B→a·归约，故G[S]不是LALR文法。 (2) 当一个文法是LR(1)而不是LALR时，那么LR(1)项目集的同心集合并后只可能出现“归约”/“归约”冲突，而不会是“移进”/“归约”冲突。因为如果存在这种冲突，则意味着面对当前输入符号a，有一个项目[A→α·,a]要求采取归约动作，同时又有另一项目[B→β·aγ,b]要求把a移进。这两个项目既然同处在合并之后的一个集合中，就意味着在合并前必有某个c使得[A→α·,a]和[B→β·aγ,c]同处于(合并之前的)某一集合中，然而这又意味着原来的LR(1)项目集已经存在着“移进”/“归约”冲突了。因此，同心集的合并不会产生新的“移进”/“归约”冲突(因为是同心合并，所以只改变了搜索符，而并没有改变“移进”或“归约”操作，故不可能存在“移进”/“归约”冲突)。

但是，同心集的合并有可能产生新的“归约”/“归约”冲突。例如本题中，对活前缀aa有效的项目集为I6：{[ A→a·,d],[ B→a·,↑]}，对活前缀 ,a有效的项目集为I9：{[ A→a·,↑],[ B→a·,d]}，这两个集合都不含冲突，它们是同心的，但合并之后就变成{[ A→a·,↑/d],[ B→a·, ↑/d]}，显然这是一个含有“归约”/“归约”冲突的集合，因为当面临“↑”或“d”时我们不知道该用A→a还是B→a进行归约。

3.29 给定文法G[A]: A→(A)|a。 (1) 证明：LR(1)项目[A→(A·),]]对活前缀“((a”是有效的； (2) 画出LR(1)项目识别所有活前缀的DFA； (3) 构造LR(1)分析表； (4) 合并同心集，构造LALR(1)分析表。 【解答】 (1) 证明：首先将文法D[A]拓广为 G[A′]：(0) A′ → A (1) A → (A) (2) A → a

其次，构造文法G[A′]的FOLLOW集如下: ① FOLLOW(A′)={#}； ② 由A→…A)得FIRST(′)′)\\{ε}?FOLLOW(A)，即FOLLOW(A)={)}； ③ 由A′→A得，FOLLOW(A′) ?FOLLOW(A)，即FOLLOW(A)={),#}。 下面构造LR(1)项目集规范族，其构造方法如下： ① I的任何项目都是属于CLOSURE(I)的； ② 若项目[A→α·Bβ,a]属于CLOSURE(I)，B→γ是一个产生式，对FIRST(βa)中的每个终结符b，如果[B→·γ,b]原来不在CLOSURE(I)中，则把它加进去； ③ 重复执行步骤②，直至CLOSURE(I)不再增大为止。 注意，b可能是从β推出的第一个符号；若β推出ε，则b就是a。 由此得到文法G[A′]的LR(1)项目集规范族如下(项目集I0由A′→·A，#开始)： I0: A′→·A,# I4: A→(A·),# A′→·(A),# I5: A→(A)·,#

A→·a,# I6: A→(·A),) I1: A′→A·,# A→·(A),) I2: A→(·A),# A→·a,) A→·(A),) I7: A→(A·),) A→ ·a,) I8: A→(A)·,) I3: A→a·,# I9: A→a·,) LR(1)识别所有活前缀的DFA如图3-18所示。 而项目[A→(A·),]]对应图3-18中的I7，即由I0到达I7的活前缀(即由I0到达I7道路上的字符组成)为“(…(A”，其中“(…(”至少有两个“(”。由此得到项目[A→(A·),])对活前缀“((A”有效。 (2) LR(1)项目识别所有活前缀的DFA如图3-18所示。 (3) 构造的LR(1)分析表见表3-14。 A′ I1：A →A·,# A) I4：A→(A·),# I5：A→(A)·,#′ I0：A →·A,# I：A→(·A),#2( ′ A →·(A),# A→·(A),)( A→·a,# A→·a,) I6：A→(·A),)A A→·(A),) I7：A→(A·),) aa A→·a,)( )a I8：A→(A)·,) I3：A→a·,# I9：A→a·,) 图3-18 识别活前缀的DFA

表3-14 习题3.29的LR(1)分析表 ACTION GOTO 状态 ( ) a # A 0 s2 s3 I 1 acc 2 s6 s9 4 3 r2 4 s5 5 r1 6 s6 s9 7 7 s8 8 r1 9 r2 将I3、I9合并成I39：[A→a· ，)/#]； 将I2、I6合并成I26：[A→(·A)，)/#]，[A→·(A)，)]，[A→·a，)]； 将I4、I7合并成I47：[A→(A·)，)/#]； 将I5、I8合并成I58：[A→(A)· ，)/#]。 由此得到合并后集族所构成的LALR分析表，见表3-15。 表3-15 合并后集族所构成的LALR分析表

ACTION GOTO 状态 ( ) a # A

0 s26 s39 1

1 acc

26 s26 s39 47

39 r2 r2 47 s58

58 r1 r1 3.30 下述文法G[S]是哪类LR文法？构造相应LR分析表。 G[S]: (1) S→L=R (2) S→R (3) L→*R (4) L→i (5) R→L

【解答】 首先将文法G[S]拓广为G[S′]：(0) S′→S (1) S→L=R (2) S→R (3) L→*R (4) L→i (5) R→L 构造文法G[S′]的LR(0)项目集规范族如下： I0: S′→·S I2: S→L·=R I5: S→R· S→·L=R R→L· I6: S→L=·R S→·R I3: L→*·R R→·L L→·*R R→·L L→·*R L→·i L→·*R L→·i R→·L L→·i I7: S→L=R· I1: S′→S· I4: L→i· I8: L→*R· 我们知道，如果每个项目集中不存在既含移进项目又含归约项目，或者含有多个归约项目的情况，则该文法是一个LR(0)文法。检查上面的项目集规范族，发现I2存在既含移进项目S→L·=R又含归约项目R→L·的情况，故文法G[S]不是LR(0)文法。 假定LR(0)规范族的一个项目集I中含有m个移进项目： A1→α·a1β1, A2→α·a2β2,…, Am→α·amβm 同时I中含有n个归约项目: B1→α·, B2→α·,…, Bn→α· 如果集合{a1,…,am}，FOLLOW(B1)，…，FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集含有“#”)，则要解决隐含在I中的动作冲突，可检查现行输入符号a属于上述n+1个集合中的哪个集合，这就是SLR(1)文法。 因此，构造文法G[S′]的FOLLOW集如下： (1) FOLLOW(S′)={#}； (2) 由S→L=…得FIRST(′=′)\\{ε}?FOLLOW(L)，即FOLLOW(L)={=}； (3) 由S′→S得FOLLOW(S′) ?FOLLOW(S)，即FOLLOW(S)={#}；

由S→R得FOLLOW(S) ?FOLLOW(R)，即FOLLOW(R)={#}； 由L→…R得FOLLOW(L) ?FOLLOW(R)，即FOLLOW(R)={=,#}； 由R→L得FOLLOW(R) ?FOLLOW(L)，即FOLLOW(L)={=,#}。 由I2的移进项目S→L·=R和归约项目R→L·得到：

{=}∩FOLLOW(L)={=}∩{=,#}={=}≠Φ 所以文法G[S]不是SLR(1)文法。 下面构造LR(1)项目集规范族，得到文法G[S′]的LR(1)项目集规范族如下(项目集I0由S′→·S,#开始)： I0: S′→·S,# I6: S→L=·R,# S→·L=R,# R→·L,# S→·R,# L→·*R,# L→·*R,= L→·i,# L→·i,= I7: L→*R·,= R→·L,# I8: R→L·,= I1: S′→S·,# I9: S→L=R·,# I2: S→L·=R,# I10: R→L·,# R→L·,# I11: L→*·R,# I3: S→R·,# R→·L,# I4: L→*·R,= L→·*R,# R→·L,= L→·i,# L→·*R,= I12: L→i·,# L→·i,= I13: L→*R·,# I5: L→i·,=

此时，I2的移进项目[S→L·=R,#]和归约项目[R→L·,#]有： {=}∩{#}=Φ 故文法G[S]是LR(1)文法。最后得到LR(1)分析表，见表3-16。 表3-16 习题3.30的LR(1)分析表

ACTION GOTO

状态 = * i # S L R

0 s4 s5 1 2 3

1 acc

2 s6 r5

3 r2

4 s4 s5 8 7

5 r4

6 s11 s12 10 9 7 r3 8 r5 9 r1 10 r5 11 s11 s12 10 13 12 r4

13 r3

3.31 已知布尔表达式的文法G[B]如下：

G[B]: B→AB︱OB︱not B︱(B)︱i rop i︱i A→B and O→B or 试为G[B]构造LR分析表。 【解答】 将文法G[B]拓广为文法G[S′]：(0) S′→B (1) B→i

(2) B→i rop I (3) B→(B) (4) B→not B (5) A→B and (6) B→AB (7) O→B or (8) B→OB

列出LR(0)的所有项目： 1. S′→·B 8. B→i rop i· 15. B→not B 22. O→·B or 2. S′→B· 9. B→·(B) 16. A→·B and 23. O→B·or 3. B→·i 10. B→(·B) 17. A→B·and 24. O→B or · 4. B→i· 11. B→(B·) 18. A→B and· 25. B→·OB 5. B→·i rop i 12. B→(B)· 19. B→·AB 26. B→O·B 6. B→i· rop i 13. B→·not B 20. B→A·B 27. B→OB· 7. B→i rop ·i 14. B→not ·B 21. B→AB· 用ε_CLOSURE方法构造出文法G[S′]的LR(0)项目集规范族，并根据状态转换函数GO画出文法G[S′]的DFA，如图3-19所示。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理教程课后习题答案——第三章(6)在线全文阅读。