编译原理第五章语法分析——自下而上分析内容总结

自下而上分析过程：边输入单词符号，边归约。其核心问题是识别可归约串。

一、知识点

一、短语：定义:令G是一个文法，S是文法的开始符号，假定abd是文法G的一个句型

  其中α,β,d∈(VN∪VT)*，A∈VN ，如果有

则b称是句型abd相对于非终结符A的短语。

2.直接短语：特别是，如果有AÞb,则称b是句型abd相对于规则A®b的直接短语。

3.句柄：一个句型的最左直接短语称为该句型的句柄。

用符号栈进行自下而上的语法分析 是一个非常重要的方法，其分析过程是自左向右对输入串ω不断向栈中进行移进——归约。

二、算符优先分析法

a <.b   表示a的优先性小于b 

2、算符优先文法及优先表构造

算符优先文法

(1)算符文法

定义：一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：

…QR… 

则我们称该文法为算符文法，也称OG文法。

(2)定义终结符之间的优先关系

假定G是一个不含产生式的算符文法。对于任何一对终结符a、b，我们说：

1. a =. b 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；

2. a <. b 当且仅当G中含有形如P→…aR…的产生式， 而R  b…或R Qb…；

3. a>.b 当且仅当G中含有形如P→…Rb…的产生式，而 R …a或R…aQ。

(3)如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：
a=.b
a>.b
a<.b

 则称G是一个算符优先文法(OPG文法)。

构造算符优先关系表

(1)通过检查产生式的每一个候选式可以找出满足a=.b
  （即P→…ab…或P→…aQb…的产生式）

(2)为了满足<.和>.，需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：

(3)构造集合FIRSTVT(P)的算法
按其定义，可用下面两条规则来构造集合FIRSTVT(P)：
① 若有产生式P→a…或P→Qa…，
则aFIRSTVT(P)；
② 若aFIRSTVT(Q)，且有产生式P→Q…，

则aFIRSTVT(P)。

(4)同理构造构造集合LASTVT(P)的算法
按其定义，可用下面两条规则来构造集合LASTVT(P)：
① 若有产生式P→… a或P→… aQ ，
则aLASTVT(P)；
② 若a LASTVT(Q)，且有产生式P→… Q ，

则aLASTVT(P)。

(5)有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系<.和>.的所有终结符对。
①假定有个产生式的一个候选形为
   …aP…
  那么，对任何bFIRSTVT(P)，有a <. b。
②假定有个产生式的一个候选形为
…Pb…

  那么，对任何aLASTVT(P)，有a >. b。

注意：
对于‘#’号，相当于在文法开始符号S前加一个额外的开始符号，比如为Z

然后，把

Z →#S#

添加到原文法中，再进行分析。

三、符号栈的使用与语法树的表示

       栈是语法分析的一种基本数据结构。在解释“移进－归约”的自下而上分析过程时我们就已经提到了符号栈。一个“移进－归约”分析器使用了这样的一个符号栈和一个输入缓冲区。今后我们将用一个不属于文法符号的特殊符号‘＃’作为栈底符，即在分析开始时预先把它推进栈；同时，也用这个符号作为输入串的“结束符”，即无条件地将它置在输入串之后，以示输入串的结束。

        “移进” 指把输入串的一个符号移进栈。

       “归约”指发现栈顶呈可归约串，并用适当的相应符号去替换这个串（这两个问题都还没有解决）。

       “接受”指宣布最终分析成功，这个操作可看作是“归约”的一种特殊形式。

       “出错处理”指发现栈顶的内容与输入串相悖，分析工作无法正常进行，此时需调用出错处理程序进行诊察和校正，并对栈顶的内容和输入符号进行调整。

四、LR分析法

        规范归约（最左归约—最右推导的逆过程）的关键问题是寻找句柄。在一般的“移进－归约”过程中，当一串貌似句柄的符号串呈现于栈顶时，我们有什么方法可以确定它是否为相对于某一产生式的句柄呢？LR方法的基本思想是，在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。

        LR分析法的这种基本思想是很符合哲理的。因而可以想象，这种分析法也必定是非常通用的。正因如此，实现起来也就非常困难。作为归约过程的“历史”材料的积累虽不困难（实际上，这些材料都保存在分析栈中），但是，“展望”材料的汇集却是一件很不容易的事情。这种困难不是理论上的，而是实际实现上的。因为，根据历史推测未来，即使是推测未来的一个符号，也常常存在着非常多的不同可能性。因此，当把“历史”和“展望”材料综合在一起时，复杂性就大大增加。如果简化对“展望”资料的要求，我们就可能获得实际可行的分析算法。

        后面所讨论的LR方法都是带有一定限制的。

       一个LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。我们将把“历史”和“展望”材料综合地抽象成某些“状态”。分析栈（先进后出存储器）用来存放状态。栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。任何时候，栈顶的状态都代表了整个的历史和已推测出的展望。因此，在任何时候都可从栈顶状态得知你所想了解的一切，而绝对没有必要从底而上翻阅整个栈。LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的。为了有助于明确归约手续，我们把已归约出的文法符号串也同时放在栈里（显然它们是多余的，因为它们已被概括在“状态”里了）。于是，我们可以把栈的结构看成是：

        栈的每一项内容包括状态s和文法符号X两部分。（s0，#）为分析开始前预先放到栈里的初始状态和句子括号。栈顶状态为sm，符号串X1X2…Xm是至今已移进归约出的部分。