编译原理与技术讲义-第5章.ppt

1、编译原理与技术，第5章，自底向上语法分析，编译原理与技术，第2章，主要内容，自底向上语法分析概述，运算符优先分析方法，LR分析方法，LALR分析器的生成工具yacc，编译原理与技术，3，5.1自底向上语法分析概述，自底向上解析器体系结构本书介绍的自底向上解析器显然使用堆栈结构来执行解析，a1，ai，an，$，$，x1，XM，自底向上解析控制程序，自底向上解析被分析的输入符号串；语法分析控制程序表达语法结构并存储控制信息的语法分析表。5，5.1自底向上语法分析概述，控制程序从左到右逐个扫描输入字符，并根据每个二进制分析堆栈元素组和输入符号的不同语法分析表执行以下四个动作之一：(1)将输入字符串的

2、当前符号A移入并读入堆栈顶部，并将指针指向下一个输入符号；(2)协议用某个产品的左非终端符号替换从堆栈顶部向下的几个符号串；(3)接受解析成功的通知，此时，堆栈指针指向堆栈中的维度符号语法开始符，输入字符串指针指向结束符号$；(4)错误发现源程序有误，调用错误处理程序。因为自底向上语法分析的基本动作是移入输入字符或缩减的符号串，所以它有时被称为移入缩减分析。编译原理和技术，6.5.1自底向上语法分析概述，例5.1:对于语法G5.1 E E T | T T T*F | F F (E) | i，根据自底向上的分析方法分析输入符号串i i，即将输入符号串I简化为语法的起始符号E。编译原理和技术，7，

3、5.1自下而上语法分析概述，规范归约过程与最右边的推导过程相反，表中的六个归约正好对应于最右边的推导(规范推导)的六个步骤：即语法分析过程可以用一个分析树来表示。编译原理与技术，8.5.1自底向上语法分析概述，有两个基本问题值得讨论：(1)如何确定是执行移入还是还原操作？例如，当前输入符号是相同的。在第(5)行，这是一个移动到堆栈顶部的操作，而第(2)、(3)和(4)行需要减少。(2)什么是可约串？在什么条件下可以进行缩减，以及产品左侧的哪些特定非终止符可以替换(缩减)符号串？编译原理与技术，9，5.1自底向上语法分析概述。在输入字符串i i的运算符优先级降低的过程中，您只需要知道用一个非终止

4、符替换当前的可降低字符串，而不需要关心非终止符是什么，这样就可以加快语法分析的过程。编译原理与技术，10，5.1自底向上语法分析概述，编译结构的短语，句柄和最左边的素数短语清晰，有组织，易于高效实现；在设计高级语言时，我们可以独立研究词法和语法的特点；增强编译器的可移植性：您可以用同一种语言为不同的机器编写不同的词法分析器，但只编写一个通用的语法分析，并使用这些词法分析器在机器中表达相同的单词；同一个单词标记的语法可以用一个更简单的语法来描述，通过把单词从语法中分离出来，可以为这个语法建立有效的特殊方法和自动构造技术。编译原理和技术，11，5.1自下而上语法分析概述，短语定义，句柄和最左边的主

5、短语5.1:s是语法G的起始符号，G是语法的一种句型。如果有S * P和P，它被称为一个短语，其句型是相对于非终止符U的，其中，和是语法的符号串，可以是空的，P是非终止符。特别是，如果有u，它被认为是相对于非终结符u的句型的直接短语。定义5.2:句型中最左边的直接短语叫做句型的句柄。定义5.3:质数短语是包含至少一个终止符的短语，除了它自己，没有更小的质数短语。编译原理和技术，12，5.1自下而上语法分析概述，短语，句柄和左基本短语，示例5.2:考虑语法g 5.2 E E T | T T T * F | F FP | P P(E)| I句子i1*i2 i3短语是：i1，i2，i3，i1*i2和

