编译器实现之旅——第五章 实现语法分析器前的准备
在前面的旅程中，我们已经实现了词法分析器。词法分析器可将源代码转变为记号流，以供语法分析器使用。所以现在就让我们启程，朝着下一站——语法分析器出发吧。
1. 什么是语法
什么是语法呢？提到词法分析器，我们能够立即联想到一个个看得见摸得着的词；而提到语法分析器，又能联想到什么呢？
词法和语法的关系，就像扑克牌和打扑克牌的游戏规则之间的关系一样：词法决定了扑克牌的印刷、张数、花色、点数等等，而语法则决定了我们应该如何打出这些扑克牌，以赢得游戏胜利；这在编程语言中就是：词法决定了代码中能够出现哪些词，而语法决定了这些词的正确组织方式。由此可见：词法是具象的，而语法是抽象的。
2. 怎么表示语法
正如我们通过一段文字描述某种游戏规则一样，我们也可以用一段文字来描述一个语法。请看：
句子的语法：
1. 一个句子，由主语 + 谓语 + 宾语构成
2. 主语是：“程序员”
3. 谓语是：“没有”
4. 宾语是：“头发”
显然，这就是一套语法了。但是我们发现，这种白话文式的语法表示显然不是我们编译器一贯的作风嘛。针对这个问题，巴科斯及后人提出了用于表示语法的“巴科斯范式”和“拓展的巴科斯范式”。拓展的巴科斯范式的主要规则如下：
1. 用“::=”符号表示“是”，或“由...构成”的意思。说的专业点，叫“推导出”
2. 用“|”符号表示“或”的意思
3. 用“[ ... ]”表示中括号中的内容是可选的
4. 用“{ ... }”表示大括号中的内容可以出现0至无穷多次的重复
现在，就让我们用“拓展的巴科斯范式”来描述我们的语法吧：
句子的语法：
1. 句子 ::= 主语 谓语 宾语
2. 主语 ::= “程序员”
3. 谓语 ::= “没有”
4. 宾语 ::= “头发”
3. 语法怎么使用
我们已经有了语法，现在的问题是，语法有什么用处？又该怎么发挥这些用处呢？
首先，我们显然可以做这样一件事：判定一个记号流是否符合语法。请看：
假如我们有记号流：（“程序员”，“有很多”，“头发”），我们从语法的第一条开始，我们知道：“句子 ::= 主语 谓语 宾语”，这句话代表什么呢？其代表着：我们需要先看到一个主语，再看到一个谓语，最后看到一个宾语，如果都看到了，我们就认为这段记号流是符合语法的，否则，只要有任何一个地方不符合要求，我们就认为这段记号流是不符合语法的。那么问题来了，主语、谓语、宾语又分别是什么？显然，接下来的三条语法告诉了我们答案。我们首先检查主语，根据语法规则，我们知道：主语必须是“程序员”，记号流呢？嗯，第一个记号确实是“程序员”，我们接着往下看；语法规则又告诉我们：谓语必须是“没有”，而此时的记号是“有很多”，这就不对了，后面也不用看了，我们可以立即判定：（“程序员”，“有很多”，“头发”）这个记号流是不符合语法的。
接下来的故事就不用我多说了吧。经过一番小小的努力，我们终于发现：只有：（“程序员”，“没有”，“头发”）这个记号流是符合语法的。
确实符合语法了，然后呢？正如前面的章节所说，此时，我们就可以将这段记号流立体化，变为一棵抽象语法树了。这棵抽象语法树长什么样呢。请看：
句子
/ | \
程序员（主语） 没有（谓语） 头发（宾语）
一句话解释：语法长什么样，语法树就长什么样。
将上面的模型变为代码，我们就得到了抽象语法树节点的定义。请看：
struct AST
{
// Attribute
TOKEN_TYPE tokenType;
string tokenStr;
vector<AST *> subList;
int lineNo;
// Constructor
explicit AST(TOKEN_TYPE _tokenType, const string &_tokenStr = "",
const vector<AST *> &_subList = {}, int _lineNo = 0);
explicit AST(const Token *tokenPtr);
// Destructor
~AST();
};
AST::AST(TOKEN_TYPE _tokenType, const string &_tokenStr,
const vector<AST *> &_subList, int _lineNo):
tokenType(_tokenType),
tokenStr (_tokenStr),
subList (_subList),
lineNo (_lineNo) {}
AST::AST(const Token *tokenPtr):
tokenType(tokenPtr->tokenType),
tokenStr (tokenPtr->tokenStr),
lineNo (tokenPtr->lineNo) {}
AST::~AST()
{
for (auto subPtr: subList)
{
delete subPtr;
}
}
可见，抽象语法树节点的定义和前面Token类的定义是高度相似的。抽象语法树节点也需要标记的类别、标记字符串，以及标记所在的行数。此外，抽象语法树节点还需要一个vector，以保存这个节点的所有子节点。
4. 语法错误的表示
当我们遇到上文中的语法错误时，我们就需要一个能够报告此问题的工具函数，实现如下：
void InvalidToken(const Token *invalidTokenPtr)
{
printf("Invalid token: %s in line %d\n",
invalidTokenPtr->tokenStr.c_str(),
invalidTokenPtr->lineNo);
exit(1);
}
这个函数的实现很简单，这里就不讨论了。
5. 消除左递归
这巴科斯范式可不是省油的灯啊。这一节和下一节，我们将分别来看看巴科斯范式中的两个常见问题。首先来看消除左递归。
假设有以下语法：
Six ::= Six \'6\'
| \'6\'
这个语法说了什么？其表示，一个“Six”可以推导出一个“Six \’6\’”；而“Six”又是什么？是“Six \’6\’”；而“Six”又是什么？是“Six \’6\’”…
怎么回事？我们连一个记号字符串都还没看到呢，就光顾着在这无限循环了，这就是“左递归”问题，是我们需要消除的。
怎么消除呢？首先需要明确的是，语法表示并不是神圣不可侵犯的，而是可以进行等价变换的。那么，上面这个语法该怎么变换呢？让我们来找找规律：
1. Six ::= \'6\'
2. Six ::= Six \'6\' ::= \'6\' \'6\'
3. Six ::= Six \'6\' ::= Six \'6\' \'6\' ::= \'6\' \'6\' \'6\'
...
找到规律了！我们发现：
- 每一次使用“Six \’6\’”替换“Six”，就会在“Six”的右边多出一个“6”
- “Six”终将被“6”而不是“Six \’6\’”替换
也就是说，“Six”推导出的应该是：1至有限多个“6”。写成语法就是：
Six ::= \'6\' { \'6\' }
可见，我们成功的消除了左递归。现在，语法的推导就可以正常开始并进行下去，而不会出现无限循环的情况了。
6. First集合
解决了左递归问题后，让我们再来看看接下来的这个问题。
假设有以下语法：
1. A ::= B | C
2. B ::= \'b\'
3. C ::= D
4. D ::= \'d\'
“A ::= B | C”？选B还是C？我们无从获知。因为“B”和“C”并不代表某个具体的字符，而是另外的两条语法。这时候怎么办呢？这时候呀，我们可就要刨根问底了。
我们先来看看“B”又是什么，我们发现：“B ::= \’b\’”，也就是说，如果我们看到了“b”，我们就选“B”。
那么，“C”又是什么？我们发现：“C ::= D”，不行，我们需要继续看。“D”又是什么？我们发现：“D ::= \’d\’”。也就是说：
- 如果我们看到了“d”，我们就选“D”
- 由于“C ::= D”，所以如果我们看到了“d”，我们也可以选“C”
经过一番刨根问底，现在我们知道了：对于“A ::= B | C”这条语法而言，如果我们看到了“b”，我们就选“B”；如果我们看到了“d”，我们就选“C”。当然了，如果我们看到的既不是“b”也不是“d”，这就是语法错误了。
上面我们得到的结果，其实就是First集合了。First集合可以帮助我们在“多选一”类语法中立即做出正确的选择。
我们的旅程到这里就快要暂告一段落了，最后，我们可以考虑两个问题。请看：
- 我就不用First集合，行不行？
行，当我们看到“A ::= B | C”时，管他呢，我们就选“B”。如果选“B”是错的，那么我们就想办法把这个“选错了”的信息传回来，然后我们再换成“C”试试看。
这样做的缺点显而易见：计算量可能会非常大，且毫无意义。如果“A ::= B | C”是语法的顶层，那么我们甚至有可能直到看到最后一个记号，才发现选错了，然后一切推翻重来。
- 刨根问底，会不会还是问不出个所以然？
不会。因为…
…接连便是难懂的话，什么“乔姆斯基体系”，什么“上下文无关文法”之类…
至此，我们就完成了所有准备工作，可以开始实现语法分析器了。请看下一章：《实现语法分析器》。