上下文无关文法

CFG 用递归替换描述嵌套结构。非终结符像尚未展开的结构类别，产生式给出一种合法展开方式；同一非终结符可在任何上下文中按同样规则展开。它比有限自动机多出的力量来自隐式递归深度，可以生成任意层括号或成对计数。文法是生成语言的规格，不自动规定唯一解析、求值顺序或高效解析算法，这些是额外性质。

文法

生成 $\{a^n{b}^n:n\ge 0\}$：例如 $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$。平衡括号可由 $S\to SS\mid (S)\mid \epsilon$ 描述，递归对应嵌套与连接。

边界语言 $\{a^n{b}^n{c}^n:n\ge 0\}$ 需要同步三个无界计数，不是上下文无关语言。另一个边界是文法本身可能歧义：同一字有多个推导树并不改变成员集合，却会给编程语言解析带来不同结构。

CFG 与下推自动机公理库下推自动机Pushdown automaton · PDA带无界栈存储的有限控制自动机。由CFG–PDA 等价定理公理库CFG–PDA 等价定理CFG–PDA equivalence上下文无关文法生成的语言恰为下推自动机接受的语言。刻画同一语言类。允许产生式读取上下文并保持非收缩，会得到更强的上下文有关语言公理库上下文有关语言Context-sensitive language · CSL可由非收缩文法生成、允许产生式读取局部上下文的形式语言类。；两者在Chomsky 层级公理库Chomsky 层级Chomsky hierarchy按产生式限制排列正则、上下文无关、上下文有关与递归可枚举语言，并由典型语言证明严格包含。中的位置与严格分离应由层级页承担，而不是混入 CFG 定义。语法树公理库语法树Parse tree · Derivation tree用树形结构记录文法产生式如何从开始符号生成一个字。记录具体推导结构，Chomsky 范式与 CYK 算法提供标准化和判定方法。

编程语言语法、配置文件、自然语言片段和递归数据格式常用 CFG 描述；解析器再把终结符流转换为 AST，并处理优先级与歧义。