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

语法分析部分知识关系图开发语法分析程序语法定义基于上下文无关文法使用实现自顶向下自底向上第五章自底向上的语法分析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自顶向下分析过程是从文法开始符出发，为所给输入串构造最左推导的过程。句型输入动作Zabec推导(1)abecaBeA匹配(a)becBeA推导(4)becbBeA匹配(b)ecBeA推导(5)eceA匹配(e)cA推导(2)cBc推导(5)匹配(c)cc成功自底向上语法分析的例子P:(1)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rmAbBbrmAbcbrmabcbAabcb---Abcb---AbBb---ABb---Z自底向上分析中归约过程的逆过程就是该句子的最右推导;5.1自底向上语法分析方法概述主要思想:–从输入串出发;–尽可能地找到可归约子串并将其归约成一个非终极符;–直到归约成文法的开始符或发现语法错误;分析动作:移入(shift),归约(reduce)包含以下方法:–LR类的方法;简单优先法;算符优先法关键问题:–什么时候进行归约，按照哪条产生式进行归约;一些相关概念短语–一个句型形如,如果存在一个句型A,而且A+,则称为句型的短语;–例如句型AbBb，则bB,AbBb是它的短语，因为存在句型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,bBZABbaBbabBb–最左简单短语a是句柄句柄的唯一性:–如果一个CFG无二义性,则它的任意一个句型都有唯一的句柄;短语、简单短语、句柄的例子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每棵子树的叶子节点构成短语：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规范前缀:一个规范句型的一个前缀称为规范前缀,如果该前缀后面的符号串不包含非终极符;规范句型规范前缀或者终极符串一些相关概念ZABb规范前缀为AB,ABb规范活前缀:AB(不包含简单短语),ABb(包含一个简单短语且在最后)规范活前缀:满足如下条件之一的规范前缀称为规范活前缀:–该规范前缀不包含简单短语;–该规范前缀只包含一个简单短语,而且是在该规范前缀的最后(这个简单短语就是句柄);Z+abcb规范前缀为a,ab,abc,abcb规范活前缀:a(包含一个简单短语且在最后)abc是不是规范活前缀？(不是，包含两个简单短语a和c)自底向上语法分析的例子P:(1)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成功自底向上分析过程是从所给输入串出发，对其进行最左归约的过程。规范活前缀或者终极符串规范句型一些相关概念规范活前缀决定分析动作–移入:规范活前缀不包含简单短语;移入型规范活前缀–归约:规范活前缀只包含一个简单短语,而且是在该规范活前缀的最后;可归约规范活前缀：归约规范活前缀ZABb规范前缀为AB,ABb规范活前缀:AB(不包含简单短语)---移入型规范活前缀ABb(包含一个简单短语)---归约规范活前缀自底向上分析知识关系图规范归约推导(*)最右推导句型(S*)短语(A+)简单短语(A)句柄(最左)规范推导规范句型(Srm*)特例特例规范前缀规范活前缀包含0或1个归约规范活前缀应用互逆最右包含1个自底向上分析5.1自底向上语法分析方法概述LR方法–主要思想L表示从左至右读入输入串;R表示构造一个最右推导的逆过程，即每次找到句柄(归约规范活前缀)来进行归约;归约直到得到开始符或报告语法错误;–关键问题:对于一个CFG,如何判定归约规范活前缀?构造一个判定归约规范活前缀的自动机--LR自动机由LR自动机构造LR分析表指导LR分析LR分析机制分析栈输入#………aLR驱动程序:-shift(移入):移入型规范活前缀-reduce(归约):可归约规范活前缀LR分析表规范活前缀5.1自底向上语法分析方法概述LR方法–不同的LR方法LR(0)SLR(1)LR(1)LALR(1)–不同的LR方法对CFG的要求不一样,能够分析的CFG多少也不一样,LR(0)SLR(1)LALR(1)LR(1)