编译原理第六章算符优先分析法

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