语法分析-自底向上分析-编译原理-05-(二)

第五章语法分析—自底向上分析5.1基本问题方法从句子出发，反复利用产生式做归约（用产生式的左部替代右部），逐步构造语法分析树，最后得到文法的开始符号核心寻找句型与句柄的匹配分析方法例5-1：S→aAcBeA→Ab｜bB→d分析过程:abbcde→aAbcde→aAcde→aAcBe→S语法分析树的生成abbcdeAABSA→bA→AbB→dS→aAcBe句柄：最左直接短语短语：设文法Ｇ＝｛ＶT，ＶN，Ｐ，Ｓ｝若Ｓ=*αＡδ且Ａ=+β，则称β是句型αβδ相对于非终结符Ａ的短语若Ｓ=*αＡδ且Ａ=β，则称β是直接短语。规范归约的定义设α为文法G的句子，称序列αn，...，α1，α0为α的规范归约，其中1)αn=α2)α0=Ｓ（开始符号）3)对每个i(1=i=n)，αi-1是将αi中的句柄归约后得到的规范归约规范归约是规范推导(最右推导)的逆过程中心问题是如何寻找和确定一个句型中的句柄各种自底向上分析采用不同的方法确定句柄移进归约分析器id＊id#＋Ｅ#移进归约控制程序产生式序列栈内容+输入缓冲区内容＝#句型#栈输入缓冲区分析器的四种动作1)移进：将下一输入符号移入栈2)归约：用产生式左侧的非终结符替换栈顶的句柄3)接受：分析成功4)出错：出错处理各种自底向上分析方法的控制方法不同例5-2：id+id*id的分析动作栈输入缓冲区1)#id1+id2*id3#2)移进#id1+id2*id3#3)归约E→id#E+id2*id3#4)移进#E+id2*id3#5)移进#E+id2*id3#6)归约E→id#E+E*id3#7)移进#E+E*id3#8)移进#E+E*id3#9)归约E→id#E+E*E#10)归约E→E*E#E+E#11)归约E→E+E#E#12)接受产生式序列表示语法分析树E→idE→idE→idE→E*EE→E+Eid+id*idEEEEE移进归约分析中的冲突文法复杂时出现:1)移进归约冲突例中的6)可以移进id或归约E→E+E2)归约归约冲突存在两个可用的产生式各种分析方法处理冲突的方法不同5.2算符优先分析方法：利用终结符之间的优先关系确定句柄。算符优先关系的定义(终结符之间)a≮ba的优先级低于ba≡ba的优先级等于ba≯ba的优先级高于b算符优先文法如果文法Ｇ中不存在具有相邻非终结符的产生式，则称为算符文法。如果无ε产生式的算符文法Ｇ中，且任意两个终结符之间至多有一种优先关系，则称为算符优先文法。算符优先分析仅适用于算符优先文法。例5-3：表达式文法的算符优先关系E→E+E｜E-E｜E*E｜E/E｜E^E｜(E)｜id存在优先级+≮**≯+id≯+id≯*+≮id*≮idid≯##≮id算符优先关系的使用分析例：id+id*id在输入符号串中插入优先符，形成一组以≮为左端，以≡为中缀，以≯为右端的短语。#≮id≯+≮id≯*≮id≯#对短语进行归约后再次插入优先符#≮E+≮E*E≯##≮E+E≯##E#算符优先分析的实现组成结构移进归约分析器+优先关系表工作框架输入、输出、初态、终态不变分析算法P93参照输入串、优先关系表，完成一组产生式归约，产生语法分析树。id+id*id的分析过程id+id*id#算符优先分析控制器E→idE→idE→idE→E*EE→E+E算符优先关系表#id#E#+E#id+E#E+E#*E+E#id*E+E#E*E+E#E+E#E#算符优先关系表的构造对于任何符号X和Y：若X的运算优先级高于Y，则设X≯Y和Y≮X若X和Y运算优先级相同，且具有左结合性，则设X≯Y和Y≯X;否则设X≮Y和Y≮X设X≮id，id≯X，X≮(，(≮X，)≯X，X≯)，(≡)，X≯#和#≮X算符优先分析小结优点简单、效率高能够处理部分二义性文法缺点文法书写限制大占用内存空间大不规范、存在查不到的语法错误习题：P1332.(2)补充题给出布尔表达式的文法bexprbexprORbexprbexprbexprANDbexprbexprNOTbexprbexpr(bexpr)bexprTRUEbexprFALSE构造该文法的算符优先关系表5.3ＬＲ分析法适用于分析LR（k）文法相当大的一类上下文无关文法分析方法最广义的无回朔的移进归约分析主要特征文法限制少、错误定位准确效率较高、易于实现自动生成LR(k)文法移进归约分析法可分析的文法L：从左到右扫描输入符号R：逆向地完成最右推导k：超前读入的符号个数存在无法分析的2型文法5.3.1分析器的概述LR分析器移进归约分析器+LR分析表特殊性栈=状态栈+文法符号栈分析表=动作表+状态转移表分析器的逻辑结构a1…ai…an#ＬＲ驱动程序(P101算法)动作表action转移表goto产生式序列状态符号栈输入缓冲区分析表SmSm-1………S1S0XmXm-1………X1#LR分析表action[s,a]状态s下输入a时的动作（移进、归约、接受、出错）goto[s,X]状态s下遇符号X时的转移目标各种LR分析法采用不同的构造方法ＬＲ分析算法：设置ip指向w#的第一个符号repeatforeverbegin令s是栈顶状态，a是ip所指向的符号ifaction[s,a]=shifts'thenbegin把a和s'先后压入栈使ip指向下一符号endelseifaction[s,a]=reduceA→βthenbegin从栈顶弹出2*｜β｜个符号令s'表示当前栈顶状态把A和goto[s',A]先后压入栈中输出产生式A→βendelseifaction[s,a]=acceptthenreturnelseerror()end.例5-4：分析例文法1)S→BB2)B→aB3)B→b状态动作表状态转移表ab#SB0s3s4121acc2s3s453s3s464r3r3r35r16r2r2r2分析表bab的分析过程栈输入动作说明#0bab#action(0,b)#0b4ab#action(4,a)B→bgoto(0,B)#0B2ab#action(2,a)#0B2a3b#action(3,b)#0B2a3b4#action(4,#)B→bgoto(3,B)#0B2a3B6#action(6,#)B→aBgoto(2,B)#0B2B5#action(5,#)S→BBgoto(0,S)#0S1#action(1,#)accept各种LR分析表LR(0)，SLR(1)，LALR(1)，LR(1)，构造分析表的方法不同分析能力不同实现效率不同共同点逻辑结构工作原理（状态转移）5.3.2SLR(1)分析状态表示分析的进程方法用产生式中符号的分割位置来近似表示分析的进展状况babBBBSS→B.BB→.aB分析的进展分析位置句型中，分析进展的当前位置（无限）例：.bab=B.ab=BaB.=BB.=S.LR(0)项目目的用产生式中的符号分割位置(有限）来表示分析位置(无限)定义右部某个位置上标有园点的产生式坐标表示(x,y)表示x号产生式的y号位置的LR(0)项目文法的改写文法G的拓广文法G’：扩充识别符号S’→S（G的识别符号)例5-50)S'→S1)S→BB2)B→aB3)B→bLR(0)项目例(0,0)S’→.S(2,1)B→a.B(3,1)B→b.用状态近似表示分析位置分析位置对应多个LR(0)项目，状态应是LR(0)项目集合。状态计算：从一个分割位置出发，考虑向前分析中可能处于同一分析位置的分割位置。α.BβA.η状态的计算求核心位置的闭包closure(I)J:=I;repeatJ=J∪{B→.η｜A→α.Bβ∈J}untilJ不再扩大例：closure（(0,0)）={(0,0),(1,0),(2,0),(3,0)}状态转移的计算：确定在某状态遇到一个文法符号后的状态转移目标A状态I核心Jα.X．β状态转移函数当前状态I×文法符号X→下一状态go(I,X)=closure(J)其中J={A→αX.β｜A→α.Xβ∈I}计算状态集合Ｃ（P105)即：LR(0)项目集规范族beginI:=closure({S'→.S});C:={I};repeatforC中的每一状态I和每一文法符号Xifgo(I,X)非空并且go(I,X)不在C中将状态go(I,X)加入到C中until不出现新的状态end.例5-6：表达式文法的状态集合拓广文法0)Ｅ'→Ｅ1)Ｅ→Ｅ+Ｔ2)Ｅ→Ｔ3)Ｔ→Ｔ*Ｆ4)Ｔ→Ｆ5)Ｆ→(Ｅ)6)Ｆ→id010,41,8690,420,4,62,97100,4,630,4,6,748110,4,6,75状态计算状态核心闭包增加0(0,0)(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)go(0,E)1(0,1)(1,1)go(0,T)2(2,1)(3,1)go(0,F)3(4,1)go(0,()4(5,1)(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)go(0,id)5(6,1)go(1,+)6(1,2)(3,0)(4,0)(5,0)(6,0)go(2,*)7(3,2)(5,0)(6,0)go(4,E)8(5,2)(1,1)go(4,T)2(2,1)(3,1)go(4,F)3(4,1)go(4,()4(5,1)go(4,id)5(6,1)go(6,T)9(1,3)(3,1)go(6,F)3(4,1)go(6,()4(5,1)go(6,id)5(6,1)go(7,F)10(3,3)go(7,()4(5,1)go(7,id)5(6,1)go(8,))11(5,3)go(8,+)6(1,2)go(9,*)7(3,2)至此，所有状态转移的可能都被考虑到了，不可能再产生新的状态。构造识别活前缀的有限自动机以状态为结点，以状态转移为有向弧。I0I6I9I1E+TI2I7I10T**FI3FFFTFI4I8I11(E)I5id(ididid+活前缀与句柄活前缀是规范归约中句型的前缀，且其右端不超过句柄的末端。例：id+id*id的分析中句型E+id.*id和E+E*.id活前缀活前缀出现在符号栈中的符号串SLR（1）分析表的构造输入：一个拓广文法G'作用表(action)：各状态下遇到终结符时的动作状态转移表(goto)：各状态下遇到非终结符时的转移构造算法：1.构造G'的状态集合{I0、I1…In}2.状态Ii的分析动作action如下：a)ifA→α.aβ∈Iiandgo(Ii,a)=Ijthen(处于状态ｉ、且识别a转移到状态ｊ）将shiftj置入action[i,a]（把a和状态ｊ推入栈）b)ifA→α.∈Iithen（在识别α之后，应做归约）将reduceA→α置入action[i,a]foranya∈FOLLOW(A)（将栈中的产生式右侧符号换为左侧符号）c)ifS'→S.∈Iithen将accept置入action[i,#]（分析成功）3.ifgo(Ii,A)=IjandA∈ＶNthen将j置入goto[i,A]（设置遇非终结符时的状态转移）4.所有空格置error5.以S'→.S所在的状态为初态例5-7：表达式文法的SLR分析表求非终结符的FISRT集和FOLLOW集FIRST(F)={id,(}FIRST(T)={id,(}FIRST(E)={id,(}FOLLOW(E)={),+,#}FOLLOW(T)={),+,#,*}FOLLOW(F)={),+,#,*}si表示移进到状态i,ri表示归约i号产生式P175ACTIONGOTO状态id+*()#ETF01234567891011s5s4s6accr2s7r2r2r4r4r4r4s5s4r6r6r6r6s5s4s5s4s