文法

文法概览与上下文无关文法（CFG）详解

---

1️⃣ 语法（Grammar）到底是什么？

在形式语言理论中，文法是一套产生式规则（production rules），用来描述一个语言（即一组合法字符串）如何“生成”。
每个文法由四个基本要素组成：

组成	符号	说明
非终结符（Non‑terminal）	大写字母或 <...> 等	用来表示 抽象结构，在推导过程中会被展开。
终结符（Terminal）	小写字母、数字、标点等	最终出现在语言中的 实际字符，不能再继续展开。
开始符号（Start symbol）	通常记作 S	推导的起点。
产生式（Production）	A → α	当左侧为非终结符 A，右侧 α 为终结符/非终结符的任意串。

文法的任务是：从 开始符号 出发，反复使用产生式，最终只剩终结符，从而得到语言中的一个句子。

---

2️⃣ 文法的层次——Chomsky 层级

诺姆·乔姆斯基（Noam Chomsky）把所有形式文法分成 四类（常称为 Chomsky Hierarchy），其中前三类（Type‑3、2、1）是最常见的：

类型	名称	产生式形式	对应语言	常见应用
Type‑3	正则文法（Regular Grammar）	A → aB 或 A → a（左线性/右线性）	正则语言	词法分析、有限状态机
Type‑2	上下文无关文法（Context‑Free Grammar, CFG）	A → γ，左侧只能是单个非终结符	上下文无关语言	编译器语法分析、算术表达式、XML/HTML
Type‑1	上下文相关文法（Context‑Sensitive Grammar, CSG）	αAβ → αγβ，左侧与右侧上下文均可出现	上下文相关语言	某些自然语言子集、约束性更强的编程语言特性
Type‑0	递归可枚举文法（Recursively Enumerable Grammar）	任意形式 α → β（只要求 α 非空）	所有可计算语言	图灵机模型、通用程序语言理论

常见误解：有时教材只提“正则、上下文无关、上下文相关”三种文法，省略了最强大的 Type‑0。但在理论上 四类 才完整。

下面重点讲 上下文无关文法（CFG）。

---

3️⃣ 什么是上下文无关文法（CFG）？

3.1 正式定义

CFG = (V, Σ, R, S)

• V：非终结符集合（Variables），如 {S, A, B, Expr, Term, Factor}
• Σ：终结符集合（Alphabet），如 {+, *, (, ), id, number}
• R：产生式集合（Rules），每条规则形如 A → γ，其中 A ∈ V，γ ∈ (V ∪ Σ)*
• S ∈ V：开始符号

上下文无关 指：左侧永远是单个非终结符，不依赖于它出现的上下文。

3.2 推导方式

• 左递归 vs 右递归
• 左most 推导（每一步展开最左侧的非终结符）
• rightmost 推导（每一步展开最右侧的非终结符）
• 句子（Sentential) 形式：在推导过程中的任何中间串（终结符/非终结符混合）

3.3 语法树（Parse Tree / Derivation Tree）

• 根节点是 S
• 内部节点是非终结符
• 叶子节点（从左到右）形成最终句子

语法树是 唯一（若文法是 二义的，则会有多棵树对应同一句子）。

---

4️⃣ CFG 的实例

4.1 基本算术表达式文法（最常见示例）

1.  Expr → Expr + Term | Expr - Term | Term
2.  Term → Term * Factor | Term / Factor | Factor
3.  Factor → ( Expr ) | number | id

• 终结符：{+, -, *, /, (, ), number, id}
• 非终结符：{Expr, Term, Factor}
• 开始符号：Expr

推导示例（生成 id + number * ( id - number )）：

Expr
→ Expr + Term
→ Term + Term
→ Factor + Term
→ id + Term
→ id + Term * Factor
→ id + Factor * Factor
→ id + number * Factor
→ id + number * ( Expr )
→ id + number * ( Term )
→ id + number * ( Factor )
→ id + number * ( id )

对应的 语法树（左递归形式）：

       Expr
     /  |   \
  Expr  +   Term
   |        / | \
 Term    Term * Factor
   |       |      |
Factor   Factor  ( Expr )
  |        |        |
 id     number    Expr
                     |
                   Term
                     |
                  Factor
                     |
                     id

为避免左递归导致的 LL(1) 解析冲突，常把文法改写成等价的 右递归 或 消除左递归 形式。

4.2 BNF（巴克斯-诺尔范式）写法

上例的 BNF（使用 ::= 表示产生式，| 表示选择）：

<Expr>   ::= <Expr> "+" <Term> | <Expr> "-" <Term> | <Term>
<Term>   ::= <Term> "*" <Factor> | <Term> "/" <Factor> | <Factor>
<Factor> ::= "(" <Expr> ")" | <Number> | <Identifier>

4.3 其他常见 CFG 示例

