9.1 上下文无关语法

在第 7 章中，对程序、语言和编译做了正式的定义，一个程序就是一个句子（字符串），语言就是一个句子集合。那么如何准确的表示这个集合？用枚举法？显然不行，这个集合可能包含了无限多个元素。用特性法？那应该如何精确的描述这个集合的特性？

编译的第一个任务就是判断给定的句子是否属于这个集合，因此必须提供一个精确的、可操作的描述来表示这集合。如 ” C 语言就是所有能编译成功的源程序的集合” 这样的描述是无法操作的，对任意的源程序显然无法用这个描述来判断其是否属于 C 语言这个句子集合。

在第 7 章中介绍了正则语言和正则表达式，一个正则表达式可以用来表示一个句子集合（正则语言），且每个正则表达式都可以构造出有限状态自动机来判断任意的句子是否属于这个句子集合。因此，用正则表达式来表示正则语言是精确的、可操作的。

那么，可以用正则表达式来表示程序语言（比如 C 语言）所代表的句子集合吗？

很遗憾，答案是否定的。正则表达式毕竟太简单了，无法来表示程序语言这样复杂级别的句子集合。

为了表示程序语言的句子集合，需要采用表达能力更强大的工具 —— 上下文无关语法（context-free grammar） 。

下面以一个简单的例子来说明什么是上下文无关语法，假设有一种非常非常原始的语言，我们把它成为 X 语言，它的句子只有： 主语**谓语**宾语 这样一种结构， 主语 中只有 我、 你、 他 三个词， 谓语 中只有 吃 一个词， 宾语 中只有 饭、菜 两个词。我们把它的语法写出下面这样的形式：

  1. 语句 -> 主语 谓语 宾语
  2. 主语 -> 我
  3. 主语 -> 你
  4. 主语 -> 他
  5. 谓语 -> 吃
  6. 宾语 -> 饭
  7. 宾语 -> 菜

可以看出， X 语言总共只有 6 个句子： { 我吃饭, 我吃菜, …, 他吃菜 }。也就是说，我们可以用上面这个语法来表示 X 语言这个集合，我们可以从第一行的 “语句 -> 主语 谓语 宾语” 开始，分别将主、谓、宾替换成可用的词，从而将所有满足语法的句子都推导出来。对于任意一个句子，我们也可以将句子和此语法来对比，判断它是否属于满足 X 语言。

上面这个语法中的每一行形如 “语句 -> 主语 谓语 宾语” 的式子称为 产生式（production） 。

产生式左侧的符号（语句、主语、谓语和宾语）称为 非终结符（nonterminal） ，代表可以继续扩展或产生的符号，也就是说，当在某条产生式的右边遇到了此非终结符的时候，总是可以用本产生式的右边来替换这个非终结符。

而 “我、你、他、吃、饭、菜” 这些符号是 X 语言中的词，无法再产生新的符号了，称为 终结符（terminal） 。终结符只能出现在产生式的右边，非终结符则左边和右边都可以出现。

上述产生式中有一个特别的非终结符： “语句” ， X 语言中的所有句子都以它为起点产生，这个符号被称为 起始符号（start**symbol）**。

通常把同一个非终结符的产生式写在一起，用 “|” 隔开，如下：

  1. 语句 -> 主语 谓语 宾语
  2. 主语 -> 我 | 你 | 他
  3. 谓语 -> 吃
  4. 宾语 -> 饭 | 菜

注意，上面的第二行中有 3 个产生式，第四行中有 2 个产生式。

一个上下文无关语法 G 就是由一个终结符集合 T ，一个非终结符集合 N （ N 和 T 不相交），一个产生式集合 P ，以及一个起始符号 S （S ∈ N）组成。由语法 G 推导（产生）出来的所有的句子的集合称为 G 语言。因此一个语法可以代表一个句子集合，也就是一个语言。

终结符和非终结符统称为符号，符号一般用字母 A, B, X, Y, a, b 表示，符号串一般用小写字母 u, v 表示。产生式的形式为 A -> u ，其中 A 为非终结符， u 为一个符号串。

