《编译原理第07章LR分析法.pptVIP

LR（0）文法 对一个文法的LR(0)项目集规范族不存在移进—归约．或归约—归约冲突时，称这个文法为LR（0）文法。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 分析表的构造 LR(0)分析表的构造算法 示例 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. LR(0)分析表的构造算法 假设已构造出LR(0)项目集规范族为：C＝{I0，I1，...，In} 其中Ik为项目集的名字，k为状态名，令包含S’→?S项目的集合Ik的下标k为分析器的初始状态。则分析表的ACTION表和GOTO表构造步骤： a)若项目A→??a?属于Ik且转换函数GO(Ik，a)＝Ij，当a为终结符时则置ACTION[k，a]为Sj，其动作含意为将终结符a移进符号栈，状态j进入状态栈，(相当状态k时遇a转向状态j)。 b)若项目A→??属于Ik，则对任何终结符a和‘#’号置ACTION[k，a]和ACTION[k，#]为“rj”，j为在文法G’中某产生式A→?的序号。rj动作的含义是把当前文法符号栈顶的符号串?归约为A，并栈指针从栈顶向下移动|a|长度(或符号栈中弹出|a|个符号)，非终结符A变为当前面临的符号。 c)若GO(Ik，A)＝Ij，则置GOTO[k，A]3为“j”，其中A为非终结符，表示当前状态为“k，，时，遇文法符号A时状态应转向j，因此A移入文法符号栈，j移入状态栈。 d)若项目S’→S?属于Ik，则置ACTION[k，#]为“acc”，表示接受。 e)凡不能用上述方法填入的分析表的元素，应填上“报错标志”。为了表的清晰可以在表中用空白表示错误标志。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. LR(0)分析表的构造示例 文法G’为： 0 S’→E 1 E→aA 2 E→bB 3 A→cA 4 A→ d 5 B→cB 6 B→ d 项目集规范族 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 分析器的工作过程 在LR分析器的总控程序控制下对输入串进行分析，即根据输入串的当前符号和分析栈的栈顶状态查找分析表应采取的动作，对状态栈和符号栈进行相应的操作即移进、归约、接受或报错。具体说明如下： 1)若ACTION[Sk,a] ＝Sj，a为终结符，则把a移入符号栈，j移入状态栈。 2)若ACTION[Sk,a]＝ rj ，a为终结符或‘#’号，则用第j个产生式归约，并将两个栈的指针减去m．其中m为第j个产生式右部的符号串长度，这时当前面临符号为第j个产生式左部的非终结符。 3)若ACTION[Sk,a] ＝acc，a应为‘#’号，则为接受，表示分析成功。 4)若GOTO[Sk,A]＝j，A为非终结符，表明前一动作是用关于A的产生式归约的，当前面临非终结符A应移入符号栈，j移入状态栈。对于终结符的GOTO[Sk,a]已和ACTION[S,a]重合。 5)若ACTION[Sk,a] ＝ ‘空白’，则转向出错处理。 示例 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. LR(0)分析示例(bccd#) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. SLR(1)分析法 概述： 对于LR(0)规范族中有冲突的项目集(状态)用向前查看一个符号的办法进行处理，以解决冲突的分析方法称为简单的LR(1)分析法。 这种办法将能满足一些文法的需要，因为只对有冲突的状态才向前查看一个符号，以确定做那种动作。 解决冲突的条件 动作决策的规定 分析表的构造算法 示例