第5章 自下而上的语法分析(Tsu版电子教案)

第5章自下而上的语法分析（Tsu版电子教案）第1页共7页第5章自下而上的语法分析从叶结点出发，步步向上归约。若能归约到根结点，说明输入串是文法的一个句子，否则输入串存在语法错误。5.1自下而上的语法分析概述㈠概述实质上是一种移进归约法，设置一个栈，将输入串符号逐个移进栈内，一旦发现栈顶形成某个产生式的候选式时，立即将栈顶这一部分符号替换（归约）成该产生式的左部符号。例给定文法Ｇ：S→aAcBeA→b|AbB→d和输入串abbcde，其移进归约过程如下所示：edBBbccccbAAAAAAAaaaaaaaaaS移移归移归移移归移归①②③④⑤⑥⑦⑧⑨⑩因最终归约到根结点，输入串abbcde是文法的一个句子。㈡问题从第④步到第⑤步有二种选择，可将b归约成A，栈顶成aAA；也可将Ab归成A，栈顶成aA，显然后者是正确的，故需精确定义可归约串。㈢句柄和规范归约①短语②直接短语（简单短语）③句柄继续问题的讨论。句型aAbcde中存在三个短语，它们是Ab、d和aAbcde，其中Ab和d是直接短语，句柄是Ab。不能因为存在规则A→b，就断定b是这个句型的一个短语，b不是句柄，甚至连短语都不是。④规范归约（最左归约）⑤规范句型⑥规范推导⑦图解法5.2LR分析法的基本原理㈠前缀㈡活前缀㈢LR分析法的基本思想㈣LR(0)项目（简称项目）在产生式右部的某个位置添加一个园点“.”。特例，A→ε的项目为A→.。例文法第5章自下而上的语法分析（Tsu版电子教案）第2页共7页0.S'→E1.E→aA2.A→cA3.A→d4.E→d这个文法的项目有○1S'→.E○2S'→E.○3E→.aA○4E→a.A○5E→aA.○6A→.cA○7A→c.A○8A→cA.○9A→.d○10A→d.○11E→.d○12E→d.㈤构造识别活前缀的NFA①将每个项目视为识别活前缀NFA的一个状态。②规定状态S'→.S为NFA的唯一初态，状态S'→S.为NFA的唯一接受态（S为原文法开始符号，S'为拓广文法开始符号）。③因在每个状态都可识别出一个活前缀（初态可识别出活前缀ε），故NFA的每个状态都是终态，终态又称为活前缀识别态。④如果状态i和状态j源自于同一产生式，而且状态i和状态j的园点位置相差一个文法符号，例状态i为i:X→X1……Xi-1.XiXi+1……Xn状态j为j:X→X1……Xi-1Xi.Xi+1……Xn那么状态i和j之间存在一条弧，标记为Xi，表示在状态i读入Xi进入状态j。⑤若状态i园点之后的符号为非终结符（例i:X→α.Aβ），那么从状态i画一条ε弧到所有k:A→.γ状态。表示只有看到了从A推出的全部符号，状态i:X→α.Aβ才可经A弧进入状态j:X→αA.β。接上例，构造识别文法活前缀的NFA，如下所示：ε○6A→.cA○7A→c.AA○8A→cA.cεε○9A→.dd○10A→d.ε○3E→.aAa○4E→a.AA○5E→aA.ε○1S'→.EE○2S'→E.ε○11E→.dd○12E→d.其中○1称为初态（含有S'→.E的项目），状态○2、○8、○10、○5和○12称为句柄识别态（含有形如A→γ.的项目），其中○2又称为接受态（含有S'→E.的项目）。㈥构造识别活前缀的DFA第5章自下而上的语法分析（Tsu版电子教案）第3页共7页5:7:c○7A→c.AA○8A→cA.○6A→.cA○9A→.dd6:○10A→d.2:c○4E→a.Ad4:○6A→.cAA○5E→aA.○9A→.d0:a○1S'→.E1:○3E→.aAE○2S'→E.○11E→.dd3:○12E→d.其中0是初态，1为接受态，3、4、6和7是句柄识别态。㈦项目分类㈧LR(0)项目集规范族（简称项目集规范族）㈨活前缀识别工作原理5.3项目集规范族的构造㈠文法拓广㈡项目集I的闭包（CLOSURE(I)）㈢状态转换函数（GO(I,X)）㈣项目集规范族构造算法第5章自下而上的语法分析（Tsu版电子教案）第4页共7页5.5LR(0)分析表的构造㈠预备工作①引入产生式S'→S，将文法拓广成G'。②对G'的产生式进行编号。③构造文法G'的状态转换函数GO(I,X)和项目集规范族C。㈡构造法设项目集规范族C={I0、I1、……In}，将I0、I1、……In视为分析表状态0、1、……n。LR(0)分析表存放在二维数组M中，第一维为状态，第二维为文法符号。①若移进项目A→α.aβ∈Ii且GO(Ii,a)=Ij，其中a∈VT，则置M[i][a]=sj（s表示移进）。②若归约项目A→α.∈Ii，对于任何a∈VT∪{#}，置M[i][a]=rk（k是产生式A→α的编号，r表示归约）。③若接受项目S'→S.∈Ii，则置M[i]['#']=Acc（Acc表示接受）。④若待约项目A→α.Bβ∈Ii且GO(Ii,B)=Ij，其中B∈VN，则置M[i][B]=j。⑤分析表中的空白表示出错。例已知文法GE→aA|dA→cA|d构造它的LR(0)分析表。解：①预备工作1）引入产生式S'→E，将文法G拓广成G'。2）产生式编号如下：0.S'→E1.E→aA2.E→d3.A→cA4.A→d3）构造上述文法的状态转换函数GO(I,X)和项目集规范族（见5.3节）。②构造分析表5.6SLR(1)分析表的构造㈠SLR(1)分析法的引出第5章自下而上的语法分析（Tsu版电子教案）第5页共7页例简单算术表达式文法G'：0.S'→E1.E→E+T2.E→T3.T→T*F4.T→F5.F→(E)6.F→i它的项目集规范族如下图所示：项目集规范族共有12个状态（I0-I11），根据项目集规范族构造LR(0)分析表，如下：第5章自下而上的语法分析（Tsu版电子教案）第6页共7页因M[2]['*']=s7r2、M[9]['*']=s7r1，分析表含多重定义，故上述分析表不是LR(0)分析表。㈡SLR(1)分析法的基本思想假定I是项目集规范族的一个项目集I={X→α.bβ，A→α.，B→α.}若follow(A)∩follow(B)={}、follow(A)∩{b}={}、follow(B)∩{b}={}，则SLR(1)分析法处理如下：①若当前输入符号t.code和b相等，则移进输入符号。②若当前输入符号t.code∈follow(A)，则用产生式A→α进行归约。③若当前输入符号t.code∈follow(B)，则用产生式B→α进行归约。④此外报错。㈢构造法SLR(1)分析表的构造是在LR(0)分析表基础上进行的，只要对LR(0)分析表的构造方法稍加修改，就可获得SLR(1)分析表的构造方法，修改部分如下所述：㈠预备工作①②③④计算非终结符的follow集。㈡构造法①②若归约项目A→α.∈Ii，对于任何a∈follow(A)，置M[i][a]=rk（k是产生式A→α的编号，r表示归约）。③④⑤接上例，构造G的SLR(1)分析表。解：①预备工作1）文法拓广（同上）2）产生式编号（同上）3）构造状态转换函数GO(I,X)和项目集规范族（同上）4）计算非终结符的follow集folow(S')={#}、folow(E)={#,+,)}、folow(T)={#,+,),*}、folow(F)={#,+,),*}②构造分析表第5章自下而上的语法分析（Tsu版电子教案）第7页共7页5.7LR语法分析器的控制程序㈠数据结构①LR分析表②状态栈③符号栈④产生式右部符号串长度㈡手工模拟控制程序计算㈢算法描述分析表用二维数组M存储，栈顶状态用Stop表示，当前输入符号用t.code表示，控制程序的算法归纳如下：①移进若M[Stop][t.code]=sj，说明句柄尚未形成，应执行移进操作。s表示移进，j为状态号，将j移入状态栈，将t.code移入符号栈，j成为新的栈顶状态Stop。读下一个单词。②归约若M[Stop][t.code]=rk，说明句柄已出现在栈顶，应该用编号为k的产生式A→β进行归约。假设，LEN(β)=r，M[Stop-r][A]=j。首先将栈顶r个元素出栈，然后将j和A分别移入状态栈和符号栈，j成为新的栈顶状态Stop。当前处理单词不变。③接受M[Stop][t.code]=Acc，表示输入串是一个合法句子，程序终止运行。④出错M[Stop][t.code]=空白，表示出错，最简单处理为程序终止运行。5.8二义文法在LR分析法中的应用任何二义文法都不是LR文法，可通过现两种途径来解决文法的二义性问题。例简单算术表达式文法G：E→E+E|E*E|(E)|i，它是一个二义文法，二义性源自于文法本身没有规定运算符的优先性和结合性。㈠根据条件将文法修改成无二义性文法规定*优先+，同级运算服从左结合，修改文法为G1：E→E+T|TT→T*F|FF→(E)|iG1是与G等价的非二义文法。㈡根据条件消除分析表的多重定义二义文法简单，分析表规模小，在程序设计语言中仍有应用。可根据二义文法构造分析表，然后根据条件消除分析表的多重定义。5.4有效项目可根据课时和学生水平选讲。5.10LR分析法在词法分析器自动构造中的应用可根据课时和学生水平选讲。