《第6章-自底向上的LR分析法课件.ppt》由会员分享，可在线阅读，更多相关《第6章-自底向上的LR分析法课件.ppt（90页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 自底向上的LR 分析法 1 在第5章的自底向上分析中的关键问题是寻找可归约串。简单优先分析方法、算符优先分析方法，基本上都是从左到右地向前看若干个输入符号，找出句柄(或其变型最左素短语)的尾，然后回头(从右到左)查看已扫描过的符号，找出句柄(或其变型最左素短语)的头。这实际上已不是严格地从左到右地查看源程序进行归约了。2LR 分析法是严格的规范归约 LR 分析法是一种自底向上的语法分析方法，它严格地从左到右地读入输入符号串中的符号，且最多向前看确定个数(k 个)的符号，就能无回溯地识别给定的符号串。3 它与算符优先分析法一样，也通过当前输入符号和栈顶符号(状态)相比较，根据栈中的符号串
2、和向前查看的k(k 0)个输入符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。46.1 LR 分析的基本原理6 自底向上分析法是一种移进-归约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程中如何确定句柄。算符优先分析法是如何确定句柄的？回忆7 在语法分析中，句柄是逐步形成的。据此，可以用“状态”的概念来描述不同时刻所形成的那部分句柄。把每个句柄的识别过程划分为若干状态，在每个状态下从左到右识别句柄的一个符号。8LR 分析法的实现原理 有上述状态可见，语法分析程序完全可以根据当前的分析栈来判断句柄的头和尾，并实行正确的归约，这就
3、是LR 分析法的基本原理。10 在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，根据所记载的“历史”和“展望”材料，来确定栈顶的符号串是否构成句柄。1 1LR(k)的含义L 表示从左到右扫描输入串；R 表示利用最右分析方法来识别句子，即构造一个最右推导的逆过程；k 表示向右查看输入串符号的个数。LR 分析法根据当前分析栈中的符号串和向右顺序查看输入串的k 个符号就可以唯一确定分析器的动作是移进还是归约、利用那个产生式进行归约。规范推导的逆过程，所以LR分
4、析过程是规范归约的过程。13 6.2 LR 分析器的逻辑结构15LR 分析器的逻辑结构状 状 态 态 符号 符号 栈 栈a a1 1 a ai i a an n#总总控程序控程序动 动 作表 作表action action状 状 态转 态转 移表 移表goto goto输 输 出 出分析表 分析表S Sn nS Sn-1 n-1 S S1 1S S0 0X Xn nX Xn-1 n-1 X X1 1#输 输 入串 入串 LR 分析法也是一种表驱动的分析方法，有一个分析栈、一个总控程序和一个分析表。特殊性 栈=状态栈+文法符号栈 分析表=动作表(ACTION)+状态转移表(GOTO)16LR 分
5、析器的逻辑结构状 状 态 态 符号 符号 栈 栈a a1 1 a ai i a an n#总总控程序控程序动 动 作表 作表action action状 状 态转 态转 移表 移表goto goto输 输 出 出分析表 分析表S Sn nS Sn-1 n-1 S S1 1S S0 0X Xn nX Xn-1 n-1 X X1 1#输 输 入串 入串 文法不同，分析表就不同。LR 分析表是LR 分析器的核心，包括动作(ACTION)表和状态转换(GOTO)表。它们都可以用二维数组表示。动作表中的每一个元素ACTIONS,a 规定了当栈顶状态为S，且面临输入符号a时应采取的动作。状态转换表中的每一
6、个元素GOTOS,x 规定了当状态S面对文法符号位x时的下一个状态。18LR 分析表的构造方法LR 分析器的关键部分是分析表的构造。规范的LR 分析表：LR(0)，能力最弱，局限性较大，但理论上最重要；LR(1)，它功能最强，但代价也最大。简单的LR 分析表：简称SLR，最容易实现，但功能最弱。向前看的LR 分析表：简称LALR，功能和代价处于前两者之间，适用于绝大多数程序语言的文法。19 LR 分析法的每一步工作都是由栈顶状态和当前输入符号所唯一确定的。一个LR 分析器实质上是一个带先进后出栈的确定的有限自动机。206.3 LR(0)分析表的构造21 首先讨论一种只概括“历史”资料而不包含推
7、测性“展望”材料的“状态”。我们希望仅由这种简单状态就能识别呈现在栈顶的句柄。LR(0)分析即LR(k)分析中k=0 的特殊情况：仅根据当前的栈顶状态就能确定应执行何种分析动作，它主要依据LR(0)分析表进行工作。22一、规范句型的活前缀 字(符号串)的前缀：字的前缀是指该字的任意首部。活前缀：是指规范句型的活前缀，它不包含该句型的句柄右边的任何符号。在活前缀的右边添上一些终结符号后，总可以构成一个规范句型。24 LR 识别过程中，栈里面的符号(自栈底而上)就是一个活前缀，把输入串的剩余部分配上后应成为一个规范句型。因此，只要输入串已扫描过的部分能构成一个活前缀，则意味着所扫描过的这一部分没有
8、错误。若A 是文法的一个产生式，S 是开始符号，有S=A=，r 是 的前缀，则称r 是规范句型 的活前缀。25有一规范句型E+T*F+i，现求出该规范句型的活前缀。规范句型：E+T*F+i26对规范句型活前缀的识别 对于一个文法G，可以构造一DFA 去识别给定文法的所有规范句型的活前缀，进而由此构造文法的LR 分析表，用来指导对句柄的识别可根据分析栈的栈顶状态了判断是否得到句柄，并进行归约。只要输入串的已扫描的部分(符号栈中的内容)可构成一个活前缀，则说明所扫描过的部分没有错误。对句柄的识别就变成了对规范句型活前缀的识别。因此，活前缀反映了句柄的识别状态。28二、LR(0)项目及其分类 定义：
9、在文法的每一个产生式的右部适当位置添加一个圆点“.”，则一个 LR(0)项目。A aBc 的LR(0)项目：1.A aBc2.A a Bc 3.A aB c 4.A aBc 注意：一个产生式可对应的项目为它的右部符号长度加1，对空产生式A 仅有项目A。29文法G 的拓广 为了使“接受”状态容易识别，把文法G进行拓广。显然，L(G)=L(G)。当LR 分析器用它来进行归约时，整个分析工作正常结束。G=G+SS31LR(0)项目的分类 根据圆点所在的位置和圆点后是终结符还是非终结符或为空把项目分为以下几种：移进项目，形如 A a 待约项目，形如 A B 归约项目，形如 A 接受项目，形如 S S
10、32三、识别所有规范句型全部活前缀的DFA 在作出文法的全部LR(0)项目后可以用它们来构造识别文法全部活前缀的DFA，这种DFA 的每一个状态都由若干个LR(0)项目所组成的集合(项目集)来表示。为什么？因为有一些状态是等价的。在第3章 词法分析中，DFA 是如何获得的？回忆33构造识别活前缀的NFA 文法GS 的拓广：GS=GS+S S；文法的每个项目为NFA 的一个状态；确定状态之间的转换关系；按规则可对文法G 的所有项目对应的状态构造出识别活前缀的NFA。34LR(0)项目集规范族C提出“LR(0)项目集规范族”的原因 若按以上方法先构造NFA，然后再确定化为DFA，这样工作量较大，不可取。对于构成识别一个文法活前缀的DFA 项目集(状态)的全体称为这个文法的LR(0)项目集规范族。求解方法：状态：闭包函数(CLOSURE)；转换关系：转换函数(GO)35项目集I 的闭包CLOSURE(I)设I 是文法G(拓广文法)的任一项目集，则定义和构造CLOSURE(I)的规则如下：属于I 的任何项目也属于CLOSURE(I)；若A.B 属于CLOSURE(I)，那么，对于任何关于B 的产生式B,项目B.也属于CLOSURE(I)；重复直到CLOSURE(I)不再增大为止。此CLOSURE(I)即为所求的一个项目子集，将其作为DFA 的一个状态。36