编译原理自下而上语法分析.ppt

《编译原理自下而上语法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理自下而上语法分析.ppt（36页珍藏版）》请在三一办公上搜索。

1、自下而上语法分析,掌握自底相上分析的基本思想，基本概念掌握算符优先关系的判定，求FIRSTVT集,LASTVT集,构造算符优先关系表，能运用算符优先分析方法进行表达式分析掌握最左素短语、句柄的定义与判定理解规范规约与算符优先归约的区别 LR(0)和SLR文法的理解,自下而上的语法分析,实现思想从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功，称为“移进-归约”方法。从语法树的角度看：从语法树的树叶开始，逐步向上归约构造分析树

2、，直到形成根结。是推导的逆过程。核心寻找可归约串(这是关键)进行规约。用不同的方法寻找可归约串，就可获得不同的分析方法。,最左推导(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)

3、B d,最左归约过程是最右推导的逆过程，对输入串abbcde的归约过程如下：,该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。,a,b a,A a,b A a,A a,c A a,dc A a,Bc A a,eBc A a,S,语法分析树的生成演示,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,这种分析过程具有如下特点：从输入串的开始依次读入单词(移进栈中)。一旦发现可归约串(某个产生式的右端)就立即归约。归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进

4、。若最终能归约成文法的开始符号，则分析成功。关键是如何判断可归约串？,问题的提出：在构造语法树的过程中，何时归约？当可归约串出现在栈顶时就进行归约。如何知道在栈顶符号串中已经形成可归约串？如何进行归约？通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。,规范归约概念,有文法G，开始符号为S,如果有S=xy,则xy是文法G的句型，x,y是任意的符号串如果有S=xAy,且有A=,则是句型xy相对于非终结符A的短语如果有S=xAy,且有A-,则是句型xy相对于A-的直接短语位于一个句型最左边的直接短语称为句柄。,注:每次归约的部分必须

