4.1 CFG、终结符、非终结符、产生式与开始符号

正则语言和有限自动机给了词法分析器（lexer）一种有限的记忆能力。它足以识别标识符、数字、运算符和空白，但不足以表达程序中的嵌套结构。词法分析器可以把 ( 和 ) 分别识别成词法单元（token），却不能只凭有限状态验证任意深度的括号是否匹配，也不能描述嵌套表达式、代码块或递归调用。

上下文无关文法（context-free grammar，CFG）处理的正是下一层结构。它是一组有限的改写规则。从一个特殊符号开始，不断应用规则，就能生成该语言中所有合法的词法单元序列。语法分析器（parser）的工作可以看成反向证明：面对一个词法单元序列，判断它能否从开始符号推导出来。

“上下文无关”有严格含义。产生式替换一个非终结符时，不需要查看它左右相邻的符号。例如 Expr -> Expr + Term 表示任意位置上的 Expr 都可以按这条规则展开。像“只有前面出现 let 时才允许把 x 改写为某种结构”这样的条件不是 CFG 的规则，它们属于后续的名字解析或类型检查。

文法的形式定义

通常把 CFG 写作：

G = (V, T, P, S)

其中：

• V 是有限的非终结符集合。

• T 是有限的终结符集合。

• P 是有限的产生式集合。

• S 是特殊的开始符号，并且 S ∈ V。

约定上，V 与 T 不相交。一个符号不能既表示还可继续展开的结构，又表示最终句子中的词法单元。产生式写成：

A -> α

这里 A 必须是 V 中的一个非终结符；α 是终结符和非终结符构成的有限序列，也可以为空。空右部写作 ε。

例如下面是一门小型表达式语言：

G = (V, T, P, Expr)

V = { Expr, Term, Factor }
T = { id, number, +, *, (, ) }

Expr   -> Expr + Term | Term
Term   -> Term * Factor | Factor
Factor -> id | number | ( Expr )

Expr、Term、Factor 并不是用户直接写进程序的词，而是语言设计者定义的结构类别。id、number、+、*、(、) 则是词法分析器输出的终结符类别。

在真实编译器中，终结符通常是词法单元类别，不是原始字符。语法分析器看到的应该是 IDENT、INT、PLUS、LPAREN、RPAREN，而不是单个 Unicode 字符。这样词法分析器专注于拼写和词法单元边界，语法分析器专注于词法单元顺序与嵌套，两个阶段的契约会更清楚。

终结符是结果，非终结符是待完成的结构

一个很实用的判断方式是：

• 终结符会保留在语言最终生成的句子中。

• 非终结符仍然可以继续被某条产生式展开。

在表达式文法中：

id + number * id

只包含终结符，因此它是语言中的候选句子。相反：

Expr + Term

不是用户写的源程序，而是推导过程中的句型（sentential form）：它同时含有终结符和还未展开的非终结符。

这一区分还能避免一个常见误解。IDENT 虽然可以代表 total、count_2、renderNode 等无限多种词素（lexeme），但在文法中它依然是一个终结符。文法只需要描述词法单元类别，不需要为每一个可能的变量名写一条产生式。

字面量也是同样的道理：

Primary -> IDENT | INT | STRING

文法不需要分别列出 42、43、44。词法分析器已经识别出具体词素，并把它的文本或数值附加在 INT 词法单元上。语法分析器只需要知道当前位置满足 INT 这个终结符类别。

产生式描述允许的形状，不是执行命令

下面的竖线：

Factor -> id | number | ( Expr )

表示可选择的候选右部，它是三条产生式的缩写：

Factor -> id
Factor -> number
Factor -> ( Expr )

产生式是声明式的。它不直接规定语法分析器在运行时“必须”选择哪一条。它定义所有合法形状；第 5、6 章的分析算法才会根据向前看符号（lookahead）、分析表、语法分析器状态或冲突处理策略决定实际走哪个分支。

ε 产生式要特别认真对待：

Params -> ParamList | ε

它表示调用可以带参数，也可以完全没有参数。ε 不是一个字符，不是缺失词法单元，也不是词法分析器错误；它是长度为零的符号串。因为空产生式会引入可选语法、循环和预测冲突，后续学习 FIRST/FOLLOW 集时会反复分析它的影响。

开始符号定义完整程序的边界

开始符号应该代表一份完整的编译单元，而不是随手选第一个非终结符：

Program -> DeclarationList EOF

这样语法分析器只有识别完整个 Program 并抵达 EOF 时才接受输入。如果开始符号只是 Expr，那么它可能接受 1 + 2，却悄悄忽略后面的 ; garbage，这对编译器来说通常不可接受。

有时会加一个增广开始符号：

Start -> Program EOF

这个包装层在 LR 分析和形式化转换中尤其常见，因为它给接受状态提供了唯一、清晰的目标。

文法是编译前端的结构契约

设计良好的文法会让后续阶段更简单。它应当暴露语义分析、IR 生成、格式化和错误诊断所需要的结构。例如：

Stmt -> IDENT = Expr ;

这条规则说明赋值语句以一个标识符形状的词法单元开头，但它不证明这个标识符一定绑定到可写变量，也不证明右侧 Expr 的类型兼容。它只为后续阶段提供一个稳定的语法节点：左侧、右侧和相应的源码范围。

CFG 也不能表达所有编程语言规则：

• “变量必须先声明后使用”需要符号表。

• “+ 两边的类型必须兼容”需要类型检查。

• “break 必须位于循环或 switch 中”需要上下文语义分析。

• “函数的所有控制流路径都必须返回值”需要控制流分析。

所以文法既不能太弱，也不应该硬塞进语义职责。它的核心任务是识别层次化词法单元结构，为后续编译阶段建立可靠基础。

在正确层次使用文法

Stmt -> IDENT = Expr ; 只说明左侧具有标识符语法、右侧具有表达式语法；它不证明名字已声明、可写，或右侧类型兼容。把职责分开才能得到好诊断：语法分析器报缺少分号，后续分析报“不能给不可变名字赋值”。

新增产生式时应问：该非终结符代表什么完整单元？什么词法单元结束它？开始符号是否要求 EOF？这能避免语法分析器接受合法前缀却悄悄忽略尾随垃圾。