第6章ＬＲ分析程序及其自动构造自下而上分析算法能力强构造复杂最常用和最有效的模型----移进归约(动作）S–>EE–>T|E+TT–>int|(E)移进-归约模型分析(int+int)的过程规范推导规范句型规范归约文法要求特定的一种shift-reduce实现技术ＬＲ分析ＬＲ分析器模型ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1LR分析算法ＬＲ分析程序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步骤ＬＲ分析LR(0)分析识别活前缀的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)项目集规范族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)项目G[S]拓广为:S’SSaAcBeAbAAbBd例6.1G[S]的LR(0)分析表Stepstates.Syms.Therestofinputactiongoto10#abbcde#s2202#abbcde#s43024#abbcde#r234023#aAbcde#s650236#aAbcde#r336023#aAcde#s570235#aAcde#s8802358#aAcde#r47902357#aAcBe#s910023579#aAcBe#r111101#S#accStepstates.Syms.Therestofinputactiongoto10#abbce#s2202#abbce#s43024#abbce#r234023#aAbce#s650236#aAbce#r336023#aAce#s570235#aAce#出错说明abbce#不是例6.1文法G[S]的句子Reala,b,…I3:S→rD．D→D．，iI3:S→rD．D→D．，i使用FOLLOW(S){,}=信息解决冲突SLR(1)技术SLR表（0）S`→S(1)S→rD(2)D→D,i(3)D→i二义性文法在ＬＲ分析中的应用算术表达式二义性文法的LR(0)项目集及状态转换矩阵在I1，I7，I8中存在移进-归约冲突在I1，I7，I8中存在移进-归约冲突0S2S311S4S5acc2S2S263r4r4r4r44S2S375S2S386S4S5S97r1S5r1r18r2r2r2r19r3r3r3r310#i+i*i#S3203#i+i*i#r41301#E+i*i#S44014#E+i*i#S350143#E+i*i#r460147#E+E*i#S5701475#E+E*i#S38014753#E+E*i#r489014758#E+E*E#r2100147#E+E#r111101#E#accSLR（1）的局限?SLR0）S`→S(1)S→aAd(2)S→bAc(3)S→aec(4)S→bed(5)A→eACTIONGOTOacebd#SA0S2S311acc2S543S764S85r5r5S9r5r5r5r56S107r7r7r7r7r7S11r78r1r1r1r1r1r19r3r3r3r3r3r310r2r2r2r2r2r211r4r4r4r4r4r4（0）S`→S(1)S→aAd(2)S→bAc(3)S→aec(