编译原理自底向上的语法分析

《编译原理自底向上的语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、语法分析部分知识关系图开发语法分析程序语法定义基于上下文无关文法使用实现自顶向下自底向上第五章自底向上的语法分析5.1自底向上的语法分析方法概述5.2LR(0)分析的有限自动机5.3LR(0)分析5.4SLR(1)分析5.5LR(1)分析5.6LALR(1)分析5.7LALR(1)语法分析器的自动生成器(YACC)5.1自底向上语法分析概述自顶向下语法分析回顾自底向上语法分析的例子自底向上语法分析的主要思想自底向上语法分析的关键问题一些相关概念自顶向下分析例P:(1)ZaBeA(2)ABc(3)Bd(4)BbB(5)Babec自顶向下分析过程是从文法开始符出发，为所给输入串构造最

2、左推导的过程。句型输入动作Zabec推导(1)abecaBeA匹配(a)becBeA推导(4)becbBeA匹配(b)ecBeA推导(5)eceA匹配(e)cA推导(2)cBc推导(5)匹配(c)cc成功自底向上语法分析的例子P:ZABb(2)Aa(3)Ab(4)Bb(5)Bc(6)BbBabcb输入符号栈动作abcb移入abcb归约(2)Abcb移入Abcb移入Abcb归约(5)AbBb归约(6)ABb移入归约(1)ABbZ成功自底向上分析过程是从所给输入串出发，对其进行最左归约的过程。自底向上归约的过程也是自底向上构建语法树的过程abcbBBZ归约过程ZrmABbrmAb

3、BbrmAbcbrmabcbAabcb--->Abcb--->AbBb--->ABb--->Z自底向上分析中归约过程的逆过程就是该句子的最右推导;5.1自底向上语法分析方法概述主要思想:从输入串出发;尽可能地找到可归约子串并将其归约成一个非终极符;直到归约成文法的开始符或发现语法错误;分析动作:移入(shift),归约(reduce)包含以下方法:LR类的方法;简单优先法;算符优先法关键问题:什么时候进行归约，按照哪条产生式进行归约;一些相关概念短语一个句型形如,如果存在一个句型A,而且A+,则称为句型的短语;例如句型AbBb，则bB,AbBb是它的短语，因为存在句

4、型ABb，ABbAbBb，=A，=b；存在句型Z，ZABbAbBb，=，=；简单短语一个句型形如,如果存在一个句型A,而且A,则称为句型的简单短语;例如句型AbBb，bB是它的简单短语，AbBb不是它的简单短语(1)ZABb(2)Aa(3)Ab(4)Bd(5)Bc(6)BbB一些相关概念句柄:一个句型的简单短语可能有多个，称最左简单短语为句柄(handler);例如：句型abBb，简单短语有两个：a,bBZABbaBbabBb最左简单短语a是句柄句柄的唯一性:如果一个CFG无二义性,则它的任意一个句型都有唯一的句柄;短语、简单短语、句

5、柄的例子P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn句型:T+(E+T)*i简单短语:T,E+T,i句柄:T通过为所给句型建立语法分析树，可以很容易地识别出该句型的所有短语、简单短语和句柄。句型的一个推导:(该句型没有最右推导)EE+TE+T*FE+T*iE+F*iE+(E)*iE+(E+T)*iT+(E+T)*i短语:T+(E+T)*i,T,E+T,i,(E+T),(E+T)*i由语法分析树识别短语、简单短语和句柄EE+TTT*FF（E）E+Ti语法分析树的叶子节点构成句型:T+(E+T)*i每棵子树的叶子节点构成短语：

6、T+(E+T)*i、T、(E+T)*i、(E+T)、E+T、i每棵简单子树(只有一层的子树)的叶子节点构成简单短语：T、E+T、i最左简单子树的叶子节点构成句柄：T一些相关概念自顶向下的语法分析方法中曾介绍过：推导：对句型中的非终极符用产生式右部替换规范推导：一个句型的最右推导称为该句型的规范推导;规范句型(右句型)：从开始符通过规范推导得到的句型;推导的逆过程称为归约规范推导的逆过程称为规范归约(最左归约)规范归约过程中产生的句型仍是规范句型规范归约的过程也是对规范句型的最左简单短语(句柄)进行归约的过程一些相关概念ZABb规范前缀为AB,ABdZ+Acb规范前缀为A,Ac,Acb规范

7、前缀:一个规范句型的一个前缀称为规范前缀,如果该前缀后面的符号串不包含非终极符;规范句型规范前缀或者终极符串一些相关概念ZABb规范前缀为AB,ABb规范活前缀:AB(不包含简单短语),ABb(包含一个简单短语且在最后)规范活前缀:满足如下条件之一的规范前缀称为规范活前缀:该规范前缀不包含简单短语;该规范前缀只包含一个简单短语,而且是在该规范前缀的最后(这个简单短语就是句柄);Z+abcb规范前缀为a,