形式语言与解析

形式语言是字母表上有限字符串的集合。文法定义从该集合中推导字符串的产生式。 编译器前端使用这一模型，将局部的词法识别与递归的程序结构分开。

Chomsky 文法层次 #

Chomsky 层次按照产生式限制对文法分类：

1. 类型 3，即正规文法，描述可由有限自动机识别的正规语言。正则表达式和词法分析器属于这一层。
2. 类型 2，即上下文无关文法（CFG），每个产生式左侧只有一个非终结符，并由下推自动机识别。
3. 类型 1，即上下文有关文法，限制产生式不能缩短句型，但规定的开始符号情况除外。
4. 类型 0，即无限制文法，不施加可比的产生式限制。

平衡分隔符体现了这种边界。有限自动机无法记住无界的嵌套深度，而 CFG 可以通过如下递归处理： Group → '(' Group ')' Group | ε。

推导、树和二义性 #

推导从开始符号向终结符应用产生式。解析树记录推导的层次结构。 当一个字符串具有多个解析树或等价的最左推导时，文法是二义的。

Expr → Expr '-' Expr | number

在该文法下，输入 number - number - number 存在相互竞争的分组。 可以重写文法来编码结合性，例如使用左递归的 Expr → Expr '-' Term | Term， 或者在冲突解决策略明确时使用解析器生成器的优先级声明。 当生成的树必须直接表示语言语义时，优先使用文法结构。

自顶向下和自底向上解析 #

LL(\(k\)) 解析器从左到右读取，构造最左推导，并根据有限的前瞻选择产生式。 递归下降解析器直接实现这种风格；预测文法必须消除左递归，并使候选项在决策点可区分。

LR 解析器从左到右读取，通过移入标记和归约已识别的句柄，构造最右推导的逆过程。 LR 系列解析器可以处理左递归表达式文法以及更广泛的确定性 CFG， 但解析器生成器冲突表示存在二义性，或优先级策略规定得不充分。

前端边界和错误设计 #

词法分析器将字符分组为标识符、字面量、运算符和源位置等标记。 解析器根据文法产生式消费这些标记，并生成语法树或执行语义动作。 当注释、转义和数字拼写不影响嵌套或结构时，应将这些词法问题排除在产生式之外。

应将错误设计作为文法接口的一部分。词法分析器必须识别无效字符序列并安全前进。 解析器应报告意外标记及其位置，然后在选定的分隔符（例如语句终止符或右花括号）处同步。 恢复规则必须保证进展；接受任意标记只会隐藏后续错误并破坏生成的树。