第7章ＬＲ分析程序及其构造自底向上分析方法是一种移进--归约过程.分析栈的栈顶符号形成句柄时--归约.自底向上分析方法的关键问题--确定句柄.LR分析的归约过程是规范（最右）推导的逆过程.LR分析过程是一种规范（最左）归约过程.LR分析方法对文法的限制少，速度快.LR分析器的构造工作量大.7.1自下而上的语法分析概述(1)S→cAd(2)A→ab(3)A→a识别输入串w=cabd是否为该文法的句子自下而上的语法分析文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d刻画“可归约串”例：i*i+i的短语、直接短语和句柄自下而上的语法分析在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”G[E]：E→E+T|TT→T*F|FF→(E)|iＬＲ分析器模型LR分析使用两张表步骤7.2LR(0)分析7.2.1可归前缀、活前缀推导过程SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]每次归约前句型的前部分依次为:ab[2]aAb[3]aAcd[4]aAcBe[1]把规范句型的这种前部分串称为可归前缀。句柄位于可归前缀之中每次归约前句型的所有前缀ε,a,ab[2]ε,a,aA,aAb[3]ε,a,aA,aAc,aAcd[4]ε,a,aA,aAc,aAcB,aAcBe[1]规范句型中形成可归前缀之前（包括可归前缀）的所有前缀都称为活前缀。规范归约中已分析的部分（LR）都是规范句型的活前缀（规范句型正确部分）7.2.2构造识别活前缀的DFALR(0)项目LR(0)项目集LR(0)项目集的闭包CLOSUREGO函数—状态转换函数LR(0)项目集规范族构造识别一个文法的活前缀的DFALR(0)项目集规范族的构造LR(0)项目集规范族的构造步骤该文法的项目有：1S′→·E10A→d.2S′→E·11E→·bB3E→·aA12E→b·B4E→a·A13E→bB·5E→aA·14B→·cB6A→·cA15B→c·B7A→c·A16B→cB·8A→cA·17B→·d9A→·d18B→d·LR(0)分析表的构造例文法G:(0)S′→E(1)E→aA(2)E→bB(3)A→cA(4)A→d(5)B→cB(6)B→dACTIONGOTOacbd#EAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6I5:B→c·BB→·cBB→·dLR(0)文法LR分析使用两张表LR分析算法LR分析算法(continue)步骤LR(0)项目分类项目集中的两种冲突例：对文法G[S]的LR分析G[S]拓广为:S’SSaAcBeAbAAbBd例G[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#不是文法G[S]的句子7.3SLR(1)分析技术LR（0）项目集规范族I3:S→rD•D→D•,i例1文法的LR(0)分析表有多重入口I3:S→rD•D→D•,i其中I3中含有移进/归约冲突文法不是LR(0)的，如何解决？当用句柄rD归约成S时，S的后跟符号集合中不包含当前所有移进项目的移进符号的集合时，则这种移进/归约冲突便可解决.例中S的后跟符号集{#},移进项目只有一个”,”，这样在状态I3,当遇到”#”时归约，遇到”,”时移进.如果LR(0)项目集规范族中某个项目集IK含移进/归约，归约/归约冲突：IK:{...A→α.bβ,Pω.,Q.,…}若FOLLOW(Q)FOLLOW(P)=FOLLOW(P){b}=FOLLOW(Q){b}=则解决冲突的方法：a