自己动手写编译器:语法解析的基本原理

在前面系列章节中我们完成了词法解析。词法解析的基本任务就是判断给定字符串是否符合特定规则，如果符合那么就给这个字符串分配一个标签(token)。词法解析完成后接下来的工作就要分配给语法解析，后者的任务就是判断一系列标签的组合是否符合特定规范。

语法解析遵守的规则叫巴克斯-诺尔范式，它由三部分组成，最左边的部分叫非终结符，然后跟着一个箭头，箭头右边是一系列终结符或者非终结符。它的意思是左边的概念可以分解成右边一系列概念的组合，举个具体例子：
人 -> 头 上半身 下半身
头 -> 头发 眼睛 耳朵 鼻子 嘴巴
上半身 -> 双手 胸部 肚子
下半身 -> 屁股 双腿

我们看上面的例子，在第一个表达式中左边是一个抽象概念“人”，箭头右边是人的组成部分或者说“人”可以分解成三个相对更具体一些的概念，也就是头，上半身，下半身。然后概念“头”又可以进一步分解成其他概念的组合，例如头发，眼睛等。这里需要注意的是，所有出现在箭头左边的概念都叫“非终结符”，所有只在箭头右边出现而且从来没有在箭头左边出现的概念叫“终结符”。非终结符可以进行分解，而终结符不能再继续往下分解。由上面一系列表达式形成的集合就叫”语法“，在语法解析中特别强调“上下文无关语法”，这个概念的意思是，语法规则只规定词法解析只分析标签的组合规律，至于这些标签的组合到底表达什么含义它不管。

例如 ：
句子 -> 主语 谓语 宾语
上面的语法描述的是，一个中文句子可以分成三部分分别是主语，谓语和宾语，但上面的分解并不能告诉我们一个具体句子的内容是什么，也就是语法只关心句子的逻辑构造而不关心句子要传递的意义。这里还需要注意的是，箭头右边一系列概念的顺序很重要，顺序是语法规则的组成部分，例如合乎逻辑的“人头”必须满足鼻子在眼睛后面，如果这个顺序颠倒了，那么这个“头”就不是人头，而是异形的头。

语法解析的基本过程就是给定一个字符串，先对其进行词法解析得到一系列标签组合，然后根据给定语法表达式看看这些标签组合能否顺利分解，我们看一个具体例子，下面是针对数字和加号进行组合的加法算算数表达式语法：
STMT -> EXPR SEMI
EXPR -> FACTOR PLUS EXPR | FACTOR
FACTOR -> NUMBER

现在我们有一个字符串：“1+2;", 首先对这个字符串做词法解析得到 NUMBER PLUS NUMBER SEMI，现在我们需要判断它是否遵守上面语法，首先从第一个表达式开始，由于最后一个标签是 SEMI，因此它满足第一个表达式右边的 SEMI，现在需要判断 NUMBER PLUS NUMBER 是否能满足 EXPR 的规则。

我们看 EXPR 的右边分解。首先 FACTOR PLUS EXPR 跟 NUMBER PLUS NUMBER 中的 PLUS 匹配，于是接下来需要判断第一个 NUMBER 是否能满足 FACTOR 的规定，同时判断第二个 NUMBER 是否满足 EXPR 规定。

我们看 FACTOR 的分解，它可以直接分解成 NUMBER，所以第一个 NUMBER 满足 FACTOR 的规定，此时再看第二个 NUMBER，由于 EXPR 可以之间分解成 FACTOR,然后 FACTOR 又可以之间分解成 NUMBER，由此第二个 NUMBER 满足 EXPR 规定，至此 NUMBER PLUS NUMBER 能被上面语法解析，因此它包含的标签组合满足给定的语法规则。

上面的推导方法也叫最左推导，因为我们总是先拿到表达式右边，然后从最左往右，依次取出非终结符，先看给定的标签是否满足规范。同时还需要注意的是我们从最顶部的规则开始推导，依次从上往下分解，这种方式也叫自顶向下的推导。后面我们会看到第一种语法解析方式，它的特点是先获得一串标签集合，然后从最左边的标签开始逐个解析，然后采用上面描述的最左推导法，于是这样的语法解析叫 LL语法解析算法，两个 L 都对应英语里的 left，也就是左边的意思。其中LL(1)表示解析时会预先多查看 1 个标签，LL(k)表示预先多查看 k 个标签。之所以预先多查看标签主语是因为一个非终结符可能有多个表达式，例如
EXPR -> FACTOR PLUS EXPR | FACTOR
它其实对应两个表达式，一个是EXPR -> FACTOR PLUS EXPR，另一个是 EXPR->FACTOR，在解析时应该选取哪一个呢，此时就可以通过预先查看 一个或多个标签来决定。后面我们还会研究 LR 解析算法，第一个 L 表示从标签串的最左边开始进行解析，R 表示在解析时采用最右方式，也就是跟我们前面说的最左方式正好相反。

还有一点需要注意的是，在前面给出的语法表达式中，左边的符号都可以解析成右边 1 个或多个符号，事实上还存在一种可能是右边可以解析成 0 个符号，还记得前面将词法解析时的 epsilon 转换吧，它表示当前状态下不需要输入任何符号就能跳转到下一个状态，同样我们允许如下语法表达式

此时它表示可以通过什么都不做来完成解析，不难理解c 语言编译器可以编译解析一个内容为空的.c 源文件。

本节描述的东西比较抽象，它很可能给你带来更多的是困惑，好在在最开始和前面做词法解析时，我们都接触过语法解析，所以前面的练习应该会有助于我们对这些理论的理解，在后面章节中，我们会拿几个较为简单的语法解析做练手，通过实践才能更好的帮我们理解和掌握抽象的理论，更多内容请在 b 站搜索 Coding 迪斯尼。