【精品】【考研计算机专业课】天津大学 编译原理讲义 lr分析法（可编辑.ppt

【考研计算机专业课】天津大学 编译原理讲义 LR分析法LR分析程序分析程序分析表分析表产生器产生器文法文法分析表分析表总控总控程序程序分析表分析表输入输入输出输出单词输入串单词输入串语句的识别语句的识别例例，文法，文法G的产生式的产生式为为:ET|E+TTF|T*FF(E)|iT+i3E+i3E+FE+TEi1*i2+i3F*i2+i3T*i2+i3T*F+i3回顾回顾:规范规约规范规约(最左规约最左规约最右推导的逆过程最右推导的逆过程)的关的关键问题是寻找键问题是寻找句柄句柄。LR分析法的分析法的基本思想基本思想就是就是:一方面记住已移进和规约出的整个符号串，即一方面记住已移进和规约出的整个符号串，即记住记住“历史历史”；另一方面根据所用的产生式，推测未来可能碰到的输入符另一方面根据所用的产生式，推测未来可能碰到的输入符号，即对号，即对未来未来进行进行“展望展望”。希望能够根据所记载的希望能够根据所记载的“历史历史”和和“展望展望”以及以及“现实现实”的输的输入符号等三方面的材料，来确定栈顶的符号串是否构成相入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。对某一产生式的句柄。在规范规约过程中，在规范规约过程中，根据根据“展望展望”的程度，一个的程度，一个LR分析器可以产生分析器可以产生若干不同的分析表。若干不同的分析表。LR(0)基本基本LRSLR简单简单LRLR(1)规范规范LRLALR向前向前LRACTIONGOTOI+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S8S119r1S7r1r110r3r3r3r311r5r5r5r5LR分析器的核心部分是一张分析表。分析器的核心部分是一张分析表。分析表包括两部分分析表包括两部分:“动作动作”(ACTION)表表:二维数组，二维数组，ACTIONk，a规定了当规定了当状态状态k面临输入符号面临输入符号a时应采取什么动作。时应采取什么动作。“状态转换状态转换”(GOTO)表表:二维数组，二维数组，GOTOk，X规定了状规定了状态态k面对文法符号面对文法符号(终结符或非终结符终结符或非终结符)时下一个状态是什么。时下一个状态是什么。ACTIONK，a的值有四种情况的值有四种情况:3.接接受受:设设LR分分析析表表中中ACTIONk，a=acc说说明明，当当S栈栈顶顶状状态态为为k，现现行行输输入入符符号号为为a，总总控控程程序序根根据据“k”和和“a”查查LR分分析析表表得得:ACTIONk，a=accacc说明语法分析成功。说明语法分析成功。4.报报错错:设设ACTIONk，a=空空白白，总总控控程程序序若若按按“k”和和“a”查查表表得得:ACTIONk，a=空白空白说明语法分析出错，所给输入串不是本文法的句子。说明语法分析出错，所给输入串不是本文法的句子。1.移移进进:设设表表中中ACTIONk，a=Sj，当当S栈栈顶顶状状态态为为k，现现行行输入符号为输入符号为a，总控程序根据，总控程序根据“k”和和“a”查查LR(0)分析表，得分析表，得:此时，此时，Sj表示表示j j状态进状态进S栈，栈，a进进T栈栈(文法符号栈文法符号栈)。ACTIONk，a=Sj按按ACTIONmn，a=rj的要求的要求:S栈栈应删除栈顶应删除栈顶p个状态个状态:mn-p+1mn删除后，删除后，S栈成为栈成为:m1mn-pT栈栈中中x1x2xp归约成归约成A，即，即，T栈栈顶删除栈栈顶删除p个文法个文法符号，非终极符符号，非终极符A进进T栈；栈；若若GOTOmn-p，A=j，则状态，则状态j进进S栈。栈。2.规规约约:设设LR表表中中ACTIONmn，a=rj，其其中中，rj表表示示使使用用文文法法的的第第j个产生式个产生式AX1X2Xk进行规约；进行规约；mn表示表示LR表的一个状态。表的一个状态。假设总控程序按假设总控程序按S栈顶状态栈顶状态mn和现行输入符号和现行输入符号a查查LR分析表，得分析表，得:此时，此时，S栈的状态一定为栈的状态一定为:m1,mn-p+1,mn文法符号文法符号T栈的符号一定为栈的符号一定为:x1x2xpACTIONmn，a=rj动作动作输入串输入串aT栈栈S栈栈移进移进*i+i#i#0规约，规约，Fii+i#*#i05规约，规约，TFi+i#*#F03移进移进i+i#*#T02移进移进+i#i#T*027规约，规约，Fii#+#T*i0275规约，规约，TT*Fi#+#T*F02710规约，规约，ETi#+#T02移进移进i#+#E01移进移进#i#E+016规约，规约，Fi#E+i0165规约，规约，TF#E+F0163规约，规约，EE+T#E+T0169接受。接受。#E01例例，输入串，输入串i i*i+ii+i的分析过程的分析过程LR文法文法一个文法，如果能构造一张分析表，使得它的每个入口均一个文法，如果能构造一张分析表，使得它的每个入口均是唯一确定的，则我们将这个文法称为是唯一确定的，则我们将这个文法称为LR文法文法。一个一个LR分析器有时需要分析器有时需要“展望展望”未来的未来的k个输入符号才能决定个输入符号才能决定采取什么样的采取什么样的“移进移进规约规约”决策。一个文法，如果每步至多决策。一个文法，如果每步至多向前展望未来向前展望未来k个符号，则相应的文法称为个符号，则相应的文法称为LR(k)文法文法。LR方法比方法比LL(1)方法更具一般化。方法更具一般化。二义性文法不是二义性文法不是LRLR文法。文法。