《编译原理》第5章LR分析方法ppt课件.ppt

《《编译原理》第5章LR分析方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、LR分析法本节重点：LR分析方法与分析过程LR(0)项目、项目集规范族及其构造Closure和go函数的定义LR(0)文法及LR(0)分析表的构造SLR文法LR分析法：是另一种有效的自下而上的分析方法，L——从左向右扫描输入串，R——构造最右推导的逆过程大多数用上下文无关文法描述的高级语言的语法成分可以用LR分析器来识别。LR分析仍然是一种移进-归约分析方法，严格的规范归约。LR分析根据当前分析栈中的符号串和向右顺序查看输入串的K(K≥0)个符号就可以唯一确定分析的动作是移进还是归约。向前查看0个符号，就是LR(0)分析方法，向前查看1个符

2、号，就是LR(1)方法。LR分析的优缺点优点：比其他“移进-归约”分析法，如算符优先分析法使用更加广泛，识别效率高能用LL(1)分析法分析的所有文法都能使用LR方法来进行分析。LR分析法在自左至右扫描输入串的过程中就能发现其中的任何错误，并能准确地指出出错位置。缺点：手工构造分析表工作量太大。必须使用自动生成器。自底向上分析法的关键问题是如何确定句柄。LR分析法与算符优先方法一样，LR方法也是通过求句柄逐步归约来进行语法分析。在算符优先分析中，通过算符的优先关系得到句柄——“最左素短语”，LR方法中句柄是通过求活前缀而求得。LR分析方法的基

3、本思想是：在规范归约过程中，一方面记住已移进和归约出的整个符号串(历史)，另一方面又根据所用产生式推测未来可能碰到的输入符号(对未来的展望)。当某一符号串类似于句柄出现在栈顶时，需要根据已记载的“历史”、“展望”和“现实”的输入符号三方面的内容来决定栈顶的符号串是否构成了真正的句柄，是否需要归约。一个LR分析器的组成见下图。1、LR分析方法的逻辑结构一个LR分析器由3个部分组成：LR分析程序，又称总控程序。所有的LR分析器都是相同的。分析表(分析函数)，不同的文法分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作

4、表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。状态栈：(S0,#)为预先放到栈中的初始状态和符号。文法符号：X1X2…Xm是目前已移进并归约出的句型部分。其实它是多余的，已经概括到状态里。分析器实际上是一个带有先进后出栈的确定的有穷自动机。将“历史”和“展望”综合成“状态”，分析栈用来存放状态，状态概括了从分析开始直到某一归约阶段的全部历史和展望资料，不必象算符优先分析法中要翻阅栈中的内容才能决定是否要进行归约。只需根据栈顶状态和输入符号就可以唯一决定下

5、一个动作。总控程序根据分析表的内容来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法：根据具体文法的分析表对输入串进行分析处理。LR分析过程：在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和当前输入符号，按分析表中的内容完成相应的分析工作。2.分析表的组成：(1)分析动作表Action是一个二维数组符号状态a1a2…atS0action[S0,a1]action[S0,a2]…action[S0,at]S1action[S1,a1]action[S1,a2]…action[S1,at]……………S

6、naction[Sn,a1]action[Sn,a2]…action[Sn,at]表中action[Si,aj]，指出如果当前栈顶为状态Si，输入符号为aj时应执行的动作。其动作有四种可能，分别为：移进(S)、归约(r)、接受(acc)、出错(error)。符号状态x1x2…xtS0goto[S0,x1]goto[S0,x2]…goto[S0,xt]S1goto[S1,x1]goto[S1,x2]…goto[S1,xt]……………Sngoto[Sn,x1]goto[Sn,x2]…goto[Sn,xt]表中goto[Si,xj]指出栈顶状态为

7、Si，碰到文法符号为Xj时应转到的下一状态。显然：分析表定义了一个以文法符号为字母表的DFA(2)状态转换表goto也是一个二维数组状态ActionGoToi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4r1937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5ri表示按第i个产生式进行归约Si表示把当前输入符号移进栈，第i个状态进状态栈。i表示转第i个状态，即第i个状态进状态栈。空白表示分析动作出错例：LR的Action和GoT

8、o表(1)EE+T(2)ET(3)TT*F(4)TF(5)F(F)(6)Fi产生式的序号设文法为G[L]：用三元式:(状态栈，符号栈，输入符号串)表示分析过程中状态栈