编译原理作业集 第五章 自下而上语法分析
FOLLOW(S) ∩{0，1}= { #} ∩{0，1}=
所以在I2 、I8中的移进-归约冲突可以由FOLLOW集解决，所以G是SLR(1)文法。 （2）构造的SLR(1)分析表如下： 状态 ACTION GOTO · 0 1 # S L B 0 s4 s5 1 2 3 1 acc 2 s6 s4 s5 r2 7 3 r4 r4 r4 r4 4 r5 r5 r5 r5 5 r6 r6 r6 r6 6 s4 s5 8 3 7 r3 r3 r3 r3 8 s4 s5 r1 7 对输入串101.110#的分析过程 步骤 状态栈 符号栈 剩余符号串 动作 1 0 # 101.110# 移进 2 0 5 #1 01.110# 归约B →1 3 0 3 #B 01.110# 归约L →B 4 0 2 #L 01.110# 移进 5 0 2 4 #L0 1.110# 归约B →0 6 0 2 7 #LB 1.110# 归约L →LB 7 0 2 #L 1.110# 移进 8 0 2 5 #L1 .110# 归约B →1 9 0 2 7 #LB .110# 归约L →LB 10 0 2 #L .110# 移进 11 0 2 6 #L. 110# 移进 12 0 2 6 5 #L.1 10# 归约B →1 13 0 2 6 3 #L.B 10# 归约L →B 14 0 2 6 8 #L.L 10# 移进 15 0 2 6 8 5 #L.L1 0# 归约B →1 16 0 2 6 8 7 #L.LB 0# 归约L →LB 17 0 2 6 8 #L.L 0# 移进 18 0 2 6 8 4 #L.L0 # 归约B →0 19 0 2 6 8 7 #L.LB # 归约L →LB 20 0 268 #L.L # 归约L →L.L 21 01 #S # acc 分析成功，说明输入串101.110是文法的句子。
8. 对于文法
S→AB
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM
- 16 -
编译原理作业集 第五章 自下而上语法分析
A→aB B→b
(1) 构造LR(1)分析表；
(2) 给出用LR(1)分析表对输入符号串abab的分析过程。
9. 给定文法G[Z]：
①Z→C S
②C→if E then ③S→A＝E ④E→E∨A ⑤E→A ⑥A→i
其中：Z、C、S、A、E∈VN ；if、then、＝、∨、i∈VT
a) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。 b) 构造其SLR（1）分析表。
9. 答案：
1.首先拓广文法：在G中加入产生式0．Z'→Z，然后得到新的文法G'，再求G'的识别全部活前缀的DFA： I0：Z′→.Z Z→.C S
C→.if E then I1： Z′→Z. I2： Z→C .S S→.A＝E A→.i
I3：C→if .E then E→.E∨A E→.A A→.i I4：Z→C S. I5：S→A.＝E I6：A→i.
I7：C→if E .then E→E.∨A I9：S→A＝.E E→.E∨A E→.A A→.i
I10：C→if E then. I11：E→E∨.A A→.i
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM
- 17 -
编译原理作业集 第五章 自下而上语法分析
I12：S→A＝E. E→E.∨A I13：E→E∨A.
Follow(Z)＝{#} Follow(C)＝{i} Follow(S)＝{#}
Follow(E)＝{#,∨,then} Follow(A)＝{＝,# ,∨,then } 则可构造SLR（1）分析表为： ACTION GOTO 0 if then ＝ ∨ i # Z C S E A 0 S3 1 2 1 OK 2 S6 4 5 3 S6 7 8 4 r1 5 S9 6 r6 r6 r6 r6 7 S10 S11 8 r5 r5 r5 9 S6 12 8 10 r2 11 S6 13 12 S11 r3 13 r4 r4 r4 西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM - 18 -
编译原理作业集 第五章 自下而上语法分析
10. 设有文法G[S]：
S→aA A→Ab A→b
求识别该文法所有活前缀的DFA；构造合适的LR分析表，并给出对输入串abb的分析过程。
解答：
(1).首先拓广文法：
在G中加入产生式0.S′→S，然后得到新的文法G′:
0.S′→S 1.S→aA 2.A→Ab 3.A→b
(2).再求G′的识别全部活前缀的DFA：
11.给定文法 G[S] ： S → SaA|a A → AbS|b
⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵请构造该文法的 LR(0) 分析表。
⑶什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ ⑷什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？
12. 下面文法属于哪类LR文法？试构造其分析表。 S→aSAB | BA A→aA | B B→ b
输入串abababb是文法的句子吗？给出分析过程。
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM
- 19 -
编译原理作业集 第五章 自下而上语法分析
12. 答案：
该文法的拓广文法G'为 (0) S' → S (1) S → aSAB (2) S → BA (3) A → aA (4) A → B (5) B → b 其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下： I0 = {S'→·S, S→·aSAB, S→·BA, B→·b} I1 = {S'→S·} I2 = {B→b·}
I3 = {S→a·SAB, S→·aSAB, S→·BA, B→·b} I4 = {S→B·A, A→·aA, A→·B, B→·b} I5 = {S→aS·AB, A→·aA, A→·B, B→·b} I6 = {S→aSA·B, B→·b}
I7 = {A→a·A, A→·aA, A→·B, B→·b} I8 = {A→B·} I9 = {S→BA·} I10 = {S→aSAB·} I11 = {A→aA·}
求FOLLOW集： FOLLOW(S')={＄} FOLLOW(S)={a,b,＄} FOLLOW(A)={a,b,＄} FOLLOW(B)={a,b,＄}
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM - 20 -