第5章+自底向上的语法分析

1第5章自底向上的语法分析2§5.1自底向上语法分析概述3自底向上语法分析从待输入的符号串开始，利用文法的产生式步步向上归约，试图归约到文法的开始符号。如果从语法树的角度看，自底向上分析的过程是以输入符号串作为端末结点符号串，向着根结点的方向往上构造语法树，是开始符号正好是该语法树的根结点。自底向上语法分析过程实际上是一个不断进行直接归约的过程。4移进—归约分析思想我们所讨论的自底向上语法分析是一种“移进—归约”的思想。这种思想的大意是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶符号串形成可归约串时（某个产生式的右部时），即把这个可归约串替换成（归约成）该产生式的左部的非终结符。5“移进—归约”的例子设文法G为：(1)S→aABe(2)A→b(3)A→Abc(4)B→d输入串：abbcdeSaaaaaaaaaAAAAAAAbcbBBde步骤：12345678910动作：进进归进进归进归进归ab(2)bc(3)d(4)e(1)b6对例子的解释上述的“移进—归约”过程实质上是自上向下最右推导的逆过程，而最右推导为规范推导，所以这个归约过程也称规范归约。最右推导：(1)(4)(3)(2)S=aABe=aAde=aAbcde=abbcde上述归约过程中，当句柄出现在栈顶符号串时，则用句柄归约。所以关键是在分析过程中如何确定句柄。7句柄具有“最左”特征，这一点对于移进－归约过程很重要。因为：句柄的“最左”性和符号栈的栈顶是相关的。对于规范句型来说，句柄的后面不会出现非终结符号（即，句柄的后面只能是终结符）。基于这一点，我们可以用句柄来刻划“可归约串”。因此，规范归约的实质是，在移进过程中，当发现栈顶呈现句柄时，就用相应产生式的左部符号进行替换。8自底向上分析方法的分类寻找句柄的方法不同，就形成了不同的自底向上分析方法。优先分析法简单优先分析法(句柄)算符优先分析法(最左素短语)LR分析法(句柄)9§5.2短语、直接短语及句柄10刻画“可归约串”句型的短语S=*αAδ且A=+β，则称β是句型αβδ相对于非终结符A的短语。句型的句柄一个句型的最左直接短语称为该句型的句柄。句型的直接短语若有Aβ，则称β是句型αβδ相对于非终结符A的直接短语。11i*i+i的短语、直接短语和句柄EE+TTFT*Fi3Fi2i1G[E]：E→E+T|TT→T*F|FF→(E)|i句型：i*i+i短语：i1*i2+i3，i1*i2，i1，i2，i3。直接短语：i1，i2，i3。句柄：i112对语法树的剪枝方法1.每个句型都有一棵语法树。2.每棵语法树的端末结自左向右排列就组成一个句型。3.每棵子树的端末结自左向右排列就组成一个短语。4.每棵简单子树的端末结自左向右排列就组成一个直接短语。5.最左简单子树的端末结自左向右排列就组成一个句柄。13上例中对应的语法树S=aABe=aAde=aAbcde=abbcdeSaABeAbcdb14§5.3简单优先分析法15优先分析法可分为简单优先分析法和算符优先分析法。简单优先分析法规定了文法符号间(VN和VT)的优先顺序和结合性质，然后借助这种优先关系和结合顺序来寻找可归约串(句柄)进行归约。算符优先分析法规定了算符间(VT)的优先顺序和结合性质，然后借助这种优先关系和结合顺序来寻找可归约串(最左素短语)进行归约。16每次查看句型中相邻的两个符号。通过两个符号的优先关系判定出前一个符号是句柄的尾。然后，反向找出句柄的头。这样我们就找到了一个句柄。S0…Si-1SiSi+1Si+2……Sj-1SjSj+1…Sn句柄句型17要通过两个相邻符号SiSi+1之间的关系来找到句柄：SiSi+1在句柄内：必然有产生式U→…SiSi+1…。Si在句柄内部，但是Si+1在句柄之后：必然有产生式U→…Si，且存在规范句型…USi+1…。Si+1在句柄内，而Si在句柄外：必然存在规范句型…SiU…，且U→Si+1…。18三种简单优先关系简单优先关系(任意两个文法符号X、Y)1.X±Y当且仅当A→…XY…2.X≮Y当且仅当A→…XB…，且B=+Y…3.X≯Y当且仅当A→…BD…且B=+…X和D=*Y…其中X、Y∈（VN∪VT），A、B、D∈VN注意：±，≮，≯之间不同于=，，和。19简单优先文法如果某个文法满足：1.在文法符号集V中，任意两个符号之间至多有一种优先关系成立。2.任何两个产生式的右部不相同。那么称这个文法为简单优先文法。第一点保证可以识别出句柄.第二点保证可以确定归约到哪个非终结符号(唯一性)。20简单优先文法定理一个简单优先文法是无二义性的，且其任何一个句型S1S2…Sn的唯一句柄是满足条件：Si-1≮Si±Si+1±……±Sj-1±Sj≯Sj+1的最左子符号串SiSi+1……Sj-1Sj。21简单优先分析算法的实现识别过程:从左到右地扫描输入符号。已经扫描或归约得到的符号被存放在一个栈中。每次扫描的时候，将当前符号a和栈顶符号S相比较。如果S≯a表示已经碰到了一个句柄的尾。然后在栈里面向前（下）找，直到找到句柄的头。此时找到右部为该句柄的产生式进行归约。22简单优先分析算法流程图开始初始化R=下一个输入符号栈顶Si≯R?把R入栈找出栈中第一个满足Sj-1≮Sj的值AB否是23简单优先分析算法流程图(续)A停止寻找其右部和句柄匹配的产生式存在这样的产生式栈顶=#且输入串=#出错处理将句柄中的符号退去，将产生式的左部入栈。B是是否否24识别过程(例子)((a),a)栈输入串关系产生式#((a),a)#≮#((a),a)#≮#((a),a)#≮#((a),a)#≯S→a#((S),a)#≯T→S#((T),a)#≯R→T#((R),a)#±#((R),a)#≯S→(R)#(S,a)#±#(S,a)#≮#(S,a)#≯S→a#(S,S)#≯T→S#(S,T)#≯T→S,T#(T)#≯R→T#(R)#±#(R)#≯S→(R)#S#OKS→(R)|a|∧R→TT→S,T|SRSTa∧,()R±S±≯T≯a≯≯∧≯≯,≮±≮≮≮(±≮≮≮≮≮)≯≯25简单优先分析的局限性简单优先分析法只适应于简单优先文法。实际上，一般的程序设计语言的文法都不是简单优先文法。26§5.4算符优先分析法27借助于终结符之间的优先关系确定可归约串。特别有利于表达式分析，宜于手工实现。能力不强，仅能对算符优先文法进行分析。分析过程是一种自下而上的归约过程，但这种归约未必是严格的最左归约。即算符优先分析法不是一种规范归约法。工具：优先表、总控程序、栈28算符优先分析法的引例小学生做四则运算的基本口诀是：先乘除后加减，从左算到右。这句话说出两点要领：第一，四则运算中乘除优先于加减；第二，同级运算一律先左后右(即左结合)。根据这个口诀，任何四则运算的计算过程是唯一的。29四则运算的过程分析9+8-6/2*3(+,-)同级，先作左边的‘+’=17-6/2*3(-,/)异级，‘-’低于‘/’=17-3*3(-,*)异级，‘-’低于‘*’=17-9完成唯一的‘-’=830对i+i*i的归约过程根据输入串中的相继两个终结符的优先级进行归约：(1)i+i*ii≯+(2)E+i*i+≮i(3)E+E*i+≮*，*≮i(4)E+E*E+≮*(5)E+E(6)E31直观算符优先分析法为了易于理解算符优先分析法，先介绍一种简单的算符优先分析法—直观算符优先分析法。四则运算的例子说明了运算的次序只与运算符有关，而与运算对象无关。因而直观算符优先分析法的关键是对一个给定文法G，人为地规定其算符(终结符)的优先关系，再根据任何两个可能相继出现的终结符的优先关系对输入串进行归约。32算符文法(OG文法)设有一文法G，如果文法中没有形如A→…BC…的产生式，则称G为算符文法，也称OG文法(OperaterGrammar)。即：产生式右部不包含两个相邻非终结符。由此定义，算符文法的句型形式如下[V1]a1[V2]a2……[Vn]an[Vn+1]其中，ai∈VT，Vi∈VN，Vi为可选项。33算符优先关系设G是一个不含ε产生式的算符文法，a,b∈VT;而A,B,C∈VN，定义算符优先关系如下：1.a±b：当且仅当G中存在形如A→…ab…或A→…aBb…的产生式。2.a≮b：当且仅当G中存在形如A→…aB…的产生式，且B=+b…或B=+Cb…。3.a≯b：当且仅当G中存在形如A→…Bb…的产生式，且B=+…a或B=+…aC。34算符优先文法(OPG文法)设有一不含ε产生式的算符文法G，如果对任意两个终结符a、b之间至多存在一种算符优先关系，那么该算符文法是一个算符优先文法，也称OPG文法(OperatorPrecedenceGrammar)。至多：要有关系就有±、≮、≯中的一种，要不就没有。算符优先分析仅适用于算符优先文法。算符优先分析法中，我们用最左素短语来刻划可归约串。35举例设有文法G:(1)E→E+T|T(2)T→T*F|F(3)F→P↑F|P(4)P→(E)|i试问G是OPG文法吗？1.先根据OG文法的定义判断G是否是OG文法；2.再找出G中所有终结符对的优先关系；3.最后根据OPG文法的定义判断G是否是OPG文法。36OPG优先关系的构造1.由算法构造算符优先关系2.由关系图构造算符优先关系(自学)37由算法构造算符优先关系定义：FIRSTVT(B)={b|B=+b…,或B=+Cb…}LASTVT(B)={a|B=+…a,或B=+…aC}构造优先关系：1.±关系：若有形如A→…ab…A→…aBb…的产生式，则a±b。2.≮关系：若有形如A→…aB…的产生式，b∈FIRSTVT(B)，则a≮b。3.≯关系：若有形如A→…Bb…的产生式，a∈LASTVT(B)，则a≯b。38FIRSTVT和LASTVT的构造FIRSTVT(A)的构造：LASTVT(A)的构造：1.若有A→a…或A→Ba…,则a∈FIRSTVT(A)；2.若a∈FIRSTVT(B),且有A→B…,则a∈FIRSTVT(A)。1.若有A→…a或A→…aB,则a∈LASTVT(A)；2.若a∈LASTVT(B),且有A→…B,则a∈LASTVT(A)39素短语素短语是满足下面条件的短语：1.至少包含一个终结符。2.该短语不再包含满足第一个条件的更小的短语。最左素短语：是处于句型最左边的那个素短语。40关于句型T+T*F+i的素短语短语有T+T*F+i，T+T*F，T*F，T，i。其中，素短语为T*F，i。T+T*F+i，T+T*F不是素短语，因为其中包含了T*F。T不是素短语，因为其中没有终结符号。最左素短语：T*F。EE+TET+FiT*FT41关于最左素短语的定理一个算符优先文法的句型的最左素短语是该句型中满足下列条件的最左子串[Vi]ai……[Vj]aj[Vj+1]：ai-1≮ai±ai+1±…±aj≯aj+1算符优先分析算法就是根据这个最左素短语的定理构造的。42算符优先分析算法的实现工作原理：对当前句型不断寻找最左素短语进行归约的过程。寻找最左素短语时，首先找到最左素短语的末尾终结符，然后再向前搜索最左素短语的首终结符。使用的数据结构：栈，数组。有关约定：＃作为语句括号，视为终结符，其优先级最低。43算符优先分析算法与简单优先分析算法的比较两个算法类似，所不同的是算符优先分析算法每一步归约不一定是规范归约，而是找出最左素短语进行归约，并且在寻找最左素短语的过程中，只比较终结符之间优先关系，不受非终结符的影响。44使用优先函数的原因对于一个实际的程序设计语言的文法，优先矩阵将会非常大。对于有n个终结符的文法，矩阵的大小是(n+1)2(终结符和#号)。解决的方法是引入优先函数，将矩阵线性化。对于有n个终结符的文法，只需2(n+1)个单元存放优先函数。45优先函数定义把每个文法符号与两个自然数f()和g()相对应，使得若a±b则f(a)=g(b)若a≮b则f(a)g(b)若a≯b