编译原理作业集-第五章-修订

编译原理作业集 第五章 自下而上语法分析

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 -