内容发布更新时间 : 2024/11/13 5:13:21星期一 下面是文章的全部内容请认真阅读。
在项目集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 GOTO name a b d # E T 0 S2 r2 r2 1 1 acc 2 S5 r2 r2 4 3 3 S6 4 S7 5 S5 r2 r4 r2 4 3
6 7 r1 r3 r1 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 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) 句型(SdG) 短语：(SdG) 最左素短语：SdG 24． 按指定类型给出下列语言的文法。 (1) L1={ anbm c| n≥0，m>0 } 用正规文法。 (2) L2={ a0n1n bdm | n>0，m>0} 用二型文法。 答： (1) 描述L1语言的正规文法如下： S→ aS|A A → bA|bB B →c (2) 描述L2语言的二型文法如下： S→ AB A →aT T →0T1|01 B →bD D →dD|d