编译原理第五章 语法分析-自底向上分析方法

第五章自底向上分析方法主要内容自底向上分析的基本思想简单优先分析方法LR类分析方法基本思想从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型的句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符，直到将输入串归约为文法的开始符。(移入-归约分析)两种分析方法简单优先和LR类分析方法自底向上语法分析方法介绍例：SaAcBe[1]Ab[2]AAb[3]Bd[4]输入流：abbcde。规范推导过程为：逆过程:(符号栈，输入流)(-,abbcde)(a,bbcde)(ab,bcde)(aA,bcde)(aAb,cde)(aA,cde)(aAc,de)(aAcd,e)(aAcB,e)(aAcBe,-)(S,-)SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]简单优先分析一种shift-reduce分析方法根据文法符号的优先关系确定句柄文法符号的优先关系的确定简单优先分析中的三种关系XY：当且仅当存在一个产生式A→…XY…X⊲Y：当且仅当存在一个产生式A→…XB…并有B+Y…。X⊳Y：当且仅当存在一个产生式A→…BC…并有B+…X，C*Y…。文法G为简单优先文法如果满足：对于任意两个语法符号X和Y，至多成立一种优先关系；任意两个产生式都具有不同的右部。文法优先关系的确定FIRST(W)={S|W+S…，S(VNVT)}LAST(W)={S|W+…S，S(VNVT)}若有U…SiSj…:则有SiSj;若有U…SiW…:任SjFIRST(W),有Si⊲Sj若有U…VW…:任SiLAST(V),Sj(FIRST(W){W})则有Si⊳Sj输入流的开始和结束标志‘＃’，文法的开始符为Z，SFIRST(Z),有#⊲S，;且＃⊲ZSLAST(Z)，有S⊳#，;且Z⊳＃优先关系矩阵一个文法的全部优先关系可以用矩阵来表示，称作优先关系矩阵。例：ZbMbMaM(LLMa)#)a(bLMZ#)a(bLMZ)aL)bM(aa(bLMZFIRSTLAST⊲⊲⊳⊳⊳⊲⊲⊲⊳⊳⊳⊳⊳⊲⊲定理：设X1…XiXi+1…Xj…Xn是一个句型，若有Xi⊲Xi+1Xi+2…Xj-1Xj⊳Xj+1则Xi+1Xi+2…Xj-1Xj一定是该句型的简单短语。结论：⊲用来确定句柄的头；用来确定句柄的内部；⊳用来确定句柄的结束。简单优先分析算法要点找第一个使Sj⊳Sj+1的Sj从Sj开始往前(左)找第一个使Si-1⊲Si的Si用SiSi+1…Sj去查产生式的右部，并用相应的左部符号代替句柄SiSi+1…Sj(归约)。重复上述过程，直至输入符结束。如果归约出文法的开始符号则成功。否则失败。简单优先分析实例符号栈关系输入流#⊲b(aa)b##b⊲(aa)b##b(⊲aa)b##b(a⊳a)b##b(Ma)b##b(Ma)b##b(Ma)⊳b##b(L⊳b##bMb##bMb⊳##Z⊳#•规范句型：用最右推导导出的句型(也称右句型）。•规范前缀：若存在规范句型，且是终极符串或空串，则称为规范前缀。•规范活前缀：若规范前缀不含句柄或含一个句柄并且具有形式=(是句柄)，则称规范前缀为规范活前缀(简称活前缀）。•归约规范活前缀：若活前缀是含句柄的活前缀，即有=，且是句柄，则称活前缀为归约规范活前缀（简称归约活前缀）。LR类分析方法活前缀的描述性定义：形成可归前缀之前，包括可归前缀在内所有规范句型的前缀都称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻已分析过的部分，即在分析栈（符号栈）中的符号串均为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。派生定理开始符产生式的右部是归约活前缀。如果A是归约活前缀，且A→是产生式，则也是归约活前缀。任何归约活前缀，都可按上述方式被派生。设文法开始符的产生式是：S→1|2|…|nRPSG={1,…,n}{|ARPSG,A→P}识别规约活前缀的LRSM的构造例有文法G[S]:S→aAc[1]A→Abb[2]A→b[3]可归前缀集：aAcaAbbabLR(0)项目：若A→是产生式，则称A→为LR(0)项目(简称项目），也写作[p]形式。项目集的投影：假设IS是LR(0)项目集，则称下面IS(X)为IS关于X的投影集：IS(X)={A→X|A→XIS,X(VTVN)}.项目集的闭包：假设IS是LR(0)项目集，则称下面CLOSURE(IS)为IS的闭包集：CLOSURE(IS)=IS{A→|Y→ACLOSURE(IS)A→是产生式}构造LR(0)活前缀状态机LRSM的算法要点构造初始状态IS0：IS0=CLOSURE({Z→S})，并给IS0标上NO。从已构造的LRSM部分图选择被标为NO的任一状态IS，并做[1]对每个符号XVTVN，做下面动作：1)令ISj=CLOSURE(IS(X))。2)若在LRSM部分图中已有ISk与ISj有相同项目集，则令m=k；否则构造ISj的状态点ISj，并给ISj标上NO，同时令m=j。3)在IS和ISm之间画有向X边：ISISm。[2]给IS标上OK。重复上一步骤，直至没有被标记为NO的状态结点为止。x例：构造LR(0)状态机SE$EE+TETTidT(E)0S→E$E→E+TE→TT→idT→(E)1S→E$E→E+T5T→id3E→E+TT→idT→(E)4E→E+T9E→T6T→(E)E→E+TE→TT→idT→(E)7T→(E)E→E+T8T→(E)TT(idETid)E+id((GE的LRSM+2S→E$$LRSM给出了所有的可归活前缀LRSM中的每个状态将对应一个饱和项目集：（1）其中一部分是由先驱状态分出来(称为基本项目)；（2）一部分则是由基本项目扩展出来的(称为扩展项目或派生项目)。派生部分项目的特点是其中的“”出现在产生式右部的最左侧。形如A→•[P]的项目称为归约型项目形如A→•[P]的项目称为移入型项目移入－归约冲突归约－归约冲突LRSM不能直接用于LR分析LRSM提供的信息：（1）合法性检查信息[A→a]（2）移入/归约信息[A→a][A→]（3）移入/归约后的转向状态信息#X1X2…Xk…XtSi0Si1Si2…Sik…Sitaiai+1…an#移入动作：设Sit的ai输入边所指向的状态为S*#X1X2…Xk…XtSi0Si1Si2…Sik…SitaiS*归约动作：设按A→Xk+1Xk+2…Xt进行归约，则首先归约为ASik的A输出边所指向的状态设为S*，则格局变为：#X1X2…XkSi0Si1Si2…SikAS*设当前格局是：#X1X2…XkSi0Si1Si2…SikALR分析模型OutputStack#an…ai…a1LR分析驱动器gotoactionInputStXt……LR(0)分析LR分析表Action矩阵：行代表状态，列代表输入符，而矩阵元素则表示相应的分析动作：Shift/Reduce/Accept/ErrorGoTo矩阵：行代表状态，而列则代表语法符号（非终极符，终极符），而矩阵元素则表示移入或归约后的转向状态。定义若IS是一个LR(0)项目集，X是一个文法符号，函数GO（IS,X）定义为GO（IS,X）=CLOSURE（IS(X)），其中IS(X)为LR(0)项目集IS的投影。假设ISk为LR(0)项目集，则若AaISk，且GO(ISk,a)=ISi，aVT，则action(ISk,a)=Si，表示把状态ISi和展望符a入栈。若AISk，则对任意aVT{#}，令action(ISk,a)=Rj，其中产生式A的编号为j，表示用编号为j的产生式进行归约。若ZISk，且Z为拓广产生式的左部非终极符，则action(ISk,#)=Accept。若GO(ISk,A)=ISi，AVN，则goto(ISk,A)=i。其它情形，则Error(n)，表示出错标志，也可不填。LR(0)分析表的构造LR(0)分析例文法如下：S→E$E→E+T|TT→id|(E)$+id()#ETS0S5S619S1S2S3S2AccS3S5S64S4R2R2R2R2R2R2S5R4R4R4R4R4R4S6S5S679S7S3S8S8R5R5R5R5R5R4S9R3R3R3R3R3R3GoTo表Action表LR(0)驱动程序首先置状态栈、符号栈和输入流的开始格局为：（#S1,#,a1a2…an#），则：若当前格局为（#S1S2…Sn,#X1X2…Xn,aiai+1…an#），且action(Sn,ai)=Sj，aiVT，则ai入符号栈，第j个状态Sj入状态栈。即移入后的格局变为：（#S1S2…SnSj,#X1X2…Xnai,ai+1…an#）若当前格局为（#S1S2…Sn,#X1X2…Xn,aiai+1…an#），且action(ISn,a)=Rj，aVT{#}，则按照第j个产生式进行归约，符号栈和状态栈相应元素退栈，归约后的文法符号入栈。假设第j个产生式为A，k=||(=Xn-k+1…Xn)，则归约后的格局变为：（#S1S2…Sn-kS,#X1X2…Xn-kA,aiai+1…an#）其中S=goto(Sn-k,A)。若状态栈的栈顶状态为Si，输入流当前值为#，且action(Si,#)=Accept，则分析成功。若状态栈的栈顶状态为Si，输入流当前值为a，且action(Si,a)=Error或空，则转向出错处理程序。LR(0)分析实例状态栈符号栈输入串ActionGoto0id+id$#shift505id+id$#reduce4909T+id$#reduce3101E+id$#shift3013E+id$#shift50135E+id$#reduce440134E+T$#reduce2101E$#shift2012E$#acceptid+id$文法G：Z→aAc[1]A→bB[2]|ba[3]B→dB[4]|e[5]构造文法的LR(0)状态机，Action表和goto表，并给出符号串abdec的LR(0)分析过程。SLR(1)分析方法LR(0)分析方法的不足LR(0)方法对文法的要求严格。LR(0)方法容易出现冲突状态。一个文法例:GE:S→E$[1]E→E+T[2]E→T[3]T→TP[4]T→P[5]P→id[6]P→(E)[7]图4.5.5.3GE的LRSM0+EPid$+Pid(TTid(idE(P)4E→TT→TP7P→id5E→E+TT→TPT→PP→idP→(E)3T→P4S→E$E→E+T1S→E$[1]E→E+T[2]E→T[3]T→TP[4]T→P[5]P→id[6]P→(E)[7]0T→TPP→idP→(E)8T→T*P9E→E+TT→TP11P→(E)E→E+T12P→(E)10P(TP→(E)E→E+TE→TT→TPT→PP→idP→(E)678S→E$2如果某个状态有如下项目集：{A→,B→,D→d}，则存在着归约-归约，移入-归约冲突若用A→归约，则当前输入符应在A的Follow集中若用B→归约，则当前输入符应在B的Follow集若移入，则当前输入符应为d。SLR(1)分析条件LRSM0中存在着状态{A1→1，…，An→n，B1→1a1r1，…，Bm→mamr