[编译原理4语法分析new.ppt

方法二：Bell有向图法 1）对每个终结符a(包括$)，令其对应两个符号fa和ga，画一张以所有符号fa和ga为结点的方向图，若a?b或a b，就要画一条从fa到gb的方向弧；若a?b或a b，就要画一条从gb到fa的方向弧。 2）对每个结点都赋予一个数，此数等于从该点出发所能到达的结点（包括该结点自身在内）的个数，赋给结点fa的数等于fa的值，赋给结点gb的数等于gb的值。 3）对构造出的优先函数f和g进行检查，看他们同原先的优先关系表是否矛盾，若没有矛盾，则f和g既为所求优先函数，否则不存在优先函数。 ? ? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.5 LR分析方法 所谓LR（K）方法：是指从左到右扫描和自底向上的语法分析方法。L是指从左到右扫描输入符号串，R是指构造最右推导的逆过程，K指最多向前看K个符号就可惟一确定是归约还是移进。 LR（K）理论证明：1)每个LR（K）文法都是无二义性文法2)一个由LR（K）文法产生的语言也可由LR（1）文法产生。而且通常的程序设计语言一般都能由LR（1）文法产生，因此对程序设计语言的编译，我们仅需要考虑K≤1的情况即可。 4.5.1 LR分析器的原理和过程 LR分析法确定句柄的基本思想：在规范归约分析过程中，根据分析栈中记录的已移进和归约的整个符号串（即历史）和使用的规则推测未来可能遇到的输入符号（即展望），以及现实读到的输入符号这三方面的信息来确定分析栈栈顶的符号串是否构成句柄。 一个LR分析器的结构示意图如下： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. a1 a2 a3 … ai … an $ 分析表 总控程序 输入串 分析器 x1 S1 $ S0 … … xm Sm 栈顶 分析栈 分析栈用来存放分析过程中的历史和展望信息。LR分析法将历史和展望信息抽象成状态，并放在分析栈中，这就是说分析栈中的每个状态概括了从分析开始到某一归约阶段的整个分析历史和对未来进行的展望。 Sm … S1 S0 T + E $ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. LR分析表是LR分析法的核心，一张LR分析表由分析动作表（ACTION）和状态转换表（GOTO）组成。 分析动作表 输入符号 状态 S0 S1 … Sn a1 Action[S0,a1] Action[S1,a1] Action[Sn,a1] a2 Action[S0,a2] Action[S1,a2] Action[Sn,a2] … at Action[S0,at] Action[S1,at] Action[Sn,at] 分析动作表元素ACTION[Si,a]规定了当状态Si面临符号a（a为文法的全部终结符和句子界符$）时应当执行的动作，有四种可能的动作： 1）移进：把状态Sj=ACTION[Si,a]和输入符号a移入分析栈。 2）归约：当栈顶符号串?形成句柄，且文法中有A ? ?的规则，其中| ? |=?,则归约动作是从分析栈栈顶去掉?个文法符号和?个状态，并把归约符A和GOTO [Si- ?,A]= Sj移入分析栈。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3）接受（acc）:表示分析成功。此时，分析栈中只剩下文法开始符号S’和当前读到的输入符号$，即输入符号串已经结束。 4）报错：表示输入串含有错误，此时出现栈顶的某一状态遇到了不该遇到的输入符号。 文法符号 状态 S0 S1 … Sn x1 Goto[S0,x1] Goto[S1,x1] Goto[Sn,x1] x2 Goto[S0,x2] Goto[S0,x2] Goto[S0,x2] … xe Goto[S0,xe] Goto[S1,xe] Goto[Sn,xe] 动作转换表 状态转换表Goto[Si,x]规定了当状态Si遇到文法符号x