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

4. 这是因为，许多句型在归约过程中虽然分析的步数和过程不一样，但它们所处的状态有一些是一样的，而这些同样的状态在有穷自动机中只需要出现一个即可。

5. LR项目是在规则右部适当位置加一个圆点得到的，用圆点的位置来标记分析过程中的某个时刻。圆点的含义为：对规则右部的符号串，已从输入串看到可由圆点左部推出的符号子串，希望能进一步看到可由圆点右部推出的符号串；如果圆点右部为?，则自然联想到可将

西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM

- 6 -

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

规则右部归约成规则左部。此时，圆点左部的符号子串一定是一个可归前缀。因此，项目刻画了在分析过程中一条规则的右部已有哪些成分被识别。

七、应用题：

1. 文法如下：

S?a | ? | (T) T?T, S | S

(1) 计算该文法的Firstvt和Lastvt；

(2) 构造算符优先关系表,并说明该文法是否是OPG文法； (3) 计算优先函数；

(4) 给出串(a,a)?和(a,(a,a)) ?的算符优先分析过程。 1.答案：

（1）Firstvt(S)={a, ?, ( }，Firstvt(T)={a, , , ?, ( }，Lastvt(S)={a, ?, ) }，Lastvt(T)={a, , , ?, ) } （2） a a ? ( ) , ?> ?> ?> ?> ? ( ?> , <. ?> 该文法是OPG文法. a ? ( ) , f0 1 1 1 1 1 g0 1 1 1 1 1 f1 2 2 1 3 3 g1 2 2 2 1 2 f2 3 3 1 3 3 g2 4 4 4 1 2 先给出该文法的语法树:

西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM - 7 -

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

S ( T ) T , S S a a

步骤 栈 优先关系 当前符号 剩余符号 动作 0 ? (a,a) ? 1 ? < ( a,a) ? 移进 2 ?( < a ,a) ? 移进 3 ?(a > , a)? 归约 4 ?(S < , a)? 移进 5 ?(S, < a ) ? 移进 6 ?(S,a > ) ? 归约 7 ?(S,S > ) ? 归约 8 ?(T = ) ? 脱括号 9 ?S = ? 接受

2. 下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。 S→Sab | bR R→S | a

2. 答案：

（1） 该文法的拓广文法G'为 (0) S' → S (1) S → Sab (2) S → bR (3) R → S (4) R → a 其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下： I0 = {S'→·S, S→·Sab, S→·bR}

西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM

- 8 -

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

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 -