上下文无关文法是一种生成「上下文无关语言」的方法。顾名思义，「上下文无关」意味着这样的文法（以及对应的语言）能从外向内「剥离」成多层，且每一层都和其之外的层（所谓的「上下文」）无关。

上下文无关文法

BNF 范式

BNF 范式是一种表示文法的格式。用 BNF 范式表示「四则运算式」的方法如下：

$$ \begin{aligned} \langle\mathrm{expression}\rangle&\to\langle\mathrm{expression}\rangle+\langle\mathrm{expression}\rangle\\ \langle\mathrm{expression}\rangle&\to \langle\mathrm{expression}\rangle-\langle\mathrm{expression}\rangle\\ \langle\mathrm{expression}\rangle&\to\langle\mathrm{expression}\rangle\times\langle\mathrm{expression}\rangle\\ \langle\mathrm{expression}\rangle&\to\langle\mathrm{expression}\rangle\div\langle\mathrm{expression}\rangle\\ \langle\mathrm{expression}\rangle&\to(\langle\mathrm{expression}\rangle) \\ \langle\mathrm{expression}\rangle&\to\mathbf{id} \end{aligned} $$

说人话就是：

• 两个式子相加、减、乘、除都是式子。
• 一个式子套上括号还是式子。
• 一个数也是式子。

按着这个思路，你可以尝试用 C 语言或其他语言写一个算式求值器，给出任一合法的算式如 ((12 - 4) / 8) * (3 + 7 * 2)，自动求出它的值。

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

上下文无关文法（CFG）$G$ 是一个四元组 $(V, T, P, S)$，其中

• $V$ 是「变元」的有穷集。在上面算式的例子中，$\langle\mathrm{expression}\rangle$ 就是变元。
• $T$ 是「终结符」的有穷集。在上面的例子中，表示具体数的 $\mathbf{id}$ 就是终结符。
• $P$ 是「产生式」的有穷集。所谓产生式就是上面的 6 个式子。包含：
  • 一个变元，称为产生式的「头」。
  • 一个产生符号 $\to$。
  • 一个 $(V\cup T)^*$ 中的串，称为产生式的「体」。
• $S$ 是「初始符号」，$S\in V$，是文法开始的地方。

派生

派生是从产生式的头向产生式的体的推导过程。符号 $\alpha A\beta\xRightarrow[G]{}\alpha\gamma\beta$ 表示将文法 $G$ 的产生式 $A\to\gamma$ 应用到了 $\alpha A\beta$ 中的变元 $A$。在 $G$ 已知的情况下，可以不写 $G$。多步推导写成 $\xRightarrow[G]{*}$。例如，算式 $\mathbf{id}\times(\mathbf{id}+\mathbf{id})$ 的派生过程：

$$ \begin{aligned} E&\xRightarrow{*}\mathbf{id}\times(\mathbf{id}+\mathbf{id})\\ E&\Rightarrow E\times E\Rightarrow E\times (E)\Rightarrow \mathbf{id}\times(E)\Rightarrow\mathbf{id}\times(E+E) \\ &\Rightarrow\mathbf{id}\times(E+\mathbf{id})\Rightarrow\mathbf{id}\times(\mathbf{id}+\mathbf{id}) \end{aligned} $$