6、i1*i2 i3，虽然有E* i2 i3， i2 i3不是这个句型中的一个短语，因为没有从起始符号E到i1 * e的派生。另一个句型中的短语包括：E T*F i、E T*F、T*F和I，其中T*F和I是直接短语，T*F是句柄； 另外，T*F和I也是质数短语，T*F是最左边的质数短语。编译原理和技术，13，5.1自底向上语法分析概述，概念之间的关系和相应的分析方法自底向上分析过程中的每一步都是找到句型中最左边的直接短语(句柄)或最左边的主短语，并将其简化为可约字符串。短语、质数短语、最左边的质数短语、直接短语、句柄、是产品的右边部分，它包含至少一个终止符、最左边的、LR分析、运算符优先分析、编译

7、原理和技术、14，5.1自底向上语法分析概述、规范和规范过程句柄始终在堆栈的顶部。不断检查堆栈顶部的符号串是否形成新的句柄，如果是，用相应产品的左符号替换该句柄；如果手柄没有形成在堆栈顶部，按下堆栈顶部的输入符号，直到手柄形成在堆栈顶部；直到分析堆栈的符号被成文法的起始符号替换。编译原理和技术，15，5.1自下而上语法分析概述，运算符优先级降低不断地将堆栈顶部最左边的质数短语减少到相应产品的左边符号中，或者将输入符号压入堆栈顶部，直到分析堆栈的符号取代成文法律的开始符号。表5.4示出了根据示例5.1的最左边的主要短语的输入串1i的缩减过程，并且句型中的斜体符号串表示句型的最左边的主要短语。编译

8、原理与技术，16，5.2运算符优先分析方法，运算符优先语法运算符优先分析是一种自下而上的分析方法，分析过程快速，特别有利于表达式分析，便于手工实现。它不是严格的最左归约，也就是说，它不是一个规范的归约方法。在算子优先分析法中，可约字符串是最左边的素短语。所谓操作符优先是指程序设计语言中表达式操作的不同优先顺序，它定义了操作符之间的一些优先约简关系，即不终止符，从而在句型中找到可约串。由于非终止符关系的定义与普通算术表达式的运算符(如加、减、乘、除)的优先关系一致，因此被称为运算符优先分析方法。在例5.3中，句型E T*F i最左边的主要短语是T*F，而E T和F i不是短语(为什么？)，表示先

9、减少T*F，然后减少由符号和左右符号组成的符号串。这个分析过程正好说明了算术表达式中乘法和除法的优先级高于加法和减法。编译原理与技术，17，5.2算符优先分析方法，算符方法定义5.4:如果没有像美国这样的生产形式.公共关系.在语法G中，P和R是不终止符，也就是说，任何生成形式的右边部分不包含两个连续的不终止符，那么这个语法就叫做算子方法。定理5.1:在运算符方法中没有两个相邻的非终结符的句型。定理5.2:如果aR(或Ra)出现在运算符语法的句型中，其中A是终止符，而R是非终止符，那么任何包含A的短语都必须包含R。定理5.3:在运算符语法的任何句型中，没有紧接在前面和紧接在后面的带有非终止符的短

10、语。编译原理与技术，18，5.2运算符优先分析方法，运算符语法句型的一般形式显然可以写成如下：n1t1n2t2.nmtmnm1，其中ti是末端编译原理和技术，19，5.2操作符优先分析方法，操作符优先语法定义5.5:在没有生产的操作符语法g中，如果有任何两个终止符a和b，最多有以下三种优先关系之一：(1)ab当且仅当g包含生产，如P.aRb.或P.ab.(2)ab当且仅当G包含P形式的生产公式.aR和R b.R或QB.(3)ab当且仅当G包含P形式的生产公式.元素铷的符号.和R.a或R.aQ。其中p，r和q都是非终结符，那么g被称为算符优先文法。编译原理与技术，20，5.2操作符优先分析方法，

11、其中，被称为操作符优先关系，它表示操作符语法G中任意两个终止符之间的关系，与非终止符无关。优先级关系ab表示A和B的归约优先级关系是相等的，它们属于同一个可归约字符串，并且在产品的左边部分被非终止符替换。优先级关系ab表示A的归约优先级低于B，包含A的符号串只有在B所在的符号串归约后才能归约。优先级关系ab表示A的归约优先级高于B，包含B的符号串只有在包含A的符号串归约后才能归约。这些优先关系是有序的，不满足对称性和传递性，也就是说，对于语法G的终止子A、B和C，如果是ab，可能没有BA；如果ab和bc存在，ba或AC不能从它们中推导出来。同样，如果ab和bc存在，则不能获得ac。编译原理与技

12、术，21，5.2算符优先分析法，例5.3:考虑语法g 5.2(1)E T(2)E T(3)T * F(4)T F(5)F FP(6)F P(7)P(E)(8)P I根据定义，根据e e t和t T T*F的规则，我们可以得到*，它是由T*F FP得到的，然后由T * FP PP(E)P(它也得到I.同样，从规则(3)到(8)，*、*(和* I；从规则(5)到(8)，我们可以得到(即它可以从E E T和E E T得到，然后从E E T T T F T P T(E) T的一系列推导中得到)。编译原理与技术，22，5.2运算符第一种分析方法，为了统一起见，取特殊符号$，它在分析时用作结束符号，作为终

13、止符并定义$ $；对于语法g中以S开头的任何终止符a和非终止符p，如果S是.还是啪.然后定义$ a；如果是.a或S.aP，定义一个$。例如，$和$可以从规则(1)中导出，$ *和$可以从E E T T T T*F T * f t中导出。语法G5.2是一个没有两个连续非终结符的运算符语法，每对终结符最多只有一个优先级关系，因此它是一个运算符优先语法。通过观察表5.5，可以发现运算符的优先关系与数学运算符的优先关系是一致的，如*、特别是，()表示如果存在以下情况.().)，则包括第一对括号的符号串应该首先被缩减，然后第二对括号的符号串应该被缩减，这与括号在数学表达式中的作用完全一致。编译原理与技术

14、，23，5.2算符优先分析法，例5.4:说明语法g5.3: e e e | e * e | (e) | i是否是算符优先语法。因为没有两个连续的非终止符e并置在一起.电子工程师.在语法的产生中，G5.3是一个运算符方法。*可从E E E和e E E*E获得；从东东和东东我们可以得到。这样，终止符和*之间有两种优先关系。根据定义，G5.3不是运算符优先语法。编译原理和技术，24，5.2运算符优先分析方法，运算符优先关系的构造容易构造优先关系，所有满足ab的优先关系都可以通过逐个检查语法生成的每个候选公式来找出，看是否有ab或aRb形式的子符号串(其中A和B是终止符，R不是终止符)。为了构造优先关

15、系，必须设计某种方法。对于每一个非终止符，满足条件的终止符集合.或R Nb.然后检查语法生成的所有候选表达式。对于aR形式的每个子符号串，终止符A与该集合中的每个终止符都有关系。优先关系的构建思想是相似的。，编译原理与技术，25，5.2运算符优先分析方法，定义5.6:对于运算符方法g，定义以下两个终止符的集合：FIRSTTV(P)=a | P a.或P Ra.a是终止符，r是非终止符lastvt(P)=a | P.a或p.ar，a. LASTTV表示每个作品右边部分的最后一个终止符。编译原理与技术，26，5.2操作员优先分析方法，第一台电视机的构造方法：(1)是否有生产公式.或P Ra.添加一

16、个要设置的第一个电视(P)，即第一个电视(P)；(2)如果有一个生产公式，则第一个电视(R)被合并到第一个电视(P)中，也就是说，如果有第一个电视(R)，则有第一个电视(P)；(3)重复应用上述两个规则，直到第一个电视(P)不再增加。编译原理与技术，27，5.2算符优先分析法，机顶盒的构造方法(P): (1)如果有一个公式P.a或P.aR，添加一个来设置LASTTV (P)，即一个LASTTV(P)；(2)如果有生产公式P.把最后一台电视机(R)合并成最后一台电视机(P)，也就是说，如果有最后一台电视机(R)，就有最后一台电视机(P)；(3)重复应用上述两个规则，直到最后电视(P)不再增加。编译原理与技术，28，5.2操作员优先级分析方法，在完成对第一台和最后一台电视机的计算后，可以系统地找到所有和的优先级关系：(1)对于每一个产品，以R.aP.每一个b代表一个b。(2)对于每一个具有R形式的生产公式.爸爸.每一台电视(r)都有一个ab。编译原理和技术，29，5.2运算符优先级分析方法，算法5.1运算符方法g优先级表的构造算法输入：运算符方法g和每个非终止符的FIRSTTV(P)和LASTTV (P)输出