西北工业大学编译原理第五章 自下而上的语法分析ppt课件.ppt

《西北工业大学编译原理第五章 自下而上的语法分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、machunyan西北工业大学软件与微电子学院1课程内容第一章概论第二章词法分析第三章上下文无关文法及分析(语法结构的描述工具)第四章自上而下的语法分析第五章自下而上的语法分析第六章语义分析第七章运行时环境(与目标代码生成有关)第八章代码生成(主要讲解中间代码的生成)第九章代码优化machunyan西北工业大学软件与微电子学院2第5章自下而上的语法分析5.1自下而上的语法分析概览5.2LR分析概览5.3LR(0)项目的有穷自动机与LR(0)分析5.4SLR(1)分析5.5一般的LR(1)5.6L

2、ALR(1)分析5.7语法分析器自动生成工具—YACC作业machunyan西北工业大学软件与微电子学院35.1自下而上的语法分析概览自下而上语法分析方法：从输入单词序列开始，自左至右逐步进行归约，试图将其归约为文法的开始符号。从输入单词序列开始，以单词做为语法树的叶节点，自底向上地构造语法分析的结果----语法树。machunyan西北工业大学软件与微电子学院4例:文法G：S→cAdA→abA→a试采用自下而上的语法分析方法识别输入串cabd是否是该文法所定义的句子？5.1自下而上的语法分

3、析概览(续)machunyan西北工业大学软件与微电子学院5bdca自左至右规约的过程：caAbdSAcabdcabdcAdcAdS5.1自下而上的语法分析概览(续)自左至右规约是规范推导的逆过程,所以称之为规范规约。machunyan西北工业大学软件与微电子学院6SraAcBeraAcderaAbcderabbcde建立输入串abbcde的规范推导：规范归约是规范推导的逆过程：abbcdeaAbcdeaAcdeaAcBeS对于文法G[S]:SaAcBeAbA

4、AbBd5.1自下而上的语法分析概览(续)machunyan西北工业大学软件与微电子学院75.1自下而上的语法分析概览(续)在自下而上语法分析工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号；为了方便对自下而上的语法分析方法进行描述，本章将每次规约的子串称为句柄；machunyan西北工业大学软件与微电子学院8句型αβδ的直接短语：若有S=>*αAδαβδ，α、β、δ(VNVT)*则称β是句型αβδ相对于非终结符A的直接短语;文法G[S]句型αβδ的句柄：句型的最左直

5、接短语（在规范推导中，最先被归约的子串），称为该句型的句柄;理解句柄machunyan西北工业大学软件与微电子学院9求句型i*i+i的直接短语和句柄例5.1:已知文法G[E]：E→E+T

6、TT→T*F

7、FF→(E)

8、i直接短语：i1，i2，i3句柄：i1EE+TFi3T*TFi2Fi1machunyan西北工业大学软件与微电子学院10总结本节内容：自下而上的语法分析算法通常采用规范归约，即规范推导的逆过程；规范规约的每一步是从当前的规范句型中将句柄归约为相应的非终结符；5.1自下而上的语法分

9、析概览(续)machunyan西北工业大学软件与微电子学院11第5章自下而上的语法分析5.1自下而上的语法分析概览5.2LR分析概览5.3LR(0)项目的有穷自动机与LR(0)分析5.4SLR(1)分析5.5一般的LR(1)5.6LALR(1)分析5.7语法分析器自动生成工具—YACC作业machunyan西北工业大学软件与微电子学院125.2LR分析概览LR分析法是一种有效的自下而上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法，其中L是指自左(Left)向右分

10、析输入单词序列，R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)，括号中的k是指在决定当前分析动作时向右看的单词个数。machunyan西北工业大学软件与微电子学院135.2LR分析概览(续)有以下原因使得LR分析法与其它语法分析方法相比，应用更广泛，具有更强的吸引力。应用面广：能够通过LR分析程序识别所有采用上下文无关文法描述的程序设计语言的语法结构；能有效实现：是无回溯的移进—归约方法；容易查错：LR分析器能够及时发现语法错误和准确指出错误位置。machunyan西北工业大学

11、软件与微电子学院14例5.2考虑以下文法：abbcde对应的规范规约：构造规范规约的语法分析程序要解决的问题？对于文法G[S]:SaAcBeAbAAbBdabbcdeaAbcdeaAcdeaAcBeSmachunyan西北工业大学软件与微电子学院15移进$abbcde$1下表给出了使用该文法对串acbc的LR分析。分析栈输入动作步骤$abbcde$移进2$abbcde$用A→b归约3$aAbcde$移进4$aAbcde$用A→Ab归约5$aAcde$移进6$aAcde$移