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

自下而上语法分析,掌握自底相上分析的基本思想，基本概念 掌握算符优先关系的判定，求FIRSTVT集,LASTVT集,构造算符优先关系表，能运用算符优先分析方法进行表达式分析 掌握最左素短语、句柄的定义与判定 理解规范规约与算符优先归约的区别 LR(0)和SLR文法的理解,自下而上的语法分析,实现思想 从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功， 称为“移进-归约”方法。 从语法树的角度看：从语法树的树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。 核心 寻找可归约串(这是关键)进行规约。用不同的方法寻找可归约串，就可获得不同的分析方法。,最左推导(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,A a,b A a,A a,c A a,d c A a,B c A a,e B c 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,这种分析过程具有如下特点： 从输入串的开始依次读入单词(移进栈中) 。 一旦发现可归约串(某个产生式的右端)就立即归约。 归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。 若最终能归约成文法的开始符号，则分析成功。 关键是如何判断可归约串？,问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。,规范归约概念,有文法G，开始符号为S, 如果有S=xy,则xy是文法G的句型，x,y是任意的符号串 如果有S=xAy, 且有A=,则是句型xy相对于非终结符A的短语 如果有S=xAy, 且有A-,则是句型xy相对于A-的直接短语 位于一个句型最左边的直接短语称为句柄。,注: 每次归约的部分必须是称之为句柄的字符串(最右推导)。 关键的问题是如何识别句柄,例子,下面的例子说明作为短语的两个条件缺一不可。 例考虑表达式文法： 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),(T,S) T = a S =* (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 aAcBe,aAcBe,S,规范归约的定义,假定是文法G的一个句子，如果序列： n, n-1, , 0 (=S)满足如下条件，则序列 n, n-1, , 0是一个规范归约: (1) n = 是给定的句子 (2) 0 =S 是文法的开始符号 (3) 对任何i, 0in，i-1是从i经把句柄替换为相应文法产生式的左部符号而得到的。 规范归约是最右推导的逆过程，规范归约又称为最左归约。 最右推导又称规范推导，由规范推导所得到的句型称规范句型，规范推导的逆过程是规范归约。,使用修剪语法树的方法来进行归约：,分析器的四种动作,移进：将下一输入符号移入栈 归约：当栈顶出现句柄，用产生式左侧的非终结符替换栈顶的句柄 接受：分析成功，是归约的一种特殊情况 出错：栈顶的内容与输入符号相悖，进行出错处理,分析成功的条件：栈顶为文法符号，输入串为空。注意，该过程并未涉及如何在栈里找可归约串。实际上，不同的找可归约串的方法，构成了不同的分析算法。 “移进-归约”分析法用栈实现的特点： 可归约串必定位于栈顶，即可归约串之后就是剩余的输入串。 栈内符号串与剩余输入串正好构成一个句型。,例：有文法： E-E+T|T T-T*F|F F-(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+ 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 | T T-T*F | F F-(E) | i,i1 + i2 * i3,F,T,E,F,T,F,T,E,算符优先分析,算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。 将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定可归约串。 显然，在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在以下四种优先关系： (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,算符优先文法（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。,按照下面两条规则来构造FIRSTVT集： 若有产生式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和LASTVT集均已知,则可构造优先关系表。 若产生式右部有.aP.的形式,则对于每个bFIRSTVT(P)都有a b 若产生式右部有.Pb的形式,则对于每个aLASTVT(P)集,都有a b 若产生是形如：Aab 或 AaBb形式，则有a b 构造优先关系表的算法如下：,For 每条形如PX1X2Xn的产生式 do for i =1 to n-1 do if Xi和Xi+1都是终结符 then Xi = Xi+1 if i Xi+1 ,算符优先分析算法,通过比较终结符间的优先关系来实现 根据优先分析的原理，语法分析程序的任务是：不断移进输入符号，识别可归约串并进行归约。 分析的方法：根据优先性“高于”来识别可归约串的头，根据优先性“低于”来识别可归约串的尾。各种优先关系已经存于优先关系表中。,不能识别只由一个非终结符组成的句柄。不能保证每次对句柄进行归约,在算符优先分析过程中,每次归约的符号串,是当前句型的最左素短语。 素短语：至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。 最左素短语(leftmost prime phrase)：是指位于句型最左边的那个素短语。,例：下述文法的一个句型： T * F + i 其短语、素短语、最左素短语分别是？,ET | E+T TF | T*F Fi | (E),短语有：i, T * F, T * F + i 素短语有： i, T * F 最左素短语是：T * F,例:文法G E-E+T|T T-T*F|F F-(E)|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 Njaj 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 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 VT THEN j=j-1 ELSE j=j-2; WHILE (not sj q) /找到最左素短语的前一