形式陈述

上下文无关文法是四元组

$$ G=(V,\Sigma,R,S), $$$$G=(V,\mathrm{\Sigma },R,S),$$

其中 $V$$V$ 为有限非终结符集，$\Sigma$$\mathrm{\Sigma }$ 为有限终结符集，$R$$R$ 为有限产生式集，且 $V\cap\Sigma=\varnothing$$V\cap \mathrm{\Sigma }=\varnothing$，$S\in V$$S\in V$ 为开始符号，产生式集合

$$ R\subseteq V\times(V\cup\Sigma)^* $$$$R\subseteq V\times (V\cup \mathrm{\Sigma }{)}^{\ast }$$

的每条规则写作 $A\to\alpha$$A\to \alpha$。一步推导允许在任意上下文中替换一个非终结符：

$$ uAv\Rightarrow_G u\alpha v. $$$$uAv{\Rightarrow }_{G}u\alpha v.$$

语言为 $L(G)=\{w\in\Sigma^*:S\Rightarrow_G^*w\}$$L(G)=\{w\in {\mathrm{\Sigma }}^{\ast }:S{\Rightarrow }_G^{\ast }w\}$。

直觉

文法从开始符号逐步展开语法树。规则左侧只有一个非终结符，所以替换是否合法不依赖其左右邻居，这正是“上下文无关”。

例子与边界

规则 $S\to0S1\mid\varepsilon$$S\to 0S1\mid \epsilon$ 生成 $\{0^n1^n:n\ge0\}$$\{0^n{1}^n:n\ge 0\}$。同一个字符串若有两棵不同解析树或两个不同最左推导，则文法有歧义；语言本身可能存在无歧义文法，也可能本质歧义。文法生成过程不是识别算法本身，需另行解析。

推论与应用

CFG 描述程序语言语法、嵌套括号和递归结构，并与下推自动机等价。Chomsky 范式、CYK 算法与泵引理建立其规范化、识别和表达边界。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 5–7。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§2.1。