编译原理第六章自底向上优先分析法课件.ppt

第六章 自底向上优先分析法 自底向上优先分析法慨述 简单优先分析 算符优先分析 6.1 自底向上语法分析概述 如名字如示，自底向上语法分析试图将一个字符串反向归约至开始符号。 自底向上语法分析比自上而下语法分析更有效率，对语法的限制更少 自底向上语法分析的策略：移进-规约分析； 移进就是将一个终结符推进栈 归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈 移进-归约过程是自顶向下最右推导的逆过程（规范归约） 例6.1设文法G[s]为: (1)S ? aAcBe (2)A? b (3)A? Ab (4)B? d对输入串abbcde进行分析，检查该符号串是否是G[s]的句子。分析：容易看出对输入串abbcde的最右推导是： S＝aAcBe＝aAcde＝aAbcde＝abbcde由此我们可以构造它的逆过程即归约过程。 自底向上分析的关键问题: 如何确定句柄。 自底向上优先分析法慨述 简单优先分析 算符优先分析 6.2 简单优先分析法 按照文法符号（包括终结符和非终结符）的优先关系确定句柄。 6.2.1 优先关系 优先关系 X=Y ? 文法G中存在产生式A→...XY... XY? 文法G中存在产生式A→...XB...，且B Y... XY? 文法G中存在产生式A→...BD...，且B ...X,D Y... 如何确定两个文法符号之间的优先关系？ (按定义求优先关系，P96) 6.2.2 简单优先文法的定义 满足以下条件的文法是简单优先文法 （1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。 （2）在文法中任意两个产生式没有相同的右部 6.2.3 简单优先分析法 算法步骤如下： 自底向上优先分析法慨述 简单优先分析 算符优先分析 6.3 算符优先分析法 某些文法具有“算符”特性 表达式运算符（优先级、结合性） 人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性 只考虑算符之间的优先关系来确定句柄 6.3.1 直观算符优先分析法 （1） ?优先级最高，右结合 （2）*和/优先级次之，左结合 （3）+和-优先级最低，左结合 （4）括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号 （5）#的优先性低于与其相邻的算符 6.3.2 算符优先文法的定义 定义 设有一文法G，如果G中没有形如A ? …BC…的产生式，其中B和C为非终结符，则称G为算符文法(Operator Grammar)也称0G文法. 性质1：在算符文法中任何句型都不包含两个相邻的非终结符.(数学归纳法) 性质2：如果从Ab或(bA)出现在算符文法的句型γ中，其中A∈ ，b∈ ，则γ中任何含b的短语必含有A。（反证法） 算符优先文法的定义（续） 设G是一个不含 产生式的算符文法 a = b G中有形如.A?…ab…或A ? …aBb… 的产生式。 a b G中有形如.A ? …aB…的产生式,而 B b….或B Cb… a b G中有形如.A ? …Bb…的产生式,而 B …a或B … aC （语法子树可以直观的说明算符的优先关系P101） 算符优先文法的定义（续） 定义 设有一不含 产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有＜、＞和＝三种关系的一种成立，则称G是一个算符优先文法(Operator Precedence Grammar)即OPG文法。（P101） 6.3.3 算符优先关系表的构造 由定义直接构造 由关系图法构造算符优先关系表 （1）由定义直接构造 首先引入两个概念 FIRSTVT(B)={b|B b…或B Cb...} 对于非终结符B，其往下推导所可能出现的首个算符 LASTVT(B)={a|B … a或B ... aC} 对于非终结符B，其往下推导所可能出现的最后一个算符 三种优先关系的计算： 1) ‘=‘关系 直接看产生式的右部，若出现了A →…ab…或A →…aBb…,则a=b 2)’‘关系 求出每个非终结符B的FIRSTVT(B) 若A→…aB…,则?b∈FIRSTVT(B),ab 3)’’关系 求出每个非终结符B的LASTVT(B) 若A→…Bb…,则?a∈LASTVT(B),ab 对以上的优先关系表我们也可以给出一下的算法，这个算法基于一下两条规则： a)若有产生式A→a…或A → Ba…，则 a∈FIRSTVT(A)，其中A、