自动构造分析表的自顶而下的语法分析

1、自顶而下语法分析（PT）前言对于国内的计算机教材，我一直是有巨大看法的，以至于写了读优秀的计算机教材来泄愤( Techniques中关于表驱动的自顶而下语法分析部分做了中文翻译，它正好对应合肥工业大学同门课程的实验二，提前说明，全文近7000汉字却没有一行代码，按这本书的说法是照顾斯坦福大学人文艺术学院的学生。良好的讲述就是艺术，不是么？当然，我的英语和汉语水平都不是很理想，所以在表意上定会有所折损，如果你对英文更有兴趣，请自行检索PT的电子版，这段内容在第九章，如果你发现有所错漏或表意不明之处，希望能帮助修订，感谢。下面，我们开始。查表法首先我们要考虑一个简单的语法格式来限制搜索情况，在这种

2、语法格式内，推导式的右部都由一个终结符开始。在这种语法格式下，预测步骤后面总是紧跟着一个匹配步骤，匹配步骤尝试匹配下一个输入的标示符与我们在预测过程所选中的推导式的右侧的第一个字符，只有在推导式右部是以输入字符开始时匹配才得以成立，而针对其他的右侧推导式将会失败。我们可以利用这一现象去限制我们所作出预测的数量：对于一个以某个终结符开始的推导式右部，只有当其首个字符与输入字符相等时，它才会被考虑加入预测集合。比如，考虑图表8.1中的语法：我们使用广度优先搜索，同时结合刚才的观察进行分析。 图(a)表示这个自动机的开始，我们将#作为终结符添加到初始预测和输入字符串的末尾。在S的右部中，只有一个是以

3、a开头的(aB)，所以这是唯一匹配的右部。我们选择了S 的第一个 aB，故而用 S1 表示，放到左边。图(b)中我们直接匹配a，将a放到左面。图(c)中，下一个输入的符号又是a，在B的右部中，我们发现只有aBB能匹配成功。把B3放到左面，我们得到图(d)。图(d)中，直接匹配a，得到图(e)。图(e)中，我们能观察到下一个输入的字符是b，这一次有两个B的右部能够匹配成功(b,bS)，我们就针对两种情况生成两行，得到图(f)，同样我们把b都移向左侧，得到(g)。图(g)中，下一个输入的字符是b。匹配第一行，B右部中的 b和bS可以满足要求；匹配第二行，S中的bA可以满足要求。把B 和 S 分别用

4、这三个可以匹配的右部替换并放到左边，得到图(h)，匹配b，得到图(i)。图(i)中，我们能发现，只剩下一个我们最初添加的#作为终止符号了，而S和AB不能再匹配成功，因此，下面两行预测走到了死胡同，只给我么留下了唯一的预测，得到图(j)。我们能够再一次提高上述方法的效率，那就是我们为每一对终结符与非终结符符的组合找到能使他们匹配的右部，就像刚才我们所寻找的那样，找到后将他们填入表单中。针对图表8.1中的语法，我们可以制作像图表8.3一样的表格，它被叫做 parse table其实怎样构造这样一个表是需要我们着重考虑的。而一旦这样的表格被建立起来，接下来的行动就好办了。我们所创造的这个语法分析器将

5、不再需要上面定义的语法推导式，取而代之的是在每一次预测时，语法分析器用下一个输入的字符和需要匹配的非终结符作为这个表格的两个索引，查找到对应的格子，格子里存着的就是我们需要考虑的推导式的右部。比如，在图表8.2(e)中，句法分析器将会用输入字符b和非终结符B去确定他需要考虑的推导式右部B1和B2.如果对应的格子是空的，我们就发现这个输入是不符合语法的。这还没有结束，前面格子里只有一个右部，而在A,a与B,b对应的各自内有不止一个元素，所以我们仍需要搜索决定哪一个符合语法。LL(1)语法分析在上一小节里我们举例的从上至下的语法分析器，其中最大的限制是我们要求语法中非终结符的右部都以一个终结符开始

6、。而在这一节中，我们将去掉这个限制条件。你会看到，我们仍然可以建立一个parse table。甚至，是带有边的。不带有规则的语法分析如果语法不带有规则，也就是说没有非终结符可以推导出一个空字符串。换句话说，每一个非终结符最终至少都能导出长度为1的字符串，这对每一个右部来说也成立。由此来说，由终结符开始的字符串就是我们所关注的对象。对于任意一个右部，一旦我们知道了它最后推导出来的字符串由哪一个字符开始，我们就能像上面那样构造一个parse table。所以，我们需要计算出每一个右部对应的字符串的首个终止字符的集合。FIRST1 集合这些由终止符构成的集合被我们叫做” FIRST1 集合”：假设我

7、们拥有一个非空左部x，那么FIRST1 (x)就是指x在一步或多步(>0)内能推导出来的字符串的首个终止字符的集合。这个下标 1 指的是这个集合只包含一个字符的终止符。其实还 FIRSTk ，当下我们无须理会，暂且用FIRST代替FIRST1。如果x是由非终止符A起始的，那么FIRST(x)等同于FIRST(A)，因为A不能产生边，那么x所能推导出的式子的最左边肯定是由A推导出来的。所以，如果我们能够计算任意非终止符A的FIRST集合，我们也就能得到x的FIRST集合。然而，FIRST(A)取决于A的右部：是A不同右部的FIRST集合的并集，这些FIRST集合又再次取决于其他非终止符的并

8、集，在A的语法存在直接或间接地左递归（A描述A）的情况下，甚至这个其他有可能是A本身。这样的观察让我们得到了一个迭代的过程去计算所有非终结符的FIRST集合：1. 将所有FIRST集合初始化为空集2. 我们对每一条语法规则进行下面的工作：设当前推导式的左部为x，右部为 xr如果xr是以一个终结符开始的，那么我们可以直接把这个符号添加到FIRST(x) 集合中。如果xr是由一个非终结符开始的，我们设这个非终结符为y，然后把当前FIRST(y)中的所有元素添加到FIRST(x)中。这些被加入符号都是能够被x推导出的字符串的首个字符。3. 重复第二个步骤直到在一次循环中没有任何一个新的元素加入任何一

9、个FIRST集合最终一定会没有新的符号能够被添加，是因为一个FIRST集合所能拥有的元素的最大数便是所有符号的总数，而FIRST集合的数量等同于非终结符的数量。因此，新元素能够被加入FIRST集合的次数限制在字符数量和非终结符数量的乘积内。这是一个传递闭包算法的典型例子。创建Parse Table通过FIRST集合的帮助，我们现在可以根据一种语法形式来创建Parse Table了！假设有一条语法规则（推导式）是A ，我们这样进行处理：如果是由一个终结符t开始的，我们就把这条推导式的右部加入到(A,t)对应的格子中；如果是由一个非终结符开始的，我们就取出每一个FIRST()中的元素，设它为n，把

10、加入到(A,n)中。现在，让我们以图表8.7中的语法为例演示一下计算出parse table的过程。这种语法描述了一个用在早期咨询系统上的简单语言：用户输入一些事实，然后再提问，也有一些设施是为子对话服务的。事实和问题的内容我们暂时先不去管它，他们用单词STRING表示，在这里STRING被当做终结符看待。第一步，我们计算FIRST集合。起初，把所有FIRST集合为空。接下来，我们对图表8.7中的所有语法规则进行前面所描述过的处理过程。对于语法规则：Session -> Fact Session ，我们需要把FIRST(Fact)集合中的字符都加入到FIRST(Session)中，但是F

11、IRST(Fact)一开始也是空的。对于语法规则：Session->Question ，我们需要把FIRST(Question)加入到FIRST(Session)中，当然，FIRST(Question)目前也是空的。对于语法规则：Session -> ( Session ) Session ，我们需要把 ( 添加到FIRST(Session)中。对于语法规则：Fact -> ! STRING ，我们需要把 ! 添加到 FIRST(Fact)中。对于语法规则：Question -> ? STRING ，我们需要把 ? 添加到FIRST(Fact)中。好了，做完这一切之后，

12、我们有了以下的结果：接下来，我们再一次对所有的语法规则进行上面的过程，这一次，对于Session -> Fact Session 我们把 ! 加到FIRST(Session)里（从FIRST(Fact)得到），对于Session -> Question 我们把?加入FIRST(Session)中，没有其他的改变了。于是得到了：由于上一次循环产生了一些变化，所以我们必须重复这个循环，这一次，我们没发现什么变化了，所以上面的表格就是我们所需要的有关于非终结符的FIRST集合。现在我们已经拥有了构造一个parse table所需的全部信息。对于Session -> Fact Ses

13、sion，我们需要把FIRST(Fact Session)中的元素依次取出，设为t，对每一个t，把Fact Session加入到Session,t格子中。前面我们说过如果x是由非终止符A起始的，那么FIRST(x)等同于FIRST(A)，所以FIRST(Fact Session)在这里等同于FIRST(Fact),所以只需要把Fact Session加到Session,!中。类似的步骤，对于Session->Question，我们把Question加入到Session,?。对于Session -> ( Session ) Session，右部直接是终止符开始的，所以把( Sessi

14、on ) Session加入到Session,)。之后过程不再赘述。最终得到parse table如图表8.8在这个表格中，格子里只有推导式的右部，因为左部已经成为了行的索引。如果一种语法生成的parse table所有的格子最多只有一个元素的话，我们就叫这种语法为LL(1)。好了，这一小节中，我们费了很大的劲终于去掉了最开始右部必须要由终结符开始的条件，创建一个parse table确实是是一个很复杂的活儿，但我们也收获了许多：许多实际应用的语法都是符合LL(1)或者可以简单地变化成LL(1)形式的。带有 规则的LL(1)语法分析不允许规则不得不说是一个重大缺陷。若不利用规则，对某些语言的构

15、建是十分困难甚至是不可能的。比如，非终结符描述一连串的终结符或非终结符就是很困难的。当然你可以把一串a表示成 A -> aA | a，但这就不是LL(1)了（显然格子里会超过一个元素）。对于上一节提到的语法：如果我们引入规则，能表达得更明晰：扩展FIRST集合允许规则最大的问题便是FIRST集合，因为我们之前讨论得并不充分。比如，非终结符Facts在图表8.9的语法中存在规则，FIRST()是空的，所以它不会告诉我们哪一个输入字符该使我们选择这个右部。为了能表现出规则，对于FIRST集合的计算方法需要一些修改。比如，如果用以前的方法对Session的第一个右部计算FIRST集合 ? 不会

16、成为集合中的一员，但它却应该在，因为Facts能推导出，当Facts被忽略掉后 ? 作为Question的开头，也被包含其中。让我们先扩展FIRST集合的定义以处理规则。这一次，除了终止符，也被允许成为FIRST集合中的一员。我们要去处理空的句式，所以我们有时需要FIRST()集合；我们把它定义成一个只包含字符串的集合。当一个句式能推导出时，我们也把加入到那个句式的FIRST集合中。这些变动影响了FIRST集合的计算过程。FIRST(u1u2 ···un)曾经被我们看做等同于FIRST(u1) ,现在要这样进行计算了：我们检查FIRST(u1)中是否存在 ，如果存

17、在，我们去掉，把它替换成FIRST(u2 ···un)，替换过后的FIRST(u1)等于FIRST(u1u2 ···un)。刚才的处理过程是很容易理解的：如果FIRST(u1)包含，那么u1便可能是透明的，所以把后面的FIRST(u2 ···un)就被暴露出来，也就可以拿掉了。当然对于FIRST(u2 ···un)也要用一样的算法。这个链条直到我们遇到了一个ui，当FIRST(ui) 不包含时，把FIRST(ui)中的元素加到FIRST(u1u2 ··&#

18、183;un)中就可以了。如果 FIRST(u1), FIRST(u2), . FIRST(un) 都包含，我们就把加到FIRST(u1u2 ···un) ，表示所有的选项都是透明的。对于一些算法，我们需要知道一个非终结符A能否推导出，只需要查看是否在FIRST(A)中就可以了。因为就像上面说的那样，如果能被A所导出，那么它也一定在FIRST(A)中。如果你没对此厌烦的话，我们再来演练一下对于图表8.9的FIRST集合的计算。首先我们先设置所有的集合为空。接着，我们对每一条语法进行处理对于Session -> Facts Question，把FIRST(Fa

19、cts)中的添加到First(Session)，但FIRST(Facts)目前是空的。对于Session -> ( Session ) Session ，把 ( 加入FIRST(Session)。对于Facts -> Fact Facts ，把 FIRST(Fact) 加入 FIRST(Facts) 对于Facts -> ，把 添加到FIRST(Facts)对于Fact -> ! STRING ，把 ！添加到FIRST(Fact)对于Question -> ? STRING，把 ? 添加到FIRST(Question)最终我们得到：第二遍更有趣，我们知道 Fact

20、s 能推导出 ，因此对于Session -> Facts Question ，我们应当把FIRST(Question) 中的字符 (?) 加到FIRST(Session)中。对于Facts -> Fact Facts ，我们应当把FIRST(Fact)中的字符(!)加入FIRST(Facts)。我们得到了：再来一遍，唯一的变动是我们要把FIRST(Fact)中新加入的!再加入到FIRST(Session)里，我们得到：第四遍并没有变化，构造结束。现在问题还剩下在一些选择的情况下，怎么决定何时选择那个右部。假设我们有这样的语法规则：A 1|2|···|n

21、其中，m是或者推导于一个，现在假设我们在预测的最前面发现A，在最后添加#作为端记号：按照我们之前的方法，将产生多个预测以至于并列：我们知道如何计算出一个预测的FIRST集合，我们也知道这些集合中没有一个包含的（因为最后有#）。如果下一个输入的字符不属于这些集合当中的任何一个，那么不是我们的预测Ax#是不可行的就是输入的句式是不符合语法的。反之，下一个输入的符号是属于这些集合当中的一个或多个的，我们就能删去那些FIRST集合中不包含这个输入符号的预测。对于FOLLOW集合的需求经过前面的知识积累，原则上我们已经能为任何一个符合LL(1)的语法创建一个语法分析器。这个语法分析器由一个预测S#开始，

22、他的预测步骤包括把预测的非终结符换成他的右部、计算已有预测的FIRST集合以及检查下一个输入字符是否属于这些集合。但如果最后保留了超过一个预测，那么这个语法分析器就会声明这个语法并非LL(1)然后停止。这当然是不理想的。首先，我们前面辛辛苦苦构建出来的parse table没有被使用，直到对一个句子进行语法分析的时候他才检查语法是否符合LL(1)，而这实际上早在建立parse table的时候就能得到检查。其次，这样效率很差，因为每一步预测都需要计算FIRST集。我们不能提前计算出这些FIRST集合，因为有了边的存在，一个FIRST集合取决于所有的预测（这是无穷尽的），而不单单取决于首个非终止

23、符。所以我们仍然不知道如何为带有规则的LL(1)构建一个parse table，也没有一种方法去确定一个语法是LL(1)。现在假设我们有一个预测Ax#和一个推导规则A , 本身是或者推导于。导致我们选择A 的输入字符存在于FIRST(x#)中，我们知道，由于的透明性，这个集合是由FIRST()并FIRST(x#)得到的。FIRST(x#)是个麻烦：我们不能在这个语法分析器的创建时期就得到它。然而，我们能提前计算的是所有x#跟着A情况下FIRST(x#)集合的并集。这仅仅是在任何S#能推导出的句式中能跟随A的终结符的集合，我们把这样的集合叫做FOLLOW(A)。看起来一个粗略的近似能够严重削弱一

24、个语法分析器甚至是让他出错，但这一次不是。假设FOLLOW(A)包含一个字符a，不是FIRST(x#)的成员，成为下一个输入字符。如果a不是FIRST(A)中的成员，我们将预测A ，最终会以匹配失败告终，因为x#不能推导出以a开始的式子。所以这个输入字符串会被正确地拒绝掉，尽管错误发现得比以前要晚，因为在发现出错前，语法分析器会做一些假设。如果a是FIRST(A)中的成员，同时也是A其他右部的FIRST集的成员，那么我们也许会遇到问题，我们之后再担心他。FOLLOW集有一个好处是我们能够在语法分析器的构造时期就计算出来。每一个非终结符都有一个FOLLOW集，他们可以用下面的方法来计算：1. 像

25、计算FIRST集合一样，我们首先把所有的FOLLOW集置空。设S是起始预测，在他后面加上#作为端记号，把#加入FOLLOW(Session)里。2. 接着，我们处理所有的推导式。如果形式是AàB，那么我们就把FIRST()中除了外的全部字符加入到FOLLOW(B)中，如果推导式是AàB或是Aà B但FIRST()中存在，就把FOLLOW(A)中的元素添加到FOLLOW(B)。3. 重复以上步骤直到一次循环中没有新的符号加入任何一个FOLLOW集。这又是一个传递闭包算法的例子。现在让我们回到我们的例子，来计算FOLLOW集。首先把#加入FOLLOW(Session)

26、里。对于Session -> Facts Question FIRST(Question)中的字符 ? 被加入到FOLLOW(Facts)中。FOLLOW(Session)中的所有符号(#)要被添加到FOLLOW(Question)中。对于Session -> ( Session ) Session ，我们把 ) 添加到FOLLOW(Session)中，把FOLLOW(Session)添加到FOLLOW(Session)中。 对于Facts->Fact Facts ，我们把FIRST(Facts)的所有符号(!)加入到FOLLOW(Fact)中，由于 Facts 能推导出，所

27、以把FOLLOW(Facts)的所有字符(?)加入到FOLLW(Fact)中。第一遍循环后我们得到了：在第二遍过程中，) 被加入到FOLLOW(Question)中，因为它现在成为了FOLLOW(Session)的成员。第三遍循环没有引起什么变动，最终结果是这样的：使用FOLLOW集来创建Parse Table一旦我们知道每一个能推导出的非终止符的FOLLOW集合，我们就能构建一个parse table了。首先我们对每一个非终止符计算它的FIRST集，在这个过程中我们也能知道哪一个非终止符会推导出。然后，我们计算每一个非终止符的FOLLOW集。接着，从一张空的parse table开始，我们对

28、每一条语法规则Aà进行如下操作：像我们先前做的那样，设FIRST()中的字符为a，我们将右部加入到A,a对应的格子内。但是在这一次，如果我们发现本身是或者能够推导出时，我们同样设FOLLOW(A)中的符号为a，把加入A,a的格子里。简单来说就是，我们对在FIRST( FOLLOW(A)中的所有终结符a，把加入到A,a的格子里。如果一个通过FOLLOW集合加入的格子中已经有了一个通过FIRST集合加入的右部，就发生了FIRST/FOLLOW冲突，这种语法不是LL(1)的。也有可能会发生FOLLOW/FOLLOW冲突，也就是说一个格子两次通过FOLLOW集合加入了两个右部，如果超过一个候选的非终结符能推导出就会发生这一点。让我们演练一下生成parse table的过程，还是根据下面的语法：对于Session -> Facts Question ，我们要先观察得到FIRST(Facts Question)，从上面的表格能发现FIRST(Facts)中有，根据我们前面提到的算法，把去掉，换成FIRST(Que