自下而上分析

《自下而上分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章自下而上语法分析所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说，从语法树末端开始，步步向上“归约”，直到根结点。5.1自下而上分析法的基本问题5.1.1自下而上分析法的基本思想5.1.2自下而上分析法的基本概念5.1.3规范归约5.2算符优先分析法5.2.1优先关系5.2.2算符优先文法及优先表的构造5.2.3算符优先分析法5.2.4优先函数5.1.1自下而上分析法中的基本思想自下而上分析法是一种“移进—归约”法。这种方法的大意是，用一个寄存符号的先进后出栈（符号

2、栈），把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，就把栈顶的这一部分替换成（归约为）该产生式的左部符号。5.1自下而上分析基本问题符号栈的使用移进-归约中的动作有4类移进：读入一个符号并把它入栈。归约：当栈中的部分形成一个句柄（栈顶的符号序列）时，对句柄进行归约。接受：当栈中的符号仅有#和文法的开始符号时，输入符号也到达结尾的时候，执行接受动作。当识别程序觉察出错误的时候，表明输入符号串不是句子，进行错误处理。[例5.1]考虑文法S→aAcBeA→bA→AbB→d把输入串abbcde归约到S。步

3、骤符号栈输入串动作01234567891011##a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S#Sabbcde#bbcde#bcde#bcde#cde#cde#de#e#e####预备进栈进栈归A→b进栈*归A→Ab进栈进栈归B→d进栈归S→aAcBe接受在上例中，每实现一步归约都是把栈顶的一串符号用某个产生式的左部符号来代替。栈顶的这样一串符号称为“可归约串”。自下而上语法分析的关键问题，精确定义“可归约串”，对这个概念的不同定义形成了不同的自下而上的分析方法。在算符优先分析中，用“最左

4、素短语”来刻画“可归约串”，在规范归约分析中，用“句柄”来刻画“可归约串”。各种不同的自下而上分析法的一个共同的特点是，边输入单词符号（移进符号栈），边归约。即在从左到右移进输入串的过程中，一旦发现栈顶呈现可归约串就立即进行归约。语法分析过程可以用一个语法分析树表示出来。在自下而上的分析过程中，每一步归约都可以画出一棵子树来，随着归约的完成，这些子树被连成一棵统一的语法分析树。例如，在例5.1中的移进归约过程中，第3步把栈顶的b归约为A时，就得到图2子树(a)。第5步得到子树(b)；第8步得到子树(c)；第10步归约

5、后连接各子树得到(d)所示的最终语法分析树。面临的基本问题如何找出进行直接归约的简单短语？将找到的简单短语归约到哪个非终结符号？返回5.1.2自下而上分析法中的基本概念句型和句子：设文法G=(Vt,Vn,S,P)，α∈(Vt∪Vn)*，如有，α∈(Vt∪Vn)*，则称α是文法G的一个句型，如α∈Vt*则称是文法G的一个句子，也即只含终结符的句型是一个句子。短语：设αβ是文法G的一个句型，如果有：SαA并且Aβ则称β是句型αβ的关于非终结符A的一个短语，或称β是αβ的一个短语，特别当A→β时，β为句型αβ的一

6、个直接短语，或简单短语。规范推导：句子i+i*i在推导序列中每一步推导都是对句型中的最右非终结符用相应产生式右部进行替换，这样的推导称为最右推导。特别我们将最右推导称为规范推导，用来表示。E=>E+E=>E+E*E=>E+E*i=>E+i*i=>i+i*i(2.1)就是句子i+i*i的规范推导，与规范推导的方向相反，便是规范归约的过程。句柄：一个句型的最左直接短语称为该句型的句柄。一个句型的直接短语可能不止一个，但最左直接短语则是唯一的，将句型中的句柄用产生式左部代替得到新句型，这便是一次规范归约，它恰与规范推导相反

7、。[例5.2]考虑文法E→T

8、E+TT→F

9、T*FF→i

10、(E)关于句型i1*i2+i3的短语，直接短语，句柄分别为：E=>E+T=>T+T=>T*F+T=>F*F+F=>F*i2+i3=>i1*i2+i3=>i1*i2+F=>i1*i2+i3=>i1*F+i3=>i1*i2+i3故i1，i2，i3都是句型的（直接）短语。其中i1是最左直接短语，即为句柄。分析树中短语、直接短语、句柄的对应关系：EET*Fi3+Fi1i2TTF(最左)素短语素短语是指这样的一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更

11、小的素短语。所谓最左素短语，是指处于句型最左边的那个素短语。例如，考虑下列推导中的一个句型：E=>E+T=>T*F+T=>F*F+T=>F*F+F=>F*F+i因为：E=>F*F+F,F=>i，故i是句型的直接短语。E=>E+i,E=>F*F，故F*F是句型的短语。E=>E,E=>F*F+i，故F*F+i是句型的短语。其中，i和F*F都是句型的