LL(1)语法分析器的设计与实现

作者：万能超        指导老师：张玉州

摘要：语法分析是编译器的核心部分。词法分析只是将字符形式的源程序中的各个单词识别出来，形成单词的机内表示形式，但是这些单词串如何构成更大的语法成分—语句，那就要语法分析来完成。语法分析的主要任务是“组词成句”，即在词法分析识别出单词串的基础上，根据语言的语法产生式，识别出各种类型的句子，如“语句”、“程序”等，并给出这些句子的语法结构。

关键词：侯选式、匹配、非终结符、终结符、FIRST集、FOLLOW集

1引言

LL（1）文法是一类可以进行确定的自上而下语法分析的文法。而自上而下分析法的基本思想是从文法的开始符号S出发采用最左推导，试图一步一步地推出输入符号串α。换句话说，也就是以文法的开始符号S为语法树的根部，试图自上而下地为输入符号串（构造一棵语法树。如果能够构造这样一棵语法树：它的叶子结点从左到右排列恰好就是输入串α，则输入串α就是文法的句子，而这个语法树就是句子α的语法结构。如果不存在这样的一棵语法树，则输入符号出串α就不是这个文法的句子。）这种分析过程实质是一种试探过程，是反复使用不同产生式匹配输入符号串的过程。

若有文法

S->cAd

A->ab|a

输入串w=cad。为了自上而下地为这个串建立分析树，首先建立只有标记S单个结点树，输入指针指向w的第一个符号c。然后用S的第一个产生式来扩展该树，得到的树如图所示：

     S                        S                             S

c    A      d   

                         c    A      d                c    A    d

    (a)

                             a     b                       a

(b)                                                                                         (c)

最左边的叶子标记为c，匹配w的第一个符号。于是，推进输入指针到w的第二个符号a，并考虑下一个标记为A的叶子。用A的第一个选择来扩展A，得到如图(b)的树。现在匹配第二个输入符号a，再推进输入指针到d，把它和下一个标记为b的叶子比较。因为b和d不匹配，报告失败，回到A，看它是否还有别的选择尚未尝试。在回到A时，必须重置指针于第二个符号，即第一次进入A的位置。现在尝试A的第二个选择，得到图（c）的分析树。叶子a匹配w的第二个符号，叶子d匹配w的第三个符号。这样，产生了w的分析树，从而宣告分析完全成功。

     实现这种自上而下分析法存在许多困难：

首先，是递归问题。一个文法是含有左递归的，如果存在非终结符P

                 P＝＞Pa

含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即，当试图用P去匹配输入串时，我们会发现，在没有识别任何输入符号的情况下，又得重新求P去进行新的匹配。因此，使用自上而下分析法必须消除文法的左递归。

其次，是回溯问题。例如，对文法：S->xAy

                                A->**|*

考虑输入串x**y。若对A首先使用第二个侯选式，A将成功地把它的唯一子结*匹配于输入串的第二个符号。但S的第三个子结y与第三个输入符号*不匹配。因而，导致了无法识别输入串x**y是一个句子的事实。然而，若A首先使用第二个侯选所得的成功匹配是虚假的。由于这种虚假现象，就应把已经做的一大堆语义工作推倒重来。这些事情既麻烦又费时间，所以，最好应设法消除回溯。而LL（1）文法是一类可以进行确定的自上而下语法分析的文法，所以，必须也必须消除左递归和回溯。

1． 1左递归的消除

直接消除见诸于产生式中的左递归是比较容易的。假定关于非终结符P的规则为

                       P->Pa|

其中，卟灰訮开头。那么我们可以把P的规则改写为如下的非直接左递归形式：

                       P->逺

                       R->aR|ε      (ε为空字)

这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。

一般而言，假定P关于的全部产生式是

                       P->Pα1|Pα2……Pαm|1| 2|……遪

其中，每个α都不等于ε，而每个叨疾灰訮开头，那么，消除P的直接左递归就是把这些规则改写成：           P->1R| 2R|...| 遪R

                        R->α1R|α2R|……αmR|ε

使用这个方法，我们容易把见诸于表面的所有直接左递归都消除掉，也就是说，把直接左递归都改成直接右递归。

对于间接左递归的消除可以采用代人法把间接左递归变成直接左递归。

例如有文法：

           S->Aα|     （1）

           A->Sγ      （2）

因为S=>Aα=>Sγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归将（2）式代人（1）式，即可得到与原方法等价的方法：S->Sγα|    （3）

（3）式是直接左递归的，可以采用消除直接左递归的方法对文法进行改写，可的文法：S->逽ˊ

        Sˊ->γαSˊ|

由此可见，为了消除间接左递归，可首先查出那些具有左递归的非终结符号，然后对以这些非终结符为左部的产生式，通过逐步代人有关产生式的方法将它们化为直接左递归的产生式。最后在消除其中的全部直接左递归。

下面给出消除左递归的算法：

（1）       把文法G的所有非终结符按任一种顺序排列成P1，P2,……Pn;按此顺序执行;

（2）       FOR  i:=1  TO   n    DO

BEGIN

          FOR  j:=1   TO   i-1   DO

                把形如Pi->Pjγ。其中Pj->δ1|δ2|…|δk是关于Pj的所有规则;消除关于Pi规则的直接左递归性

       END

(3)化简由(2)所得的文法。即去除那些从开始符号出发永远也无法到达的非终结符的产生规则。

1．2消除回溯、提左因子

   为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个侯选去执行任务，并且次侯选的工作结果是确信无疑的。也就是说，若此侯选获得成功匹配，那么，这种匹配不会是虚假的；若此侯选无法完成任务，则任何其它侯选也肯定也无法完成任务。换句话说，假定现在轮到非终结符A去执行匹配任务，A共有n个侯选α1，α2，……αn,即A->α1|α2|……αn。A能够根据不同的输入符号指派相应的αi作为全权代表去执行任务，那就肯定无需回溯了。在这里A已不再是让某个侯选去试探地执行任务，而是根据所面临的输入符号α准确地指派唯一的一个侯选。其次，被指派侯选的工作成败也完全代表了A。

2  LL（1）语法分析器的设计策略

首先判别一个文法是否是LL（1）文法，如果不是LL（1）文法则需要转化为LL（1）文法。要判别一个文法是否为LL（1）文法，首先需要给出FIRST集合、FOLLOW集合。

2．1构造FIRST集

根据定义：FIRST（α）={a|α=>a...，a(-Vt}，特别是，若α=>ε，则规定ε(-FIRST（α）

对于文法符号串X（-(Vn∪Vt)＊。其办法是连续使用下面的规则，直至没个集合不在增大为止。

（1）       若X(-Vt，则FIRST（X）={X}。

（2）       若X(-Vn，且有产生式X->a…,则把a加入到FIRST(X)中；若X->ε也是一条产生式则把ε也加到FIRST（X）中。

（3）       若X->Y…是一个产生式且Y(-Vn,则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；若X—＞Y1 Y2…Yk是一个产生式，Y1…Yi_1都是非终结符，而且，对于任何j，1≤j≤i-1，FIRST（Yj）都含有ε，则把FIRST（Yj）中的所有非ε-元素都加到FIRST（X）中；特别是，若所有的FIRST（Yj）均含有ε，j=1，2，…,k，则把ε加到FIRST（X）中。