编译原理复习题及答案

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 GOTO name b d a # M A 0 r3 S3 1 1 acc 2 S4 3 r2 4 r6 S5 r6 6 5 r4 r4 6 S7 r1 7 S8 8 r5 r5 答：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作 # dbba# 移进 1 0 #d bba# 用V →d归约 2 03 #V bba# 移进 3 02 #Vb ba# 用A →ε归约 4 024 #VbA ba# 5 0246 #VbAb a# 移进 6 02467 #VbAba # 移进 7 024678 #VbA # 用A →Aba 归约 8 0246 #M # 用M →VbA 归约 9 01 接受

19．文法G[S]及其LR分析表如下，请给出对输入串da;aoa#的分析过程。

G[S]: 0) S′→S

1) S→dSoS

2) S →dS

3) S →S;S

V 2

4) S →a name 0 1 2 3 4 5 6 7 8 d S2 S2 S2 S2 a S3 r4 S7 r3 r1 ACTION ; S4 r4 S4 r3 S4 a S3 S3 S3 S3 # acc r4 r2 r3 r1 GOTO S 1 5 6 8 答：输入串da;aoa#的分析过程如下表：步骤状态栈文法符号栈 # 1 0 #d 2 02 #da 3 023 #dS 4 025 #dS; 5 0254 #dS;a 6 02543 #dS;S 7 02546 #dS 8 025 #dSo 9 0257 #dSoa 10 02573 #dSoS 11 02578 #S 12 01 剩余输入符号 da;aoa# a;aoa# ;aoa# ;aoa# aoa# oa # oa # oa # a # # # # 动作移进移进用S →a 归约移进移进用S →a 归约用S →S;S 归约移进移进用S →a 归约用S→dSoS 归约接受

20．文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。

G[M]: 1) S →VdB

2) V →e

3) V →ε

4) B →a

5) B →Bda

6) B →ε ACTION 状态 d e a # S 0 r3 S3 1 1 acc 2 S4 3 r2 4 r6 S5 r6 5 r4 r4 6 S7 r1 7 S8 8 r5 r5 答：对串dada#的分析过程如下表步骤状态栈文法符号栈剩余输入符号 1 0 # dada# 2 02 #V dada# 3 024 #Vd ada# 4 0245 #Vda da# 5 0246 #VdB da#

GOTO B 6 V 2 动作用V →ε归约移进移进用B →a归约 6 7 8 9 02467 024678 0246 01 #VdBd #VdBda #VdB #S a# # # # 移进移进用B →Bda 归约用S →VdB 归约接受

21．文法G[E]为： E→E+T|T T→T*F|F F→(E)|i

试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。答：

短语有: (E+F)*i ，(E+F) ，E+F ，F ，i 简单(直接)短语有：F ，i 句柄是：F

最左素短语是：E+F

22．文法G[S]为： S→V

V→T | ViT T→F| T+F F→)V* |(

试给出句型ViFi( 的短语，简单(直接)短语,句柄和最左素短语。答：

短语有: ViFi( ，ViF ， F ，( 简单(直接)短语有: F ，( 句柄是: F

最左素短语是: ViF

23．文法G[S]为： S→SdT | T T→T

试给出句型(SdG)