做个编译器——递归下降语法分析

Table of Contents

General #

为什么需要语法分析器 #

原因1：正确处理“嵌套”

正规式无法表达嵌套语法。

例如要实现语法(^i)^i，即处理括号的配对。但是你会发现正规式无法表达这种语法。
这是因为NFA无法完成诸如“计数”等的功能，即无法保证两个i相等。

例如如图的FA想要识别这8个1构成的序列，你会发现无论有多少个1，它都能识别成功，只要保证1的数量是偶数即可（因为必须保证到了输入末尾的同时到达了终态才算Accepted）。因为NFA没有一种机制能记录你经过了多少次状态转换。像如图这样的情形，顶多能保证奇偶性（推广到一般情况，就是mod k性），但是不能保证具体数值。换句话说，只要能mod k，都算是Accepted。

原因2：词法分析得到的结果不足以形成逻辑

词法分析的作用是把输入的程序中的词汇都匹配到了编程语言中的合法的“角色”，或者说“符号”，保证了合法性。
但是符号之间有什么关系，不得而知。

语法分析器的任务 #

任务：接受从词法分析器得到的token序列，输出语法树。例如：

第一行是程序原文，通过词法分析器得到了第二行，也就是把各个词都化成了“符号”。
现在需要语法分析器来把上述的“符号”序列解析成层次结构，得到一颗语法树。

编译器也可以不显式生成一棵语法树。也就是可以做“不完全分析”。

上下文无关文法（CFG） #

对于上下文无关文法，无二义性CFG包含于它，再往下是LR、LALR和SLR。

Context-Free Grammers（CFG）能够很好地表示程序中的嵌套（递归）定义方式。例如下面这种情况就是递归定义：

组成 #

上下文无关文法由四要素构成：T/N/S

终结符集合 a set of terminals，T
非终结符集合 a set of non-terminals，N
一个开始符号 S，是非终结符集合中的元素
产生式集合 a set of productions

产生式 #

要求左边必须是非终结符，右边可以是终结符、非终结符或{ε}。

产生式可以用于“代入”。也就是在任意地方出现的产生式左边的元素都可以被原地替换为右边的。

终结符和非终结符 #

终结符只会出现在产生式的右边，所以一旦被推导出来就永久保留在那里了，无法再被替换了

终结符一般是语言的lexeme。

直观理解，非终结符可以认为是一种抽象的概念，其代表了”一类符号“，而不仅仅是”一个符号“。

例如非终结符E代表Expressions，其可以推导出任何的表达式，例如int + int。

而最终的表达式肯定是终结符构成的。程序员编写的程序在编译器看来，都是由终结符构成的。

推导 #

所谓推导，就是一系列对产生式进行应用的序列，如下。

语法树🌲 #

任意的推导都可以被写成语法树的形式。遵循如下规则：

树的根是开始符号S
对于每一个推导例如X->Y1Y2Y3，为结点X增加孩子Y1、Y2、Y3.

例子如图。

对于每一步推导，依次修改语法树，最终得到完整的语法树。
左边的式子的排列不一定要和右边的层数有任何联系。因为你完全可以选择一次性展开一个非终结符，也可以选择一次性展开所有的非终结符。

即：也就是如果要完全变成终结符，推导的步数其实是随意的，但是语法树的层数却必然是固定的。

语法树🌲的性质 #

叶子结点都是终结符，内部节点都是非终结符
从左向右遍历所有叶子结点，即可得到输入串，即token序列串
语法树具有层次性，例如上面那棵树的乘法会比加法的层数更加大。这能体现运算的优先级。

【算法】上下文无关文法的推导 #

从开始符号S开始
不断地把其中的非终结符利用产生式进行替换
重复2，直到不再包含任何非终结符

推导和语法树🌲的关系 #

注意：一个推导可以唯一确定一棵语法树，但是一棵语法树可以由不同的推导得出。

因此，我们主要关心以下两种推导：

最左推导和最右推导的定义和联系 #

每次替换最左边或最右边的非终结符。
尽管可以使用任意的顺序去替换非终结符，我们最习惯使用最左、最右推导来做。

最左推导和最右推导是等价的，因为他们能生成完全相同的语法树。

星号推导 #

如图，从a0到an需要经过>=0步的推导，则称0到n是星号推导。
注意，可以取0。

除0推导 #

例如这种，带有一个‘+’的，称为除0推导。
也就是需要>=1步的推导。

上下文无关文法的语言 #

上下文无关文法可以决定一系列string，因此可以定义为一些string构成的集合，因此也算得上是一门语言。

Let G be a context-free grammar with start symbol S.

Then the language L(G) of G is:

可以看出，上下文无关文法的目的在于从开始符号推导出纯终结符构成的字符串。

可以认为，上下文无关文法的语言是终结符构成的string的集合。

二义性文法 Ambiguity Grammar #

例子🌰 #

以id*id+id为例，根据不同的推导方式，其可以生成两颗不同的语法树。

推导方式多样，没有关系；但是如果语法树不唯一，则就是具有二义性了。

这里的二义性很显然由乘法和加法的运算顺序导致。

从层数上可以看出，如果先使用乘法的产生式，就会得到右边的语法树；如果先使用加法的产生式，就会得到左边的语法树。

定义 #

语法树不唯一的文法称为二义性文法。换言之，对于给定的输入串，它有不止一种正确的推导方式。

消除二义性 #

例子：id*id+id、if-else-then语句

二义性文法对编程语言很不友好，会造成各种错误。但是又不得不用它，例如if-else语句、连加语句（int+int+int）等。

可以通过重新编写文法的方式来实现二义性的消除。但是，不存在自动把二义性文法转换为非二义性的算法。这只能我们手工去做。而且，显然，经过转换后，文法变得非常复杂，难以阅读与维护。
此外，也可以不去重新编写文法，而是引入结合性与优先级声明等方式来消除二义性。

抽象语法树 AST #

Abstract Syntax Tree

抽象语法树忽略的语法树的一些细节。类似于语法树，同样用于追踪文法的推导和程序的层次关系。

例如如图的语法树，如果真的交给计算机去做下一步编译工作，实际上没有必要存储这么多信息。
例如int5可以直接写到E的位置，因为E真的没有什么用，它对下一步的编译没有参考价值。
我们想要的只是表达各终结符的层次关系、逻辑关系的化简版本的语法树。

例如，转化成如图的抽象数据结构，这就称为AST。这是编译器中非常重要的数据结构。

递归下降语法分析 #

【算法】语法树的“自顶向下”遍历 #

自顶向下的顺序是什么？语法树是从根向叶结点、从左向右构造的。所以其自顶向下就是这个顺序。

例如这颗语法树的自顶向下顺序是t2 t5 t6 t8 t9.它由如下算法得出：

从根节点开始往孩子依次找：对于每个结点
如果其是终结符，则输出；如果其不是终结符，则找他的各孩子结点，从左向右遍历其孩子，并按照步骤1处理。

这样得到的顺序，层数越靠近根节点的越靠前，对于同一层，越靠左边的越靠前。

【算法】语法树递归下降分析 #

对于给定的文法，例如：

需要动态维护一个指针，其指向输入串的比较（匹配）对象。一开始指向第一个token。

从树根（开始符号，这里是E）出发进行分析。
选择行：对于非终结符，根据各行产生式的前件选择产生式所在行。例如T就选择第二行。
选择列：对于每一行产生式，尝试进行代入推导。如果失败，则返回此处，继续尝试该行的下一个产生式。（根据后件从左到右遍历产生式，如有必要则进行递归返回）
比较：如果某次推导出现了终结符，则开始进行比较。如果比较失败，则转到3的“失败”，并重置输入串指针到比较前的位置（不一定是开头）；如果成功，则移动输入串指针，并在语法树中选择下一个叶子结点（紧跟着的右边的）为比较对象。如果发现比较对象是终结符，则继续步骤4；如果发现比较对象是非终结符，则返回步骤2.

