编译原理实用教程 -杨德芳 第6章 LR分析技术.pptVIP

第6章 LR分析技术 本章学习目标 LR(k)分析器是这样一种分析程序：它总是按从左到右的方式扫描输入串，并按照自底向上的方式进行归约。在这种分析过程中，它至多向前查看k个输入符号就能确定当前的动作是移进还是归约。本章要点： LR分析的基本原理 LR（0）分析表的构造 SLR（1）分析表的构造 LR（1）分析表的构造 LALR（1）分析表的构造 6.1 LR分析器的工作原理 自底向上分析方法是一种移进—归约过程，当分析栈的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析方法的关键问题是在分析过程中如何确定句柄。LR分析方法根据当前分析栈中的符号串（通常用状态来表示）和向右顺序查看输入串的k（k≥0）个符号就能惟一确定句柄。LR分析方法的归约过程正是规范推导的逆过程，所以LR分析过程是一种规范归约。 LR(k)分析方法是1965 年Knuth提出的。括号中的 k表示向右查看输入串符号的个数。这种方法比起自顶向下的LL（k）分析方法和自底向上的优先分析对文法的限制要少得多。也就是说对于大多数无二义性上下文无关文法描述的语言都可以用相应的LR分析器识别。而且这种方法还具有分析速度快，能准确、及时地指出出错位置等优点。它的主要缺点是对于一个实用语言文法分析器的构造工作量相当大，实现比较困难。 1．LR分析的概述 一个LR分析器由三部分组成： （1）总控程序，也称为驱动程序。对所有的LR分析器总控程序是相同的。 （2）分析表或分析函数。不同的文法其分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换表（GOTO）两部分,，们都用二维数组表示。 （3）分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作由栈顶状态和当前输入符号所决定。 其中SP为栈顶指针，S[i]为状态栈，X[i]为文法符号栈。状态栈的内容按关系GOTO[Si，X]= Sj。其中X为终结符或非终结符。 ACTION[Si,a]规定了栈顶状态为Si时遇到输入符号a应该执行的动作。动作有4种可能： （1）移进：当Sj=GOTO[Si,a]成立，则把Sj移入到状态栈，把a移到文法符号栈，其中i和j表示状态。 （2）归约：当在栈顶形成句柄为?时，则用?归约为相应的非终结符A，即当文法中有A??的产生式，当?的长度为?（即|?|=?）时，则从状态栈和文法符号栈中自栈顶向下去掉?个符号，即栈指针SP减去?；并把A移入文法符号栈，再把满足Sj=GOTO[Si,A]的状态移进状态栈，其中Si为修改后指针的栈顶状态。 （3）接受acc：当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是?#?，则分析成功。 （4）报错：当遇到状态为某一个状态下出现不该遇到的文法符号栈时，则报错。说明输入串不是该文法能接受的句子。 2．LR分析举例 表达式文法G[E]如下所示，它对应的LR分析表如表6-1所示。 （1）E?E+T （2）E?T （3）T?T*F （4）T?F （5）F?（E） （6）F?i 我们主要是关心的问题是如何由文法构造LR分析表。对于一个文法，如果能构造一张分析表，使得它的每一个入口均是惟一确定的，则称这个文法是LR 文法。对于一个LR文法，当分析器对输入串进行自左向右扫描时，一旦句柄呈现在栈顶，就能及时的对它实行归约。 在有些情况下，LR分析器需要“展望”和实际检查未来的k个输入符号才能决定对应采取什么样的“移进—归约”决策。一般而言，一个文法如果能用一个每步最多向前检查k 个输入符号的LR分析器进行分析，则这个文法称为LR(k)文法。 6.2 LR(0)分析表的构造 LR(0)语法分析方法是其他构造LR分析的基础。进行LR分析主要完成的任务是设计出LR分析表。LR分析表的设计方法过程是：首先给出文法，根据文法构造出NFA和DFA。根据文法的DFA设计出LR分析表，根据分析表写出LR分析器的总控程序。设计LR分析表的方法有两种，第一种是采用活前缀的方法构造有限自动机，第二种是采用项目集规范族的方法构造有限自动机。 给出文法： （1）S?aAcBe （2）A?b （3）A?Ab （4）B?d 采用LR(0)分析判断输入串abbcde#是否合法。 6.2.1 采用活前缀的方法构造有限自动机 用分析表的方法进行归约： （1）S?aAcBe[1] （2）A?b[2] （3）A?Ab[3] （4）B?d[4] 根据这个文法对输入串abbcde 进行判断，形成如下的推导过程。 S? aAcBe[1] ? aAcd[4]e[1] ? aAb[3]cd[4]e[1] ? ab[2]b[3]cd[4]e[1] 判断出该输入串是该文法的句子。 它的逆过程—最左归约（规范归约）则为：