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

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,语法分析部分知识关系图,开发语法分析程序,语法定义,基于,上下文无关文法,使用,实现,自顶向下,自底向上,第五章 自底向上的语法分析,5.1 自底向上的语法分析方法概述,5.2 LR(0)分析的有限自动机,5.3 LR(0)分析,5.4 SLR(1)分析,5.5 LR(1)分析,5.6 LALR(1)分析,5.7 LALR(1)语法分析器的自动生成器(YACC),5.1 自底向上语法分析概述,自顶向下语法分析回顾,自底向上语法分析的例子,自底向上语法分析的主要思想,自底向上语法分析的关键问题,一些相关概念,自顶向下分析例,P:,(1)Z,aBeA,(2)A,Bc,(3)B,d,(4)B,bB,(5)B,a b e c,自顶向下分析过程是从,文法开始符,出发，为所给,输入串,构造,最左推导,的过程。,句型,输入,动作,Z,abec,推导(1),abec,a,B,eA,匹配(a),bec,B,eA,推导(4),bec,b,B,eA,匹配(b),ec,B,eA,推导(5),ec,e,A,匹配(e),c,A,推导(2),c,B,c,推导(5),匹配(c),c,c,成功,自底向上语法分析的例子,P:,Z,ABb,(2)A a,(3)A,b,(4)B,b,(5)B,c,(6)B,bB,a b c b,输入,符号栈,动作,abcb,移入,a,bcb,归约(2),A,bcb,移入,Ab,cb,移入,Ab,c,b,归约(5),Ab,B,b,归约(6),AB,b,移入,归约(1),ABb,Z,成功,自底向上分析过程是从所给,输入串,出发，对其进行,最左归约,的过程。,自底向上归约的过程也是自底向上构建语法树的过程,a b c b,B,B,Z,归约过程,Z,rm,A,B,b,rm,Ab,B,b,rm,A,bcb,rm,abcb,A,abcb,-Abcb,-AbBb,-ABb,-Z,自底向上分析中归约过,程的逆过程就是该句子,的最右推导;,5.1 自底向上语法分析方法概述,主要思想:,从输入串出发;,尽可能地找到,可归约子串,并将其归约成一个非终极符;,直到归约成文法的开始符或发现语法错误;,分析动作:移入(shift),归约(reduce),包含以下方法:,LR 类的方法;简单优先法;算符优先法,关键问题:,什么时候进行归约，按照哪条产生式进行归约;,一些相关概念,短语,一个句型形如,如果存在一个句型A,而且 A,+,则称为句型的,短语,;,例如句型AbBb，则bB,AbBb是它的短语，因为,存在句型ABb，A,B,b A,bB,b，=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,A,Bb,a,B,b,a,bB,b,最左简单短语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,由语法分析树识别短语、简单短语和句柄,E,E,+,T,T,T,*,F,F,（,E,）,E,+,T,i,语法分析树,的叶子节点构成,句型,:,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,ABd,Z,+,Acb 规范前缀为 A,Ac,Acb,规范前缀,:一个规范句型的一个前缀称为,规范前缀,如果该前缀后面的符号串不包含非终极符;,规范句型,规范前缀,或者终极符串,一些相关概念,Z,ABb 规范前缀为 AB,ABb,规范活前缀:AB(不包含简单短语),ABb(包含一个简单短语且在最后),规范活前缀,:满足如下条件之一的规范前缀称为规范活前缀:,该规范前缀不包含简单短语;,该规范前缀只包含一个简单短语,而且是在该规范前缀的最后(这个简单短语就是句柄);,Z,+,abcb 规范前缀为 a,ab,abc,abcb,规范活前缀:,a,(包含一个简单短语且在最后),abc是不是规范活前缀？,(不是，包含两个简单短语a和c),自底向上语法分析的例子,P:,Z,ABb,(2)A a,(3),A b,(4)B,b,(5)B,c,(6)B,bB,a b c b,输入,符号栈,动作,abcb,移入,a,bcb,归约(2),A,bcb,移入,Ab,cb,移入,Abc,b,归约(5),AbB,b,归约(6),AB,b,移入,归约(1),ABb,Z,成功,自底向上分析过程是从所给,输入串,出发，对其进行,最左归约,的过程。,规范活前缀,或者,终极符串,规范句型,一些相关概念,规范活前缀,决定,分析动作,移入,:,规范活前缀不包含简单短语;,移入型规范活前缀,归约,:,规范活前缀只包含一个简单短语,而且是在该规范活前缀的最后;,可归约规范活前缀：归约规范活前缀,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 分析机制,分析栈,输入,#,a,LR驱动程序:,-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),