领域	文法（简化）	说明
编程语言	`Stmt → if ‘(‘ Cond ‘)’ Stmt else Stmt	while ‘(‘ Cond ‘)’ Stmt
正则表达式	`R → R “	“ S
自然语言（子集）	S → NP VP `NP → Det N	N
XML/HTML	Element → "<" Tag ">" Content "</" Tag ">" `Content → Element Content	Text

---

5️⃣ CFG 的关键性质

性质	描述	判定难易度
语言闭包	CFL 对 并、连接、星号 闭合；对 交、补 不闭合（补语言不一定是 CFL）。	交、补判定不可判定
等价性	两个 CFG 是否生成同一语言是不可判定的（等价问题）。	—
空语言（emptiness）	是否存在任意句子 w ∈ L(G) 可在 多项式时间 判定。	P
可达性（reachability）	某非终结符是否能够推导出终结符串，可在 线性时间 判定。	O(
二义性（ambiguity）	是否存在同一字符串对应多棵不同语法树，不可判定（一般只能手工或通过限定文法）	—
决定性	是否能用 LL(k)、LR(k) 等确定性自顶向下/自底向上解析器	取决于文法结构

---

6️⃣ CFG 的解析技术（Parsing Algorithms）

方法	适用文法	时间复杂度	备注
递归下降（手写 LL(1)）	LL(1) 文法（无左递归、左因子化）	O(n)	实现简单，常用于教学/小型 DSL
表驱动 LL(k)	LL(k) 文法（k ≥ 1）	O(k·n)	需要构造预测分析表
SLR / LR / LALR	LR(k) 文法（几乎所有实用编程语言）	O(n)	自动生成（Yacc/Bison、ANTLR）
Earley	任意 CFG（包括二义的）	O(n³) 最坏 / O(n²) 对二义 / O(n) 对 LR(k)	适合自然语言、快速原型
CYK（Cocke‑Younger‑Kasami）	CNF（Chomsky 正规形）	O(n³)	常用于语言成员性（membership）检测
Packrat（基于 PEG）	Parsing Expression Grammar（与 CFG 等价但不二义）	O(n)（需缓存）	实现简洁，常用于现代解析库

实际选型：

• 编程语言：LR/LALR（如 Yacc/Bison、ANTLR）
• 嵌入式 DSL：LL(1) 手写或递归下降
• 自然语言：Earley / CYK（或统计模型）
• 文档/配置文件：PEG + Packrat（如 Rust pest、Go participle）

---

7️⃣ CFG 与其他层次文法的关系

文法层级	包含关系	简单例子
正则文法 (Type‑3)	⊂ 上下文无关文法 (Type‑2)	a* b 能写成 `S → a S
上下文无关文法 (Type‑2)	⊂ 上下文相关文法 (Type‑1)	a^n b^n c^n 不是 CFL，但是 CSG
上下文相关文法 (Type‑1)	⊂ 递归可枚举文法 (Type‑0)	a^n b^n c^n 可用规则 a A b → a a A b b 生成
递归可枚举文法 (Type‑0)	= 所有可计算语言	图灵机可模拟的任意语言

注意：正则文法是 最强的可用有限状态机 能识别的语言，而 CFG 需要 栈（push‑down automaton, PDA）才能实现，这也是二者能力上的根本差别。

---

8️⃣ 如何手动设计一个 CFG？

1. 明确语言的结构
   • 列举基本构件（表达式、语句、块、标识符等）。
2. 划分层次（把大的结构拆成若干子结构）
   • 例：Program → StmtList、StmtList → Stmt StmtList | ε。
3. 写出产生式，确保左侧始终是单个非终结符。
4. 消除左递归（如果要用 LL 解析）
   • A → A α | β → A → β A' ; A' → α A' | ε。
5. 左因子化（消除同一前缀的冲突）
   • A → α β1 | α β2 → A → α A' ; A' → β1 | β2。
6. 检查二义性（手工构造或使用工具）
   • 若出现不同的解析树，考虑重新设计或使用 优先级/结合性 标记。
7. 转化为标准形式（可选）
   • CNF（Chomsky Normal Form）或 GNF（Greibach Normal Form）用于某些算法（如 CYK）。

工具推荐：

• ANTLR（生成 LL(*) 解析器）
• Bison/Yacc（LR/LALR）
• EarleyParser（Python earley 包）
• JFlex + CUP（Java 组合）

---

9️⃣ 小结 —— CFG 的核心要点

项目	关键点
定义	G = (V, Σ, R, S)；每条产生式左侧只能是单个非终结符
生成能力	与 压栈自动机 (PDA) 等价；可以描述嵌套结构（如括号匹配、递归表达式）
常用形式	BNF、EBNF、BNF++（用于语言规范）
解析算法	LL(1) → 手写；LR/LALR → Yacc/Bison；Earley → 通用；CYK → 成员性检测
局限	不能表达交叉依赖（如 a^n b^n c^n），对交、补不闭合
应用	编译器前端、解释器、配置文件、XML/HTML、部分自然语言子集、教学语言
与其他文法的关系	正则 ⊂ CFL ⊂ CSG ⊂ RE（递归可枚举）

---