形式文法

形式文法把合法结构写成可操作的符号规则，而不是只列举一些正确例子。终结符是最终字符串中的符号；非终结符是生成过程中可以继续展开的符号；开始符号指定推导的起点；产生式规定如何替换。一个文法生成的语言，是从开始符号能够推导出的全部终结符串。

上下文无关文法是一种常用形式，每条产生式左侧只有一个非终结符，右侧可以包含终结符和非终结符。这里的“上下文无关”表示替换这个非终结符时，不必检查它左右邻接的符号。它是形式文法的一类，不能把所有形式文法都定义为这种规则。

参考：[1]

设开始符号为 S，终结符为 a、b，规则为 S → aSb 或 S → ε，其中 ε 表示空串。使用两次第一条规则，再用第二条结束，就得到 S ⇒ aSb ⇒ aaSbb ⇒ aabb。每次展开都在两端各增加一个符号，所以最终结果恰好是若干个 a 后跟同样多个 b，也包括空串。

这个例子区分了规则、过程和结果：S → aSb 是产生式，连续替换是推导，aabb 是生成的字符串，而所有可能结果合起来才是语言。递归规则允许有限的文法描述无限多的字符串，不表示某一次有限推导会生成一个无限长的串。

参考：[1]

推导可以组织成树，以父子关系记录结构如何展开；解析器则从输入出发寻找符合语法的结构。具体语法树通常保留较多语法细节，抽象语法树着重保留后续处理需要的构造。LLVM 的教学编译器把括号用于确定分组，却不必为括号本身保留独立的抽象语法树节点。

结构仍需配合语义规则。假设语法允许“名字 + 数字”，那么 x + 2 可以有明确的语法树，但 x 指什么、它能否与数字相加、计算结果是多少，并不能仅从这棵树得知。名称解析、类型规则和求值规则解决的是另一些问题。

同一字符串也可能在给定文法中有两棵不同的解析树，这叫文法歧义。例如E → E + E | E × E | n，其中n代表数值字面量记号，就允许2 + 3 × 5分别按2 + (3 × 5)或(2 + 3) × 5分组，算术含义便不同。可以在这个例子中引入表达式、项和因子等非终结符，让乘法在比加法更深的一层展开，在保留同一字符串语言的同时规定优先级；不能假定解析器选出一棵树，就证明原文法本来无歧义。

参考：[3] [2] [5]

语言文档常使用 BNF 或 EBNF 风格的记号，以规则名表示可展开结构，用引号标明字面符号，再用选择、重复和可选记号压缩写法。阅读时必须先核对文档对这些符号的定义：相似的外观不保证相同的形式含义。

例如上下文无关文法中的备选产生式，与解析表达式文法 PEG 的有序选择并不相同。PEG 按次序尝试备选项，前一项成功后不再尝试后项，交换顺序可能改变结果。Python 的 PEP 617 讨论了这种差别，以及文法、解析器和抽象语法树生成之间的关系。规则描述与具体解析算法应当分清。

参考：[2] [4]