编程语言理论与类型系统入门

第二章 形式文法与 BNF

阅读提示

本章会频繁使用“终结符（terminal）/ 非终结符（nonterminal）”“具体语法（concrete syntax）/ 抽象语法（abstract syntax）”“抽象语法树（abstract syntax tree, AST）”“BNF（Backus–Naur Form）”等概念。若你在阅读时想快速回查术语与记号，建议配合：

• 附录A《术语表》中的相关条目；
• 附录B《符号速查表》中的元变量与常见记号说明。

第一章介绍了推导规则和归纳定义，现在我们把这些工具真正用在“语言本身”上：

怎样精确地说明：什么样的程序是合法的？

这件事如果只靠自然语言描述，往往不够稳定，也不够适合后续的数学推理。于是我们需要形式文法（formal grammar）。

在阅读本章时，建议同时记住两条线索：

• 本章主要处理“程序在表面上如何写出来”与“它在结构上如何被分析”；
• 下一章开始，我们会把这里的语法工具真正用于 Lambda 演算，并更多地站在抽象语法而不是源代码表面写法的层面讨论问题。

如果你在术语或记号上感到不确定，可以配合附录A“术语表”和附录B“符号速查表”一起阅读。

2.1 为什么自然语言不够？

假设我们这样描述一个简单表达式语言：

算术表达式由数字、加号、乘号和括号组成，乘法优先级高于加法。

这段话对人类读者来说已经“差不多能懂”，但对于形式化讨论来说还不够。

例如：

1 + 2 * 3

它到底应该理解成：

• $(1+2)\ast 3$，还是
• $1+(2\ast 3)$？

人类会说：“当然是后者，因为乘法优先级更高。”

但如果你要把这件事交给编译器、解释器，或者要在这个语言上定义类型规则，就不能只说“当然”。你必须把优先级和结合性直接体现在语法规则中。

这就是形式文法的作用：

• 明确什么字符串是合法程序；
• 明确它们应该如何解析；
• 为后续的抽象语法和类型规则打基础。

2.2 BNF：最常见的语法表示法

类型系统文献里最常见的语法记法是 BNF（Backus–Naur Form）。

它的基本形式是：

<非终结符> ::= 定义

其中：

• ::= 表示“定义为”；
• | 表示“或”；
• 尖括号里的名字表示一个语法类别，称为非终结符（nonterminal）；
• 真正出现在程序里的字面符号，称为终结符（terminal）。

这里先提醒一个后文会反复用到的区分：

• 当我们用 BNF 讨论源代码表面写法时，重点通常是具体语法（concrete syntax）；
• 当我们在后续章节里写 t ::= ...、T ::= ... 这类生成式时，重点往往已经转向抽象语法（abstract syntax）的归纳定义。

例如：

<expr> ::= <expr> + <term> | <term>
<term> ::= <term> * <factor> | <factor>
<factor> ::= ( <expr> ) | <number>

这里：

• <expr>、<term>、<factor>、<number> 是非终结符；
• +、*、(、) 以及数字字符属于终结符。

BNF 的价值不在于记号本身，而在于它把“合法程序长什么样”变成了一组可以机械检查的规则。

2.3 优先级与结合性如何写进文法？

回到前面的算术表达式例子。为什么要分成 expr / term / factor 三层？

因为这恰好把优先级写进了语法：

• expr 对应较低优先级的加法层；
• term 对应较高优先级的乘法层；
• factor 对应最基本的原子层。

于是 1 + 2 * 3 只能被解析成：

• 一个 expr
• 其左边是 1
• 其右边是一个 term
• 而那个 term 再展开为 2 * 3

这就自然得到：

$$1+(2\ast 3)$$

一个简单推导示例

<expr>
→ <expr> + <term>
→ <term> + <term>
→ <factor> + <term>
→ <number> + <term>
→ 1 + <term>
→ 1 + <term> * <factor>
→ 1 + <factor> * <factor>
→ 1 + 2 * 3

这个推导过程说明：

• 2 * 3 先在 term 层形成；
• 然后整个式子才回到 expr 层；
• 因而乘法天然绑定得更紧。

左结合与右结合

除了优先级，文法也常用来表达结合性。

例如：

<expr> ::= <expr> + <term> | <term>

这是一种典型的左递归写法，它对应左结合：

1 + 2 + 3  读作  (1 + 2) + 3

后面第三章讲 Lambda 项时，我们同样会用“左结合”和“向右延伸”这样的书写约定来消歧义。到那时你会看到：很多看起来像“BNF 规则”的写法，真正服务的对象其实已经是抽象语法层面的结构表示。

2.4 形式文法的四元组表示

从更抽象的角度看，一个形式文法通常写成四元组：

$$G=(N,\Sigma ,P,S)$$

其中：

对于前面的算术表达式文法，可以理解为：

• $N=\{⟨expr⟩,⟨term⟩,⟨factor⟩,⟨number⟩\}$
• $\Sigma =\{+,\ast ,(,),0,1,2,\dots \}$
• $P$ 是所有产生式规则
• $S=⟨expr⟩$

四元组写法的好处是：

• 你可以精确讨论“这是哪一类文法”；
• 也可以把“语法”当成一个标准数学对象来研究。

一个简短的 Chomsky 层级说明

本教程主要用的是上下文无关文法。它的特征是：

每条产生式左侧都是一个单独的非终结符。

这正好就是 BNF 最常见的写法。

对本书来说，你不需要深入掌握整个 Chomsky 层级。只要记住：

