自下而上语法分析课件

1、1第五章 语法分析自下而上分析 5.1 自下而上分析基本问题5.2 算符优先分析5.3 LR分析法5.4 语法分析器的自动产生工具YACC（略）25.1 自下而上分析基本问题一、归约1.“移进规约”的思想： 用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。3举例：已知文法G为(1)SaAcBe (2)Ab (3)AAb (4)Bd 及输入串abbcde归约过程如下:eBcAa进9BcAa归8dcAa进7cAa进6bAa进4Aa归5Aa归3ba进2S归10a进1动作:步骤:5.1 自下而上分析基本

2、问题42.自下而上分析的关键:“可归约串”如何精确定义？“可归约串”的不同定义，形成了不同的自下而上的分析方法。从上例的步骤（）可发现5.1 自下而上分析基本问题“算符优先分析”中：“最左素短语”“可归约串”“规范归约分析”中：“句柄”“可归约串”例：5.自下而上分析的中心问题： 怎样判断栈顶的符号串的可归约性以及如何归约。5.1 自下而上分析基本问题各种自下而上分析法的共同特点： 边输入单词符号（移进符号栈），边归约。即：在从左到右移进输入串的过程中，一旦发现栈顶呈现可归约串就立即进行归约。6二.规范归约简述5.1 自下而上分析基本问题(1)短语:若且,则称是句型相对于 非终结符的短语。*

3、+(2)直接短语:若，则称是句型相对于规则 的直接短语。(3)句柄：一个句型的最左直接短语成为该句型的句柄。.定义：令是一个文法，是的开始符号， 假定是文法的一个句型， 即 *75.1 自下而上分析基本问题规范规约中的概念短语：直接短语：句柄：是句型的短语仅当 S A 且A S.A.A =最左直接短语8例1：EE+T | TTT*F | FF(E) | i i1*i2+i3短语：直接短语：句柄： i1，i2，i3，i1*i2，i1*i2+i3 i1，i2，i3i19练习：EE+T | TTT*F | FF(E) | i E+T*F+i 短语：直接短语：句柄： E+T*F+i, E+T*F, T

4、*F, i T*F, i T*FEETETTFFi+*10例2：利用句柄对句子进行归约5.1 自下而上分析基本问题句型归约规则aAbcdeaAcdeaAcBeS对文法(1)SaAcBe; (2)Ab; (3)AAb; (4)Bd 的句子abbcde进行归约。 abbcde(2)Ab(3)AAb(4)Bd(1)SaAcBe112.规范归约规范归约是关于的一个最右推导的逆过程.5.1 自下而上分析基本问题例: S aAcBe aAcde aAbcde abbcde (1) (2) (3) (4)(1)定义:设是文法G的一个句子,我们称序列n, n-1,0 是的一个规范归约,若此序列满足:n=;0=

5、S，S为文法开始符号;对任何i,0in, i-1是经把i的句柄替换为相应产生式的左部符号而得到的.12(2)规范推导:即最右推导.5.1 自下而上分析基本问题 规范句型:由规范推导所得到的句型,称为规范句型. 若文法G是无二义的,则规范推导(最右推导)的逆过程必是规范归约(最左归约)。(3)规范归约的实质:在移进过程中，当发现栈顶呈现句柄时， 就用相应产生式的左部符号进行替换。2.规范归约规范归约的中心问题：如何寻找或确定一个句型的句柄。给出了寻找句柄的不同算法就给出了不同的规范归约方法。13三、符号栈的使用1.与LL(1)方法区别：符号栈输入串开始#W#分析成功#S#符号栈输入串开始#SW#

6、分析成功#LL(1)分析:5.1 自下而上分析基本问题142.举例：规范归约（课本88页例5.3） 语法分析对符号栈的使用有四类操作：5.1 自下而上分析基本问题“移进”指把输入串的一个符号移进栈.“归约”指发现栈顶呈可规约串,并用适当的相应符号去 替换这个串.“接受”指宣布最终分析成功.“出错处理” 指发现栈顶的内容与输入串相悖,分析工 作无法正常进行,此时需调用出错处理程序.15例2：有文法：E-E+T|TT-T*F|FF-(E)|i对输入串 i1+i2*i3 的规范规约过程：16 动作 栈 输入缓冲区1) 准备 # i1+i2*i3#2) 移进 #i1 +i2*i3#3) 归约 Fi #

