1.写在开头

在上篇文章结尾我们成功实现了一个非常简单的词法分析器，接下来便是要把得到的token们按照文法的规则识别，以确定一句话是否能够通过所有规则同时形成类似语法树的结构并输出，即语法分析。

先回顾上篇文章的结果

//书上&&上篇文章的例句
begin x:=9; x:=2*3; b:=a+x end #
//词法分析得到的token
(1,begin)(10,x)(18,:=)(11,9)(26,;)(10,x)(18,:=)(11,2)(15,*)(11,3)(26,;)(10,b)(18,:=)(10,a)(13,+)(10,x)(6,end)(0,#)(0,#)

这里我们语法的规则采用扩展的巴科斯范式（ABNF）的规则：

1<程序>::=begin<语句串>end
2<语句串>::=<语句>{;<语句>}
3<语句>::=<赋值语句>
4<赋值语句>::=ID:=<表达式>
5<表达式>::=<项>{+<项>|-<项>}
6<项>::=<因子>{*<因子>|/<因子>}
7<因子>::=ID|NUM|(<表达式>)

1.1 递归下降分析法

那么我们记下来需要做的便是按照ABNF构造有穷自动机，首先想到的便是对任意token组（ABNF中的程序） $L$ 做规则上的“遍历”检查，我们先查询它是否满足第一条规则，如果满足则将内部剩下的token子组（ABNF中的语句串）送入规则2检查…以此类推。这种想法是非常自然的，毕竟就是我们肉眼检查语法时采取的方案，也被称作递归下降分析法。伪代码非常容易，就是递归程序那一套：

//第一条规则
程序(){
    tk=GetToken(tokens);
    if(tk.type对应begin){
        语句串();
        tk=GetToken(tokens);
        if(tk.type对应end){
            输出success;
            return;
        }
        //这里你也可以详细一些，保存报错原因之类
        else 输出error;
    }
    else 输出error;
    return;
}
//第二条规则
语句串(){
    语句();
    while(tk.type对应';'){
        tk=GetToken(tokens);
        语句();
    }
    return;
}
//第三条规则
语句(){
    赋值语句();
}
//后续规则相似的递归写法
...

可以看到递归下降分析法是典型的递归算法风格，好处在于方便逻辑理解以及程序的编写方便，但是在算法复杂度的角度则并不上乘，同时随着规则数的增长程序文本量也不断上升。因此在这里我们考虑一种更好的方法：预测分析法。不过谈论该算法之前我们需要一些前置理论。

2.前置理论

2.1 所谓自上而下

自上而下的思路就是人脑自然产生的思路，也就是根据产生式将初始符号S一步步推理出所需要的句子或句型，这种推理我们一般称为推导，用 $\Rightarrow$ 符号表示，他的逆过程被称为规约。（句子就是非终结符组成的符号串，如 $abcd$ ，而句型就是非终结符和终结符混合的“句子”，一般作为推导过程的中间状态，如 $aAeDc$ 这样的结构）

2.1.1 推导

举一个例子，有文法G：

1 2	S->A A->a\|b\|aA

对这个文法，我们给一个句子 $ab$ ，那么他是如何得来的呢，显然是先从S得到A，再从A得到aA，最后将A变为b，这便是推导，写成符号语言便是： $S\Rightarrow A\Rightarrow aA\Rightarrow ab$ 。也就是说根据产生式的所进行的每一步推理便称一次直接推导，那么将多次推导整合在一块便有 $\Rightarrow^+$ （1次或1次以上直接推导）以及 $\Rightarrow ^*$ （0次或0次以上直接推导）， $\Rightarrow ^*$ 也被称为广义推导 ，换言之对这里的例子我们可以说A广义推导出了 $ab$ 。

除此以外还有最左推导和最右推导，顾名思义最左（最右）推导表示每一次推导都优先考虑句型中的最左（最右）非终结符对应的产生式，其中最左推导也被称为规范推导，对应的逆过程为最右规约。

2.1.2 自上而下算法的限制

回顾上文中的递归下降算法，我们发现他的特点是当接收到一个终结符 $a$ （此处的终结符就是某个已知的token单位）后，便会找到对应的递归函数继续处理子token组了，我们自然就会感觉到该文法一定有一个较为严格的语法规则。比如举个例子：

1
2
3

S->aAb
A->cB|cD
...

观察这个文法，我们发现一个致命问题：如果用递归下降法，那么对于规则2也就是A->cB|cD而言我们无从下手！因为此时接收到一个终结符c时我们不知道要跳转到函数B()还是D()中，只能遍历尝试所有可能，那么假设正确的文法推理要进入D()中，那么先进入C()的过程会变成无效过程，即产生回溯情况。出于程序员的本能我们自然是希望尽量避免回溯发生的，所以我们发现普通的上下文无关文法是不满足我们自然想到的梯度下降算法。事实上包括预测表分析法在内的所有自上而下分析法都不满足于2型文法，它们需要一个约束更高的文法：LL(1)文法。

#注意1#

自上而下的思想虽然容易理解但是想要在计算机上复现这种思路则势必要对适用范围进行缩小，这也是符合我们的编程经验的，计算机不同于人脑的架构和做事逻辑导致很多时候符合“正常脑回路”的方式往往需要做很多其他方面的妥协，事实上后续我们也会学习适用大部分2型文法的自下而上分析思路，不过这就是后续的话题了。

2.2 回溯问题产生的两大来源

在谈LL(1)文法之前我们先来思考为什么会产生回溯，只有明白了回溯产生的原因才能在面对解决方案时更加游刃有余。

2.2.1 最左公因子

正如上文中的困局，归根到底在于A->cB|cD中两种选择中最左非终结符同时是 $c$ 导致自动机下一状态无法确定（还记得词法分析器中的DFA和NFA吗），我们称 $c$ 为最左公因子。

2.2.2 epsilon问题

我们观察这样一个文法G:A->Bx, B->epsilon|x（这里 $epsilon$ 表示希腊字母 $\varepsilon$ ）。我们会发现如果此时推导一个句子 $x$ ：它只有一个字母 $x$ ，在句子的推导中B显然采取产生式B->epsilon，可是对于程序而言实际推导过程中A所在的状态接收到终结符 $x$ 时他可能就采纳产生式B->x了，那么推导结果就变成 $xx$ 无法匹配我们的句子白费功夫了。换句话说若存在非终结符X广义推导出 $\varepsilon$ 的同时后一个符号a与X某一产生式最左因子相同，那么DFA依然会出现回溯现象，也就是具有 $\varepsilon$ 问题。

总之在上下文无关文法中这两种问题产生了回溯现象，于是我们提出更为严格的LL(1)文法标准以满足自上而下的分析思路。

2.3 LL(1)文法

为了判断一个2型文法是不是LL(1)文法，我们提出了两个非常重要的集合：FIRST集和FOLLOW集。后续这两个集合将会伴随我们学完几乎所有的语法分析算法。

2.3.1 FIRST集–最左公因子的搜查令

正如标题所言，FIRST集的建立便是为了解决最左公因子的问题。回到上文最左公因子处的文法，问题就在于产生式A->cB|cD中同时含有c，因此对于某文法中左部相同的规则们而言（ $A \rightarrow \beta_1,A\rightarrow\beta_2,A \rightarrow \beta_3,A \rightarrow \beta_4...$ ）一旦发现之间存在右部首个终结符相同，那么该文法必然就存在回溯现象，即不是LL(1)文法。需要注意的是这里的首个终结符指的是 $\beta_i$ 广义推导下的首个终结符。

于是得到FIRST集的概念：对任意符号串 $\alpha$ 它所有首个终结符组成的集合称为 $FIRST(\alpha)$ 。一般的我们给出数学概念：

$FIRST(\alpha)=\lbrace \alpha\Rightarrow^{*}a... 且a\in V_T\rbrace$

举个例子，比如说有规则组：

(0) S->A,
(1) A->cB,
(2) A->De,
(3) A->a,
(4) D->b|epsilon

那么第1条显然后续无论怎么推导，右部首个终结符为c，同样的第3条后续推导可以得到首个终结符为a，此时便有 $\lbrace a,c \rbrace \subset FIRST(A)$ 。继续观察第2条，我们发现在该条产生式中D的首终结符也就是A的首终结符，即想要推导A的首终结符就得先算出D的首终结符。因此我们利用第4条先计算出了 $FIRST(D)=\{b,\varepsilon \}$ ，那么终结符 $b$ 自然也成为A的首终结符之一，但是需要注意的是这里的 $\varepsilon$ 不能简单等同于 $b$ ，由于 $\varepsilon$ 作为空串的特殊性导致若D选择它时第2条产生式便改变为了A->e，那么此时e就加入到了 $FIRST(A)$ 中。综上我们得到 $FIRST(A)=\{ a,b,c,e\}$ 。

也就是说对任意非终结符 $X$ 有产生式： $X\rightarrow \alpha \beta...$ 有 $FIRST(X)\supset FIRST(\alpha)$ ,若出现 $\alpha \Rightarrow^*\varepsilon$ 的话，那么有 $FIRST(X)$ $\supset $$FIRST(\beta)$。结合上文的例子这句话应该就很好理解了。

2.3.2 FOLLOW集–破解epsilon问题的钥匙

在上文中我们知道另一种造成回溯问题的原因在于若某产生式左部非终结符B可以推导出 $\varepsilon$ ，这将导致分析句子时自动机接受到一个符号 $x$ ，它的实际位置可能在B的后面而非B的内部，也就是说自动机进入B中进行推理的过程都是无效过程必然发生回溯。那么既然自动机接受的条件符号可能在后面，那么我们就把后面的符号找出来比对就好了嘛。

于是我们有了FOLLOW集的概念：对...->...Aa...而言A之后所有可能出现的首符号作为一个集合，即 $FOLLOW(A)$ 。也就是说上述所有产生式中A之后的字符都属于 $FOLLOW(A)$ 集。于是给出一般的数学定义：

$FOLLOW(A)=\{a|S\Rightarrow^*...Aa..., 且a\in V_T\}$

回到上文2.2.2的例子，对文法G:A->Bx, B->epsilon|x而言 $FOLLOW(B)=\{x\}$ 。因此DFA在对句子 $x$ 进行语法分析时，一旦接受到转移符号 $x$ 那么分析系统必然出现回溯现象，也就是说这里的FOLLOW集合可以在程序运行前便发现该文法存在epsilon问题。进一步探讨FOLLOW集的定义后对某一状态X获得对应的 $FOLLOW(X)$ 有如下规则：(alpha表示 $\alpha$ )

1.扩充定义，如果X是初始符号S，那么#属于FOLLOW(X);
2.根据定义有A->...Xa... 那么a属于FOLLOW(X);
3.根据定义有A->...Xalpha 那么FIRST(alpha)属于FOLLOW(X),alpha指代X后面的子串;
4.如果有A->...X 那么FOLLOW(A)属于FOLLOW(X);

前三条根据定义是非常好理解的，这里重点摊开说说第四条。首先对于 $FOLLOW(A)$ 我们用 $\Gamma_1$ （注意 $\Gamma_1$ 是一个集合，单纯为了在推导式中表示follow集）代替，于是由定义我们知道是初始符号 $S\Rightarrow^*...A\Gamma_1...$ ，那么当 $A\rightarrow ...X$ ，自然可以得到一种推导： $S\Rightarrow^*...X\Gamma_1...$ 那么我们可以确定 $\Gamma_1$ 的元素都是 $X$ 后面的一个符号，也就是说这里的 $\Gamma_1$ 一定是集合 $FOLLOW(X)$ 的子集，也就是第四条中的 $FOLLOW(A)$ 属于 $FOLLOW(X)$ 了。

当然你或许会好奇思考，进一步发问：那为什么不是相等而是属于关系呢？一方面我们的推导过程只能证明一半，即A属于X，另一方面我们可以这么理解：整个产生式中除了A可以推导出X也有可能有别的符号，比如B也能推导出X，那么对于X的FOLLOW集就不可能仅仅依靠A来决定了。

接下来为了理解FOLLOW集的求法，不妨考虑以下文法：(epsilon表示 $\varepsilon$ )

1 2	A->aB\|d B->bBA\|epsilon

那么首先由于A是初始符号，故根据规则1有 $\{\#\}\subset FOLLOW(A)$ 。接着看B，我们发现A->aB于是根据规则2有 $\{\#\}=$ $FOLLOW(A)\sub FOLLOW(B)$ ；接着通过B->bBA知道 $FIRST(A)=\{a,d\}\in FOLLOW(B)$ ；综上得到FOLLOW(B)的集合为 $\{\#,a,d\}$ 。

2.3.3 SELECT集合–双剑合璧

$FIRST$ 集和 $FOLLOW$ 集的存在终究是为了判断文法是否存在上述两种问题，因此我们自然提出一种新的集合将两者联立起来直接判定是否为LL(1)文法，即 $SELECT$ 集合。

先给出 $SELECT$ 集合的数学定义：

$SELECT(A\rightarrow \alpha)= \left\{ \begin{matrix} FIRST(\alpha), \alpha\nRightarrow \varepsilon \quad(1)\\ FIRST(\alpha) /\{\varepsilon\} \bigcup FOLLOW(A), \alpha\Rightarrow\varepsilon \quad(2) \end{matrix} \right.$

有了定义我们来分析它的实际含义， $SELECT(A\rightarrow\alpha)$ 就是**“选择它的原因”，这里的“它”自然指的是这一条产生式**，即对状态A而言为什么选择 $A\rightarrow\alpha$ 。那么如果判断出某一文法是LL(1)文法，则对于状态A它对应的产生式应该都是不同的，反应在 $SELECT$ 集合上应该是A的任意两个产生式有 $SELECT(A\rightarrow\alpha_1)\bigcap SELECT(A\rightarrow\alpha_2)=\emptyset$ ，毕竟只有在两个产生式最左公因子完全不同的同时也不存在 $\varepsilon$ 问题时，该文法才可能视为LL(1)文法。自然当所有状态的 $SELECT$ 集合都检查完毕全为空集后，我们就可以确定该文法是一个LL(1)文法了。总之兜兜转转这么多我们现在应该了解到LL(1)文法的核心便是：相同左部的任意两条产生式SELECT集合无交集！。

为了方便理解我们来看之前的那些例子：

1)最左公因子问题A->cB|cD，根据前文我们知道推导时A状态有两条路但存在最左公因子 $c$ ，那么我们观察他们SELECT集合： $SELECT(A\rightarrow cB)=FIRST(cB)=\{c\}$ ( $cB\nRightarrow\varepsilon$ )，同理有 $SELECT(A\rightarrow cD)=FIRST(cD)=\{c\}$ ，显然两者的交集不为空，故不为LL(1)文法。

2) $\varepsilon$ 问题A->Bx, B->epsilon|x，A只有一条产生式故无需考虑SELECT集合，而对于B：由于第一条产生式可以直接推导出 $\varepsilon$ ，所以 $SELECT(B\rightarrow \varepsilon)=FIRST(\varepsilon)/\{\varepsilon\}\bigcup FOLLOW(B)=\{x\}$ ，而第二条产生式无法广义推导出 $\varepsilon$ ，那么自然 $SELECT(B\rightarrow x)=FIRST(x)=\{x\}$ ，两产生式交集不为空，于是此文法不为LL(1)文法。

通过这两个例子我们会发现SELECT集设计的精巧：对左部均为X的一组产生式而言，如果X不会广义推导出 $\varepsilon$ 那么只需要判断最左公因子是否存在的问题，因此定义中的 $(1)$ 就能解决。如果会出现 $\varepsilon$ 问题那么就需要考虑到 $\varepsilon$ 之后的单个符号，也就是 $FOLLOW$ 集元素，自然此时就不光只有 $FIRST$ 集了。而且FOLLOW集的需求是来自于 $FIRST集$ 中的 $\varepsilon$ ，因此 $(2)$ 中是FIRST集去掉了 $\varepsilon$ 在与 $FOLLOW$ 相交。至此，我们应该对 $SELECT$ 集合有了较为深刻的理解，它的构造是符合需要且自然的。

#注意2#

这里我们尝试花费很大的篇幅（甚至有些啰嗦）来介绍 $FIRST,FOLLOW,SELECT$ 三种集合的“前因后果”就是为了能够更好的理解，站在理解的角度去学习要远比死记硬背效果来的更好，效率来的更高。如果一开始有些难以接受，不妨多看几遍亦或是在之后的学习中返回来继续琢磨，总之我们需要牢记一点，一切的设计都是来源于目的本身，这些结构或算法都可以说是自然的，唯有理解才能真正掌握前人的智慧结晶。

总结

在具有了以上有关LL(1)文法的前置理论之后，我们就可以开始探讨自上而下思路中比较好的方法：预测分析法。这篇博客写之前是打算一次性解决自上而下的部分，但没想到光是三个集合便说了如此多的篇幅。。。再写下去可能我还没累之前读者都看累了233，所以有关预测分析法的内容就放在下篇吧！

个人编译原理课程总结，如有不足还望海涵，欢迎提出宝贵意见。