《编译原理第六章算符优先分析法》由会员分享，可在线阅读，更多相关《编译原理第六章算符优先分析法（22页珍藏版）》请在金锄头文库上搜索。
1、第6章自底向上优先分析第六章 算符优先分析法课前索引 【课前思考】 什么是自下而上语法分析的策略？ 什么是移进-归约分析？ 移进-归约过程和自顶向下最右推导有何关系？ 自下而上语法分析成功的标志是什么？ 什么是可归约串？ 移进-归约过程的关键问题是什么？ 如何确定可归约串？ 如何决定什么时候移进，什么时候归约？ 什么是算符文法？什么是算符优先文法？ 算符优先分析是如何识别可归约串的？ 算符优先分析法的优缺点和局限性有哪些？ 【学习目标】算符优先分析法是自下而上（自底向上）语法分析的一种，尤其适应于表达式的语法分析，由于它的算法简单直观易于理解，因此，也是学习其它自下而上语法分析的基础。通过本章
2、学习学员应掌握： 对给定的文法能够判断该文法是否是算符文法 对给定的算符文法能够判断该文法是否是算符优先文法 对给定的算符文法能构造算符优先关系表，并能利用算符优先关系表判断该文法是否是算符优先文法。 能应用算符优先分析算法对给定的输入串进行移进-归约分析，在分析的每一步能确定当前应移进还是归约，并能判断所给的输入串是否是该文法的句子。 了解算符优先分析法的优缺点和实际应用中的局限性。【学习指南】算符优先分析法是自下而上语法分析的一种，它的算法简单、直观、易于理解，所以通常作为学习其它自下而上语法分析的基础。为学好本章内容，学员应复习有关语法分析的知识，如：什么是语言、文法、句子、句型、短语、
3、简单短语、句柄、最右推导、规范归约基本概念。【难 重 点】 通过本章学习后，学员应该能知道算符文法的形式。 对一个给定的算符文法能构造算符优先关系分析表，并能判别所给文法是否为 算符优先文法。 分清规范句型的句柄和最左素短语的区别，进而分清算符优先归约和规范归约的区别。 算符优先分析的可归约串是句型的最左素短语，在分析过程中如何寻找可归约串是算符优先分析的关键问题。对一个给定的输入串能应用算符优先关系分析表给出分析（归约）步骤，并最终判断所给输入串是否为该文法的句子。 深入理解算符优先分析法的优缺点和实际应用中的局限性。【知 识 点】短语、直接短语、句柄的定义：文法GS，S A且A 则称是句型
4、 相对于非终结符A的短语。若有A则称是句型 相对于A或规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。 算符优先分析法是一种自底向上分析方法，也称移进-归约分析法，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，(该句柄对应某产生式的右部)，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。本章将在介绍自底向上分析思想基础上，着重介绍算符优先分析法。 栈顶符号串是指该符号串包含栈顶符号在内
5、，并由栈中某个符号为该符号串的头，栈顶符号为该符号串的尾，也可以只有一个栈顶符号。6.1 自底向上分析概述自底向上分析法，也称移进-归约分析法，或自下而上分析。现举例说明。例6.1设文法GS为：(1) SaAcBe(2) Ab(3) AAb(4) Bd对输入串abbcde#进行分析，检查该符号串是否是GS的句子。由于自底向上分析的移进-归约过程是自顶向下最右推导的逆过程，而最右推导为规范推导，自左向右的归约过程也称规范归约。容易看出对输入串abbcde的最右推导是：SaAcBeaAcdeaAbcdeabbcde由此我们可以构造它的逆过程即归约过程。先设一个先进后出的符号栈，并把句子左括号#号放
6、入栈底，其分析过程如表6.1。表6.1 用移进-归约对输入串abbcde#的分析过程f6-1-1.swf图6.1 自底向上构造语法树的过程推倒的逆过程为：SaAcBeaAcdeaAbcdeabbcde对上述分析过程也可看成自底向上构造语法树的过程，每步归约都是构造一棵子树，最后当输入串结束时刚好构造出整个语法树，图6.1(a)(b)(c)(d)给出构造过程，可与表中相应分析步骤对照。 在上述移进-归约或自底向上构造语法树的过程中，我们怎么知道何时移进，何时归约，不能只简单地看成栈顶出现某一产生式的右部就可用相应产生式归约，例如在表6.1分析到第5)步时栈中的符号串是#aAb，栈顶符号串b和Ab
7、分别是产生式(2)，(3)的右部，这时到底用(2)归约还是用(3)归约是自底向上分析要解决的关键问题。由于移进-归约是规范推导(最右推导)的逆过程，即规范归约(最左归约)。当一个文法无二义性时，那么它对一个句子的规范推导是唯一的，规范归约也必然是唯一的。因而每次归约时一定要按当前句型的句柄，也就是说，任何时候栈中的符号串和剩余的输入串组成一个句型，当句柄出现在栈顶符号串中时，则可用句柄归约，这样一直归约到输入串只剩结束符，文法符号栈中只剩开始符号。这时才能认为输入符号串是文法的句子。否则为出错。 由此可见自底向上分析的关键问题是在分析过程中如何确定句柄，也就是说如何知道何时在栈顶符号串中已形成
8、某句型的句柄，那么就可以确定何时可以进行归约。自底向上的分析算法很多，我们仅在本章和第7章介绍目前常用的算符优先分析和LR类分析法。小练习：用PL/0的READ(A)语句为例构造自底向上的语法分析树,以体会自底向上的归约过程。下面为参考答案。 图6.3 自底向上的语法分析6.2 算符优先分析法算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈
9、中的符号和剩余的输入符号构成句型的最左素短语。例如:若有文法G为：(1) EE+E(2) EE*E(3) Ei对输入串i1+i2*i3的归约过程可表示为表6.3。表6.3 对输入串i1+i2*i3的归约过程f6-2-2.swf在分析到第6步时，栈顶的符号串为E+E，若只从移进-归约的角度讲，栈顶已出现了产生式(1)的右部，可以进行归约，但从通常四则运算的习惯来看应先乘后加，所以应移进，这就提出了算符优先的问题。本节所给例子是二义性文法，对二义性文法不能构造确定的分析过程，但是在本例中，人为地规定了算符之间的优先关系，仍然可构造出确定的分析过程。6.2.1 直观算符优先分析法 通常在算术表达式求
10、值过程中，运算次序是先乘除后加减，这说明了乘除运算的优先级高于加减运算的优先级，乘除为同一优先级但运算符在前边的先做，这称为左结合，同样加减运算也是如此，这也说明了运算的次序只与运算符有关，而与运算对象无关，因而直观算符优先分析法的关键是对一个给定文法G，人为地规定其算符的优先顺序，即给出优先级别和同一个级别中的结合性质，算符间的优先关系表示规定如下：ab表示a的优先性低于b。ab表示a的优先性等于b，即与b相同。ab表示a的优先性高于b。但必须注意，这三个关系和数学中的，是不同的。当有关系ab时，却不一定有关系ba，当有关系ab时，却不一定有ba，例如：通常表达式中运算符的优先关系有+-，但
11、没有-+，有()，但没有)(。下面给出一个表达式的文法为：EE+E|EE|E*E|E/E|EE|(E)|i本文法是二义性的，由于人为地规定了算符之间的优先级别和同一个级别中的结合性质，所以可能构造出确定的分析过程。我们可以对此表达式的文法按公认的计算顺序规定优先级和结合性如下： 优先级最高。遵循右结合，相当。例如：232=29=512。（而若为左结合则232=82=64） 也就是同类运算符在归约时为从右向左归约。即 i1i2i3式先归约i2i3。 *,/ 优先级其次。服从左结合，相当 * 、*/ 、/ 、/* 。 +，- 优先级最低。服从左结合，相当 +、+- 、-+ 、- 。 对(，)规定括
12、号的优先性大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号。对于句子括号#号规定与它相邻的任何运算符的优先性都比它大。此外，对运算对象的终结符i其优先级最高。综上所述，我们可对表达式运算符的优先关系构造如表6.4。 表 6.4 算符优先关系表+-*/()i#+-*/()i#.很显然所给表达式文法是二义性的，但我们人为直观地给出运算符之间的优先关系，由优先关系表6.4可知这种优先关系是唯一的，有了这个优先关系表我们对前面表达式的输入串i1+i2*i3归约过程就能唯一确定了，也就是说在表6.3分析到第6）步时，栈中出现了#E+E，可归约为E，但当前输入符为*，由于规定 +*，所以应
13、移进。本节简单介绍直观算符优先分析法，仅仅是为了易于理解算符优先分析法的概念，下一节将介绍对任意给定的一个文法如何按形式算法的规则计算算符之间的优先关系。6.2.2 算符优先文法的定义 我们首先给出算符文法和算符优先文法的定义。定义6.1 设有一文法G，如果G中没有形如ABC的 产生式，其中B和C为非终结符，则称G为算符文法(Operater Grammar)也称OG文法。例如：表达式文法EE+E|E*E|(E)|i其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法是算符文法。小练习：学员可证明算符文法有如下两个性质。性质1 在算符文法中任何句型都不包含两个相邻的非终结符 。性质2 如果Ab或(bA)出现在算符文法的句型中，其中AVN ，bVT，则中任何含b的短语必含有A。参考答案：证明：性质1用归纳法设是句型，即SS=01 . n-1n=推导长度为n，归纳起点n=1时，S=01=，即S，必存在产生式S，而由算符文法的定义，文法的产生式中无相邻的非终结符，显然满足性质1。假设n1, n-1满足性质1。若n-1=A，A为非终结符。由假设的尾符号和的首符号都不可能是非终结符，否则与假设矛盾。又若A是文法的产生式，则有n-1n=而A是文法的原产生式，不含两个相邻的非终结符，所以也不含两个相邻的非终结符。满足性质1。证毕。 证明：性质2用反证法。因为由算符文法的性质1知可有：
