上下文无关文法（CFG）

在 正则表达式（RE）、有限自动机（FA）和词法分析（LA） 一文中介绍了用于描述正则语言（RL, Regular Language）的两种等价方法——正则表达式（RE, Regular Expression）和有限自动机（Finite Automata）。但是 RE 和 FA 在描述有递归结构的语言时就显得力不从心了，例如诸如 { 0 n 1 n ∣ n ≥ 0 } \{ 0^{n}1^{n} | n \ge 0 \} {0n1n∣n≥0} 这样的递归结构。本文介绍一种适合处理这种语言的表达能力更强的新方法——上下文无关文法（CFG, Context-free Grammar）。

使用上下文无关文法描述和产生的语言被成为上下文无关语言（CFL, Context-free Language）。

上下文无关文法的形式化定义

下面这个是一个上下文无关文法的一个例子，成为 $G1$：
S − > a S b S − > T T − > ∗

$$\begin{aligned} S &-> aSb \\ S &-> T \\ T &-> * \end{aligned}$$ SST​−>aSb−>T−>∗​

CFG 是由一系列产生式组成，每个产生式是由被一个箭头分成左右两个部分。左边的符号被称为非终结符，一般用大写字母表示。右边是一个字符串，包括非终结符和被称为终结符的其他符号组成，终结符可以是小写字母、数字和特殊符号组成。第一个产生式左边的非终结符被成为起始符。例如，$G1$ 有三个产生式，$S$ 和 $T$ 是非终结符，并且 $S$ 是起始符，$G1$ 的终止符为 $a$、$b$ 和 $\ast$。

上下文无关文法的形式化定义如下：

上下文无关文法是一个四元组 $(V,\Sigma ,R,S)$，其中

• $V$ 是非终结符的有限集，
• $\Sigma$ 是终结符的有限集，
• $R$ 是产生式的有限集，每个产生式是有非终结符和非终结符、终结符的字符串组成，
• $S$ 是起始符，$S\in V$。

使用文法产生一个具体的语句的过程被成为推导，推导的过程就是不断挑选文法中的产生式将起始符的右边替换成只有终结符的字符串为止。例如，使用 $G1$ 产生字符串 $aaa\ast bbb$ 的推导如下：
S − > a S b − > a a S b b − > a a a S b b b − > a a a ∗ b b b

$$\begin{aligned} S &->aSb \\ &-> aaSbb \\ &->aaaSbbb \\ &->aaa*bbb \end{aligned}$$ S​−>aSb−>aaSbb−>aaaSbbb−>aaa∗bbb​

这里安利一个非常好用的工具，可戳 cfg-grammar-tool，能够根据 CFG 文法推到句子和判断句子是否可以被推导。

上下文无关文法之所以是“上下文无关”的，那是因为该文法中每个产生式的左边只有唯一符号（即非终结符）。每个产生式左边的非终结符可以自由地被替换成右边的字符串，而不管这个非终结符出现的位置（所处的上下文）。例如：
S − > a S b S − > a b

$$\begin{aligned} S &-> aSb \\ S &-> ab \end{aligned}$$ SS​−>aSb−>ab​

这个就是一个上下文无关文法。而下面的例子则不是。

a S b − > a a S b b S − > a b

$$\begin{aligned} aSb &-> aaSbb \\ S &-> ab \end{aligned}$$ aSbS​−>aaSbb−>ab​

这是个上下文相关文法，它的第一个产生式左边有不止一个符号，所以你在匹配这个产生式中的 $S$ 的时候必需确保 $S$ 所处的“上下文”，即其左边的 $a$ 和右边的 $b$，所以是上下文相关文法。

在 CFG 中可能存在多个产生式的左边非终结符相同，可以将这样的产生式合并简化。例如：
S − > a S b S − > a b

$$\begin{aligned} S &-> aSb \\ S &-> ab \end{aligned}$$ SS​−>aSb−>ab​

可以简化为：
S − > a S b ∣          a b

