《编译原理实践及应用》PPT教学课件-第4章（2） 自下而上语法分析.ppt

自下而上语法分析方法,第四章（2）,本节要求,主要内容：自下而上语法分析的概念，规范归约，算符优先分析方法及其相关概念。 重点掌握：掌握自下而上分析的基本思想，规范规约的概念及过程；算符优先文法、算符优先关系的判定，最左素短语、句柄的定义与判定，构造算符优先关系表，能用算符优先分析法进行表达式分析,g = (e, i, +, *, (, ) , p , e) p： e e + e e e * e e ( e ) e i,使用最左推导：e e*e (e)*e (e + e)*e (i + e)*e (i + i)*e (i + i)*i,例：判定输入串(i+i)*i是否是下述文法的句子？,结论：自上而下语法分析采用最左推导，每一步推导使用哪个产生式要视当前非终结符匹配输入字符串中的哪个符号来确定。 自下而上语法分析是最右推导的逆过程，由输入符号串反向推导到文法的开始符号。,自下而上的语法分析,实现思想：“移进-归约”方法 设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。重复这一过程，直到栈中只剩下文法的开始符号，就确认输入串是文法的句子，分析成功，否则出错。 语法树：从树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。 核心 寻找句柄（这是关键）进行规约。用不同的方法寻找句柄，就可获得不同的分析方法。,最左推导(left-most derive) 每一步推导都替换当前句型的最左边的非终结符。 其逆过程称为最右归约 最右推导(right-most derive) 每一步推导都替换当前句型的最右边的非终结符。 其逆过程称为最左归约(规范归约)，得规范句型,例：设有文法gs： (1) s aacbe (2) a b (3) a ab (4) b d 使用最右推导： 因为s aacbe aacde aabcde abbcde，所以 abbcde是文法g的句子。,步骤 动作,(1)s aacbe (2)a b (3)a ab (4)b d,最左归约过程是最右推导的逆过程， 对输入串abbcde的归约过程如下：,该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。,a,b,a,c,s,b,d,b,e,a,语法分析树的生成演示,a b b c d e,a,a,b,s,ab,aab,bd,saacbe,(1)s aacbe (2)a b (3)a ab (4)b d,这种分析过程具有如下特点： 从输入串的开始依次读入单词(移进栈中) 。 一旦发现可归约串（某个产生式的右端）就立即归约。 归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次。 若最终能归约成文法的开始符号，则分析成功。 由于总是将句型的最左边的可归约串替换成非终结符，该方法与最右推导对应。 关键是如何判断可归约串？,问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 不同的自下而上的分析方法对可归约串的定义是不同的，但分析过程的一个共同特点是：边移进边归约。,规范归约的概念,有文法g，开始符号为s, 如果有s=xy,则xy是文法g的句型，x,y是任意的符号串 如果有s=xay, 且有a=,则是句型xy相对于非终结符a的短语 如果有s=xay, 且有a-,则是句型xy相对于a-的直接短语 位于一个句型最左边的直接短语称为句柄.,注意: 每次归约的部分必须是句柄 (最右推导)。 关键的问题是如何识别句柄,例：考虑如下文法：,求句型 i1 * i2 + i3 的短语、直接短语和句柄。,et | e+t tf | t*f fi | (e),因此： 短语有：i1, i2, i3, i1*i2, i1*i2+i3 直接短语有：i1, i2 , i3 句柄是： i1,e = f * i2 + i3 e = i1 * f + i3 e = i1 * i2 + f,e = t + i3 （t =t*f =i1 * i2） e = i1 * i2 + i3,fi,从语法分析树来识别： 一棵子树是由树的某个结点连同它的所有子孙组成的。 子树的所有端末结点自左至右排列成一个相对子树根的短语。 直接短语：只有父子两代结点形成的短语。 句柄：最左子树的直接短语。,从语法树可以看出： i1, i2, i3, i1*i2, i1*i2+i3是句型i1*i2+i3的短语 直接短语有：i1, i2 , i3 句柄是： i1,et | e+t tf | t*f fi | (e),句型i1*i2+i3的语法树如图：,对下述文法，求句型 e+t * f + i的短语、直接短语、句柄,et | e+t tf | t*f fi | (e),短语有：i, t * f, e+t * f, e + t * f + i 直接短语有： i, t * f 句柄是：t * f,练 习,给定右边的文法，用句柄对符号串abbcde进行归约,用句柄对句子进行归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。,(1)s aacbe (2)a b (3)a ab (4)b d,(2)ab,(3)a ab,aabcde,aacde,(4)b d,(1)s aacbe,aacbe,s,规范归约的定义：,假定是文法g的一个句子，如果序列： n, n-1, , 0 (=s)满足如下条件，则序列n, n-1, , 0是一个规范归约: (1) n = 是给定的句子 (2) 0 =s 是文法的开始符号 (3) 对任何i, 0in，i-1是从i经把句柄替换为相应文法产生式的左部符号而得到的。 规范归约是最右推导的逆过程，又称为最左归约。 最右推导又称规范推导，由规范推导所得到的句型称规范句型，规范推导的逆过程是规范归约。,(1)s aacbe (2)a b (3)a ab (4)b d,上述例子中句子abbcde的规范归约过程是： abbcde， aabcde， aacde， aacbe，s,练 习,使用下述文法对句型i1*i2+i3进行规范归约:,et | e+t tf | t*f fi | (e),i1*i2+i3 , f*i2+i3 , t*i2+i3, t*f+i3 , t + i3 , e+i3 , e + f, e + t , e,使用修剪语法树的方法来进行归约：,规范归约分析中栈的使用,1、句型表示,符号栈内容 + 输入缓冲区内容 # 当前句型 #,2、分析器结构,能够到达终态，分析成功，不能到达终态，分析失败。,例2：有文法： e e+t|t t t*f|f f (e)|i 对输入串 id1+id2*id3 的规范归约过程：,动作 栈 输入缓冲区 1) 准备 # id1+id2*id3# 2) 移进 #id1 +id2*id3# 3) 归约 fid #f +id2*id3# 4) 归约 tf #t +id2*id3# 5) 归约 et #e +id2*id3# 6) 移进 #e+ id2*id3# 7) 移进 #e+id2 *id3# 8) 归约 fid #e+f *id3# 9) 归约 tf #e+t *id3# 10) 移进 #e+t* id3# 11) 移进 #e+t*id3 # 12) 归约 fid #e+t*f # 13) 归约 tt*f #e+t # 14) 归约 ee+t #e # 15) 接受,所得的结果是：用产生式序列表示语法分析树,id1 + id2 * id3,f,t,e,f,t,f,t,e,(1) et | e+t (2) tf | t*f (3) fi | (e),练习,给出句型(a,(a,a)的 规范归约过程,给定文法gs：,s a | (t) t t,s | s,3. 过程描述： repeat repeat 将输入串最左边的符号移入栈内； until 栈顶出现一个可归约串； 归约可归约串； until 文法开始符号出现在栈顶或者发现错误,分析成功的条件：栈顶为文法开始符号，输入符号串为空。 注意：该过程并未涉及如何在栈里找可归约串。实际上，不同的找可归约串的方法，构成了不同的分析方法。 “移进-归约”分析法用栈实现的特点： 可归约串必定位于栈顶，即可归约串之后就是剩余的输入串。 栈内符号串与剩余输入串正好构成一个句型。,分析器的四种动作,1) 移进：将下一输入符号移入栈 2) 归约：当栈顶出现句柄，用产生式左侧的非终结符替换栈顶的句柄 3) 接受：分析成功，是归约的一种特殊情况 4) 出错：栈顶的内容与输入符号相悖，进行出错处理 ？决定移进和归约的依据是什么,移进归约分析中的问题,1) 移进-归约冲突 在分析到某一步时，既可以移进，又可以归约 上例第10)步可以移进*，也可以按产生式ee+t进行归约。 2) 归约-归约冲突 存在两个可选的句柄，可对栈顶符号进行归约 例如上述第13)步，可以用tf进行归约，又可以按tt*f进行归约。 各种分析方法中处理冲突的技术不同,语法分析树的表示,具体实现时可以采用不同的数据结构 可以使用“穿线表”方法来表示语法树,优先分析法有两种： 简单优先分析法(规范归约)文法按一定规则规定文法符号的优先关系 算符优先分析法(不规范归约)规定算符之间的优先关系,自下而上优先分析法概述,算符优先分析,算符优先分析法的思想源于表达式的分析，是利用相邻终结符号之间的关系来寻找可归约串。 将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄，分析过程是自下而上的归约过程，不是一种严格的规范归约。,优先关系的定义：,在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在三种优先关系： (1) a优先性等于b ，记作a b。 (2) a优先性高于b， 记作a b。 (3) a优先性低于b ，记作a b。,另一种情况是，a与b不可能相邻，即此符号串不是句型(出错)。 如果以上四种关系中的任意两种都不会同时成立，则可以根据终结符号之间的归约关系进行语法分析。,1.算符文法：如果文法g没有p.qr.(p,q,r属于非终结符)的产生式,(主要是看产生式中是否包含两个非终结符相邻的情况) 2.算符优先关系的定义：文法g是一个不含-产生式的算符文法，定义终结符a、b之间的优先关系 a b,g中有p.ab.或p.aqb. (在同一产生式中) a b,g中有p.ar.的产生式,且r=b.或r=qb. (注意ab相邻) a b,g中有p.rb.的产生式,且r=.a或r=.aq (注意ab相邻),算符优先文法的定义,例：ee+e | e*e | (e) | i 证明不是算符优先文法。 因 为：ee+e ，ee*e 则有 + *(由规则2) 又因为：ee*e, ee+e 则有 + *(由规则3) 所以不是算符优先文法。,3.算符优先文法 算符文法g的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有 = , 中的一种成立,则g为一算符优先文法。,练 习,对右边的文法g，计算终结符+，*，和 )之间的优先关系：,ee + t tt * f fp f p(e),因为： ee + t ，t=t*f，所以：+ e + t ，所以：+ + (规则3) 因为： t t * f ，f = p f，所以：* t * f，所以：* * (规则3) 因为： p(e) ， e = e + t ，所以：+ ) (规则3) 因为：fp f, p = (e)，所以：） (规则3) 因为： fp f， f =p f，所以： (规则2) ,算符优先关系表的构造,用表格形式来表示各终结符号的优先关系，这种表称为优先表。 构造优先关系表的方法： 按照定义手工计算 使用算法 例: p: e e+t|t t t*f|f f (e)|i 求算符优先关系表。,由f(e) 得 ( = ),例: p: ee+t|t tt*f|f f (e)|i 求算符优先关系表,终结符+#,终结符+#,对于结束符#和其它终结符a之间若有关系,则必有: # # ，计算方法是拓展成e#e#,注意：,a,b之间未必有优先关系,在优先表中，空白部分是一种错误关系 相同的终结符之间的优先关系不一定是 如果有a = b,不一定有b = a(不具对称性) 如果有a b,不一定有b a(不具对称性)，因为只定义相邻运算符之间的优先关系，a,b相邻时，不一定b,a相邻。 如果有a b, b c不一定有a c,算符优先关系表的自动构造算法,1.firstvt集 定义：对每个非终结符p, firstvt(p)=a|p=a.或p=qa.,a为终结符,p，q为非终结符,由优先性低于的定义和firstvt集合的定义可以得出： 若存在某个产生式：q-ap， 对所有：bfirstvt(p) 都有：a b。,构造firstvt集算法:,按照下面两条规则来构造firstvt集： 若有产生式pa.或pqa.,则afirstvt(p) 若有产生式pr.,若afirstvt(r),则afirstvt(p),所有终结符,所有非终结符,数组值为真假，为真的条件是c firstvt(q),通过构造一个二维数组f来实现, 数组f的每一行反映任何一个非终结符p的firstvt集中的元素。步骤：,(1)先用第一条规则进行初始化,(2)使用第二条规则对数组f进行修改，修改方法是： (1) 用一个栈，将所有f数组中值为真的元素fp,a的符号对(p,a)压入堆栈； (2) 对栈施行如下操作：若栈不空，将栈顶符号对出栈，记为(q,a)，检查所有的产生式，若有形为：pq的产生式，且fp,a为假， 则置fp,a为真，将(p,a)压入堆栈； (3) 重复这一过程，直到栈空,例：求文法各非终结符的firstvt：,定义数组：,ee+t | t tt*f | f f(e) | i,从而得到： firstvt(e) = +, *,(, i firstvt(t) = *,(,i firstvt(f) = (,i,练习,firstvt(s) = a,( firstvt(t) = a,(, , ,计算firstvt,给定文法gs：,s a | (t) t t,s | s,求firstvt集的算法描述:,begin for 对每个非终结符p和终结符a do fp,a = false for 对每个形如pa或pqa的产生式 do insert(p,a) while stack 非空 begin 栈顶项出栈，记为(q,a) for 对每条形如pq的产生式 do insert(p,a) end; end.,procedure insert(p,a); if not fp,a then begin fp,a = true; (p,a)进栈 end;,对数组初始化,应用规则1,应用规则2,2. 求lastvt集 定义：lastvt(p)=a|p = .a或 p =.aq,a为终结符,p，q为非终结符,+,+,构造lastvt集算法 ： 自己练习,练习,lastvt(s) = a,) lastvt(t) = a,), , ,计算lastvt,给定文法gs：,s a | (t) t t,s | s,3.构造优先关系表的算法 如果每个非终结符的firstvt和lastvt集均已知,则可根据定义构造优先关系表。,构造思路： (1) 若产生式是形如：pab 或 paqb的形式，则有a b (2)若产生式右部是.ar.的形式,则对于每个bfirstvt(r)都有a b (3)若产生式右部有.rb的形式,则对于每个alastvt(r)集,都有a b,for 每个形如px1x2xn的产生式 do for i =1 to n-1 do begin if xi和xi+1都是终结符 then xi = xi+1 if i xi+1 ; end;,优先关系表构造算法,同一产生式中的相邻符号1,同一产生式中的相邻符号2,a出现在其它产生式中，通过计算得到,练习,firstvt(s) = a,( firstvt(t) = a,(, , lastvt(s) = a,) lastvt(t) = a,), , ,的firstvt和lastvt集,构造优先关系表。,给定文法gs：,s a | (t) t t,s | s,算符优先分析方法,原理： 通过比较相邻终结符间的优先关系来实现 实现机制： 仍然采用“移进-归约”方式，不断移进输入符号，识别可归约串，并进行归约。 分析方法： 根据优先性“低于”来识别句柄的头，根据优先性“高于”来识别句柄的尾。各种优先关系已经存于优先关系表中。,几个定义,1.算符优先分析过程，不是严格的规范归约，每次归约的符号串，不一定是规范归约中的“句柄”，不能识别只由一个非终结符组成的句柄，是当前句型的最左素短语。,2. 素短语：是一个短语，至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。 3. 最左素短语：是指位于句型最左边的那个素短语。,例：给定右边文法的一个句型： t * f + i 求其短语、素短语、最左素短语？,et | e+t tf | t*f fi | (e),短语有：i, t * f, t * f + i 素短语有： i, t * f 最左素短语是：t * f,练习:给定文法ge: 求句型t+t*f+i的短语、素短语、最左素短语。,根据语法树可知： 句型#t+t*f+i#的短语有： t 相对非终结符e的短语 t*f 相对非终结符t的短语 t+t*f 相对非终结符e的短语 i 相对非终结符p、f、t的短语 t+t*f+i 相对非终结符e的短语,根据素短语的定义可知： i和t*f为素短语。 其中：t+t*f (含t*f素短语)、 t+t*f+i (含t*f素短语) 和 t(不含终结符)也不是素短语 t*f为最左素短语。,ee+t|t tt*f|f f(e)|i,设算符文法g的句型的一般形式为 #n1a1 n2a2 nnan # (nivn,ai vt） 它的最左素短语是满足下列条件的最左子串： niai ni+1ai+1 njaj nj+1 其中：ai-1 ai , ai ai+1 aj-1 aj ， aj aj+1,该定理说明了最左素短语与周围符号之间的关系,定 理,符号栈内容 + 输入缓冲区内容 # 当前句型 #,#n1a1 n2a2 nnannn+1# (ai为终结符,ni为可有可无的 非终结符),句型的一般形式：,分析时句型表示：,3.算符优先分析,分析模型,过程： (1)从左向右扫描输入符号并移入堆栈,并查优先矩阵,直至找到满足aj aj+1时为止. (2)再从aj开始往左扫描堆栈,直至找到某个i,满足ai-1 ai为止 (3)niai ni+1ai+1 njaj nj+1形式的子串即为最左素短语，应被归约。,算符优先分析过程,开始： 分析栈中为：#，输入缓冲区为：输入串#,结束： 输入缓冲区为#，分析栈中为#s，分析成功 否则失败,表达式 i+i*i的算符优先过程,ee+t|t tt*f|f f(e)|i,例:给定文法ge：,top:=1;stop = #; repeat a := 下一个输入符号; if stop vt then j:=top else j:=top-1; while sj a do begin repeat q:=sj; if sj-1 vt then j:=j-1 else j:=j-2; until sj q; 把sj+1.sk归约为某个n，将n入栈； top:=j+1; end if sj a or sj = a then begin top:=top+1; stop:=a; end; else error; until a=#;,算法：p95,栈顶符号sj与即将输入的符号a进行比较,栈顶符号优先性低于或等于输入符号a，则移进a,向前查找最左素短语的头， j记录可归约串的头,进行归约,s表示堆栈，top记录栈顶位置，j记录栈顶符号位置,算符优先分析不是严格的规范归约 不对文法的非终结符定义优先关系，无法发现由单个非终结符组成的“可归约串”。即无法使用单非产生式(如：tf)进行归约。 算符优先分析比规范归约过程要快，跳过了所有的单非终结产生式。 可能将本来不是句子的输入串误认为是句子。,总结归约的策略: 在文法中寻找这样的产生式: 它的右部形如: niai ni+1ai+1 njaj nj+1,其中每个终结符号与最左素短语对应位置上的终结符号完全相同,而每一个非终结符号uk应与相应位置上的非终结符号nk相对应,不必完全相同。,算符优先分析法小结,优点 简单、效率高 能够处理部分二义性文法 缺点 文法书写限制大 占用内存空间大 不规范、存在查不到的语法错误,优先函数,一般不直接用优先关系表，构造优先函数,将每个终结符与两个自然数f()和g()对应，f()和g()的选择满足如下关系： 1 2 , f(1)g(2) 函数f为入栈优先函数，g为比较优先函数。,给定一个文法，如果存在优先函数，则一定存在多个，即f和g的选择不是唯一的。,从优先关系表构造优先函数的方法：,(1) 对应于每个终结符a(包含#)，令其对应两个符号fa和ga，然后画一张以所有这些符号为结点的方向图，如果a = b，就从fa画箭弧到gb ，如果a = b，就从gb画箭弧到fa ； (2) 对每个结点都赋予一个数，此数值等于从该结点出发(含该结点)，能够到达的所有不相同的结点的个数，即不记重复数； (3) 检查所构造的函数f和g，看是否同原来的优先关系表相矛盾。如果不矛盾，f和g就是所要求的优先函数；如果有矛盾，则不存在优先关系函数。(因