编译原理自底向上的语法分析.ppt
语法分析部分知识关系图,开发语法分析程序,语法定义,基于,上下文无关文法,使用,实现,自顶向下,自底向上,第五章 自底向上的语法分析,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,aBeA,匹配(a),bec,BeA,推导(4),bec,bBeA,匹配(b),ec,BeA,推导(5),ec,eA,匹配(e),c,A,推导(2),c,Bc,推导(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,移入,Abc,b,归约(5),AbB,b,归约(6),AB,b,移入,归约(1),ABb,Z,成功,自底向上分析过程是从所给输入串出发，对其进行最左归约的过程。,自底向上归约的过程也是自底向上构建语法树的过程,a b c b,B,B,Z,归约过程,Z rm ABb rm AbBb rm Abcb rm abcb,A,abcb-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,bBZ 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*FE+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),
