发布时间 : 星期日 文章编译原理作业集-第五章-修订更新完毕开始阅读
编译原理作业集 第五章 自下而上语法分析
I1 = {S'→S·, S→S·ab}
I2 = {S→b·R, R→·S, R→·a, S→·Sab, S→·bR} I3 = {S→Sa·b} I4 = {S→bR·}
I5 = {R→S·, S→S·ab} I6 = {R→a·} I7 = {S→Sab·}
求FOLLOW集： FOLLOW(S')={＄}
FOLLOW(R)=FOLLOW(S)={a,＄}
在I5中，出现移进－归约冲突，且FOLLOW(R)∩{a}={a} 因此，此文法不是SLR(1)文法。
3. 证明下面文法是SLR(1)文法，并构造其SLR分析表。 E→E+T|T T→TF|F F→F*|a|b
输入串b+ab*是该文法的句子吗？给出对该串的分析过程。
答案：3. 该文法的拓广文法G'为 (0) E' → E (1) E → E+T (2) E → T (3) T → TF (4) T → F (5) F → F* (6) F → a (7) F → b 其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下: I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*, F→·a, F→·b}
I1 = {E'→E·, E→E·+T}
I2 = {E→T·, T→T·F, F→·F*, F→·a, F→·b} I3 = {T→F·, F→F·*} I4 = {F→a·} I5 = {F→b·}
I6 = {E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I7 = {T→TF·, F→F·*}
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM
- 9 -
编译原理作业集 第五章 自下而上语法分析
I8 = {F→F*·}
I9 = {E→E+T·, T→T·F, F→·F*, F→·a, F→·b}
求FOLLOW集：
FOLLOW(E)={＋, ＄} FOLLOW(T)={＋, ＄, a, b} FOLLOW(F)={＋, ＄, a, b, *} 构造的SLR分析表如下：
显然，此分析表无多重定义入口，所以此文法是SLR文法。
4. 下面文法属于哪类LR文法？试构造其分析表。
S→(SR|a R→,SR|)
输入串（a,a）是文法的句子吗？给出分析过程。
4.答案：
该文法的拓广文法G'为 (0) S' → S (1) S → (SR (2) S → a (3) R → ,SR (4) R → ) 构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下: I0 = {S'→·S, S→·(SR, S→·a} I1 = {S'→S·}
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM
- 10 -
编译原理作业集 第五章 自下而上语法分析
I2 = {S→(·SR, S→·(SR, S→·a} I3 = {S→a·}
I4 = {S→(S·R, R→·,SR, R→·)} I5 = {S→(SR·} I6 = {R→)·}
I7 = {R→,·SR, S→·(SR, S→·a} I8 = {R→,S·R, R→·,SR, R→·)} I9 = {R→,SR·}
每个LR(0)项目集中没有冲突。因此，此文法是LR(0)文法。其分析表如下：
5. 设文法G为
S → A A → BA | ε B → aB | b
（1）证明它是LR(1)文法； （2）构造它的LR(1)分析表；
（3）给出输入符号串abab的分析过程。 5. 答案：(1) 构造其拓广文法G'的产生式为 (0) S' → S (1) S → A (2) A → BA (3) A → ε (4) B → aB (5) B → b 构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下：
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM
- 11 -
编译原理作业集 第五章 自下而上语法分析
I0 = { [S'→·S, $], [S→·A, $], [A→·BA, $], [A→·, $], [B→·aB, a/b/$], [B→·b, a/b/$]} I1 = {[S'→S·, $]} I2 = {[S→A·, $]}
I3 = {[A→B·A, $], [A→·BA, $], [A→·, $], [B→·aB, a/b/$], [B→·b, a/b/$]} I4 = {[B→b·, a/b/$]}
I5 = {[B→a·B, a/b/$], [B→·aB, a/b/$], [B→·b, a/b/$]} I6 = {[A→BA·, $]} I7 = {[B→aB·, a/b/$]}
该文法的LR(1)项目集规范族中没有冲突，所以该文法是LR(1)文法。 (2)构造LR(1)分析表如下：
以上分析表无多的定义入口，所以该文法为LR(1)文法。 (3)对于输入串abab，其分析过程如下：
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM - 12 -