《西北工业大学编译原理所有课件第五章自下而上的语法分析》由会员分享，可在线阅读，更多相关《西北工业大学编译原理所有课件第五章自下而上的语法分析（126页珍藏版）》请在金锄头文库上搜索。
1、machunyan,西北工业大学软件与微电子学院,1,课程内容 第一章 概论 第二章 词法分析 第三章上下文无关文法及分析(语法结构的描 述工具) 第四章自上而下的语法分析 第五章自下而上的语法分析 第六章语义分析 第七章运行时环境(与目标代码生成有关) 第八章代码生成(主要讲解中间代码的生成) 第九章 代码优化,machunyan,西北工业大学软件与微电子学院,2,第5章 自下而上的语法分析,5.1 自下而上的语法分析概览 5.2 LR分析概览 5.3 LR(0)项目的有穷自动机与LR(0)分析 5.4 SLR(1) 分析 5.5 一般的LR(1) 5.6 LALR(1)分析 5.7 语法分
2、析器自动生成工具YACC,作业,machunyan,西北工业大学软件与微电子学院,3,5.1 自下而上的语法分析概览,自下而上语法分析方法： 从输入单词序列开始，自左至右逐步进行归约，试图将其归约为文法的开始符号。 从输入单词序列开始，以单词做为语法树的叶节点，自底向上地构造语法分析的结果-语法树。,machunyan,西北工业大学软件与微电子学院,4,例:文法G： S cAd A ab A a 试采用自下而上的语法分析方法识别输入串cabd是否是该文法所定义的句子？,5.1 自下而上的语法分析概览(续),machunyan,西北工业大学软件与微电子学院,5,自左至右规约的过程：,5.1 自下
3、而上的语法分析概览(续),自左至右规约是规范推导的逆过程, 所以称之为规范规约。,machunyan,西北工业大学软件与微电子学院,6,建立输入串abbcde的规范推导：,规范归约是规范推导的逆过程：,S,对于文法GS:SaAcBe Ab AAb Bd,5.1 自下而上的语法分析概览(续),machunyan,西北工业大学软件与微电子学院,7,5.1 自下而上的语法分析概览(续),在自下而上语法分析工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号； 为了方便对自下而上的语法分析方法进行描述，本章将每次规约的子串称为句柄；,machunyan,西北工业大学软件与微电子学院,8,
4、句型的直接短语： 若有S =*A ， 、(VNVT)* 则称是句型相对于非终结符A 的直接短语;,文法GS,句型的句柄： 句型的最左直接短语（在规范推导中，最先被归约的子串），称为该句型的句柄;,理解句柄,machunyan,西北工业大学软件与微电子学院,9,求句型i*i+i 的直接短语和句柄,例5.1:已知文法GE：EE+T|T TT*F|F F(E)|i,直接短语： i1 ， i2 ， i3,句柄： i1,machunyan,西北工业大学软件与微电子学院,10,总结本节内容： 自下而上的语法分析算法通常采用规范归约，即规范推导的逆过程； 规范规约的每一步是从当前的规范句型中将句柄归约为相应
5、的非终结符；,5.1 自下而上的语法分析概览(续),machunyan,西北工业大学软件与微电子学院,11,第5章 自下而上的语法分析,5.1 自下而上的语法分析概览 5.2 LR分析概览 5.3 LR(0)项目的有穷自动机与LR(0)分析 5.4 SLR(1) 分析 5.5 一般的LR(1) 5.6 LALR(1)分析 5.7 语法分析器自动生成工具YACC,作业,machunyan,西北工业大学软件与微电子学院,12,5.2 LR 分析概览,LR分析法是一种有效的自下而上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法，其中 L是指自左(Left)向右分析输入
6、单词序列， R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)， 括号中的k是指在决定当前分析动作时向右看的单词个数。,machunyan,西北工业大学软件与微电子学院,13,5.2 LR 分析概览(续),有以下原因使得 LR分析法与其它语法分析方法相比，应用更广泛，具有更强的吸引力。 应用面广：能够通过LR分析程序识别所有采用上下文无关文法描述的程序设计语言的语法结构； 能有效实现：是无回溯的移进归约方法； 容易查错：LR分析器能够及时发现语法错误和准确指出错误位置。,machunyan,西北工业大学软件与微电子学院,14,例5.2 考虑以下文法：,abbcde对应的规范规约：
7、,构造规范规约的语法分析程序要解决的问题？,对于文法GS:SaAcBe Ab AAb Bd,aAbcde,machunyan,西北工业大学软件与微电子学院,15,移进,$,abbcde$,1,下表给出了使用该文法对串acbc的LR分析。,分析栈,输入,动作,步骤,machunyan,西北工业大学软件与微电子学院,16,分析栈,输入,动作,步骤,状态栈,machunyan,西北工业大学软件与微电子学院,17,为了描述何时移进，何时规约，现将分析栈中存储的符号串称之为活前缀； 符号串前缀的定义：符号串的前缀是指从符号串的尾部删去若干(包括0个)个符号之后所余下的部分。 若 x，y，z是字母表上的符
8、号串，且z=xy,则x是符号串z的前缀，y是符号串z的后缀。,5.2 LR 分析概览(续),machunyan,西北工业大学软件与微电子学院,18,当前规范句型()的句柄是什么？,活前缀和可归前缀： 设有文法GS，若S =* A = 是文法G的一个规范推导，(， (VT VN)+，VT*，AVN)， 的一个前缀称为文法G的一个活前缀 称为文法G的可归前缀。 包含句柄的活前缀是可归前缀？,5.2 LR 分析概览(续),machunyan,西北工业大学软件与微电子学院,19,在对文法句型规范归约的过程中，自左向右分析输入串的任何时刻，在符号栈中的符号串均为规范句型的活前缀。,如果符号栈的内容是当前
9、句型的可归前缀，那么栈顶已经形成当前句型的句柄，进行归约，否则继续移进。,machunyan,西北工业大学软件与微电子学院,20,规范句型,当前句柄,可归前缀,abbcde,b,ab,aAbcde,Ab,aAb,aAcde,d,aAcd,aAcBe,aAcBe,aAcBe,S,S,S,例，对于GS SaAcBe Ab AAb Bd 输入串:abbcde,machunyan,西北工业大学软件与微电子学院,21,LR分析算法的关键技术：,如何识别(符号栈)栈顶的符号组成的符号串是否是可归前缀，是可归前缀就规约，否则移进 分析表指导，分析表如何构造 求文法中的所有可归前缀 识别可归前缀和活前缀 分析
10、表的构造,1,2,3,machunyan,西北工业大学软件与微电子学院,22,1.求文法中的所有可归前缀,方法：对任一文法，若已知它有可归前缀xUy，UVN，且文法中有产生式Uu，则有xUy xuy,则xu也是文法的可归前缀。,例：对文法 (1) SaAcBe (2) Ab (3) AAb (4) Bd,例：对拓广文法 (0) SS (1) SaAcBe (2) Ab (3) AAb (4) Bd,machunyan,西北工业大学软件与微电子学院,23,S为当前句型S的句柄，故S为可归前缀。,因S为可归前缀，且有产生式SaAcBe，故 aAcBe是可归前缀,因aAcBe 为可归前缀，且有产生式
11、AAb，故aAb是可归前缀,因aAcBe 为可归前缀，且有产生式Ab，故ab是可归前缀,1.求文法中的所有可归前缀(续),machunyan,西北工业大学软件与微电子学院,24,因aAb 为可归前缀，且有产生式AAb，故aAb是可归前缀(重复),因aAb 为可归前缀，且有产生式Ab，故ab是可归前缀(重复),因aAcBe 为可归前缀，且有产生式Bd，故aAcd是可归前缀,1.求文法中的所有可归前缀(续),machunyan,西北工业大学软件与微电子学院,25,因aAcd 为可归前缀，且有产生式AAb，故aAb是可归前缀(重复),因aAcd 为可归前缀，且有产生式Ab，故ab是可归前缀(重复),
12、所以文法的可归前缀有：S , aAcBe , aAb , ab , aAcd,1.求文法中的所有可归前缀(续),machunyan,西北工业大学软件与微电子学院,26,2.识别可归前缀和活前缀,可以证明一个文法G的所有可归前缀是一个正规集，它可以由DFA加以识别。,每个终态都是可归前缀的识别态。,终结符和非终结符都看成是有限自动机的输入符号。,machunyan,西北工业大学软件与微电子学院,27,将以上有限自动机合并：,从初态到任一终态形成的符号串构成了文法的可归前缀,可以指导移进-规约动作?,machunyan,西北工业大学软件与微电子学院,28,识别上述文法所有可归前缀的DFA,输入串:
13、abbcde,machunyan,西北工业大学软件与微电子学院,29,2.识别可归前缀和活前缀(续),上述有限自动机就是识别该文法所有活前缀和可归前缀的有限自动机。 中间状态为活前缀识别态（移进）； 所有终态都是可归前缀的识别态，此时分析栈中形成句柄（规约）； 带星号（*）的状态为唯一的句子识别态，这次归约到开始符号；,machunyan,西北工业大学软件与微电子学院,30,3.分析表的构造,分析表由动作表和状态转换表组成： 动作表(Action)以一个二维数组表示，列代表识别活前缀的状态，行代表当前的输入符号，数组元素Actioni，a表示所执行的分析动作，即：当前识别活前缀的状态为i，而输
14、入符号为a时所执行的动作。,machunyan,西北工业大学软件与微电子学院,31,3.分析表的构造(续),machunyan,西北工业大学软件与微电子学院,32,共有4种动作： 移进：输入符号进符号栈； 归约：用相应的产生式进行归约； 接受：当文法符号归约到只剩下开始符号，且输入串结束时(当前输入为$)，分析成功； 报警：当状态栈顶为某一状态下，出现了不该出现的文法符号时，报错。,3.分析表的构造(续),machunyan,西北工业大学软件与微电子学院,33,分析表由动作表和状态转换表组成： 状态转换表用一个二维数组表示，列代表识别活前缀的状态，行代表文法符号，数组元素表示当前识别活前缀的状
15、态为i面对文法符号为X时，应转去的新状态Gotoi,X。,3.分析表的构造(续),machunyan,西北工业大学软件与微电子学院,34,3.分析表的构造(续),machunyan,西北工业大学软件与微电子学院,35,动作表和状态转换表的合并,machunyan,西北工业大学软件与微电子学院,36,LR分析算法的逻辑结构：,总控程序,a1a2aiai+1an$,输出,machunyan,西北工业大学软件与微电子学院,37,在总控程序的控制下，从左到右处理词法分析输入串，根据分析栈和输入符号的情况，查分析表确定分析动作； 分析栈包括文法符号栈Xi和相应的状态栈Si两部分(状态是指识别活前缀的自动机状态) 。 分析表是LR分析器的核心，它包括动作表(Action)和状态转换表(Goto)两部分; 根据识别文法所有活前缀和可归前缀的有限自动机，可以构造分析表来指导移进-规约动作；,5.2 LR 分析概览(续),machunyan,西北工业大学软件与微电子学院,38,第5章 自下而上的语法分析,5.1 自下而上的语法分析 5.2 LR分析概览 5.3 LR(0)项目的有穷自动机与LR(0)分析 5.4 SLR(1) 分析 5.5 一般的LR(1) 5.6 LALR(1)分析 5.7 语法分析器自动生成工具YACC,作业,1. 构造识别活前缀的NFA 2. 构造
