编译原理复习题及答案

5 6 r1 r3 r1 14. 某语言的文法G为:E → aTd|ε T → Eb|a

证明G不是LR(0)文法而是SLR(1)文法,请给出该文法的SLR(1)分析表。 答:

拓广文法G',增加产生式S'→E 在项目集I0中: 有移进项目E →·aTd 和归约项目E→·

存在移进-归约冲突,所以G不是LR(0)文法。 若产生式排序为: (0) S′→E (1) E → aTd (2) E →ε (3) T → Eb (4) T → a

G′的LR(0)项目集族及识别活前缀的DFA如下图:

.

由产生式知: Follow(E)={# ,b} Follow(T)= {d} 在I0,I2中:

Follow(E) ∩{a}={# ,b} ∩{a}= 在I5中:

Follow(E) ∩{a}={# ,b} ∩{a}= Follow(T) ∩{a}= {d} ∩{a}=

Follow(T) ∩ Follow(E) = {d} ∩{# ,b}=

所以在I0, I2, I5中的移进-归约和归约-归约冲突可以由Follow集解决,所以G′是SLR(1)文法。 构造的SLR(1)分析表如下表:

ACTION name a 0 1 2 3 S2 S5 b r2 r2 d S6 # r2 acc r2 E 1 4 T 3 GOTO 4 5 6 7 S5 S7 r2 r1 r4 r3 r2 r1 4 3 15. 给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。 G[S]为:S →BD|D B →aD|b D →B

I0:

答: I0:

16. 给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。 G[S]为:S →D;D|D D →DB|B B →a|b

I0:

答:

I0:

17. 给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。 G[S]为: S →S;V|V V →VaA|A A →b(S)| ε I0:

答: I0:

18. 文法G[M]及其LR分析表如下,请给出对串dbba#的分析过程。 G[M]: 1) M →VbA

2) V →d 3) V →ε

4) A →a 5) A →Aba

6) A →ε

ACTION name b d a # M A V GOTO 0 1 2 3 4 5 6 7 8 答:

r3 S4 r2 r6 r4 S7 r5 S3 S5 S8 acc r6 r4 r1 r5 1 6 2 对串dbba#的分析过程如下表

步骤 1 2 3 4 5 6 7 8 9 状态栈 0 03 02 024 0246 02467 024678 0246 01 文法符号栈 # #d #V #Vb #VbA #VbAb #VbAba #VbA #M 剩余输入符号 dbba# bba# bba# ba# ba# a# # # # 移进 用V →d归约 移进 用A →ε归约 移进 移进 用A →Aba 归约 用M →VbA 归约 接受 动作 19. 文法G[S]及其LR分析表如下,请给出对输入串da;aoa#的分析过程。

G[S]: 0) S′→S

1) S→dSoS

2) S →dS

3) S →S;S

4) S →a

name ACTION GOTO

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4