编译原理5.1-自下而上分析基本问题.ppt

1、第五章 语法分析,自下而上分析 Bottom-up Parsing,自下而上语法分析 优先分析法 简单优先分析法* 算符优先分析法 LR分析法 YACC,第五章 语法分析,5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析 5.4 YACC,5.1 自下而上分析基本问题,5.1.1 归约 5.1.2 规范归约简述 5.1.3 符号栈的使用和语法树的表示,1. 自下而上分析过程 2. 自下而上分析面临的问题,1. 自下而上分析过程 - 补充例,GS: ScAd Aab Aa,识别输入串 cabd 是否该文法的句子,S,c,A,d,a,b,自下而上分析过程中的每一步，都是从当前串

2、中选择一个子串，将它归约到某个非终结符号,该子串称为“可归约串”,GS: ScAd Aab Aa,2. 自下而上分析面临的问题,当串中的某部分和某个产生式右部匹配时,该不该归约? 如何确定可归约串?,a不是可归约串 ,ab是可归约串,可归约串,最左素短语,句柄,算符优先分析,规范规约,如何精确定义 “可归约串” ?,本章核心,1. 采用哪一种自下而上分析方法? 2. 如何定义可归约串? 3. 如果在当前符号串中确定可归约串?,5.1.1 归约,G:(1) SaAcBe (2) Ab (3) AAb (4) Bd 识别输入串abbcde# 是否该文法的句子,a,b,b,c,d,e,例: p83,

3、a,b,b,c,d,e,G:(1) SaAcBe (2) Ab (3) AAb (4) Bd 输入串abbcde#,可行的实现方案: 边扫描, 边归约,最左归约 (规范归约),复习最左推导、最右推导、最左归约、最右归约、规范推导、规范归约的概念,a,G: (1) SaAcBe (2) Ab (3) AAb (4) Bd 输入串abbcde#,b,a,A,b,c,何时移进,何时归约?归约谁?,如何确定 可归约串?,a,a,A,a,A,a,A,c,a,A,d,c,a,A,B,c,a,A,B,e,S,动作,移进,移进,归约,移进,归约,移进,归约,归约,移进,移进,a,b,(2),b,(3),c,d

4、,(4),e,(1),图5.1 符号栈的变迁,移进-归约分析,用栈实现规范归约,栈顶出现可归约串即可归约,5.1.2 规范归约简述,1. 短语、直接短语、句柄 的定义 2. 从句型的语法树上找出句型的短语、直接短语、句柄 3. 规范归约与句柄的关系,精确定义规范归约过程中的可归约串,短语（Phrase）,S A, 且A , 则称是 句型 相对于 非终结符A 的短语,直接短语 (简单短语, Simple phrase),S A, 且A , 则称是 句型 相对于 规则A 的直接短语,句柄 (Handle),一个句型的 最左直接短语 称为该句型的句柄.,1. 定义,找出句型 i1*i2+i3 的所有

5、 短语, 直接短语, 句柄 .,G:ET | E+T TF | T*F F(E) | i,短语: i1, i2, i3, i1*i2, i1*i2+i3 直接短语: i1, i2, i3, 句柄: i1,一棵子树的所有末端结点自左至右排列起来就形成一个相对子树根的短语.,2. 从语法树中,p85 例5.1,p85 例5.2 找出句型 E+T*F+i 的所有短语, 直接短语, 句柄,G:ET | E+T TF | T*F F(E) | i,短语: E+T*F+i E+T*F, i , T*F 直接短语: T*F, i 句柄: T*F,G:(1) SaAcBe (2) Ab (3) AAb (4)

6、 Bd,a,b,b,c,d,e,A,A,B,S,例: p83,a,b,a,A,b,c,a,a,A,a,A,a,A,c,a,A,d,c,a,A,B,c,a,A,B,e,S,移进,移进,归约,移进,归约,移进,归约,归约,移进,移进,a,b,(2),b,(3),c,d,(4),e,(1),图5.1 符号栈的变迁,规范归约过程中的可归约串是句柄,3. 规范归约与句柄的关系,规范归约精确定义 P86,假定是文法G的一个句子, 如果序列: n, n-1, , 0 满足如下条件, 则 n, n-1, , 0 是一个规范归约: (1) n = 是给定的句子 (2) 0 = S 是文法的开始符号 (3) 对任何i, 0i n，i-1是从i 经过把 句柄 替换为相应文法产生式的左部符号 而得到的。,结论,规范归约过程中的可归约串是句柄 规范归约的实质: 在移进的过程中, 当发现栈顶呈现句柄就用相应的产生式的左部符号进行替换. 规范归约的中心问题: 如何寻找或确定一个句型的句柄?,5.1.3 符号栈的使用和语法树的表示,移进-归约分析,用栈实现规范归约,GS:ScAd Aab Aa,S,c,A,d,a,b,分析过程详见黑板,移