下面再来看一个例子：

  1. S –> AB
  2. A –> aA | ε
  3. B –> b | bB

这里面的第二行中的 ε 表示一个空句子，表示 A 可以用一个空句子来代替。

经过观察可知，这个语法所能推导出的所有句子的集合为：

  1. A : { ε, a, aa, aaa, ... }
  2. B : { b, bb, bbb, ... }
  3. S : { b, bb, bbb, ..., ab, abb, ..., aab, aabb, ... }

因此 S 相当于正则表达式 a*b+ 。

再来看一个稍微复杂的例子：

  1. Expr -> Expr op Expr | (Expr) | number
  2. op   -> + - * /

其中的 number 是词法分析得到的一个 token ，它在词法分析中用正则表达式 [0-9]+ 表示。

经过观察可知，此语法可以推导出所有的整数算术表达式：

  1. Expr : { 123, 25 + 24, 78 - 34, 12 * ( 23 + 9 ), ... }

可以看出，上下文无关文法可以采用递归的形式推导，比正则表达式的表达能力要强大的多。

下面给出上下文本无关语法及相关术语的正式定义：

终结符集合 T （terminal set） ： 一个有限集合，其元素称为 终结符（terminal） 。

非终结符集合 N （non-terminal set) ： 一个有限集合，与 T 无公共元素，其元素称为 非终结符（non-terminal） 。

符号集合 V （alphabet） ： T 和 N 的并集，其元素称为 符号（symbol） 。因此终结符和非终结符都是符号。符号可用字母：A, B, C, X, Y, Z, a, b, c 等表示。

符号串（a string of symbols） ： 一串符号，如 X1 X2 … Xn 。只有终结符的符号串称为 句子（sentence）。 空串 （不含任何符号）也是一个符号串，用 ε 表示。符号串一般用小写字母 u, v, w 表示。

产生式（production） ： 一个描述符号串如何转换的规则。对于上下文本无关语法，其固定形式为： A -> u ，其中 A 为非终结符， u 为一个符号串。

产生式集合 P （production set） ： 一个由有限个产生式组成的集合。

展开（expand） ： 一个动作：将一个产生式 A -> u 应用到一个含有 A 的符号串 vAw 上，用 u 代替该符号串中的 A ，得到一个新的符号串 vuw 。

折叠（reduce） ： 一个动作：将一个产生式 A -> u 应用到一个含有 u 的符号串 vuw 上，用 A 代替该符号串中的 u ，得到一个新的符号串 vAw 。

起始符号 S （start symbol） ： N 中的一个特定的元素。

推导（derivate） ： 一个过程：从一个符号串 u 开始，应用一系列的产生式，展开到另一个的符号串 v。若 v 可以由 u 推导得到，则可写成： u => v 。

上下文本无关语法 G （context-free grammar, CFG） ： 一个 4 元组： (T, N, P, S) ，其中 T 为终结符集合， N 为非终结符集合， P 为产生式集合， S 为起始符号。一个句子如果能从语法 G 的 S 推导得到，可以直接称此句子由语法 G 推导得到，也可称此句子符合这个语法，或者说此句子属于 G 语言。 G 语言（ G language） 就是语法 G 推导出来的所有句子的集合，有时也用 G 代表这个集合。

解析（parse） ： 也称为分析，是一个过程：给定一个句子 s 和语法 G ，判断 s 是否属于 G ，如果是，则找出从起始符号推导得到 s 的全过程。推导过程中的任何符号串（包括起始符号和最终的句子）都称为 中间句子（working string） 。

为什么要把这种语法称为上下文本无关语法呢？这是由其产生式的固定形式 A -> u 所决定的，事实上，还有所谓的上下文有关语法，其产生式的形式为 v A w -> v u w ，也就是说只有 A 的上下文分别为 v 和 w 时，才能应用该产生式。上下文本无关语法其实是上下文有关语法中的一种特例，也就是 v 和 w 分别为空串时的特例。