[第六章LR分析法..ppt

第六章 LR 分 析 法 LR分析法是自底向上的规范归约的语法分析方法 主 要 内 容： ●LR(0)分析法 ●SLR(1)方法 ●LR(1)方法 ●LALR(1)方法 (其中：SLR(1)是LR(0)方法的改进方法; LALR(1)是LR(1)方法的改进方法) §1 LR方法的概述 一、LR方法的优点 适用大多数无二义性上下文无关文法描述的语言的分析，对文法限制少。 归约过程是确定的，即每次归约能唯一确定句型的句柄。 3. 分析效率高速度快，能准确及时地指出出错位置。 主要缺点：对使用的语言文法要求有一定限制，分析器构造的工作量大，实现难度高。 二、LR分析器的组成 LR分析器的逻辑结构 一个LR分析器由3个部分组成： (1)总控程序(驱动程序),对所有的LR分析器的总控程序都是相同的。 其主要功能：在分析的每一步，按照状态栈顶状态S和当前输入串中符号a，查阅分析表，并执行其中ACTION[S,a]和GoTo部分规定的操作。操作分为：移进、归约、报错或接受。 (2)分析表：包括动作表(ACTION)和状态转换表(GoTo)两个部分。它们都可以用二维数组表示。 不同的文法分析表内容不同 同一个文法采用的LR分析器不同时，分析表的内容将也不同。 LR分析器的关键部分是分析表的构造。 (3)分析栈：包括文法符号栈x和相应的状态栈S。它们均用一维数组表示。 三，LR分析器的工作原理 例：文法G[E]: E::=E+T|T T::=T*F|F F::=(E)|i §2. LR(0)分析法 LR(0)分析法表示的含义： L：自左向右进行分析；R：采用最右推导的逆过程－最左规约；（规范归约）;0：向貌似句柄的符号串后面查看0个输入符号。 LR(0)分析法虽存在对文法限制的问题，但它是构造其它LR类分析器的基础。 LR分析方法的重点：分析表的构造。 分析表的构造过程： 上下文无关文法＝＝识别文法所有规范句型活前缀的DFA=＝LR分析表 ●问题： （1）什么是文法所有规范句型的活前缀？ （2）如何构造识别活前缀的DFA？ （3）如何构造LR的分析表？ 一、可归前缀和活前缀 例：设有文法G[S]：(上下文无关文法) S∷=A S ∷=B A∷=aAb A∷=c B∷=aBb B∷=d 如果将它们产生式的右部编上序号，并将序号人为的带入句型分析中，即有： S∷=A[1] S ∷=B[2] A∷=aAb[3] 设有句子aacbb的规范推导过程和其逆过程－规范归约过程，为： S=A[1] =aAb[3][1] =aaAb[3]b[3][1] =aac[4]b[3] b[3][1] 归约时，只参考当前规范句型的前部分，它们依次为： aac[4] aac是规范句型aacbb的可归约前缀 aaAb[3] aaAb是规范句型aaAbb的可归约前缀 aAb[3] aAb是规范句型aAb的可归约前缀 A[1] A是规范句型A的可归约前缀 注：它们正是上节分析过程表中，每次采用归约动作前，符号栈中的内容，即4，6，8，9步骤内栈中的符号串。称规范句型的前部分串为可归前缀。 ●活前缀：规范句型的前缀，这种前缀不包含句柄右边的任何符号。 例如：规范句型aaAbb的句柄是aAb，且aaAb是它的可归前缀;则规范句型aaAbb的活前缀为ε,a,aa,aaA,aaAb,它们均不包含句柄右边符号b。 注: (1)可归前缀也是规范句型的活前缀。 (2)活前缀可以是一个或多个规范句型的前缀。 (3)在分析栈中全部符号串均为当前规范句型的活前缀。 只要输入串已扫描过的部分保持可归约成一个活前缀，意味着所扫描的部分是正确的。这样，对句柄的识别就变成了对规范句型活前缀的识别。 (4)可利用有穷自动机去识别文法所有规范句型的活前缀。 二、LR(0)项目 活前缀与句柄有以下三种情况： （1）活前缀中已含有句柄的全部符号，表明此时某一产