• 编程语言的核心语法，通常适合用上下文无关文法描述；
• 而“变量必须先声明后使用”这类约束，往往不属于纯语法层，而要交给后续的语义分析或类型系统处理。

2.5 具体语法与抽象语法

真正编程时，你写下的是具体语法（concrete syntax）；

而类型系统和解释器更关心的是：

去掉无关书写细节之后，程序的核心结构是什么？

这就是抽象语法（abstract syntax）。

这一点对后文非常重要。因为从第三章开始，本教程虽然仍会沿用类似 BNF 的紧凑写法，但默认更关心的是：

• 哪些对象属于语言的抽象语法；
• 它们如何按归纳方式生成；
• 后续的自由变量、替换、归约和类型规则如何定义在这些结构上。

也就是说，后文很多看起来像“文法”的写法，主要服务于抽象语法对象的定义，而不是完整源代码语法的刻画。

例如，下面这些写法在具体语法上不同：

1 + 2 * 3
1+2*3
(1) + ((2) * 3)

但它们都对应同一个抽象语法树（AST）：

      Add
     /   \
   Num    Mul
   1     /   \
       Num   Num
        2     3

这就是为什么后面定义语义和类型规则时，我们通常直接面向 AST，而不是面向源代码表面的括号和空格。

第三章的 Lambda 项语法就是第一个完整例子：虽然表面上仍会写成类似 BNF 的形式，但那时我们真正关心的已经是“变量、抽象、应用”这三类抽象语法构造，而不是某门具体语言里的排版细节。

一个重要提醒

很多入门材料会说：“BNF 的每个分支都对应一个 AST 节点。”

这句话作为直觉有帮助，但不能说得太绝对。更准确的说法是：

• 抽象语法构造子通常来自我们对文法的整理；
• 具体语法里的某些产生式只是为了优先级、结合性或书写方便服务；
• 它们未必都会在 AST 中保留下来。

比如括号就是典型例子：

• 它在具体语法里非常重要；
• 但在 AST 里通常不会单独形成一个“括号节点”。

因此，后面如果你看到教程把某个语法写成

t ::= ...

这样的形式，最稳妥的理解通常不是“这里在讨论完整源代码语法”，而是“这里在用一种紧凑记法描述抽象语法对象的生成方式”。

这也是为什么本章虽然从 BNF 讲起，但它真正要为后文准备的，不只是“怎么写文法”，更是：

怎样把语言对象写成可归纳定义、可做推理、可接上语义与类型规则的抽象结构。

2.6 词法层与语法层

还有一个常见细节值得提早说明：

• 词法层负责把字符流切成记号（token），如标识符、数字、关键字；
• 语法层负责把这些记号组织成树状结构。

因此，如果你在 BNF 里看到类似：

<number> ::= <digit> | <digit> <number>
<digit> ::= 0 | 1 | 2 | ... | 9

这只是为了教学清楚，把数字的内部结构也显式写出来。

但到了 AST 层，解释器或类型检查器往往只关心：

Num(123)

也就是说：

词法细节在 AST 中常被折叠。

这点后面非常重要。因为类型规则通常对应的是 AST 构造，而不是字符级别的文法细节。

2.7 本书中的常见元变量

类型系统文献喜欢使用固定的元变量约定。熟悉这些记号，会让后面的公式更容易读。

这里的“项”可以理解成“形式化语言中的表达式对象”。例如：

• 在第三章，Lambda 项就是用语法规则生成出来的项；
• 在第五章，类型规则判断的对象也是项。

2.8 本章小结

这一章最重要的不是记住某种特定文法，而是理解下面几件事：

1. 形式文法的任务是精确定义“什么样的程序合法”。
2. BNF 是最常见的语法书写方式，尤其适合描述上下文无关语法。
3. 优先级与结合性并不是语法之外的注释，而是可以直接写进文法结构里的。
4. 类型系统真正操作的对象通常是抽象语法，而不是源代码的表面写法。
5. 从第三章开始，本教程中的许多生成式写法都应优先理解为抽象语法的归纳定义，而不是完整 concrete syntax 的逐字描述。

下一章开始，我们就会把这些工具用在一个真正重要的对象上：

Lambda 演算。

届时你会看到，本章区分的几件事会立刻变得具体起来：

• 什么是语法对象；
• 什么是抽象语法层面的构造；
• 为什么后续的自由变量、替换、β-归约和类型规则，都更自然地定义在 AST 结构上。

如果你想提前做准备，建议特别回顾本章中的“优先级 / 结合性”“具体语法 vs 抽象语法”“元变量约定”这三部分。

回看导航

如果你读完本章后仍觉得“文法看着都懂，但不知道它和后面章节有什么关系”，建议这样回看：

• 回看本章中的“优先级 / 结合性”和“具体语法 vs 抽象语法”；
• 配合附录A确认“终结符、非终结符、抽象语法、AST”这些术语；
• 配合附录B确认本章使用的元变量记法；
• 然后再进入第 3 章，看这些语法工具如何真正落到 Lambda 项上。

本章练习

1. 用 BNF 定义一个简单的布尔表达式语言，包含 true、false、not、and、or，并体现 not 的优先级高于 and，and 高于 or。
2. 用你定义的文法推导字符串 true and (false or true)。
3. 为表达式 1 + 2 * 3 画出对应的 AST。
4. 解释“具体语法”和“抽象语法”的区别，并说明类型系统主要工作在哪一层。