$$\begin{aligned} S &-> aSb \\ &| \ \ \ \ \ \ \ \ ab \end{aligned}$$ S​−>aSb∣        ab​

或者：
S − > a S b   ∣   a b

$$\begin{aligned} S -> aSb \ | \ ab \end{aligned}$$ S−>aSb ∣ ab​

巴科斯-瑙尔范式

上述 CFG 的符号表示法起源于传统的 CFG 符号表示法——巴科斯-瑙尔范式（BNF, Backus-Naur Form）。例如：
$$\begin{gathered} <SheepNoise>::=\underline{baa}<SheepNoise> \\ |\underline{baa} \end{gathered}$$

BNF 使用 $<>$ 包围的字符串标记非终结符，终结符带有下划线，符号 $::=$ 表示“推导”。

语法分析树

根据 CFG 推导句子的过程也可以使用图形化展示，被成为语法分析树（parse tree）。例如 $G1$ 产生字符串 $aaa\ast bbb$ ：

最左推导和最右推导

最左推导：每个步骤都替换最左侧的非终结符。
最右推导：每个步骤都替换最右侧的非终结符。

给定一个括号表达式的 CFG：
E X P R − > (   E X P R   ) ∣         E X P R    O P    I D ∣         I D O P − > + ∣         − ∣         ∗ ∣         ÷ I D − > a ∣         a ∣         b ∣         c

$$\begin{aligned} EXPR &-> (\ EXPR\ ) \\ &| \ \ \ \ \ \ \ EXPR \ \ OP \ \ ID \\ &| \ \ \ \ \ \ \ ID \\ OP &-> + \\ &| \ \ \ \ \ \ \ - \\ &| \ \ \ \ \ \ \ * \\ &| \ \ \ \ \ \ \ \div \\ ID &-> a \\ &| \ \ \ \ \ \ \ a \\ &| \ \ \ \ \ \ \ b \\ &| \ \ \ \ \ \ \ c \\ \end{aligned}$$ EXPROPID​−>( EXPR )∣       EXPR  OP  ID∣       ID−>+∣       −∣       ∗∣       ÷−>a∣       a∣       b∣       c​

考虑 $(a+b)\ast c$，它的最左推导为：
E X P R − > E X P R    O P    I D − > (   E X P R   )    O P    I D − > (   E X P R    O P    I D   )    O P    I D − > (   I D    O P    I D   )    O P    I D − > ( a    O P    I D   )    O P    I D − > ( a + I D   )    O P    I D − > ( a + b )    O P    I D − > ( a + b ) ∗ I D − > ( a + b ) ∗ c

$$\begin{aligned} EXPR &-> EXPR \ \ OP \ \ ID \\ &->( \ EXPR \ ) \ \ OP \ \ ID \\ &->( \ EXPR \ \ OP \ \ ID \ ) \ \ OP \ \ ID \\ &->( \ ID \ \ OP \ \ ID \ ) \ \ OP \ \ ID \\ &->( a \ \ OP \ \ ID \ ) \ \ OP \ \ ID \\ &->( a + ID \ ) \ \ OP \ \ ID \\ &->( a + b ) \ \ OP \ \ ID \\ &->( a + b ) * ID \\ &->( a + b ) * c \end{aligned}$$ EXPR​−>EXPR  OP  ID−>( EXPR )  OP  ID−>( EXPR  OP  ID )  OP  ID−>( ID  OP  ID )  OP  ID−>(a  OP  ID )  OP  ID−>(a+ID )  OP  ID−>(a+b)  OP  ID−>(a+b)∗ID−>(a+b)∗c​

对应的语法分析树为：

再看最右推导：
E X P R − > E X P R    O P    I D − > E X P R    O P    c − > E X P R    ∗ c − > (   E X P R   ) ∗ c − > (   E X P R    O P    I D   ) ∗ c − > (   E X P R    O P    b   ) ∗ c − > (   E X P R + b   ) ∗ c − > (   I D + b   ) ∗ c − > (   a + b   ) ∗ c

