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

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

与之对应，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分析程序的每一步工作都是由栈顶状态和现行输入符号惟一确定的。根据文法，可以将各种状态下面临不同输入符号所要做的工作用一张表表示出来，然后用这张表直到整个分析过程的进行。