上下文无关文法

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

文法

生成 $\{a^n{b}^n:n\ge 0\}$。每用一次 $S\to aSb$，就给尚未展开的 $S$ 左右各加一个符号：$S\Rightarrow aSb\Rightarrow aaSbb$；最后用 $S\to \epsilon$ 移去中间的待办符号，得到 aabb。图中的叶子从左到右给出同一结果。任意有限次展开后，中间句型总是 $a^{k}S{b}^k$；只有使用空规则才能结束，因此不会生成 abab 或 aab。反过来，要生成 $a^n{b}^n$，展开恰好 $n$ 次再结束即可。这两个方向共同说明语言“恰好”是什么。

平衡括号可由 $S\to SS\mid (S)\mid \epsilon$ 描述：$SS$ 把两个平衡片段并排放置，$(S)$ 在一个平衡片段外包一层。比如 $S\Rightarrow SS\Rightarrow (S)S\Rightarrow ()S\Rightarrow ()(S)\Rightarrow ()()$ 展示的是连接，$S\Rightarrow (S)\Rightarrow ((S))\Rightarrow (())$ 展示的是嵌套。

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

歧义不能仅凭“有两种改写顺序”判断。对 $S\to AB,A\to a,B\to b$，先改写 $A$ 或先改写 $B$ 都得到 ab，但只有一棵树。相反，$E\to E+E\mid E\ast E\mid a$ 对 a+a*a 可把根分成加法或乘法，对应 $a+(a\ast a)$ 与 $(a+a)\ast a$ 两种结构。固定最左推导仍会留下这两种选择，因此它们才见证歧义。

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，并处理优先级与歧义。

从栈机器反向构造文法公理库CFG–PDA 等价定理CFG–PDA equivalence上下文无关文法与非确定性下推自动机刻画同一语言类；三元变量描述受保护的弹栈段，完整八变量例子及双向归纳将运行转换为推导。给出另一种得到规则的方式：状态与栈符号组合成变量，运行的首次弹栈边界决定子推导的分割。完整八变量例子也展示了不生成变量的删除；有递归产生式并不保证存在有限的终结推导。

PEG公理库解析表达式文法 PEGParsing expression grammar · PEG以有序选择、序列和不消费前看定义确定前缀识别结果的文法。的有序选择不等于 CFG 的备选产生式。CFG 的 $S\to aC\mid abC$、$C\to c$ 同时生成 ac 与 abc，规则排列次序无关；把同样外观写成 PEG 的 $(\mathtt{\text{"a"}}/\mathtt{\text{"ab"}})\mathtt{\text{"c"}}$，在 abc 上却会先让短分支成功，再因后面的 c 失败而拒绝。比较的是生成式的存在选择与识别式的优先承诺，不能未经证明把两套文法互换。