编译原理 自底向上优先分析方法

1第六章自下而上优先分析法所有的自下而上分析方法都是按照移进-归约法的原理.基本思想是用一个寄存文法符号的先进后出栈，将输入符号按从左到右扫描顺序逐个移入栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时（对应于某条规则右部）就进行一次归约，即用该规则左部非终结符替换相应规则右部符号串.重复这一过程直到整个输入串分析完毕.最终若栈中剩下句子右界符“#”和文法的开始符号，则所分析的输入符号串是文法的正确句子.否则,就不是正确的句子，报告错误.2设G=(VT,VN,S,P),α,β∈(VT∪VN)*,A→β∈P,αAwαβw归约的过程是，已知αβw和产生式A→β，用产生式A→β左部A替换αβw中的β，得到符号串αAw.从输入符号串出发，每次从被归约的句型中找到一个产生式的右部，用其左部替换之，得到新的句型，直至归约到文法的开始符号。归约3【例】文法G[S]对输入串abbcde#进行语法分析，检查该符号串是否是该文法的正确句子。S→aAcBeA→bA→AbB→d4S→aAcBeA→bA→AbB→dabbcdeabbcdeaAbcdeaAcdeaAcBeSAABS5右句型句柄归约规则abbcdebA→baAbcdeAbA→AbaAcdedB→daAcBeaAcBeS→aAcBeS从例子中可以看出，一个句型中当含有多个子串可以匹配不同产生式的右部时，将有不同的归约过程，究竟应该对谁先归约呢？61.一个句型的最左直接短语称为该句型的句柄，句柄是规范归约的可归约串。2.假定α是文法G的一个句子，称序列αn,αn-1,αn-2,…,α0是α的一个规范归约，如果此序列满足：1)αn=α；α0为文法的开始符，即α0=S；2)对任何i，0＜i＜n,αi-1是从αi经把句柄替换为相应产生式的左部符号而得到的。3.如果文法G是无二义的，规范归约是最右推导的逆过程，规范归约也称最左归约,最右推导也称规范推导。4.结论：对规范句型来说，句柄的后面不会出现非终结符。因此，规范归约的实质是在移进过程中，发现栈顶呈现句柄时就用相应的产生式的左部符号进行替换。规范归约简述7对输入串abbcde的最右推导过程是：SaAcBeaAcdeaAbcdeabbcde。用语法树表示如下图所示：8用语法树表示规范归约过程如下图所示：它与最右推导的逆过程相对应。9非形式地，一个符号串的“句柄”是和一个规则右部匹配的子串，而且把它归约到该规则左部的非终结符,代表了最右推导逆过程的一步。句柄找句柄是非常重要的在很多情况下，匹配某个规则A右部的最左输入子串不是句柄，因为用这个规则归约产生的串不能归约到开始符号。【例】对于串aAbcdeb是产生式Ab的右部,但b不是句柄。如果进行归约，得到aAAcde，而aAAcde不能归约到S.因此我们必须更精确地定义句柄。10形式的说，右句型(最右推导可得的句型)γ的句柄是一个与规则A→β和γ中的一个位置有关的，从这个位置开始往右可找到β，用A代替β得到γ最右推导的前一个右句型，即如果SAwβw,那么，在后β是βw的句柄。句柄右侧的w是未读入的终结符号。句柄(续)*rmrm11“移进一归约”分析器使用一个栈和一个存放输入符号串w的缓冲器。分析器的初始状态为:栈输入动作#w#工作过程：自左至右把串w的符号一一移进栈里，一旦栈顶形成句柄时，就进行归约。这种归约可能持续多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重复这个过程，直至最终形成如下格局：栈输入#S#(分析成功接受)“移进-归约”分析法的栈实现12符号栈输入串动作初态#w#……(移进、归约、出错)（中间过程）终态#S#(分析成功接受)符号栈的使用13对符号栈的使用有“移进”、“归约”、“接受”、“出错处理”等操作。1)“移进”是指在栈顶还没有形成可归约串时，把输入串的一个符号移进符号栈；2)“归约”是指发现栈顶已形成可归约串，对其进行归约；3)“接受”是指宣布分析成功，表明输入串是文法合法的句子；4)“出错处理”是指栈顶符号和要输入的符号在某种关系上出现矛盾，分析过程无法正常进行，通常此时要调用出错处理程序确定错误类型、校正错误，并使分析过程继续进行下去。14还有一个非常重要的事实，任何可归约串的出现必在栈顶，不会在栈的内部。对规范归约而言，这个事实是明显的。规范归约是最左归约，这种“最左性”保证可归约串一定在栈顶。也正因为如此，先进后出栈在自下而上分析中是一种非常重要的数据结构。156.1自下而上优先分析法概述优先分析法有两种：①简单优先分析法(规范归约)——文法按一定原则规定文法符号的优先关系②算符优先分析法(不规范归约)——规定算符之间的优先关系简单优先分析法:准确、规范，但效率较低，实际使用价值不大.算符优先分析法：分析速度快，适用于表达式分析，但归约不规范.166.2简单优先分析法简单优先分析法是按照文法符号的优先关系确定句柄.因此，在这种方法中的关键是确定文法符号间的优先关系.1.优先关系(1)X=·Y当且仅当G中存在产生式规则A－…XY…(2)X·Y当且仅当G中存在产生式规则A－…XB…，且B＝Y…(3)X·Y当且仅当G中存在产生式规则A－…BD…，且B＝…X和D=Y…例6.2见书P.105++*172.简单优先文法若一个文法满足：（1）在文法符号集V中，任意两个符号之间最多只有一种关系成立；（2）在文法中任意两个产生式没有相同的右部.则这样的文法为简单优先文法.183.简单优先分析法－优先分析算法（1）根据优先文法构造优先关系矩阵；（2）存储文法产生式，并设符号栈S；（3）将输入符号串a1a2…an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止.（4）栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak,即找到ak-1ak为止.（5）由句柄ak…ai在文法的产生式中查找右部为ak…ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子.（6）重复（3）－（5）直至归约完输入串，栈中只剩下文法的开始符号为止.196.3算符优先分析法算符优先分析法是一种简单、直观的自下而上分析法。特别适合分析程序语言中各类文法且宜于手工实现。206.3.1方法概述算符优先分析法是一种简单、直观、广为使用的自下而上语法分析方法，它是依据算术表达式的四则运算过程而设计的一种方法，也适用于对一般的高级语言程序的分析。算符优先分析法的基本思想是，首先确定运算符（确切地说是终结符）之间的优先关系和结合性质，然后借助这种关系，比较相邻运算符之间的优先级来确定句型的可归约串，并进行归约。值得注意的是，算符优先分析过程虽然是自下而上归约过程，但它的可归约串未必是句柄，也就是说，算符优先分析过程不是一种规范归约。21【例】文法G[E]：E→E+E|E*E|(E)|id这是一个二义性文法，对句子id+id*id有两种不同的规范归约，在规范过程中句型的句柄不唯一。第一个规范归约过程(1)id+id*id(2)E+id*id(3)E+E*id(4)E+E*E(5)E+E(6)E第二个规范归约过程(1)id+id*id(2)E+id*id(3)E+E*id(4)E*id(5)E*E(6)Eid是句柄E+E是句柄此现象是由于没有定义运算符+和*的优先关系而引起的。在归约过程中起决定作用的是相邻两个终结符符号之间的优先关系。22任何两个相邻终结符a和b之间的优先关系有三种：a·ba的优先级低于ba·ba的优先级高于ba=·ba的优先级等于b相邻终结符号的优先关系注意：优先关系与出现的左右次序有关。a·b不一定有b·aa=·b不一定有b=·a例：表达式中运算符的优先关系有+.-,但没有-.+成立，（=·）成立但没有）=·（成立.23优先关系矩阵（优先关系表、优先表）一个文法的终结符号之间的优先关系可用一个矩阵来表示，矩阵的每一行每一列都是文法的终结符，矩阵元素是两终结符之间可能的优先关系。算符优先分析法就是借助优先关系矩阵寻找句型的可归约串。需要指出的是，算符优先分析法并不是对所有的文法都适合，它对文法有一定的要求，要求文法是算符优先文法，也就是说，只有当描述语言的文法是算符优先文法，才能采用算符优先分析法进行语法分析。246.3.2算符优先文法的定义1、算符文法的定义设有文法G，若它的任一规则的右部都不含两个相邻的非终结符，即不含形如：U…VW…的规则，则称该文法为算符文法，也称OG(OperatorGrammar)文法。算符文法具有如下性质：25性质1：在算符文法中，任意句型都不含两个相邻的非终结符。1.推导长度是n，归纳起点n＝1时，S=01＝，即S，必存在一个规则S，而由算符文法的定义，文法的规则中无相邻的非终结符，满足性质1。2.假设n1，n-1满足性质1。若n-1＝A，A为非终结符。由假设的的尾符号和的首符号都不是非终结符，否则与假设矛盾。又若A是文法的规则，则有n-1n＝=而A是文法的规则，它不含两个相邻非终结符，所以也不含两个相邻的非终结符，满足性质1。*证明：用归纳法设是句子，S，即S01...n-1n＝26性质2：若Ab或bA出现在算符文法的句型中，其中AVN,bVT,则中任何含b的短语必包含A.证明：用反证法。由算符文法的性质1可知。S＝bA若存在Bb，这时b和A不同时归约，分属于不同的短语，则必有SBA，这样在句型BA中，存在相邻的非终结符，所以与性质1矛盾。故：中任何含b的短语必包含A，证毕。*注意：含b的短语必含A，含A的短语不一定含b。272．终结符号间的优先关系的定义设G是一个算符文法，对于任何终结符a、b，算符优先关系·、=·、·定义如下：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；++++28由语法树来说明优先关系1)a=•b则存在语法子树(a)，a和b在同一句柄中同时归约，所以优先级相同。2)a•b则存在语法子树(b)，a和b不在同一句柄中，b先归约，所以a的优先级小于b。3)a•b则存在语法子树(c)，a和b不在同一句柄中，a先归约，所以b的优先级小于a。其中为或非终结符293．算符优先文法的定义设有一个不含ε-规则的算符文法G，如果任何终结符对(a，b)至多只满足下述关系之一：a=·b，a·b，a·b；则称G是一个算符优先文法，也称OPG文法。(OPG—OperatorPrecedenceGrammar)30【例】文法G[E]：E→E+E|E*E|(E)|id1.所有规则中都没有相邻的非终结符，所以它是算符文法OG文法。2.由于E→E+E和EE*E，所以有+·*由于E→E*E和EE+E，所以有+·*运算符+和*之间存在两种不同的优先关系，所以该文法不是算符优先文法OPG.++文法G[E]：E→E+T|TT→T*F∣FF→(E)|id该文法是算符优先文法（OPG）316.3.3算符优先关系表的构造对任意的文法非终结符A，给出集合FIRSTVT(A)和LASTVT(A)的定义：FIRSTVT(A)={a︱Aa…或ABa…，a∈VT而B∈VN}LASTVT(A)={a∣A…a或A…aB，a∈VT而B∈VN}＋＋＋＋若产生式右部是…aA…，且b∈FIRSTVT(A)，则必有优先关系：a·b若产生式右部是…Ab…，且a∈LASTVT(A)，则必有优先关系：a·b由上述定义，我们有：32构造优先关系表的算法输入：算符优先文法G输出：关于文法G的优先关系表方法：1.为每一个非终结符A构造集合FIRSTVT(A)和LASTVT(A);2.由FIRSTVT(A)和LASTVT(