会计学7.1LR分析(fēnxī)概述LR(K)的含义:L表示从左到右扫描输入串，R表示最左规约(即最右推导(tuīdǎo)的逆过程)，K表示向右查看输入串符号的个数。当K=1时，能满足当前绝大多数高级语言编译程序的需要，所以着重介绍LR(0)，SLR(1)，LR(1)，LALR(1)方法。ＬＲ分析(fēnxī)LR(0)文法能力最弱，理论上最重要存在FA识别活前缀(qiánzhuì)识别活前缀(qiánzhuì)的DFA如何构造（LR(0)项目集规范族的构造）LR(0)分析表的构造定义(dìngyì)如果有Zαβ(Z为开始符)，且β为终极符串(或空)。称α是规范前缀。若α是含有句柄的规范前缀,且每个句柄是α的后端，称α是可归规范前缀。例子(lìzi)：SmABcde定理(dìnglǐ)设α1Aα2为可归前缀，A∈VN，A→u为一产生式，则α1u也为可归前缀。例:G[S]:S→aAc[1]A→Abb[2]A→b[3]求：该文法(wénfǎ)的可归前缀图[1]构造(gòuzào)可归前缀图方法定义(dìngyì)构造LR(0)项目(xiàngmù)集规范族例子：U→XYZ，求项目U→XYZU→XYZU→XYZU→XYZ可归前缀图的构造(gòuzào)算法例:G(S):S→aAc[1]A→bB[2]|ba[3]B→dB[4]|e[5]定义(dìngyì)LR(0)文法：文法的可归前缀(qiánzhuì)图不包含二义性结点(可用于判是否LR(0)文法)。LR分析法的步骤：格局(géjú)为(01…i,#X0X1…Xi,ajaj+1…an#)状态栈符号栈输入流3.若ACTION[i,aj]=ok,则成功(chénggōng)。4.若ACTION[i,aj]=en,则失败。例：G(E):E→aA|bBA→cA|dB→cB|d1.用形式化方法作可归前缀图。2.求LR(0)矩阵。3.写出输入(shūrù)串bccd的LR(0)分析过程。解：可归前缀(qiánzhuì)图0:S→.EE→.bBE→.aALR(0)分析过程的关键点：1.用分析栈的栈顶元素对输入串的第一个元素查矩阵，以确定下一步的动作。2.每一步都要保持分析栈和符号栈长度一致。3.归约时，符号栈的元素（产生式的右部）弹出栈时，等长的分析栈元素同时弹出栈，以保持两栈长度一致。4.归约时，产生式的左部压进符号栈时，分析栈压进分析栈栈顶元素对产生式左边查goto矩阵得到(dédào)的状态编号。例如：第5步：用B→d归约,d，(11)出栈，B进栈；5对B查表得9。ＬＲ分析器模型(móxíng)例G[S]为:SaAcBeAbAAbBd1)构造识别活前缀(qiánzhuì)的DFA2)构造它的LR(0)分析表。3)分别给出对输入符号串abbcde和Abbce的LR(0)分析步骤。G[S]拓广为:S’SSaAcBeAbAAbBdG[S]的LR(0)分析(fēnxī)表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#不是(bùshi)例6.1文法G[S]的句子当有I={x→●bA→r●}时，为移进-归约冲突(chōngtū)，如果FOLLOW(A)∩b=；或当有I={A→r●B→●}时，为归约-归约冲突(chōngtū)，如果FOLLOW(A)∩FOLLOW(B)=,则称该冲突(chōngtū)可以解决。SLR(1)方法:是只在LR(0)可归前缀图的二义性状态下向前看一符。当有I={x→●bA→r●B→●}FOLLOW(A)∩FOLLOW(B)=,FOLLOW(A)∩b=；FOLLOW(B)∩b=则称该冲突可以解决。满足(mǎnzú)上述条件则可利用SLR(1)方法例：有项目集S→Aa.bBcA→d.B→e.设：FOLLOW(A)=a，FOLLOW(B)＝c所以：FOL