# 语法分析

按照传统的编译原理教材讲述的编译器结构， 词法分析阶段 之后，便是 语法分析阶段 。

以下摘自百度百科：

语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如 “程序”，“语句”，“表达式” 等等。语法分析程序判断源程序在结构上是否正确。源程序的结构由上下文无关文法描述。语法分析程序可以用 YACC 等工具自动生成。

简而言之，语法分析即要求完成对输入串是否能符合语言文法规定的检查。
关于文法的定义，参照下文。

# 语法分析器

我们需要实现的是语法分析器。
语法分析器的主要工作就是接收词法分析器输出的 Token，产出抽象语法树。

本意我是不想讲太多学科中严谨定义的内容，一个是不好懂，容易劝退；一个是我个人的理解也有限。
所以本系列文章就只简单提及我认为的 ToyLang 开发过程中必要的东西。

# 文法

这里还是请出百度百科：

文法是一个汉语词汇，读音为 wén fǎ ，即文章的书写法规，一般用来指以文字、词语、短句、句子的编排而组成的完整语句和文章的合理性组织。

学习编译原理的过程中，确实会有许多概念难以理解。

我们先简单理解成，文法就是描述如何将 token 组织成语法树的规则。

我们的语言自然也需要存在文法，比如 if 语句必须按照下列文法来解析：

  • if exp block

当然，现在我们还是将重心放到四则表达式的解析上。

# 上下文无关文法

在推导产生式时，正在进行的非终结符展开与前后已经展开的终结符不存在关联的文法。
可以先继续向下看。

# EBNF

我们选择通过 EBNF 来描述 ToyLang 的文法。

EBNF 是什么呢？

扩展巴科斯 - 瑙尔范式 (Extended Backus–Naur Form,EBNF) 是一种用于描述计算机编程语言等正式语言的与上下文无关语法的元语法 (metasyntax) 符号表示法。简而言之，它是一种描述语言的语言。它是基本巴科斯范式 (BNF) 元语法符号表示法的一种扩展。

只看描述通常很难理解新事物，咱们尝试一下用 EBNF 描述四则运算表达式的文法。

1
2
3
exp = exp '+' number | exp '-' number | number
number = digit {digit}
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

为了便于理解，这里只描述了加法与减法。

# 基本规则

读者或许没看明白，没关系，笔者简单讲解一下：

  • 在 = 左边的，我们称为 左式 ；
  • 在 = 右边的，我们称为 右式 ；
  • 这样一行式子，我们称为 产生式 。

# 非终结符

是某条产生式的左式，可以用其右式代换。
如 exp ， number ， digit 。

# 终结符

无法被再被代换的符号。
如 + 、 - 、 0 、 1 …。

关于更多 EBNF 的语法规则，请参阅相关资料。

# 自顶向下

已知 输入串 为某条产生式的左式，扫描输入串以不断展开其非终结符，直至只剩下终结符。
这个展开的过程我们叫做推导，这属于自顶向下解析的思想。

# 尝试解析

我们先来看第一行产生式：
exp = exp '+' number | exp '-' number | number
它描述了 表达式 可以由：

  • 表达式+数字 组成；
  • 也可以由 表达式-数字 组成；
  • 也可以只由 数字 组成。

其中， | 表示或的意思，如果读者学习过正则表达式，应当很容易理解。

假设我们需要解析的 exp 非终结符输入串为 1 + 2 ，解析过程如下：

1
2
3
4
exp -> exp '+' number
        -> number '+' 'number'
            -> '1' '+' 'number'
                -> '1' '+' '2'

就是在重复将右式中的非终结符展开的过程。
这里为了节约篇幅，笔者没有将从 number 推导成 digit，再推导成数字的推导过程记录下来，读者明白这一点即可。

再尝试一下解析 exp 非终结符输入串 1 + 2 - 3 :

1
2
3
4
5
6
exp -> exp '-' number
        -> exp '+' number '-' number
            -> number '+' number '-' number
                -> '1' '+' number '-' number
                    -> '1' '+' '2' '-' number
                        -> '1' '+' '2' '-' '3'

当然，这个推导过程我们忽略了很多细节，并不能直接编写代码实现。

# 尾声

在下一篇文章，我们会通过 EBNF 来描述完整的四则表达式的文法，并讲解 递归下降 分析法。

# 参考文献

[1] 扩展巴科斯范式 (EBNF) 简介.https://blog.csdn.net/lin_strong/article/details/78583543
[2] 应该如何理解「上下文无关文法」？.https://www.zhihu.com/question/21833944
其他网络上较为零散的资料，无法一一列举，十分抱歉。