7、F +i2*i3#4) 归约 TF #T +i2*i3# 5) 归约 ET #E +i2*i3#6) 移进 #E+ i2*i3#7) 移进 #E+i2 *i3#8) 归约 Fi #E+F *i3#9) 归约 TF #E+T *i3# 10) 移进 #E+T* i3#11) 移进 #E+T*i3 #12) 归约 Fi #E+T*F #13) 归约 TT*F #E+T #14) 归约 EE+T #E # 15) 接受所得的结果是：用产生式序列表示语法分析树E-E+T|TT-T*F|FF-(E)|ii1 + i2 * i3FTEFTFTE175.2 算符优先分析算符优先分析： 不是一种规范归约法，是

8、一种自下而上的语法分析法，关键在于规定算符（即终结符）之间的优先顺序和结合性质，借助这种优先关系寻找“可归约串”进行归约。特点：有利于表达式分析，宜于手工实现。18一、算符优先文法及优先表构造1.算符优先文法算符文法:一个文法，如果它的任一产生式的右部都不含 两个相继（并列）的非终结符，即不含如下形 式的产生式右部：则我们称该文法为算符文法。5.2 算符优先分析19算符优先文法:如果一个算符文法G中的任何终结符对(a,b) 至多只满足下述三关系之一: a b，a b，a b 则称G是一个算符优先文法。 假定是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说： a b当且仅当 文法G

9、中含有形如 Pab或aQb的产生式；5.2 算符优先分析+ (2) a b当且仅当 G中含有形如 PaR 的产生式, 而Rb或R Qb;+ (3) a b当且仅当 G中含有形如 PRb的产生式, 而R a或R aQ 。+ + FIRSTVT(R)LASTVT(R)20按定义,我们用以下两条规则构造集合FIRSTVT(P):(1)若有产生式Pa或PQa, 则aFIRSTVT(P);(2)若aFIRSTVT(Q), 且有产生式PQ, 则aFIRSTVT(P)。返回 5.2 算符优先分析构造集合FIRSTVT(P):构造集合LASTVT(P):按定义,我们用以下两条规则构造集合LASTVT(P):(

10、1)若有产生式Pa或PaQ, 则aLASTVT(P);(2)若aLASTVT(Q), 且有产生式PQ, 则aLASTVT(P)。215.2 算符优先分析文法G：(1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|iFIRSTVT(E)=FIRSTVT(T)=FIRSTVT(F)=FIRSTVT(P)=+, *, , (,i (,i ,(,i *,(,i LASTVT(E)=LASTVT(T)=LASTVT(F)=LASTVT(P)= ),i +, *, , ),i ,),i *,),i 22（1）a b：找出满足“ ”的所有终结符对。(借助于FIRSTVT(P)和LAST

11、VT(P)实现)5.2 算符优先分析2.构造优先表（3）构造出优先表（2）ab，ab：找出满足“”和“”的所有终结符对。ab: 有形如aP的候选,且bFIRSTVT(P)；ab: 有形如Pb的候选,且aLASTVT(P)。23另:“”是作为语句的起始和结束标记,认为存在候选式： #开始符号#（1）#=#（2）#5.2 算符优先分析24例:优先关系和优先表考虑文法G：(1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|i5.2 算符优先分析FIRSTVT(E)=FIRSTVT(T)=FIRSTVT(F)=FIRSTVT(P)=+, *, , (,i (,i ,(,i *,(

12、,i LASTVT(E)=LASTVT(T)=LASTVT(F)=LASTVT(P)= ),i +, *, , ),i ,),i *,),i 25按定义,我们可得文法G终结符对的优先关系表,如下所示:+*i()#+*i()# (1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|i26返回按定义,我们可得文法G终结符对的优先关系表,如下所示:+*i()#+*i()#对于G的任何终结对(a,b),至多只有一种关系成立。 因此，G是一个算符优先文法。27二、算符优先分析算法1.最左素短语 素短语:是指这样的一个短语,它至少含有一个终结符,并且, 除它自身之外不再含任何更小的素短