5、是称之为句柄的字符串(最右推导)。关键的问题是如何识别句柄,例子,下面的例子说明作为短语的两个条件缺一不可。例考虑表达式文法：E T|E+T T F|T*F F i|(E)对于句型i*i+i 推导E E+T E+F E+i T+i T*F+T T*i+i F*i+i i*i+i尽管有E+i+i 但是,i+i 并不是该句型的一个短语，因为不存在从E(文法开始符）到i*E的推导。,句型的短语和句柄举例,文法：S(T)|TS|T,S|a 短语：句型(a),S)S=*(T,S)T=+(a)句型(T,S),S)S=*(T),S)T=+T,S 句型(a,(T),(T,S)直接短语以及句柄：S=*(T,(T

6、),(T,S)T=aS=*(a,S,(T,S)S=(T)S=*(a,(T),(T)T=T,S,短语与语法树的关系,短语：语法树子树的叶子结点组成的符号串。直接短语：语法树简单子树（只有父子两代）的叶子结点组成的符号串。句柄：语法树最左边简单子树的叶子结点组成的符号串。,短语与语法树关系的例子,句型(a,(T),(T,S)的语法树：,用句柄对句子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 aA

7、cBe,aAcBe,S,规范归约的定义,假定是文法G的一个句子，如果序列：n,n-1,0(=S)满足如下条件，则序列 n,n-1,0是一个规范归约:(1)n=是给定的句子(2)0=S 是文法的开始符号(3)对任何i,0in，i-1是从i经把句柄替换为相应文法产生式的左部符号而得到的。规范归约是最右推导的逆过程，规范归约又称为最左归约。最右推导又称规范推导，由规范推导所得到的句型称规范句型，规范推导的逆过程是规范归约。,使用修剪语法树的方法来进行归约：,分析器的四种动作,移进：将下一输入符号移入栈归约：当栈顶出现句柄，用产生式左侧的非终结符替换栈顶的句柄接受：分析成功，是归约的一种特殊情况出错：

8、栈顶的内容与输入符号相悖，进行出错处理,分析成功的条件：栈顶为文法符号，输入串为空。注意，该过程并未涉及如何在栈里找可归约串。实际上，不同的找可归约串的方法，构成了不同的分析算法。“移进-归约”分析法用栈实现的特点：可归约串必定位于栈顶，即可归约串之后就是剩余的输入串。栈内符号串与剩余输入串正好构成一个句型。,例：有文法：E-E+T|TT-T*F|FF-(E)|i对输入串 i1+i2*i3 的规范归约过程：,动作 栈 输入缓冲区1)准备#i1+i2*i3#2)移进#i1+i2*i3#3)归约 Fi#F+i2*i3#4)归约 TF#T+i2*i3#5)归约 ET#E+i2*i3#6)移进#E+i

9、2*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)|i,i1+i2*i3,F,T,E,F,T,F,T,E,算符优先分析,算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定可归约串。显然，在一个符号串中，任意两个相邻终结符号a和b之间

10、，只可能存在以下四种优先关系：(1)a,b优先性相同，记作a b。(2)a优先性高于b，记作a b。(3)a优先性低于b，记作a b。(4)a与b不可能相邻，即此符号串不是句型(出错)。如果以上四种关系中的任意两种都不会同时成立，则可以根据终结符号之间的归约关系进行语法分析。,算符文法:一个上下无关文法G,如果没有P-,且没有P-.QR.(P,Q,R属于非终结符),则G是一个算符文法。算符优先关系的定义：a b,G中有P-.ab.或P-.aQb.(在同一产生式中)a b,G中有P-.aR.的产生式,且R=b.或R=Qb.a b,G中有P-.Rb.的产生式,且R=.a或R=.aQ,算符优先文法（

11、OPG）的定义,+,+,+,+,例：EE+E|E*E|(E)|i 证明不是OPG文法。因为：EE+E，EE*E 则有+*又因为：EE*E,EE+E 则有+*所以不是算符优先文法。,算符优先文法算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有,中的一种成立,则G为一算符优先文法。,算符优先关系表的构造,FIRSTVT集定义：对每个非终结符P,FIRSTVT(P)=a|P=a.或P=Qa.,a为终结符,P，Q为非终结符,由优先性低于的定义和FIRSTVT集合的定义可以得出：若存在某个产生式：aP，对所有：bFIRSTVT(P)，都有：a b。,按照下面两条规则来构造FIRST

12、VT集：若有产生式P-a.或P-Qa.,则aFIRSTVT(P)若有产生式P-R.,则FIRSTVT(R)包含在FIRSTVT(P)中,LASTVT集 定义：对每个非终结符P,LASTVT(P)=a|P=.a或P=.aQ,a为终结符,P，Q为非终结符,+,+,由优先性高于的定义和LASTVT集合的定义可以得出：若存在某个产生式：Pb，对所有：aLASTVT(P)，都有：a b。,按照下面两条规则来构造LASTVT集：若有产生式P-.a或P-.aQ,则aLASTVT(P)若有产生式P-.R,则LASTVT(R)包含在LASTVT(P)中,构造优先关系表如果每个非终结符的FIRSTVT和LASTV

13、T集均已知,则可构造优先关系表。若产生式右部有.aP.的形式,则对于每个bFIRSTVT(P)都有a b若产生式右部有.Pb的形式,则对于每个aLASTVT(P)集,都有a b 若产生是形如：Aab 或 AaBb形式，则有a b构造优先关系表的算法如下：,For 每条形如PX1X2Xn的产生式 dofor i=1 to n-1 do if Xi和Xi+1都是终结符 then Xi=Xi+1 if i Xi+1,算符优先分析算法,通过比较终结符间的优先关系来实现根据优先分析的原理，语法分析程序的任务是：不断移进输入符号，识别可归约串并进行归约。分析的方法：根据优先性“高于”来识别可归约串的头，根

14、据优先性“低于”来识别可归约串的尾。各种优先关系已经存于优先关系表中。,不能识别只由一个非终结符组成的句柄。不能保证每次对句柄进行归约,在算符优先分析过程中,每次归约的符号串,是当前句型的最左素短语。素短语：至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。最左素短语(leftmost prime phrase)：是指位于句型最左边的那个素短语。,例：下述文法的一个句型：T*F+i 其短语、素短语、最左素短语分别是？,ET|E+TTF|T*FFi|(E),短语有：i,T*F,T*F+i素短语有：i,T*F最左素短语是：T*F,例:文法G E-E+T|T T-T*F|F F-(E)|

15、i句型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为最左素短语。,一个算符文法G的某个句型的最左素短语可描述：设句型的一般形式为(NiVN,ai VT#N1a1 N2a2 Nnan Nn+1#它的最左素短语是满足下列条件的最左子串：Niai Ni+1ai+1 Nj

16、aj Nj+1其中：ai-1ai,aiai+1.aj-1aj，ajaj+1,该定理说明了最左素短语与周围符号之间的关系,算符优先分析过程：(根据最左素短语的定义)句型的一般形式:#N1a1N2a2.NnanNn+1#(ai为终结符,Ni为可有可无的非终结符)从左向右扫描各符号,依次查看算符优先矩阵,直至找到满足ai ai+1的终结符为止,一直移进，再从ai开始往左扫描,直至找到满足关系aj-1 aj的终结符为止,进行归约。此时,形如:Nj aj Nj+1 aj+1.Ni ai Ni+1的子串即为最左素短语，应被归约。分析过程的结束：分析栈中为#S，输入串为#,例:E-E+T|T T-T*F|F

17、F-(E)|i把#入栈,读一符号i,因为#+,所以归约:F-i因#*,所以归约:F-i因+#,所以归约:F-i因*#,所以归约:T-F*F因+#,所以归约:E-T+F分析成功,求i+i*i的算符优先分析过程,栈 输入缓冲区#i+i*i#i+i*i#F+i*i#F+i*i#F+i*i#F+F*i#F+F*i#F+F*i#F+F*F#F+T#E#,k=1;sk=#;a=下一个输入符号;WHILE(a#)DO IF sk VT THEN j=k ELSE j=k-1;/sj为栈顶终结符 WHILE sj a DO/当栈顶终结符优先级高于输入符号时/寻找最左素短语进行归约DO q=sj;if sj-1

18、 VT THEN j=j-1 ELSE j=j-2;WHILE(not sj q)/找到最左素短语的前一个终结符把sj+1.sk归约为某个N；k=j+1;sk=N;IF sj a or sj=a THEN k=k+1;sk=a;a=下一个输入符号;ELSE error;,算符优先分析一般并不等价于规范归约并不对文法的非终结符定义优先关系，无法发现由单个非终结符组成的“可归约串”。即无法使用单非产生式(如：TF)进行归约。算符优先分析比规范归约过程要快，跳过了所有的单非产生式。可能将本来不是句子的输入串误认为是句子。,算符优先分析法小结,优点简单、效率高能够处理部分二义性文法缺点文法书写限制大占用内存空间大不规范、存在查不到的语法错误,