编译器实现之旅——第五章实现语法分析器前的准备

2021 年 2 月 19 日
筆記
编译原理

在前面的旅程中，我们已经实现了词法分析器。词法分析器可将源代码转变为记号流，以供语法分析器使用。所以现在就让我们启程，朝着下一站——语法分析器出发吧。

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”是语法的顶层，那么我们甚至有可能直到看到最后一个记号，才发现选错了，然后一切推翻重来。

刨根问底，会不会还是问不出个所以然？

不会。因为…

…接连便是难懂的话，什么“乔姆斯基体系”，什么“上下文无关文法”之类…

至此，我们就完成了所有准备工作，可以开始实现语法分析器了。请看下一章：《实现语法分析器》。

Tags: 编译原理