13、语。 最左素短语：指处于句型最左边的那个素短语。5.2 算符优先分析28练习：EE+T | TTT*F | FF(E) | i 练习：(1)EE+T|T(2)TT*F|F(3)FPF|P(4)P(E)|i29一个算符优先文法G的任何句型的最左素短语是满足 如下条件的最左子串：NjajNiaiNi+15.2 算符优先分析aj-1 ajaj aj+1, ,ai-1 aiai ai+1句型的一般形式：#N1a1N2a2 aj-1 NjajNiaiNi+1ai+1 NnanNn+1#N1a1N2a2 aj-1 ai+1 NnanNn+1#302.算法 过程：读入一个输入符号a, 然后比较栈顶终结符a。

14、Si存放“文法符号”的分析栈始终指向VT符号始终指向栈顶存放“输入符号”的字符变量用于存放待比较的终结符号：j5.2 算符优先分析31K:=1; SK:=#; REPEAT 把下一个输入符号读进a中； IF SkVT THEN j:=k ELSE j:=k-1;WHILE Sja DO BEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把 Sj+1Sk归约为某个N； k:=j+1; Sk:=N END OF WHILE; IF Sj a OR Sja THEN BEGIN k:=k+1; Sk:=a END EL

15、SE ERROR;UNTIL a=#aj-1 aj aj+1,ai-1 ai ai+1Sj Q Sk=Q a32REPEATQ:=S j;IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2UNTIL Sj Q使得Q不断向左移,指向新终结符使得j指向VT左符号Sj与右符号Q之间还可能满足:Sj Q 不可能出现,若成立则前面已经归约过了;Sj Q 此时,符合“最左素短语” 定义,一直repeat;S j与Q无优先关系不可能出现, 若成立则前面已经报告“Error”5.2 算符优先分析335.2 算符优先分析+*i()#+*i()#步骤分析栈剩余输入串动作 1 # i+i*ii #

16、 2 #i +i*ii # 移进 #*R=RS A a B a=*R=RbFirst( a)b, a71(2)GO(I,X) = CLOSURE(J)AX, a IAX, a J72例：(0)SS(1)SBB (2)BaB(3)BbLR(1)项目集规范族：I0:SS, # S BB , B aB, B b,#a/ba/bI1:SS , #I2:S BB ,# B aB, B b,#I3: Ba B,a/b B aB, B b,a/ba/bI4: B b , a/bI5:S BB ,#I6: Ba B,# B aB, B b,#I7: B b , #I8: Ba B ,a/bI9: Ba B ,

17、#73状态ACTIONGOTOab#SB012345678974练习：若有文法GS:SS;M|MMMbD|DDD(S)|（1）证明GS是SLR文法，并构造它的分析表；（2）给出GS的LR(1)项目集规范族中的I0。75五、LALR分析表的构造同心集的合并：76同心集的合并 不会产生新的移进-归约冲突 但会产生新的归约-归约冲突A , aB , bA , bB , aA , a/bB , b/b77五、LALR分析表的构造1、SLRLR(1)LALR(1)之间的关系LALR(1)一种折衷的方法对于同一个文法,LALR分析表永远具有相同数目的状态5.3 L分析法782、同义集合并 (1)同心集:若

18、两个LR(1)项目集,除去搜索符外,这两 个集合相同,则称它们是同心集 (2)引出的问题 A.同心集合并不会产生“移进归约”冲突 证明:(反证)假设合并后才存在“移进归约”冲突,则:对当前输入符号a,项目A ,a要求归约 项目Ba ,b要求移进既然两项目处于合并后的一个集合中,则:合并前,必c、d,使得A ,a与Ba ,b 已同处于某一集合中。即合并前,已有LR(1)项目集 存在“移进归约”冲突故同心集合并不会产生“移进归约”冲突 B.同心集合并会产生“归约归约”冲突5.3 L分析法79例:考虑文法(0)SS(1)SaAd|bBd|aBe|bAe(2)Ac(3)Bc项目集:Ac ,d,Bc ,e Ac ,e,Bc ,d(合并)Ac ,d/e,Bc ,d/e问题:面临a=d/e时,采用哪一个归约?5.3 L分析法803、构造LALR(1)分析表的步骤:(1)文法拓广: