《编译原理 第四章自顶向下语法分析法》由会员分享，可在线阅读，更多相关《编译原理 第四章自顶向下语法分析法（16页珍藏版）》请在金锄头文库上搜索。
1、 1Sc A da bW：cad 2p 指示口第四章第四章 自顶向下语法分析方法自顶向下语法分析方法语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源程序符号串中识别出各 类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分 析程序。也称为语法分析器，它是编译程序的主要子程序之一。 在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我 们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。本章重点：自顶向下分析、LL（1）分析，然后再介绍自底向上分析。 第一节第一节 自顶向下分析方法自
2、顶向下分析方法 一、带回溯的自顶向下分析算法一、带回溯的自顶向下分析算法 这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出 发，根据文法自上而下地为输入串建立一棵语法树。 下面用一个简单例子来说明这种过程： 假定有文法 GS： Scd Aab|a 以及输入串 w=cad 为了自上而下地构造 w 的语法树，我们首先按文法的识别符号产生根结点 S，并让指示器 IP 指 向输入串的第一符号 c。然后，用 S 的规则（此处左部为 S 的规则仅有一条）把这棵树发展为（ a）（b） （c）图 3-1-1 图 3-1-1a 图。我们希望用 S 的子结从左至右匹配整个输入串
3、w。首先，此树的最 左子结是终结符 c 为标志的子结，它和输入串的第一个符号相匹配。于是，我们 就把 IP 调整为指向下一输入符号 a，并让第二个子结 A 去进行匹配，非终结符 A 有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图 3-1-1b 图。子树 A 的最左子结和 IP 所指的符号相符，然后我们再把 IP 调为指向下一符号 d 并让 A 的第二个子结进入工作。但 A 的第二个子结为终结符号 b，与 IP 当前指的符号 d 不一致。因此， A 宣告失败。这意味着 A 的第一个选择此刻不适用于构造 w 的语法树。这时，我们应该回头（回 溯）看 A 是否还有别的选择。
4、为了实现回溯，我们一方面应把 A 的第一个选择所生长的子树注销掉；另一方面，应把 IP 恢 复为进入 A 时的原值，也就是让它重新指向第二输入符号 a。现在我们试探用 A 的第二个选择，即 考虑生成图 3-1-1c 的语法树。 由于子树 A 只有一个子结 a，而且，它和 IP 所指的符号相一致，于是，A 完成了匹配任务。 在 A 获得匹配后，指示器指向下一个未被触及的符号 d。 在 S 的第二子结 A 完成匹配后，接着就轮到第三个子结 d 进行工作。由于这 个子结和最后一个输入符号相符，于是，我们完成了构造语法树的任务，证明了 w 是文法 G s的一个句子。 上述自顶向下地为输入符号 w 建立
5、语法树的过程，实际上也是设法建立一个 最左推导序列，以便通过一步步推导将输入串推导出来。很明显，对于输入串 w 可以通过如下的推导过程将其推导出来：SCAdcad 所以用最左推导，是因为我们对输入串是自左向右扫描的，只有使用最左推导，adcASbadcASdcAS2AAB|Bb BAc|d Aa BA CB bA CSSa|bSSaSaSaSaAABAC cBbAC cAaAB|B b BAc|d才能保证按扫描顺序去匹配输入串。在上述推出符号串 w 的过程中，由于出现在符号串中的非终 结符号只有一个，因此，未明显地表现出最左推导的性质。 根据以上分析，不难编出程序来实现这种分析的算法。但是，上
6、述这种自顶向下的分析算法存 在着一定的困难和缺点。困难表现在不能为左递归文法构造自顶向下的语法分析器（上述所举例子 的文法 Gs是不具有在递归性的） 。缺点主要表现在存在着回溯问题。当然，应用带回溯的自顶向 下的分析算法还必须将文法规则存放于内存。下面将具体介绍这种分析算法所存在的问题及其解决 办法。 二、存在问题及解决办法二、存在问题及解决办法 （一）左递归问题 自顶向下分析法只有规则排列得合适时，才能正确工作。该法的一个基本缺点是不能处理具有 左递归的文法。如下所示。 如：直接左递归 和 间接左递归无法确定语法树的终止， 清除直接左递归的较好方法是改 改为右递归 如：SSa|b 改为 Sb
7、S SaS| 一般情况下，直接左递归的形式可为：消除 AA1|A2| Am|1|2n 清除左递归后改写为： A1A1|2A1 |nA1 A11A|2A1 |mmA1| 对于间接左递归的消除，需先将间接左递归变为直接左递归，然后再接上述方法消除。 条件是文法中无 AA 的有害规则和或 A 的空产生式 算法： SQc|c QRb|b SSabc 排列 R、Q、S R 代入 Q，QSab|ab|b Q 代入 S，SSabc|abc|bc|c S（abc|bc|c）S Sabc S| QRb|b RSa|a （二）回溯 问题 当产生式都有多个选择时，选那个输入串去匹配3为了避免回溯，就必须保证：对文法
8、的任何非终结符号特别是规则都右部有多个选择的非终结 符号，当用它去匹配输入串时，应是确定无疑的。即： U11|22|nn 该规则右部有 n 个选择,为了实现目的,我们对文法的要求是: F1rstIRST（i）f1rstFIRST（j）=（ij） 定义 1：设 G=（VT，VN，S，P）是上下文无关文法 FIRST（）=a| a，aVT，V* 若 ，则规定 FIRST（） 即对文法中的任意一个非终符号，其规则右部有多个选择时，那么，由各个选择所推出的终结 符号串的头符号集合要两两不相交。这样，就可能根据当时读进的符号是属于哪个选择的 FIRST（） ，来唯一地确定应该选用哪个选择来匹配输入串。如
9、当前的输入符号为 b(bVT)， 若 bFIRST（i） ，则用第 i 个选择； 若 b 不FIRST（i） ，其中 i=1n，则语法错，转出错处理。这样就避免了分析过程的回溯。 若文法的任一非终结符号，其规则右部的各个选择所能推出的终结符号串的头符号集合不满足 两两相交的条件时，那么，要构造一个不带回溯的自顶向下的语法分析程序，需要采取什么措施呢？ 一般可采取改写文法的办法来解决。 定义 1：设 G=（VT，VN，S，P）是上下文无关文法 F1RST（） =|，VT，V* 若 ，则规定 F1RST（） （三）改写文法， 当文法不满足，可改写文法 提因子 Uxv|xw Ux(vx|w) 提因子
10、提因子 三、递归子程序法三、递归子程序法 此方法的主要做法是：对文法中每个非终结符 号 U（它们都分别代表一种语法成分）,都编出一个 子程序，以完成该非终结符号所对应的语法成分的 分析和识别任务。某个非终结符号的语法分析子程 序的功能是：用该非终结符号的规则的右部符号串 去匹配输入串。分析过程是按文法规则自顶向下一 级一级地分配任务，即调用有关的子程序来完成。 当编译程序根据文法和当前输入符号预测到下一个 语法成分为 U 时，即预测到待匹配的输入符号串可 以为从 U 出发所推导出的符号串相匹配时，就确定 U 为目标，并调用分析和识别 U 的子程序。在分析 和识别 U 的过程中，有可能还要确立其
11、他子目标并调用相应的子程序，只有在被调用的分析和识 别某语法成分的子程序匹配输入串成功并正确返回时，该语法成分才算真正的获得了识别，并确定 输入串无语法错误。由于这种分析方法的特点是带有预测性的，并在分析过程中对着一个目标，所 以，称为预测的和面向目标的。 下面，我们简单讨论一下，为什么针对某些非终结符号所编出的分析程序要编成递归子程序? 。回答很简单，因为文法具有递归性。前面已讲过，自顶向下分析不能处理左递归文法，若有左递 归，则应改写文法予以消除。但是，消除了左递归不等于消除了文法的所有递归性质，此时，文法 仍可以有右递归性或自嵌入性。如在文法中有规则 UU 或UU 此仍为递归规则，故分析
12、 U 的子程序要编成递归子程序。因为该子程序在用规则右部符号串去匹 配输入串的过程中，又要调用 U 自己。即在通过该子程序正常出口返回调用程序以前，又要重新 直接进入该子程序，这就是直接递归。此外，还有间接递归，如在文法中有规则： UV VUW 那么UVUWa1a2aian#X分析栈#图 4-2-1总控程序分析表 m4即UUW+在该情况下，在分析 U 的子程序中要调用分析 V 的子程序；而在分析 U 的子程序中又要调用分析 V 的子程序。这样，对 U 的分析程序就要编成递归子程序，因在进入 U 的分析程序以后，在返回 调用程序以前，又可能间接地进入自己。 下面，我们举两个例子，说明如何根据文法
13、来构造该文法的语法分析程序。 例 1 文法 GZ Z（U）|aUb UdZ|Ud|e（4-7） 文法有左递归，所以，首先要改写文法： Z（U）|aUb U（dZ|e）d（4-8） 由分析可知，经改写之后的文法左递归；上述两条规则，其右部均各有两个选择，但两个选择各自 所推出的终结符号串的头符号集合不相交，即： （a= de= 所以，文法满足构造一个不带回溯的自顶向下分析器的条件。故我们可对文法中的两个非终结符号 分别编出其分析子程序。且由于有：Z Z 和 U U+所以，都要编成递归子程序。我们以框图形式给出这两个子程序，见图 4.2SSFSSFFF递归入口(SYM)=（？读符号U(SYM)=（
14、？出错读符号递归出口(SYM)=a？读符号U(SYM)=b？出错(a) 非终结符 Z 的分析程序5SSSFF递归入口(SYM)=d？读符号Z(SYM)=d？读符号递归出口(SYM)=e读符号出错(b) 非终结符 U 的分析程序图 4.2 图中，除要调用递归入口和递归出口两个子程序（这两个子程序后面介绍）此外，还要调用读 符号和出错处理子程序。 读符号子程序的功能是：扫描下一个符号，并把它放在全程单元 SYM 中。 出错处理子程序：当分析过程中发现有语法错误时，就调用出错处理程序，用它打印错误信息 和跳过一段源程序。关于错误处理，我们将在第九章中专门讨论。 当子程序调用时，在读下一个符号方面，要
15、注意衔接的正确性。我们约定：当调用某个子程序 时，它所要分析的第一个符号已经读进单元 SYM 中；同样地，在从子程序返回报告成功之前，已 经把跟在分析过的子符号串之后的那个符号读进 SYM 中了。上述两个子程序的框图就是按此约定 画出的。第二节第二节 LL(1)分析方法分析方法 本节，我们将介绍实现自顶向下分析的另一种 方法，即所谓 LL(1)分析方法。如此命名该分析方 法的原因在于相应的语法分析将按自左至右的顺序 扫描输入符号串，并在此过程中产生一个句子的最 左推导。至于括号中的“1” ，则表示在分析过程中， 每进行一步推导，只要向前查看一个输入符号，便 能确定当前所应选用的产生式（规则） 。因此，我们 通常把按上述方法执行语法分析任务的程序称为 LL(1)分析程序或 LL(1)分析器，使用这种方法进行 语法分析，可借助于一张分析表及一个语法分析栈， 在一个总控程序控制下很方便地实现。 下面，我们将首先介绍 LL(1)分析器的逻辑结 构和工作过程，然后再介绍 LL(1)分析器的构造方 法。 （一）（一）LL(1)分析器的逻辑结构及工作过程分
