编译原理作业集 第五章 自下而上语法分析
与之对应，G的LR(0)项目集规范族或有下面的(i)，或有下面的(ii)，或两者皆有：
因为G是SLR(1)文法，因此有：
a不属于FOLLOW(A)， FOLLOW(A)∩FOLLOW(B)＝Φ 根据G的LR(1)项目集，有
a∈FOLLOW(A)， FOLLOW(A)∩FOLLOW(B)≠Φ 这和假设矛盾。因此，任何SLR(1)文法都是LR(1)文法。
2. 自底向上分析技术采用移进－归约法实现句型分析，但移进－归约法决不是一种分析技术，它本身不能解决自底向上分析计数所必须解决的两个基本问题，移进－归约法仅仅是适用于各种自底向上技术的一种实现方法。
3. 自底向上分析的关键是寻找句柄。简单优先分析法、算符优先分析法都是自左向右地向前查看若干个输入符号，找出句柄（或其变型－最左素短语）的尾，然后回头（从右到左）找出句柄（或其变型－最左素短语）的头，这已不是严格地从左到右查看源程序来进行归约了。 LR(k)分析法则严格地从左到右地读入输入符号串中的符号，且最多向貌似句柄的符号串后看确定个数的符号，就能一点不回溯地识别该貌似句柄的符号串是否真正的句柄。它的基本思想是：在规范归约的过程中，一方面记住已移进和归约出的符号串，即记住“历史”，另一方面根据所用的产生式（规则）推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶部时，能够根据所记载的“历史”、“展望”的信息以及“现实”中的输入符号三方面的材料，来确定符号栈顶部的符号串是否构成相对于某一规则左部的句柄，从而确定将要做的工作。 为了记住分析的“历史”和汇集全新的“展望”信息，LR分析技术这样来处理：将归约过程的“历史”和“展望”材料综合地抽象成某些状态，存放在一个状态栈中，栈中每个状态都概括了从分析开始直到某一归约阶段的全部“历史”和“展望”材料。因此，任何时候栈顶的状态都代表了整个“历史”和已推测出的“展望”信息，都可以从栈顶状态得知所要了解的一切，而无需自底向上翻阅整个栈。LR分析程序的每一步工作都是由栈顶状态和现行输入符号惟一确定的。根据文法，可以将各种状态下面临不同输入符号所要做的工作用一张表表示出来，然后用这张表直到整个分析过程的进行。
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 -