编译原理 第五章自底向上优先分析法

《编译原理 第五章自底向上优先分析法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章自底向上优先分析法自底向上优先分析法，其基本思想是采用自左向右扫描，向下而上分析。该类分析方法是从输入符号串开始，查找句柄，并使用规则把它归约成相应的非终结符号。任何自底向上分析的关键，就是要找出这种句柄。本章首先介绍自底向上分析一般过程，然后介绍算符优先分析法。本章重点：句柄、算符优先分析法第一节自底向上分析一般过程。先举例说明例1有一文法G[S]S→aAcBeA→bA→AbB→d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。它的最右推导是：S⇒aAcBe⇒aAcde⇒aAbcde⇒abbc

2、de由此我们可以构造它的逆过程即归约过程。先设一个先进后出符号栈，并且把句子左括号“#”号放入栈底，其分析过程如下所示步骤符号栈输入符号中（1）#abbcde#（2）#abbcde#（3）#abbcde#A→b归约（4）#aAbcde#（5）#aAbcde#A→Ab归约（6）#aAcde#（7）#aAcde#（8）#aAcde#B→d归约（9）#aAcBe#（10）#aAcBe #S→aAcBe归约（11）#S #接受上述归约过程，是从输入符号串开始，自底向上地通过归约当前句型的句柄来建立语法树的。我们不难画出上述分析

3、过程的语法树，下图。在图中，我们仅画出与生成语法树有关的几步。从所建立的语法树，可以清楚看出，上述每一步确实都是归约当前句型的句柄。且句柄出现在符号栈栈顶，不会在栈中间，其实上述分析过程并未真正解决句柄的识别问题。例如，对于上面的例子，分析进行到第（5）步，当时栈内符号串为aAb。根据该符号串，我们有规则A→Ab。和规则A→b。那么，符号串Ab和b都是某条规则的右部，故都有可能被判别是句型的句柄。假如我们选择b作为句柄，并把b归约为A，那么，最终就达不到归约到S的目的。因而，我们也就无从得知输入串abbcde是一个句子

4、了。AASABA BAAAabbcda bbc deaba bb在自底向上分析中，如何寻找确定一个句型的句柄是构造一个自左向右扫描，自底向上分析方法必须要解决的一个问题。11第二节算符优先分析法众所周知，作算术式的四则运算时，为了保证计算过程和结果的唯一性，必须要规定一个统一四则运算法则。这种法则的主要方面，就是规定运算之间的优先顺序。现在人们所遵循的统一法则是：乘除运算优先于加减运算，故在算术中要先作乘除运算后作加减运算；同优先级的运算符是先左后右（即左结合），先作左边的运算符的运算，后作右边运算符的运算。根据这个法

5、则，如果每一步只做一个运算，那么，任何算术式的计算过程和结果便是唯一的。例如：9+8－6/2×3‘+’和‘－’同级，先作‘+’=17－6/2×3‘－’优先级低于‘/’，先作‘/’，=17－3×3‘－’优先级低于‘×’，先作‘×’=17－9只有唯一的‘－’。=8对于含有括号一目运算减的算术式，我们只需对上述的法则加以补充。如规定要先作括号里的运算，后作括号外的；一目运算减的优先级高于加减低于乘幂。那么，包含有括号和一目运算的算术式的计算过程也是唯一的。以上关于算术式的四则运算法则，连小学生也是熟知的。所谓算符优先分析法就

6、是仿照上述算术式的四则运算过程而设计的一种语法分析方法。实际上，该方法在一开始就是为了分析和翻译程序语言中的表达式而设计的。这种方法首先是要规定运算符之间（更一般说是终结符号之间）的优先关系和结合性质，然后就利用这种关系，用比较相邻运算符的优先顺序来确定句型的“句柄”和进行归约。应该指出，这种归约未必是严格的最左归约，即每一步未必是归约当前句型的句柄，所以，我们在句柄上打上了引号。下面，举一个简单的例子，来说明应用该方法分析符号串的过程。例2有文法：G[E]：E∷E=E

7、E－E

8、E*E

9、E/E

10、E（E）

11、i这是一个二义

12、性的文法，它的句子往往有不同的规范推导，因而就有不同的规范归约（句型的句柄未必是唯一的）。例如，对句子i+i－i*(i+i)，就有两种不同的规范推导和规范归约。所以，归约过程中句型的句柄不唯一。但是，如果采用上述关于运算符优先顺序和结合原则的规定，并按这种规定进行归约，那么，该句子的归约过程就是唯一的。例如，我们按正常的四则运算法则，即规定乘除运算符的优先级高于加减运算符；同级运算符是左边的运算符的优先级高于右边的；有括号时，先括号内后括号外；另外，因i是一个基本的运算对象（属终结符号），因此，我们要先算一算它，然后进

13、行别的运算，故规定i的优先级高于其他运算符。按此条件来归约分析上述句子，那么，可得该句子的归约过程为：（1）i+i－i*（i+i）（2）E+i－i*（i+i）（3）E+E－i*（i+i）（4）E－i*（i+i）（5）E－E*（i+i）（6）E－E*（E+i）（7）E－E*（E+E）（8）E－E*（E）（9）E－E*E（10）E－E