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

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

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'
    ...

找到规律了!我们发现:

  1. 每一次使用“Six '6'”替换“Six”,就会在“Six”的右边多出一个“6”
  2. “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'”。也就是说:

  1. 如果我们看到了“d”,我们就选“D”
  2. 由于“C ::= D”,所以如果我们看到了“d”,我们也可以选“C”

经过一番刨根问底,现在我们知道了:对于“A ::= B | C”这条语法而言,如果我们看到了“b”,我们就选“B”;如果我们看到了“d”,我们就选“C”。当然了,如果我们看到的既不是“b”也不是“d”,这就是语法错误了。

上面我们得到的结果,其实就是First集合了。First集合可以帮助我们在“多选一”类语法中立即做出正确的选择。

我们的旅程到这里就快要暂告一段落了,最后,我们可以考虑两个问题。请看:

  1. 我就不用First集合,行不行?

行,当我们看到“A ::= B | C”时,管他呢,我们就选“B”。如果选“B”是错的,那么我们就想办法把这个“选错了”的信息传回来,然后我们再换成“C”试试看。

这样做的缺点显而易见:计算量可能会非常大,且毫无意义。如果“A ::= B | C”是语法的顶层,那么我们甚至有可能直到看到最后一个记号,才发现选错了,然后一切推翻重来。

  1. 刨根问底,会不会还是问不出个所以然?

不会。因为...

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

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

相关推荐

发表评论

路人甲

网友评论(0)