$$\begin{aligned} EXPR &-> EXPR \ \ OP \ \ ID \\ &->EXPR \ \ OP \ \ c \\ &->EXPR \ \ * c \\ &->(\ EXPR \ ) * c \\ &->(\ EXPR \ \ OP \ \ ID \ ) * c \\ &->(\ EXPR \ \ OP \ \ b \ ) * c \\ &->(\ EXPR + b \ ) * c \\ &->(\ ID + b \ ) * c \\ &->(\ a + b \ ) * c \\ \end{aligned}$$ EXPR​−>EXPR  OP  ID−>EXPR  OP  c−>EXPR  ∗c−>( EXPR )∗c−>( EXPR  OP  ID )∗c−>( EXPR  OP  b )∗c−>( EXPR+b )∗c−>( ID+b )∗c−>( a+b )∗c​

对应的语法分析树为：

这个例子最左推导和最右推导得到的语法分析树是相同的。

二义性

如果一个语法使用不同的方式推导一个语句产生不同的语法分析树，而不同的语法分析树有不同的含义，这可能不是我们期望的，称这个语法具有二义性。

如果语法 $G$ 的语言 $L(G)$ 中有一个以上的最左（或最右）推导，那么语法 $G$ 就是二义性的。

还是上文给的 CFG：
E X P R − > (   E X P R   ) ∣         E X P R    O P    I D ∣         I D O P − > + ∣         − ∣         ∗ ∣         ÷ I D − > a ∣         a ∣         b ∣         c

$$\begin{aligned} EXPR &-> (\ EXPR\ ) \\ &| \ \ \ \ \ \ \ EXPR \ \ OP \ \ ID \\ &| \ \ \ \ \ \ \ ID \\ OP &-> + \\ &| \ \ \ \ \ \ \ - \\ &| \ \ \ \ \ \ \ * \\ &| \ \ \ \ \ \ \ \div \\ ID &-> a \\ &| \ \ \ \ \ \ \ a \\ &| \ \ \ \ \ \ \ b \\ &| \ \ \ \ \ \ \ c \\ \end{aligned}$$ EXPROPID​−>( EXPR )∣       EXPR  OP  ID∣       ID−>+∣       −∣       ∗∣       ÷−>a∣       a∣       b∣       c​

考虑 $a+b\ast c$，很容易得到下面两个语法分析树：

求值表达式的一种方式是采用后根遍历的方法，左图的含义是 $a+b\ast c$，而右图的含义为 $(a+b)\ast c$。这样的语法显然有问题，它的问题是设计语法的时候没有考虑运算符的优先级。我们可以根据表达式中运算符的优先级进行层次分组设计，例如，$()$ 有最高优先级，$\ast$ 和 $÷$ 有中优先级，$+$ 和 $-$ 有最低优先级。下面给出改进的语法：
G O A L − > E X P R E X P R − > E X P R + T E R M ∣         E X P R − T E R M ∣         T E R M T E R M − > T E R M ∗ F A C T O R ∣         T E R M − F A C T O R ∣         F A C T O R F A C T O R − > (   E X P R   ) ∣         I D I D − > a ∣         b ∣         c

$$\begin{aligned} GOAL &-> EXPR \\ EXPR &-> EXPR + TERM\\ &| \ \ \ \ \ \ \ EXPR - TERM \\ &| \ \ \ \ \ \ \ TERM \\ TERM &-> TERM * FACTOR \\ &| \ \ \ \ \ \ \ TERM- FACTOR \\ &| \ \ \ \ \ \ \ FACTOR \\ FACTOR &-> (\ EXPR \ ) \\ &| \ \ \ \ \ \ \ ID \\ ID &-> a \\ &| \ \ \ \ \ \ \ b \\ &| \ \ \ \ \ \ \ c \\ \end{aligned}$$ GOALEXPRTERMFACTORID​−>EXPR−>EXPR+TERM∣       EXPR−TERM∣       TERM−>TERM∗FACTOR∣       TERM−FACTOR∣       FACTOR−>( EXPR )∣       ID−>a∣       b∣       c​