例如要解析(int5)。一开始指针指向(.

这里选择第一行的第一个产生式E->T，对于T继续推导，选择第二行第一个产生式T->int.

此时得到了终结符int，但是现在指针指向(，匹配失败，回退一层，到如图状态。

现在尝试第二行第二个产生式T->int*T，则如图进行推导。

推导得出了终结符！转换为匹配模式。

因为指针指向(，匹配失败。同样回退一层，然后尝试第二行第三个产生式T->(E)。

匹配成功：和指针指向的一样，都是(。

指针移动一个元素，现在指向int5。同时，比较下一个元素。

发现不是非终结符了！转换为推导模式！于是开始推导。

应当选择前件是E的产生式，因此从第一行寻找，首先尝试第一行第一个产生式E->T，进行推导如图。

发现还是非终结符，而且是T，所以应该从第二行的产生式中找，首先尝试第二行第一列产生式T->int，如图推导。

现在是终结符了，转换为比较模式！因为现在指针指向了int5，匹配成功！指针继续移动，指向)，同时语法树选择选择下一个比较对象：)。

匹配成功。

且因为现在语法树已经推导完毕（叶结点都是终结符），指针也走到了输入串末尾，Accepted！算法结束。

【代码实现】语法树递归下降分析 #

数据结构

next指针：指向输入串中，要比较的token

term函数

bool term(TOKEN tok){return *next++ == tok;}

执行*next和tok的匹配操作，并向前移动next指针。

E的第2个产生式函数，例如E->T+E

bool E2(){
    return T()&&term(PLUS)&&E();
}

E的产生式函数（根产生式），例如E有3个产生式，则：

bool E(){
    TOKEN* save = next;
    return (next = save, E1())
    || (next = save, E2())
    || (next = save, E3())
}

总之

term函数用于匹配终结符，同时移动next指针。
第i个产生式函数用于实现该产生式的递归下降与比较操作。遇到非终结符号就调用其根产生式，遇到终结符就调用term函数来比较终结符。
根产生式函数用于尝试其各个产生式，进行推导与比较。每次的next = save是在比较之前把next指针再恢复到上次的地方（不一定是输入串开头）。

运行这个语法分析程序

调用开始符号E的根产生式函数。
递归结束时，查看next指针的位置。如果指向输入串末尾，则Accepted，否则Rejected。

目前存在的问题 #

如图，仍以该文法为例，并使用上面的代码实现来做一个递归下降语法分析器。

如果匹配int*int，会出现问题。如图。

根据算法，应当会先尝试T的第一个产生式，此时int匹配成功。

然后，T的根函数就返回了！然后E的根函数就返回了！因为他们都是有短路效应的，对于多个并列的“与”式，只要前面的成功了，后面的就不执行了。

可是现在我们只匹配了一个终结符号，输入串中还有俩token等着呢，可是程序却提前退出。因为退出的时候next没有指向输入串末尾，导致Rejected。但是它这个本来是合法的，本应当Accepted。

因此，这种实现方法存在的问题是：只要有一个产生式能局部性地匹配成功，该非终结符的其他产生式即便更加优秀（例如T的第二个产生式T->int*T就看起来更容易成功），也没有机会被尝试了。

左递归文法 #

造成死循环 #

考虑文法S->Sa。那么其代码实现如下：

bool S1(){return S()&&term(a);}
bool S(){return S1();}

现在启动语法分析器。也就是调用S()，但是S()会接着调用S1()，S1()又反过来调用S()，于是导致陷入死循环。

也就是说，递归下降算法不适用于左递归文法。

定义 #

因此，凡是形如S-+>Sa的文法，就称为左递归文法。（注意是除0推导。）

特点 #

根据S->Sa，那么一个S可以产生Sa，Saa，Saaa，…。每次推导，都会产生一个全新的S（非终结符），而且这个非终结符位于终结符的左边，这意味着必须先去消除这个非终结符才能开始比较。但是每次要消除，就又产生一个新的，导致永远也消除不完。

一直进行推导的原因是非终结符在终结符的左边，需要先把左边这个非终结符推导、比较完了，才能轮到后面那个。可惜左边这个非终结符一直卡在“推导”的死循环里面，永远到不了他比较的那一步。

消除左递归 #

可以把左递归用右递归来代替（重写为等价的右递归）。

对于左递归文法 S->Sα|β，实际上是β后面跟着若干α，可以拆分成S->βS',S'->αS'| ε，也就是先把β拿出来，然后后面再去产生那些α。

但是，产生的方式不同。对于左递归，是在S右边不断产生α；对于右递归，是在S’左边不断插入α。

一般地，对于推广的左递归文法 S->Sα1|Sα2|...|β1|β2|...，可以拆分成 S->β1S'|β2S'|...,S'->α1S'|α2S'|...| ε。即对于不同的α、β，构成和上述简单拆分相同形式的产生式即可。

要当心隐式左递归 #

例如有如下文法。

S->Aα|δ
A->Sβ

因为存在推导 S->Sβα，所以也是左递归文法。只是你第一时间看不出来。