《编译原理7.ppt

第7章 自下而上的LR(k)分析方法 LR(k)分析器是这样一种分析程序：它总是按从左至右方式扫描输入串，并按自下而上方式进行规范归约。在这种分析过程中，它至多只向前查看k个输入符号就能确定当前的动作是移进还是归约；若动作为归约，则它还能唯一地选中一个产生式去归约当前已识别出的句柄（这里称为活前缀）。若该输入串是给定文法的一个句子，则它总可以把这个输入串归约到文法的开始符号；否则报错，指明它不是该文法的一个句子。 7.1 LR(k)文法和LR(k)分析器 给定文法G，S是其开始符号。考虑该文法中一个终结符号串w的一个规范推导 S=w1=w2=…=w 假定 uAv=uxv 是上述推导中的一个推导步。A::=x是用于该推导步的产生式。 对于每一个这样的推导和推导步，仅通过扫描ux和查看v中开始的k个符号就能唯一确定选用产生式A::=x，我们就称G为LR(k)文法。 7.2 LR(0)分析表的构造 LR分析方法的基本原理是：把每个句柄（某个产生式的右部）的识别过程划分为若干状态，每个状态从左至右识别句柄中的一个符号，若干个状态就可识别句柄左端的一部分符号。识别了句柄的这一部分就相当于识别了当前规范句型的左起部分——规范句型的活前缀。因而，对句柄的识别就变成了对规范句型活前缀的识别。 7.3 SLR分析表的构造 LR(0)文法所构造出来的识别活前缀的DFA中每个状态（每个项目集）不能包含冲突项目。 许多冲突动作都可以通过考察有关非终结符的FOLLOW集而得到解决，即通过向前查看一个输入符号来协助解决冲突。 7.4 规范LR(1)分析表的构造（略） 重新定义项目，使得每个项目包含两个部分，第一部分就是原来的项目本身，第二部分是由一个终结符号（可能为$）组成。重新定义后的项目称为LR(1)项目，其一般形式为 [A→α.β,a] 项目中第二部分称为向前看符号。 对于β＝ε的项目[A→α.,a]，其作用在于：当相应的状态呈现于栈顶且下一个输入符号为a时，才可选用产生式A→α，将栈顶的α规约到A。 7.5 LALR分析表的构造（略） LALR（向前看LR）分析技术是介于规范LR分析器构造法和SLR分析器构造法之间的一种方法。 某些LR(1)项目集称为同心，即如果除了向前看符号之外，这些项目集是相同的。在LALR分析方法中，就试图将这些同心项目集合并成一个项目集。 * 湖北大学数计学院计科系 2008年3月 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 7.1 LR(k)文法和LR(k)分析方法 7.2 LR(0)分析表的构造 7.3 SLR分析表的构造 7.4 规范LR(1)分析表的构造 7.5 LALR分析表的构造 7.6 无二义性规则的使用 7.7 小结 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. LR分析器的逻辑结构? 一个输入、一个输出、一个栈、一个驱动程序和一张分析表。 id+id*id$ Sm Xm Sm-1 Xm-1 … S0 LR驱动程序 动作 转移 action goto 输出 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 分析动作表（ACTION）： 移进 ai 和s=goto[sm,ai]进栈 action[sm,ai]=归约 rj : A::=Xm-r+1Xm-r+2…Xm 接收 s=goto[sm-r , A] 错误处理 LR分析器的分析表：分析动作表和goto函数表 GOTO函数表： GOTO[si