根据该语法推导 $a+b\ast c$ 得到语法分析树如下：

上下文无关文法的设计

上下文无关文法的设计有以下几个思路：

• 第一，一个复杂的 CFG 可能能够分解成几个简单的 CFG，然后分别进行设计，再合并到一起。

例如 { 0 n 1 n ∣ n ≥ 0 } ∪ { 1 n 0 n ∣ n ≥ 0 } \{ 0^{n}1^{n} | n \ge 0 \} \cup \{ 1^{n}0^{n} | n \ge 0 \} {0n1n∣n≥0}∪{1n0n∣n≥0}。

先构建 { 0 n 1 n ∣ n ≥ 0 } \{ 0^{n}1^{n} | n \ge 0 \} {0n1n∣n≥0} 的 CFG，很容易设计如下：
$$S_1->0S_{1}1|ϵ$$

再构建 { 1 n 0 n ∣ n ≥ 0 } \{ 1^{n}0^{n} | n \ge 0 \} {1n0n∣n≥0} 的 CFG，如下：
$$S_2->1S_{2}0|ϵ$$

最后将二者合并即可：
S − > S 1   ∣   S 2 S 1 − > 0 S 1 1   ∣   ϵ S 2 − > 1 S 2 0   ∣   ϵ

$$\begin{aligned} S &-> S_1 \ | \ S_2 \\ S_1 &-> 0 S_{1} 1 \ | \ \epsilon \\ S_2 &-> 1 S_{2} 0 \ | \ \epsilon \end{aligned}$$ SS1​S2​​−>S1​ ∣ S2​−>0S1​1 ∣ ϵ−>1S2​0 ∣ ϵ​

• 第二，正则表达式语法是上下文无关文法的子集，如果一个 CFG 正好是 RE 的话，则可以先构建 NFA，然后把 NFA 转换为 CFG。方式如下：
  （1）构建 NFA 。
  （2）每个 NFA 中的状态 $q_i$ 对应一个非终结符 $R_i$，对于 DFA 的 $\delta (q_i,a)=q_j$，则对应添加一个产生式 $R_i->a{R}_j$ 。
  （3）对于 DFA 的 $\delta (q_i,ϵ)=q_j$，则对应添加一个产生式 $R_i->R_j$ 。
  （4）若 NFA 的 $q_i$ 是一个接受状态，则添加一个产生式 $R_i->ϵ$ 。

例如有如下 NFA：

根据上述步骤很容易得到 CFG：
R 0 − > a R 0   ∣   b R 0   ∣   a R 1 R 1 − > b R 2 R 2 − > b R 3 R 3 − > ϵ

$$\begin{aligned} R_0 &-> a R_0 \ | \ b R_0 \ | \ a R_1 \\ R_1 &-> b R_2 \\ R_2 &-> b R_3 \\ R_3 &-> \epsilon \end{aligned}$$ R0​R1​R2​R3​​−>aR0​ ∣ bR0​ ∣ aR1​−>bR2​−>bR3​−>ϵ​

• 第三，某些 CFG 中有两个相互联系的子串，需要检测一个子串是否正好对应另一个子串，这就需要记住子串的信息。例如 { 0 n 1 n ∣ n ≥ 0 } \{ 0^{n}1^{n} | n \ge 0 \} {0n1n∣n≥0}，为了检查 0 的个数是否等于 1 的个数，则需要记住 0 的个数。对于这种情况，可以使用 $R->uRv$ 形式的产生式。

• 第四，在更复杂的语言中，字串中可能包含一种被递归使用的结构，例如前文介绍的算术表达式的文法，每次出现一个 $ID$， 就会递归地出现一个用括号括起来的完整表达式。可以考虑将这样的递归结构放在对应的位置上。

以上介绍的几个思路可以作为 CFG 设计时的参考。

至此，本文结束。

参考：

• Engineering a compiler, 2E.
• Introduction to the Theory of Computation, 3E.