形式文法

形式陈述 ​

形式文法是四元组

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

其中 $V$ 是有限非终结符集，$\mathrm{\Sigma }$ 是与 $V$ 不交的有限终结符字母表，$S\in V$ 是开始符号，$R$ 是有限产生式集。一般产生式写作

$$\alpha \to \beta ,\alpha ,\beta \in (V\cup \mathrm{\Sigma }{)}^{\ast },$$

并要求左侧 $\alpha$ 至少含一个非终结符；否则规则会凭空改写一段已经完成的终结符字，失去“展开尚未生成结构”的含义。

若 $u\alpha v$ 中出现某条规则的左侧，就可一步改写为 $u\beta v$，记作 $u\alpha v{\Rightarrow }_{G}u\beta v$。由这项一步关系公理库关系Relation · Binary relation带源集与目标集的二元关系，其底层关系图是 A×B 的子集。的自反传递闭包得到多步推导 ${\Rightarrow }_G^{\ast }$。文法生成的形式语言公理库形式语言Formal language · Language over an alphabet字母表上有限字符串集合的抽象，是自动机输入与计算问题编码的基本对象。是

$$L(G)=\{w\in {\mathrm{\Sigma }}^{\ast }:S{\Rightarrow }_G^{\ast }w\}.$$

非终结符只在推导中充当结构标记，最终字只能由终结符组成。文法、某次推导与生成语言是三个层次：同一个语言可以有多份文法，同一份文法也可能用多条路径生成同一个字。

直觉 ​

文法从一个开始符号出发，反复把仍待展开的片段替换成更具体的符号串。它像一套有限的搭建规则：规则数量有限，推导长度却没有固定上界，所以可以描述任意深的递归结构。与自动机从输入外部读取一个字不同，文法从内部把字生成出来；二者何时具有相同表达能力，是各语言层的机器—文法对应定理所研究的问题。

本页只固定所有 Chomsky 类型共享的语法接口，不预先限制产生式形状。上下文无关文法公理库上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。要求左侧恰为一个非终结符；上下文有关文法进一步用非收缩或等价的上下文规则限制改写；正则文法则把规则收紧到线性形状。限制越强，可用的推导越少，但由某份较自由文法写出并不证明语言本身需要更高层能力。

例子与边界 ​

取 $V=\{S\}$、$\mathrm{\Sigma }=\{a,b\}$ 与规则

$$S\to aSb,S\to \epsilon .$$

推导 $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ 展示了规则如何在有限次替换后只留下终结符；同一文法生成 $\{a^n{b}^n:n\ge 0\}$。这个例子恰好是 CFG，因为每条规则左侧只有 $S$，但通用形式文法允许左侧包含更长上下文。

产生式箭头不是逻辑蕴含，也不是程序赋值。它描述字形的局部重写；若要给生成的语法树附上求值、类型或概率，还需额外的语义动作、属性或权重。允许 $\epsilon$ 规则也不等于所有文法都能任意删除符号：不同文法类别对收缩规则有不同边界，必须在相应定义中固定。

文法有限不意味着生成语言有限，也不保证成员资格、歧义性或等价性都可判定。表达能力越高，许多分析问题越早越过可判定边界；不能从“规则能写下来”推出“存在通用解析算法”。

推论与应用 ​

Chomsky 层级公理库Chomsky 层级Chomsky hierarchy按产生式限制排列正则、上下文无关、上下文有关与递归可枚举语言，并由典型语言证明严格包含。按产生式约束排列正则、上下文无关、上下文有关与不受限文法，并分别联系有限自动机、下推自动机、线性有界自动机和图灵机。该层级比较语言是否存在某种受限文法，而不是比较两份规则文本的长度。

编译器与数据格式通常选用 CFG，以便从 token 流恢复嵌套结构；字符串重写、语法变换和可计算性研究则会使用更一般的文法。语法树公理库语法树Parse tree · Derivation tree用树形结构记录文法产生式如何从开始符号生成一个字。记录一次 CFG 推导的层次结构，但一般文法的规则左侧可跨越多个符号，未必自然形成同样的单父节点树。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Chapters 1 and 5–11.
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Chapters 2 and 4.