语法分析自下而上分析.ppt

国防科技大学计算机系602教研室,第五章 语法分析自下而上分析,自上而下分析法(Top-down)自下而上分析法(Bottom-up),国防科技大学计算机系602教研室,语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约,国防科技大学计算机系602教研室,5.1.1 归约,采用“移进归约”思想进行自下而上分析。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。,国防科技大学计算机系602教研室,国防科技大学计算机系602教研室,b,d,b,a,c,e,分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串,国防科技大学计算机系602教研室,5.1.2 规范归约,定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且,则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,国防科技大学计算机系602教研室,在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。,国防科技大学计算机系602教研室,定义：假定是文法G的一个句子，我们称序列 n，n-1，0 是的一个规范归约，如果此序列满足：1 n=2 0为文法的开始符号，即0=S 3 对任何i，0 i n，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,国防科技大学计算机系602教研室,把上例倒过来写，则得到：S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约 规范推导由规范推导推出的句型称为规范句型。,国防科技大学计算机系602教研室,5.2 算符优先分析,四则运算的优先规则：先乘除后加减，同级从左到右考虑二义文法文法G(E)：G(E)：E i|E+E|E-E|E*E|E/E|(E)它的句子有几种不同的规范规约。归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。,国防科技大学计算机系602教研室,起决定作用的是相邻的两个算符之间的优先关系。所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。,国防科技大学计算机系602教研室,首先必须定义任何两个可能相继出现的终结符a与b的优先关系 三种关系a b a的优先级低于ba b a的优先级等于ba b a的优先级高于b注意：与数学上的=不同，a b并不意味着b a,国防科技大学计算机系602教研室,5.2.1 算符优先文法及优先表构造,一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：QR 则我们称该文法为算符文法。约定：a、b代表任意终结符；P、Q、R代表任意非终结符；代表由终结符和非终结符组成的任意序列，包括空字。,国防科技大学计算机系602教研室,假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：1.ab当且仅当文法G中含有形如Pab或PaQb的产生式；,如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：ab，ab，ab 则称G是一个算符优先文法。,2.ab当且仅当G中含有形如PaR的产生式，而R b或R Qb；,3.ab 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。,国防科技大学计算机系602教研室,优先关系表,国防科技大学计算机系602教研室,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,国防科技大学计算机系602教研室,有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。假定有个产生式的一个候选形为aP 那么，对任何bFIRSTVT(P)，有 ab。假定有个产生式的一个候选形为Pb 那么，对任何aLASTVT(P)，有 ab。,国防科技大学计算机系602教研室,首先讨论构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式Pa或PQa，则aFIRSTVT(P)；2.若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P)。,国防科技大学计算机系602教研室,数据结构：布尔数组FP，a，使得FP，a为真的条件是，当且仅当aFIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。栈STACK，把所有初值为真的数组元素FP，a的符号对(P，a)全都放在STACK之中。,国防科技大学计算机系602教研室,运算：如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如PQ 的产生式，若FP，a为假，则变其值为真且将(P，a)推进STACK栈。上述过程必须一直重复，直至栈STACK拆空为止。,国防科技大学计算机系602教研室,如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：PROCEDURE INSERT(P，a)；IF NOT FP，a THENBEGIN FP，a:=TRUE；把(P，a)下推进STACK栈 END；,国防科技大学计算机系602教研室,主程序：BEGIN FOR 每个非终结符P和终结符a DO FP，a:=FALSE；FOR 每个形如Pa或PQa的产生式 DO INSERT(P，a)；WHILE STACK 非空 DOBEGIN 把STACK的顶项，记为(Q，a)，上托出去；FOR 每条形如PQ的产生式 DOINSERT(P，a)；END OF WHILE；END,国防科技大学计算机系602教研室,这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。FIRSTVT(P)a|FP，a=TRUE同理，可构造计算LASTVT的算法。使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：,国防科技大学计算机系602教研室,FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2；IF Xi为终结符而Xi+1为非终结符 THENFOR FIRSTVT(Xi+1)中的每个a DO 置 Xia；IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END,国防科技大学计算机系602教研室,例:考虑下面的文法G(E)：(1)EE+T|T(2)TT*F|F(3)FP F|P(4)P(E)|i1.计算文法G的FIRSTVT和LASTVT;2.构造优先关系表;3.G是算符优先文法吗?,国防科技大学计算机系602教研室,国防科技大学计算机系602教研室,结论:G是算符优先文法,G的算符优先关系表,国防科技大学计算机系602教研室,5.2.2 算符优先分析算法,可归约串，句型，短语，直接短语，句柄，规范归约。一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。最左素短语是指处于句型最左边的那个素短语。,国防科技大学计算机系602教研室,考虑下面的文法G(E)：(1)EE+T|T(2)TT*F|F(3)FP F|P(4)P(E)|i,句型：T+F*P+i,短语：T+F*P+i,T,F，P,F*P,i,T+F*P直接短语：T,F,P,i句柄：T素短语：F*P,i最左素短语：F*P,国防科技大学计算机系602教研室,算符优先文法句型(括在两个之间)的一般形式写成：#N1a1N2a2NnanNn+1#其中，每个ai都是终结符，Ni是可有可无的非终结符。定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1，aj-1aj aj aj+1，ai-1ai aiai+1,国防科技大学计算机系602教研室,算符优先分析算法使用一个符号栈S，用它寄存终结符和非终结符，k代表符号栈S的使用深度。1 k:=1;Sk:=#;2 REPEAT3 把下一个输入符号读进a中；4 IF SkVT THEN j:=k ELSE j:=k-1;5 WHILE Sja DO6 BEGIN7 REPEAT8 Q:=Sj;9 IF Sj-1VT THEN j:=j-1 ELSE j:=j-210 UNTIL SjQ;,国防科技大学计算机系602教研室,11把Sj+1Sk归约为某个N；12k:=j+1;13Sk:=N14END OF WHILE;15IF Sja OR Sja THEN16 BEGIN k:=k+1;Sk:=a END17ELSE ERROR/*调用出错诊察程序*/18 UNTIL a=#,国防科技大学计算机系602教研室,在算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：#N#。算法的第11行中的N是指那样一个产生式的左部符号，此产生式的右部和Sj+1Sk 构成如下一一对应关系：自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。,国防科技大学计算机系602教研室,算符优先分析一般并不等价于规范归约。,国防科技大学计算机系602教研室,算符优先分析法特点：优点:简单，快速缺点:可能错误接受非法句子，能力有限.算符优先分析法是一种广为应用、行之有效的方法。用于分析各类表达式ALGOL 60,国防科技大学计算机系602教研室,5.2.3 优先函数,把每个终结符与两个自然数f()与g()相对应，使得若1 2，则f(1)g(2)f称为入栈优先函数，g称为比较优先函数。优点:便于比较，节省空间；缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。,国防科技大学计算机系602教研室,文法G(E)(1)EE+T|T(2)TT*F|F(3)FP F|P(4)P(E)|i的优先函数如下表,国防科技大学计算机系602教研室,有许多优先关系表不存在优先函数，如：,不存在对应的优先函数f和g 假定存在f和g，则有 f(a)=g(a)，f(a)g(b)，f(b)=g(a)，f(b)=g(b)导致如下矛盾:f(a)g(b)=f(b)=g(a)=f(a)如果优先函数存在，则不唯一(无穷多),国防科技大学计算机系602教研室,如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数:1 对于每个终结符a，令其对应两个符号fa和ga，画一以所有符号和为结点的方向图。如果ab，则从fa画一条弧至gb，如果ab，则画一条弧从gb至fa。2 对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)，赋给ga的数作为g(a)。3 检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数。,国防科技大学计算机系602教研室,现在必须证明：若ab，则f(a)g(b)；若ab，则f(a)g(b)。第一个关系可从函数的构造直接获得。因为，若ab，则既有从fa到gb的弧，又有从gb到fa的弧。所以，fa和gb所能到达的结是全同的。至于ab和ab的情形，只须证明其一。,国防科技大学计算机系602教研室,如果ab，则有从fa到gb的弧。也就是，gb能到达的任何结fa也能到达。因此，f(a)g(b)。我们所需证明的是，在这种情况下，f(a)g(b)不应成立。我们将指出，如果f(a)g(b)，则根本不存在优先函数。假若f(a)g(b)，那么必有如下的回路：,国防科技大学计算机系602教研室,因此有ab,a1b,a1b1,ambm,abm对任何优先函数f和g来说，必定有f(a)g(b)f(a1)g(b1)f(am)g(bm)f(a)从而导致f(a)f(a)，产生矛盾。因此，不存在优先函数f和g。,国防科技大学计算机系602教研室,例:取前面文法G(E)(1)EE+T|T(2)TT*F|F(3)FP F|P(4)P(E)|i的终结符+，*，i,国防科技大学计算机系602教研室,国防科技大学计算机系602教研室,5.3 LR分析法,LR分析法：1965年 由Knuth提出,分析表产生器,产生分析表,LR分析器工作,国防科技大学计算机系602教研室,主要介绍,1.总控程序(LR分析器)的处理思想2.LR分析表的构造方法及原理,国防科技大学计算机系602教研室,5.3.1 LR分析器,规范归约的关键问题是寻找句柄.“历史”：已移入符号栈的内容“展望”：根据产生式推测未来可能遇到的输入符号“现实”：当前的输入符号,国防科技大学计算机系602教研室,LR分析方法：把历史及展望综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作,LR分析程 序,国防科技大学计算机系602教研室,LR分析器的核心是一张分析表：ACTIONs，a：当状态s面临输入符号a时，应采取什么动作.GOTOs，X：状态s面对文法符号X时，下一状态是什么,国防科技大学计算机系602教研室,每一项ACTIONs，a所规定的四种动作:1.移进 把(s，a)的下一状态s和输入符号a推进栈，下一输入符号变成现行输入符号.2.归约 指用某产生式A进行归约.假若的长度为r，归约动作是，去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r,A)的下一状态s=GOTOsm-r,A和文法符号A推进栈.3.接受 宣布分析成功，停止分析器工作.4.报错,国防科技大学计算机系602教研室,分析开始时:状态 已归约串 输入串(s0，#，a1a2 an#)以后每步的结果可以表示为:(s0 s1 sm，#X1 Xm，aiai+1 an#),国防科技大学计算机系602教研室,(s0 s1 sm，#X1 Xm，aiai+1 an#)分析器根据ACTION(sm,ai)确定下一步动作1.若ACTION(sm,ai)为移进，且s，则三元式格局变为:(s0 s1 sms，#X1 Xm ai，ai+1 an#)2.若ACTION(sm,ai)为按A归约，三元式变为:(s0 s1 sm-rs，#X1 Xm-rA，aiai+1 an#)此处,s=GOTO(sm-r,A),r为的长度,=Xm-r+1 Xm3.若ACTION(sm,ai)为接受，则三元式不再变化，变化过程终止，宣布分析成功.4.若ACTION(sm,ai)为报错，则三元式变化过程终止，报告错误.,国防科技大学计算机系602教研室,LR分析器示例：,文法G(E)：(1)EET(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi,国防科技大学计算机系602教研室,其LR分析表为:,国防科技大学计算机系602教研室,假定输入串为i*i+i，LR分析器的工作过程:步骤状态符号输入串(1)0#i*i+i#(2)05#i*i+i#(3)03#F*i+i#(4)02#T*i+i#(5)027#T*i+i#(6)0275#T*i+i#(7)02710#T*F+i#(8)02#T+i#(9)01#E+i#(10)016#E+i#,国防科技大学计算机系602教研室,步骤状态符号输入串(11)0165#E+i#(12)0163#E+F#(13)0169#E+T#(14)01#E#(15)接受,国防科技大学计算机系602教研室,定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为LR文法。定义：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法.非LR结构LR文法不是二义的，二义文法肯定不会是LR的。S iCtS|iCtSeS 栈 输入 iCtS e#,国防科技大学计算机系602教研室,5.3.2 LR(0)项目集族和LR(0)分析表的构造,字的前缀：是指字的任意首部，如字abc的前缀有，a，ab，abc活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型，为句柄，如果=u1u2ur，则符号串u1u2ui(1ir)是的活前缀。(必为终结符串)对于一个文法G,可以构造一个DFA,它能识别G的所有活前缀.,国防科技大学计算机系602教研室,文法G的每个产生式的右部添加一个圆点称为G的LR(0)项目如:AXYZ有四个项目：A.XYZ AX.YZ AXY.Z AXYZ.A.称为归约项目归约项目 S.称为接受项目A.a(aVT)称为移进项目 A.B(BVN)称为待约项目.,国防科技大学计算机系602教研室,文法G(S)SE EaA|bB AcA|d BcB|d 该文法的项目有：1.SE2.SE3.EaA 4.EaA5.EaA6.AcA7.AcA8.AcA9.Ad 10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB 16.BcB17.Bd18.Bd,国防科技大学计算机系602教研室,构造识别文法所有活前缀的NFA方法 1.若状态i为XX1 Xi-1.Xi Xn，状态j为XX1 Xi-1Xi.Xi+1 Xn，则从状态i画一条标志为Xi的有向边到状态j；2.若状态i为X.A，A为非终结符，则从状态i画一条边到所有状态A.。把识别文法所有活前缀的NFA确定化。构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。,国防科技大学计算机系602教研室,识别活前缀的NFA,国防科技大学计算机系602教研室,识别活前缀的DFA,国防科技大学计算机系602教研室,有效项目,我们说项目A 1.2对活前缀1是有效的，其条件是存在规范推导,在任何时候，分析栈中的活前缀X1X2 Xm的有效项目集正是栈顶状态Sm所代表的那个集合。也正是从识别活前缀的DFA的初态出发，读出X1X2 Xm后到达的那个项目集(状态)。,国防科技大学计算机系602教研室,结论:若项目A.B对活前缀=是有效的且B 是一个产生式，则项目B.对=也是有效的。,所以，B.对=也是有效的。,国防科技大学计算机系602教研室,文法G(S)SE EaA|bB AcA|d BcB|d 考虑：项目：B c.BB.cB B.d 活前缀：bcS E bB bcBS E bB bcB bccBS E bB bcB bcd,国防科技大学计算机系602教研室,LR(0)项目集规范族的构造,假定文法G是一个以S为开始符号的文法，我们构造一个G，它包含了整个G，但它引进了一个不出现在G中的非终结符S，并加进一个新产生式SS，而这个S是G的开始符号。那么，我们称G是G的拓广文法。这样，便会有一个仅含项目SS.的状态，这就是唯一的“接受”态。,国防科技大学计算机系602教研室,假定I是文法G的任一项目集，定义和构造I的闭包CLOSURE(I)如下：1.I的任何项目都属于CLOSURE(I)；2.若AB属于CLOSURE(I)，那么，对任何关于B的产生式B，项目B也属于CLOSURE(I)；3.重复执行上述两步骤直至CLOSURE(I)不再增大为止。,国防科技大学计算机系602教研室,为了识别活前缀，我们定义一个状态转换函数GO是一个状态转换函数。I是一个项目集，X是一个文法符号。函数值GO(I，X)定义为：GO(I，X)CLOSURE(J)其中 J任何形如AX的项目|A X属于I。直观上说，若I是对某个活前缀 有效的项目集，那么，GO(I，X)便是对 X 有效的项目集。,国防科技大学计算机系602教研室,文法G(S)SE EaA|bB AcA|d BcB|d I0=SE,EaA,EbB GO(I0,E)=closure(J)=closure(SE)=SE=I1 GO(I0,a)=closure(J)=closure(EaA)=EaA,AcA,Ad)=I2 GO(I0,b)=closure(J)=closure(E b.B)=E b.B,B.cB,B.d=I3,国防科技大学计算机系602教研室,构造文法G的拓广文法G的LR(0)项目集规范族算法：PROCEDURE ITEMSETS(G)；BEGINC:=CLOSURE(SS)；REPEAT FOR C中每个项目集I和G的每个符号X DO IF GO(I，X)非空且不属于C THEN 把GO(I，X)放入C族中;UNTIL C不再增大END转换函数GO把项目集连接成一个DFA转换图.,国防科技大学计算机系602教研室,0:SE EaA EbB,4:AcA AcA Ad,5:BcB BcB Bd,3:EbB BcB Bd,1:SE,2:EaA AcA Ad,11:Bd,8:AcA,10:Ad,9:BcB,6:EaA,7:EbB,国防科技大学计算机系602教研室,LR(0)分析表的构造,假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况：1)既含移进项目又含归约项目，2)含有多个归约项目 则称G是一个LR(0)文法。,国防科技大学计算机系602教研室,构造LR(0)分析表的算法,令每个项目集Ik的下标k作为分析器的状态，包含项目SS的集合Ik的下标k为分析器的初态。,国防科技大学计算机系602教研室,分析表的ACTION和GOTO子表构造方法：1.若项目Aa属于Ik且GO(Ik,a)Ij，a为终结符，则置ACTIONk,a 为“sj”。2.若项目A属于Ik，那么，对任何终结符a(或结束符#)，置ACTIONk,a为“rj”(假定产生式A是文法G的第j个产生式)。3.若项目SS属于Ik，则置ACTIONk,#为“acc”。4.若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j。5.分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。,国防科技大学计算机系602教研室,LR(0)分析表为,国防科技大学计算机系602教研室,例:按上表对acccd进行分析步骤状态符号输入串10#acccd#202#acccd#3024#acccd#40244#acccd#502444#acccd#60244410#acccd#7024448#acccA#802448#accA#90248#acA#10026#aA#1101#E#,国防科技大学计算机系602教研室,5.3.3 SLR分析表的构造,LR(0)文法太简单，没有实用价值.假定一个LR(0)规范族中含有如下的一个项目集(状态)IXb，A，B。FOLLOW(A)和FOLLOW(B)的交集为，且不包含b，那么，当状态I面临任何输入符号a时，可以:1.若a=b，则移进；2.若aFOLLOW(A)，用产生式A进行归约；3.若aFOLLOW(B)，用产生式B进行归约；4.此外，报错。,国防科技大学计算机系602教研室,假定LR(0)规范族的一个项目集I=A1a11，A2a22，Amamm，B1，B2，Bn 如果集合a1，am，FOLLOW(B1)，FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集合有#)，则：1.若a是某个ai，i=1,2,m，则移进；2.若aFOLLOW(Bi)，i=1,2,n，则用产生式Bi进行归约；3.此外，报错。冲突性动作的这种解决办法叫做SLR(1)解决办法。,国防科技大学计算机系602教研室,构造SLR(1)分析表方法:首先把G拓广为G，对G构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO.然后使用C和GO，按下面的算法构造SLR分析表：令每个项目集Ik的下标k作为分析器的状态，包含项目SS的集合Ik的下标k为分析器的初态。,国防科技大学计算机系602教研室,分析表的ACTION和GOTO子表构造方法：1.若项目Aa属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTIONk,a为“sj”；2.若项目A属于Ik，那么，对任何终结符a，aFOLLOW(A)，置ACTIONk,a为“rj”；其中，假定A为文法G的第j个产生式；3.若项目SS属于Ik，则置ACTIONk,#为“acc”;4.若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j；5.分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。,国防科技大学计算机系602教研室,按上述方法构造出的ACTION与GOTO表如果不含多重入口，则称该文法为SLR(1)文法。使用SLR表的分析器叫做一个SLR分析器。每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的.,国防科技大学计算机系602教研室,例5.11 考察下面的拓广文法：(0)SE(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi,国防科技大学计算机系602教研室,这个文法的LR(0)项目集规范族为：,I0:SE EE+T ET TT*F TT*F TF F(E)Fi,I1:SE EE+T,I2:ET TT*F,I3:TF,I4:F(E)EE+T ET TT*F TF F(E)Fi,I5:Fi,I6:EE+T TT*F TF F(E)Fi,I7:TT*F F(E)Fi,I8:F(E)EE+T,I9:EE+T TT*F,I10:TT*F,I11:F(E),国防科技大学计算机系602教研室,I1、I2和I9都含有“移进归约”冲突。FOLLOW(E)#,),+，,国防科技大学计算机系602教研室,其分析表如下:,国防科技大学计算机系602教研室,非SLR文法示例：考虑如下文法：(0)SS(1)SL=R(2)SR(3)L*R(4)Li(5)RL,计算FOLLOW集合所得到的超前符号集合可能大于实际能出现的超前符号集。,国防科技大学计算机系602教研室,这个文法的LR(0)项目集规范族为：,I0：SS SL=R SR S*R Li RL,I1：SS,I2：SL=R RL,I3：SR,I4：L*R RL L*R Li,I5：Li,I6：SL=R RL L*R Li,I7：L*R,I9：SL=R,I8：RL,国防科技大学计算机系602教研室,国防科技大学计算机系602教研室,SLR在方法中,如果项目集Ii含项目A.而且下一输入符号aFOLLOW(A),则状态i面临a时,可选用“用A归约”动作。但在有些情况下,当状态i显现于栈顶时,栈里的活前缀未必允许把归约为A，因为可能根本就不存在一个形如“Aa”的规范句型。因此，在这种情况下，用“A”归约不一定合适。如上例，当状态2显现于栈顶而且面临输入符号为=时，实际上不能用对栈顶L进行归约，因为这个文法不含“R=”为前缀的规范句型。,国防科技大学计算机系602教研室,5.3.4 规范LR分析表的构造,我们需要重新定义项目，使得每个项目都附带有k个终结符。每个项目的一般形式是A,a1a2ak，这样的一个项目称为一个LR(k)项目。项目中的 a1a2ak 称为它的向前搜索符串(或展望串)。向前搜索符串仅对归约项目A，a1a2ak有意义。对于任何移进或待约项目A,a1a2ak,，搜索符串 a1a2ak 没有作用。,国防科技大学计算机系602教研室,归约项目A,a1a2ak意味着：当它所属的状态呈现在栈顶且后续的k个输入符号为 a1a2ak 时，才可以把栈顶上的归约为A。我们只对k1的情形感兴趣，向前搜索(展望)一个符号就多半可以确定“移进”或“归约”。形式上我们说一个LR(1)项目A,a对于活前缀是有效的，如果存在规范推导,其中，1)；2)a是的 第一个符号，或者a为#而为。,国防科技大学计算机系602教研室,为构造有效的LR(1)项目集族我们需要两个函数CLOSURE和GO。,国防科技大学计算机系602教研室,AB,a对活前缀是有效的，则对于每个形如B的产生式，对任何bFIRST(a)，B,b对也是有效的。证明：若项目AB,a对有效，则有规范推导,国防科技大学计算机系602教研室,项目集I 的闭包CLOSURE(I)构造方法：1.I的任何项目都属于CLOSURE(I)。2.若项目AB,a属于CLOSURE(I)，B 是一个产生式，那么，对于FIRST(a)中的每个终结符b，如果B,b原来不在CLOSURE(I)中，则把它加进去。3.重复执行步骤2，直至CLOSURE(I)不再增大为止。,国防科技大学计算机系602教研室,令I是一个项目集，X是一个文法符号，函数GO(I，X)定义为：GO(I，X)CLOSURE(J)其中 J任何形如AX,a的项目|AX,aI,国防科技大学计算机系602教研室,文法G的LR(1)项目集族C的构造算法：BEGINC:=CLOSURE(SS，#);REPEATFOR C中每个项目集I和G的每个符号XDO IF GO(I，X)非空且不属于C，THEN 把GO(I，X)加入C中UNTILC不再增大END,国防科技大学计算机系602教研室,构造LR(1)分析表的算法。令每个Ik的下标k为分析表的状态，令含有SS,#的Ik的k为分析器的初态。,国防科技大学计算机系602教研室,动作ACTION和状态转换GOTO构造如下：1.若项目Aa,b属于Ik且GO(Ik,a)Ij，a为终结符，则置ACTIONk,a为“sj”。2.若项目A，a属于Ik，则置ACTIONk,a为“rj”；其中假定A为文法G的第j个产生式。3.若项目SS,#属于Ik，则置ACTIONk,#为“acc”。4.若GO(Ik，A)Ij，则置GOTOk,A=j。5.分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。,国防科技大学计算机系602教研室,按上述算法构造的分析表，若不存在多重定义的入口(即，动作冲突)的情形，则称它是文法G的一张规范的LR(1)分析表。使用这种分析表的分析器叫做一个规范的LR分析器。具有规范的LR(1)分析表的文法称为一个LR(1)文法。LR(1)状态比SLR多，LR(0)SLR LR(1)无二义文法,国防科技大学计算机系602教研室,例5.13(5.10)的拓广文法G(S)(0)SS(1)SBB(2)BaB(3)Bb,国防科技大学计算机系602教研室,LR(1)的项目集C和函数GO,I0:SS,#SBB,#BaB,a/b B b,a/b,I1:SS,#,I2:SB B,#BaB,#B b,#,I3:BaB,a/b BaB,a/b B b,a/b,I4:B b,a/b,I5:SBB,#,I6:BaB,#BaB,#B b,#,I7:B b,#,I8:B aB,a/b,I9:B aB,#,国防科技大学计算机系602教研室,LR(1)分析表为:,国防科技大学计算机系602教研室,例:按上表对aabab进行分析步骤状态符号输入串00#aabab#103#aabab#2033#aabab#30334#aabab#40338#aaBab#5038#aBab#602#Bab#7026#Bab#80267#Baa#90269#BaB#10025#BB#1101#S#acc,国防科技大学计算机系602教研室,例:按上表对abab进行分析步骤状态符号输入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#acc,国防科技大学计算机系602教研室,基本概念,定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且,则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,国防科技大学计算机系602教研室,定义：假定是文法G的一个句子，我们称序列 n，n-1，0 是的一个规范归约，如果此序列满足：1 n=2 0为文法的开始符号，即0=S 3 对任何i，0 i n，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,国防科技大学计算机系602教研室,作业,P1331，2，3P1345(1)，(2)，(3),(4)P1348(选作),