编译原理 第四章自顶向下语法分析法

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

1、第四章自顶向下语法分析方法语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分析程序。也称为语法分析器，它是编译程序的主要子程序之一。在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。本章重点：自顶向下分析、LL（1）分析，然后再介绍自底向上分析。第一节自顶向下分析方法一、带回溯的自顶向下分析算法这是自顶向下分析

2、的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。下面用一个简单例子来说明这种过程：假定有文法G[S]：S→cＡd　　　　　　　　A→ab

3、a以及输入串w=cad为了自上而下地构造w的语法树，我们首先按文法的识别符号产生根结点S，并让指示器IP指adcASbadcASdcAS向输入串的第一符号c。然后，用S的规则（此处左部为S的规则仅有一条）把这棵树发展为（a）（b）（c）图3-1-1图3-1-1a图。我们希望用S的子结从左至右匹配整个输入串w。首先，此树的最左子结是终结符c为标志的

4、子结，它和输入串的第一个符号相匹配。于是，我们就把IP调整为指向下一输入符号a，并让第二个子结A去进行匹配，非终结符A有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b图。子树A的最左子结和IP所指的符号相符，然后我们再把IP调为指向下一符号d并让A的第二个子结进入工作。但A的第二个子结为终结符号b，与IP当前指的符号d不一致。因此，A宣告失败。这意味着A的第一个选择此刻不适用于构造w的语法树。这时，我们应该回头（回溯）看A是否还有别的选择。为了实现回溯，我们一方面应把A的第一个选择所生长的子树注销掉；另一方面，

5、应把IP恢复为进入A时的原值，也就是让它重新指向第二输入符号a。现在我们试探用A的第二个选择，即考虑生成图3-1-1c的语法树。由于子树A只有一个子结a，而且，它和IP所指的符号相一致，于是，A完成了匹配任务。在A获得匹配后，指示器指向下一个未被触及的符号d。在S的第二子结A完成匹配后，接着就轮到第三个子结d进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了构造语法树的任务，证明了w是文法G[s]的一个句子。上述自顶向下地为输入符号w建立语法树的过程，实际上也是设法建立一个最左推导序列，以便通过一步步推导将输入串推导出来。很明显，对

6、于输入串w可以通过如下的推导过程将其推导出来：ScAdab①W：cad↑2p指示口SCAdcad所以用最左推导，是因为我们对输入串是自左向右扫描的，只有使用最左推导，才能保证按扫描顺序去匹配输入串。在上述推出符号串w15的过程中，由于出现在符号串中的非终结符号只有一个，因此，未明显地表现出最左推导的性质。根据以上分析，不难编出程序来实现这种分析的算法。但是，上述这种自顶向下的分析算法存在着一定的困难和缺点。困难表现在不能为左递归文法构造自顶向下的语法分析器（上述所举例子的文法G[s]是不具有在递归性的）。缺点主要表现在存在着回溯问题。当然，应用

7、带回溯的自顶向下的分析算法还必须将文法规则存放于内存。下面将具体介绍这种分析算法所存在的问题及其解决办法。二、存在问题及解决办法（一）左递归问题自顶向下分析法只有规则排列得合适时，才能正确工作。该法的一个基本缺点是不能处理具有左递归的文法。如下所示。A→AB

8、BbB→Ac

9、dAa   BACBbAC如：直接左递归和间接左递归AABACcBbACcS→Sa

10、bSSaSaSaSaA→aAB

11、BbB→Ac

12、d无法确定语法树的终止，清除直接左递归的较好方法是改改为右递归如：S→Sa

13、b改为S→bS′S′→aS′

14、Σε一般情况下，直接左递归的形式可为：消

15、除A→Aα1

16、Aα2

17、…Aαm

18、β1

19、β2…βn清除左递归后改写为：A→β1A′1

20、β2A1′…

21、βnA1′A′1→α1A′

22、α2A1′…

23、αmmA′1

24、Σε对于间接左递归的消除，需先将间接左递归变为直接左递归，然后再接上述方法消除。条件是文法中无A→A　的有害规则和或A→Σε的空产生式算法：S→Qc

25、cQ→Rb

26、bSSabc排列R、Q、SR代入Q，Q→Sab

27、ab

28、bQ代入S，S→Sabc

29、abc

30、bc

31、cS→（abc

32、bc

33、c）S′S′→abcS′

34、ΣQ→Rb

35、bR→Sa

36、a（二）回溯问题当产生式都有多个选择时，选那个输入串去匹配为了避免回

37、溯，就必须保证：对文法的任何非终结符号特别是规则都右部有多个选择的非终结符号，当用它去匹配输入串时，应是确定无疑的。即：15U→α11

38、α22

39、…

40、α