编译原理课程设计之第五章 自下而上的语法分析

《编译原理课程设计之第五章 自下而上的语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程内容第一章概论第二章词法分析第三章上下文无关文法及分析第四章自上而下的语法分析第五章自下而上的语法分析第六章语义分析第七章运行时环境第八章代码生成1第5章自下而上的语法分析5.1自下而上的语法分析5.2LR分析概览5.3LR(0)项目的有穷自动机与LR(0)分析5.4SLR(1)分析5.5一般的LR(1)5.6LALR(1)分析5.7语法分析器自动生成工具—YACC作业25.1自下而上的语法分析自下而上语法分析方法：从输入符号串开始，自左至右逐步进行归约，直至归约到文法的开始符号。如果能为输入符号串构造一个最左规约，则其是一个合法的句

2、子，否则它是一个非法的符号串。从输入符号串开始，以它做为语法树的叶节点，自底向上地构造语法树。3例:文法G：S→cAdA→abA→a试采用自下而上的语法分析算法识别输入串cabd是否是该文法所定义的句子？4bdca自左至右规约的过程(最右推导的逆过程)：caAbdSAcabdcabdcAdcAdS5最右推导：在推导的任何一步αβ，其中α、β是句型，都是对α中的最右非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型复习最右推导6SraAcBeraAcderaAbcderabbcde建立输入串abbc

3、de的规范推导：规范归约是规范推导的逆过程：abbcdeaAbcdeaAcdeaAcBeS对于文法G[S]SaAcBeAbAAbBd7在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”；为了便于求解语法分析算法，我们对可归约串进行定义：自下而上语法分析：8刻画“可归约串”的相关定义文法G[S]句型αβδ的短语：若有S=>*αAδ=>+αβδ，α、β、δ(VNVT)*则称β是句型αβδ相对于非终结符A的短语;S=>*S=>+αβδαβδ是句型αβδ相对于非

4、终结符S的短语吗？结论：任何句型都是其自身相对于文法的开始符号的短语。9句型αβδ的直接短语：若有S=>*αAδαβδ，α、β、δ(VNVT)*则称β是句型αβδ相对于非终结符A的直接短语;文法G[S]句型αβδ的句柄：句型的最左直接短语称为该句型的句柄;10求句型i*i+i的短语、直接短语和句柄例5.1:已知文法G[E]：E→E+T

5、TT→T*F

6、FF→(E)

7、i短语：i1*i2+i3，i1，i2，i3。直接短语：i1，i2，i3。句柄：i1i1*i2，EE+TFi3T*TFi2Fi111自下而上的语法分析算法通常采用规范归约

8、，即规范推导的逆过程；规范规约的每一步是从当前的规范句型中将句柄归约为相应的非终结符；自下而上语法分析：12第5章自下而上的语法分析5.1自下而上的语法分析5.2LR分析概览5.3LR(0)项目的有穷自动机与LR(0)分析5.4SLR(1)分析5.5一般的LR(1)5.6LALR(1)分析5.7语法分析器自动生成工具—YACC作业135.2LR分析概览LR分析法是一种有效的自下而上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法，其中L是指自左(Left)向右词法分析输入单词串，R是指分析过程都是构造最右(R

9、ight)推导的逆过程(规范归约)，括号中的k是指在决定当前分析动作时向前右看的单词个数。14有以下原因使得LR分析法与其它语法分析方法相比，应用更广泛，具有更强的吸引力。(1)应用面广：能够通过LR分析程序识别所有采用上下文无关文法描述的程序设计语言的语法结构；(2)能有效实现：是最一般的无回溯的移进—归约方法；(3)容易查错：LR分析器能够及时发现语法错误和准确指出错误位置。15例5.2考虑以下文法：S→aSbS

10、cacbcacbc对应的规范规约：ccSS¢SbSaaSbcaSbSS思路构造规范规约的语法分析程序要解决的问

11、题？回忆LL（1）？16移进$acbc$1下表给出了使用该文法对串acbc的LR分析。分析栈输入动作步骤$acbc$移进2$acbc$用S→c归约3$aSbc$移进4$aSbc$移进5$aSbc$用S→c归约6$aSbS$用S→aSbS归约78$S$接受17LR分析算法的关键是：如何识别(符号栈)栈顶的符号组成的符号串是否形成句柄？即何时移进，何时规约？分析表指导，分析表如何构造？活前缀和可归前缀的定义求文法中的所有可归前缀：识别可归前缀和活前缀分析表的构造18活前缀和可归前缀的定义：若x,y,z是字母表上的符号串，且z=xy,则x是符

12、号串z的前缀(头)，y是符号串z的后缀(尾)，符号串的前缀是指从符号串的尾部删去若干(包括0个)个符号之后所余下的部分。19设有文法G[S],若S=>*A=>是文法G的一个规范推导,