第6章ＬＲ分析程序及其自动构造自下而上分析算法能力强构造复杂最常用和最有效的模型----移进归约(动作）S–>EE–>T|E+TT–>int|(E)Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S（即施用S–>w），且没有余留输入了，意味着已成功分析了整个输入串.移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析int+)时就会发生错误.移进-归约模型分析(int+int)的过程(E+T)#Reduce:E–>E+Twhy?不用E–>T(E)#若使用了E–>T，在栈中形成的(E+E不是规范句型的活前缀（viableprefixes）（E+E不能和任何产生式的右端匹配（E+E）不是规范句型活前缀是规范句型（右句型）的前缀，但不超过句柄移进归约分析的栈中出现的内容加上余留输入构成规范句型规范推导规范句型规范归约文法要求特定的一种shift-reduce实现技术ＬＲ分析ＬＲ分析器模型ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1LR分析算法ＬＲ分析程序例6.1:G[S]:SaAcBe[1]Ab[2]AAb[3]Bd[4]w=abbcde#Stepstates.Syms.Therestofinputactiongoto10#abbcde#s2202#abbcde#s43024#abbcde#r2goto(2,A)4023#aAs650236#aAbcde#r36023#aAs570235#aAcde#s8802358#aAcde#r4902357#aAcBs910023579#aAcBe#r11101#Sacc文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d步骤推导过程SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]规约时在栈里的句型的前缀规约前可在栈里的规范句型(不含句柄)的前缀ab[2]aaAb[3]a,aAaAcd[4]a,aA,aAcaAcBe[1]a,aA,aAc,aAcBLR文法对于一个cfg文法,如果能够构造一张LR分析表,使得它的每一个入口均是唯一的（Sj,rj,acc,空白），则称该cfg是LR文法．ＬＲ分析LR(0)分析活前缀G=(Vn,Vt,P,S),若有S’αAωαβω,γ是αβ的前缀,则称是文法G的活前缀.其中S’是对原文法扩充(S’S)增加的非终结符.?为使S’不出现在任何产生式的右部.如G=({S},{a},{SSa,Sa},S)识别活前缀的DFAG[S]:(0)S’S(1)SaAcBe(2)Ab(3)AAb(4)BdG[S]:(0)S’S(1)SaAcBe(2)Ab(3)AAb(4)BdxDFA构造LR(0)项目集规范族活前缀与句柄的关系：活前缀,与句柄,与LR(0)项目构造识别活前缀的DFALR（0）项目集的闭包ＣLOSURELR(0)项目集规范族例6.2文法G:（0）S`→E(1)E→aA(2)E→bB(3)A→cA(4)A→d(5)B→cB(7)B→dLR(0)项目集规范族（识别G的活前缀的DFA)：I0:S`→．EI1:S`→E．I2:E→a．AE→．aAA→.cAE→．bBA→．dI3:E→b．BI4:A→c.AI5:B→．cBA→．cAB→c．BB→．dA→.dB→．cBB→．dI6:I7:I8:E→aA．E→bB．A→cA．I9:B→cB．I10:A→d．I11:B→cB．LR(0)分析表的构造按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)表。具有LR(0)表的文法G称为一个LR（0）文法。LR(0)文法是无二义的。例6.2文法G:（0）S`→E(1)E→aA(2)E→bB(3)A→cA(4)A→d(5)B→cB(7)B→dACTIONGOTOacbd#EAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r3r39r5r5r5r5r5r510r4r4r4r4r4r411r6r6r6r6r6r6LR(0)项目例6.1G[S]为:SaAcBeAbA