[理学]第4章 语法分析3_自底向上分析方法LR分析

编译原理(PrincipleofCompiler)谌志群Email:chenzq@hdu.edu.cnTel:13958123910Office:一教501*第四章语法分析语法分析器概述语法分析-自顶向下分析(预测分析器)语法分析-自底向上分析算符优先分析法LR分析器*4.5LR分析器LR（k）分析技术：L指从左至右扫描输入符号串R指构造一个最右推导的逆过程（最左归约）k指在作出分析决定前（构造分析表时）要向前看的输入符号个数，通常为0或1LR分析技术是功能最强的（自底向上）语法分析技术，适用文法广，效率高，分析能力强*4.5LR分析器LR分析器的逻辑结构：P90栈输入输出SmXmSm-1Xm-1..S1X1S0a1...ai...an$action表goto表LR驱动程序*4.5LR分析器LR分析器的逻辑结构：LR分析程序——固定不变的分析表——动作表（action）、状态转移表（goto）栈——状态符号、文法符号输入缓冲输出——产生式序列*4.5LR分析器LR分析器运行：根据当前栈顶状态符号与输入符号查分析表决定下一步动作假设当前（s0X1s1X2s2…Xmsm,aiai+1…an$）1、action[sm,ai]=shifts（s0X1s1X2s2…Xmsmais,ai+1…an$）2、action[sm,ai]=reduceA→β（s0X1s1X2s2…Xm-rsm-rAs,aiai+1…an$）*4.5LR分析器LR分析算法：P91关键步骤:s:栈顶符号a:当前符号1.如果action[s,a]=“accept”停机,接受,成功如果action[s,a]=“reduceAβ”则:2a.从栈中弹出2*|β|个符号2b.把A压入栈中2c.把goto[s*,A]压入栈中如果action[s,a]=“shifts*”移进;把s*压入栈中*4.5LR分析器LR分析算法：LR分析的关键问题是如何构造分析表，不同的构造方法形成不同的分析方法，主要有LR（0）、SLR、LR（1）、LALR*例子：分析句子：abbcde文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d*4.5LR分析器LR(0)分析表ACTIONGOTOacebd$SAB0S211Acc2S433S5S64R2R2R2R2R2R25S876R3R3R3R3R3R37S98R4R4R4R4R4R49R1R1R1R1R1R1*4.5LR分析器对abbcde$的分析过程步骤栈输入串ACTIONGOTO10abbcde$S220a2bbcde$S430a2b4bcde$R2340a2A3bcde$S650a2A3b6cde$R3360a2A3cde$S570a2A3c5de$S880a2A3c5d8e$R4790a2A3c5B7e$S9100a2A3c5B7e9$R11110S1$Acc*4.5LR分析器LR分析过程中的性质与特点：栈中的文法符号串并上剩余的输入串构成一个右句型（ 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 句型）当该右句型的句柄出现在栈顶时，归约，否则，移进栈中的文法符号串是当前（右）句型的前缀，该前缀不包含当前句型的句柄后面的符号，称之为活前缀*4.5LR分析器活前缀：上例aAbcde,a,aA,aAb可归前缀：包含完整句柄的活前缀*4.5LR分析器可以证明：一个文法的规范句型的所有活前缀构成一个语言，而且是正规语言，可以用一个DFA来识别**并且可以由该DFA来决定下一步分析动作（根据当前活前缀的识别态）*4.5LR分析器例子：文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d*4.5LR分析器每个状态都是活前缀的识别态，双圈状态是可归前缀（句柄）识别态，标识了*的状态是句子识别态02357SabAbcBed*(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d46981*4.5LR分析器构造识别活前缀的DFA拓广文法：增加产生式S’→S，S’作为新的开始符号文法等价确保文法的开始符号只在产生式的左部出现为了在分析过程中区别是归约到了文法的最初开始符号还是产生式右边出现的开始符号*4.5LR分析器LR（0）项目在文法产生式右部的适当位置添加圆点构成项目例：A→XYZA→·XYZA→X·YZA→XY·ZA→XYZ·例：A→εA→·*4.5LR分析器移进项目：A→α·aβ待约项目：A→α·Bβ归约项目：A→α·接受项目：S’→S·项目的含义：圆点的左部表示分析过程中的某时刻用该产生式归约时句柄已识别过的部分，圆点右部表示待识别部分*4.5LR分析器项目集的闭包（closure）I在closure(I)中例：求closure({E’·E})若A→α·Bβ在closure(I)，且B→γ是产生式，将B→·γ添加到closure(I)中E’EEE+T|TTT*F|FF(E)|id*4.5LR分析器goto函数goto(I,X)例：求goto({E’E·，EE·+T},+)goto(I,X)=closure(A→αX·β)，其中A→α·Xβ在I中E’EEE+T|TTT*F|FF(E)|id*4.5LR分析器构造规范的LR（0）项目集族算法P97C={closure({S’·S})}C=C∪goto(I,X)例子：P98-100*4.5LR分析器I0:E·EE·E+TE·TT·T*FT·FF·(E)F·idI1:EE·EE·+TI2:ET·TT·*FI3:TF·*4.5LR分析器I0:I4:E·EF(·E)E·E+TE·E+TE·TE·TT·T*FT·T*FT·FT·FF·(E)F·(E)F·idF·idI5:Fid·*4.5LR分析器I1:EE·EE·+TI6:EE+·TT·T*FT·FF·(E)F·idI2:ET·TT·*FI7:TT*·FF·(E)F·id*4.5LR分析器I4:I8:F(·E)F(E·)E·E+TEE·+TE·TT·T*FT·FF·(E)F·idI9:…I10:…I11:…*4.5LR分析器构造识别文法所有活前缀的DFA项目集作为状态，项目集族作为状态集例子：P100goto(I,X)作为状态转换函数*I1I0+toI7EI6I9I3I2I4I11I8I7I10*TI5toI4toI3toI5toI4toI5toI6toI2toI3F(FTid*idFF(Eid+)id(FT*4.5LR分析器例：文法G’:S’EET+EETTint*TTintT(E)*S’®.EE®.TE®.T+ET®.(E)T®.int*TT®.intS’®E.E®T.E®T.+ET®int.*TT®int.T®(.E)E®.TE®.T+ET®.(E)T®.int*TT®.intE®T+E.E®T+.EE®.TE®.T+ET®.(E)T®.int*TT®.intT®int*.TT®.(E)T®.int*TT®.intT®int*T.T®(E.)T®(E).ET(intint*)EETint((int+(1234567891011TT*4.5LR分析器每个状态都是识别态，识别的是从初态到该状态的通路上标记的文法符号构成的活前缀含有规约项目的是可归前缀识别态含有“S‘→S•”的是“句子”识别态*4.5LR分析器例：文法G’:(0)S’S(1)SaA(2)SbB(3)AcA(4)Ad(5)BcB(6)Bd(0)S’S(1)SaA(2)SbB(3)AcA(4)Ad(5)BcB(6)BdI0:S‘→•SS→•aAS→•bBI4:A→c•AA→•cAA→•dI2:S→a•AA→•cAA→•dI5:B→c•BB→•cBB→•dI3:S→b•BB→•cBB→•dI1:S‘→S•I8:A→cA•I10:A→d•I6:S→aA•I7:S→bB•I11:B→d•I9:B→cB•baSccccAddABddB*4.5LR分析器初态是活前缀ε的有效项目集活前缀的有效项目集活前缀γ的有效项目集是从初态出发经过γ道路所到达的那个状态所代表的项目集**根据当前活前缀的有效项目集确定下一步的分析动作I0:S‘→•SS→•aAS→•bBI4:A→c•AA→•cAA→•dI2:S→a•AA→•cAA→•dI5:B→c•BB→•cBB→•dI3:S→b•BB→•cBB→•dI1:S‘→S•I8:A→cA•I10:A→d•I6:S→aA•I7:S→bB•I11:B→d•I9:B→cB•baScccAddABddB(0)S’S(1)SaA(2)SbB(3)AcA(4)Ad(5)BcB(6)Bdc(0)S’S(1)SaA(2)SbB(3)AcA(4)Ad(5)BcB(6)Bd有了识别活前缀的DFA可以分析句子：accd<=accA<=acA<=aA<=S<=S’*每个状态识别其左边活前缀步骤栈输入串ACTIONGOTO10accd$S220a2ccd$S430a2c4cd$S440a2c4c4d$S1050a2c4c4d10$R4860a2c4c4A8$R3870a2c4A8$R3680a2A6$R1190S1$Acc(0)S’S(1)SaA(2)SbB(3)AcA(4)Ad(5)BcB(6)Bdaccd<=accA<=acA<=aA<=S<=S’步骤栈输入串动作1$accd$移进2$accd$移进3$accd$移进4$accd$移进5$accd$归约46$accA$归约37$acA$归约38$aA$归约19$S$Acc*4.5LR分析器有了识别活前缀的DFA可以分析句子：处于含有移进项目的状态可移进（句子中下一个符号为b）0αb*4.5LR分析器含有归约项目（Aβ•）的状态是可归前缀识别态，处于此状态可归约（用Aβ）*含有接受项目的状态是句子识别态，归约后完成分析0αβ*4.5LR分析器处于含有待约项目（Bα•Aγ）的状态可以等待归约（用Aβ），然后状态转移0αβA*4.5LR分析器构造LR（0）分析表：若goto(Ik，a)=Ij，则action[k，a]=Sj若goto(Ik，A)=Ij，则goto[k，A]=j若Ik包含S’→S·，则action[k，$]=acc若Ik包含A→α·，则aciton[k，a]=rj，a为任何终结符号或$，j为产生式A→α的编号（含有归约项目的状态是可归前缀识别态）I0:S‘→•SS→•aAS→•bBI4:A→c•AA→•cAA→•dI2:S→a•AA→•cAA→•dI5:B→c•BB→•cBB→•dI3:S→b•BB→•cBB→•dI1:S‘→S•I8:A→cA•I10:A→d•I6:S→aA•I7:S→bB•I11:B→d•I9:B→cB•baSccccAddABddB(0)S’S(1)SaA(2)SbB(3)AcA(4)Ad(5)BcB(6)Bd*4.5LR分析器LR（0）分析表ACTIONGOTOabcd$SAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6*(0)S’S(1)SaA(2)SbB(3)AcA(4)Ad(5)BcB(6)Bd有了LR(0)分析表可以分析句子：accd<=accA<=acA<=aA<=S<=S’步骤栈输入串ACTIONGOTO10accd$S220a2ccd$S430a2c4cd$S440a2c4c4d$S1050a2c4c4d10$R4860a2c4c4A8$R3870a2c4A8$R3680a2A6$R1190S1$Acc*4.5LR分析器项目集合中的冲突移进-归约冲突项目集合中同时含有形如A→α·aβ和B→γ·的项目归约-归约冲突项目集合中同时含有形如A→α·和B→β·的项目项目集合中若存在冲突，LR（0）分析表中存在多重定义入口*文法G’：(0)S’S(1)SrD(2)DD,i(3)DiLR(0)分析表*4.5LR分析器如果文法G的规范LR（0）项目集族中不含有移进-归约冲突和归约-归约冲突，则称文法G为LR（0）文法构造分析表时没有向前看，或者说向前看了0个符号基于LR（0）分析表的LR分析称为LR（0）分析*4.5LR分析器对于规范LR（0）项目集族中有冲突的项目集合，有的可以通过向前看一个符号（考察当前正在扫描的符号）来解决冲突当存在冲突时才向前看一个符号，因此是一种简单的LR（1）分析方法，称为SLR分析*4.5LR分析器解决方法：假设一个LR（0）项目集规范族中有如下项目集合：{X→α·bβ，A→γ·，B→δ·}即存在移进-归约冲突和归约-归约冲突*4.5LR分析器1、若a=b，则移进2、若a∈FOLLOW（A），则用产生式A→γ归约3、若a∈FOLLOW（B），则用产生式B→δ归约4、否则，报错如果FOLLOW（A）∩FOLLOW（B）∩{b}=ф，则可以如下来解决冲突（假设当前符号是a）：*SLR(1)分析表文法G’：(0)S’S(1)SrD(2)DD,i(3)Di*4.5LR分析器如果文法G的规范LR（0）项目集族中的移进-归约冲突和归约-归约冲突可以用上述方法解决，则称文法G为SLR（1）文法。构造分析表中的归约项时，考察了产生式左边非终结符号的FOLLOW集，这样形成的分析表称为SLR分析表基于SLR分析表的LR分析称为SLR分析