《编译原理自下而上语法分析》由会员分享，可在线阅读，更多相关《编译原理自下而上语法分析（36页珍藏版）》请在金锄头文库上搜索。
1、 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 自下而上语法分析v掌握自底相上分析的基本思想，基本概念v掌握算符优先关系的判定，求FIRSTVT集,LASTVT集 ,构造算符优先关系表，能运用算符优先分析方法 进行表达式分析v掌握最左素短语、句柄的定义与判定v理解规范规约与算符优先归约的区别 vLR(0)和SLR文法的理解编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 自下而上的语法分析v实现思想从输入符号串开始，从左到右进行扫描，将输入 符号逐个移入一个栈中，边移入边分析，一旦栈顶符 号串形成某个产生式的右部时，就用该
2、产生式的左部 非终结符代替，称为归约。重复这一过程，直到归约 到栈中只剩下文法的开始符号时，则分析成功， 称为 “移进-归约”方法。从语法树的角度看：从语法树的树叶开始，逐步 向上归约构造分析树，直到形成根结。是推导的逆过 程。v核心寻找可归约串(这是关键)进行规约。用不同的方法寻找可归约串，就可获得不同的分析方法。编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院v最左推导(Left-most Derive)每次推导都替换当前句型的最左边的非终结符 。与最右归约对应v最右推导(Right-most Derive)每次推导都替换当前句型的最右边的非终结符 。与最
3、左归约(规范归约)对应，得规范句 型例：设有文法例：设有文法GSGS：(1) S (1) S aAcBeaAcBe(2) A (2) A b b (3) A (3) A AbAb(4) B (4) B d d使用最右推导：使用最右推导： 因为因为S= S= aAcBeaAcBe= = aAcdeaAcde= = aAbcdeaAbcde= = abbcdeabbcde， 所以所以 abbcdeabbcde是文法是文法GG的句子。的句子。编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院步骤动作(1)S aAcBe (2)A b (3)A Ab (4)B d最左归
4、约过程是最右推导的逆过程，最左归约过程是最右推导的逆过程， 对输入串对输入串abbcdeabbcde的的 归约过程如下：归约过程如下：该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。ab aAab A aAac A ad c A aB c A ae B c A aS1移 进 a2移 进 b3归 约 24移 进 b5归 约 36移 进 c7移 进 d8归 约 49移 进 e10归 约 1编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 语法分析树的生成演示a b b c d eAABSAbAAbBdSaAcBe(1)S aAcBe (2)
5、A b (3)A Ab (4)B d编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院v这种分析过程具有如下特点：从输入串的开始依次读入单词(移进栈中) 。一旦发现可归约串(某个产生式的右端)就立即 归约。归约就是将栈顶的一串符号用文法产生式的左 部代替，归约可能重复多次，然后继续移进。若最终能归约成文法的开始符号，则分析成功 。v关键是如何判断可归约串？编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院问题的提出：问题的提出： 在构造语法树的过程中，何时归约？在构造语法树的过程中，何时归约？当可归约串出现在栈顶时就进行归约。当可
6、归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？如何知道在栈顶符号串中已经形成可归约串？如何进行归约？如何进行归约？通过不同的自底向上的分析算法来解释，不同的算法通过不同的自底向上的分析算法来解释，不同的算法 对可归约串的定义是不同的，但分析过程都有一个共同的对可归约串的定义是不同的，但分析过程都有一个共同的 特点：边移进边归约。特点：边移进边归约。规范归约：使用句柄来定义可归约串。规范归约：使用句柄来定义可归约串。算符优先：使用最左素短语来定义可归约串算符优先：使用最左素短语来定义可归约串编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学
7、院 规范归约概念v有文法G，开始符号为S, 如果有S=xy,则xy是 文法G的句型，x,y是任意的符号串v如果有S=xAy, 且有A=,则是句型xy相对于 非终结符A的短语v如果有S=xAy, 且有A-,则是句型xy相对于A -的直接短语v位于一个句型最左边的直接短语称为句柄。*+*注注: : 每次归约的部分必须是称之为每次归约的部分必须是称之为句柄句柄的字符串的字符串( (最右推导最右推导) )。 关键的问题是关键的问题是如何识别句柄如何识别句柄编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院例子下面的例子说明作为短语的两个条件缺一不可。 例考虑表达式文法：
8、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|av 短语：句型(a),S) S =* (T,S) T =+ (a) 句型(T,S),S) S =* (T),S) T =+ T,S v句型(a,(T),(T,S)直接短语以及句柄： S =* (T,(
9、T),(T,S) T = a S =* (a,S,(T,S) S =(T) S =* (a,(T),(T) T =T,S编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院短语与语法树的关系v短语：语法树子树的叶子结点组成的符号 串。v直接短语：语法树简单子树（只有父子两 代）的叶子结点组成的符号串。v句柄：语法树最左边简单子树的叶子结点 组成的符号串。编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院短语与语法树关系的例子句型(a,(T),(T,S)的语法树：S()TTS,T,S(T)a(T)T,S编译原理编译原理 长春工业大学计
10、算机科学与工程学院长春工业大学计算机科学与工程学院 用句柄对句子abbcde进行归约v用句柄对句子进行归约的过程与用移进-归约过程是一 致的，使用归约的产生式及其顺序是一致的。句型 归约规则 abbcde(1)S aAcBe (2)A b (3)A Ab (4)B d(2) Ab(3)A AbaAbcde aAcde(4)B d(1)S aAcBeaAcBeS编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 规范归约的定义v假定是文法G的一个句子，如果序列：n, n-1, , 0 (=S)满足如下条件，则序列n, n-1, , 0是一个规范归约: (1) n
11、= 是给定的句子 (2) 0 =S 是文法的开始符号 (3) 对任何i, 0E+T|TE-E+T|T (2)(2)T-T*F|FT-T*F|F (3)(3)F-(E)|iF-(E)|i对输入串对输入串 i1+i2*i3 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) 接受所得的结果是：用产生式序列表示语法分析树所得的结果是：用产生式序列表示语法分析树(1) E-E+T | T (2) T-T*F | F (3) F-(E) | ii1 + i2 * i3FTEFTFTE编译原理编译原理
