上下文无关文法入门

学习目标

通过本集的学习，你将能够：

理解什么是文法
掌握产生式规则
区分终结符和非终结符
写出简单的算术表达式文法

1. 什么是文法？

文法是描述语言语法的一套规则。

1.1 自然语言的文法类比

中文句子的文法：
句子 → 主语 谓语 宾语
主语 → 名词 | 代词
谓语 → 动词
宾语 → 名词

例子：
句子 → 我 吃 饭
     → 主语 谓语 宾语

1.2 编程语言的文法

算术表达式的文法：
表达式 → 表达式 + 表达式
       | 表达式 - 表达式
       | 表达式 * 表达式
       | 表达式 / 表达式
       | ( 表达式 )
       | 数字

数字 → 0 | 1 | 2 | ... | 9

2. 上下文无关文法的组成

2.1 四元组

上下文无关文法（CFG）由四个部分组成：

G = (V, T, P, S)

V: 非终结符集合
T: 终结符集合
P: 产生式规则集合
S: 开始符号

2.2 终结符与非终结符

终结符（Terminal）：
- 不能再分解的符号
- 如：+、-、*、/、(、)、数字
- 用小写字母表示

非终结符（Non-terminal）：
- 可以继续分解的符号
- 如：表达式、语句、数字
- 用大写字母表示

3. 产生式规则

3.1 基本形式

产生式形式：
A → α

A: 非终结符
α: 终结符和/或非终结符组成的串

3.2 多个产生式

同一个非终结符可以有多个产生式：
E → E + E
E → E * E
E → (E)
E → id

或者简写为：
E → E + E | E * E | (E) | id

4. 简单的算术表达式文法

4.1 完整的例子

G = (V, T, P, E)

V = {E, T, F}
T = {+, *, (, ), id}
S = E

产生式P：
E → E + T | T
T → T * F | F
F → (E) | id

4.2 解释

E: 表达式（Expression）
T: 项（Term）
F: 因子（Factor）

优先级：
* 高于 +
括号可以改变优先级

5. 实用案例

5.1 案例1：简单表达式

文法：
E → E + T | T
T → T * F | F
F → (E) | id

推导 id + id * id：
E → E + T
  → T + T
  → F + T
  → id + T
  → id + T * F
  → id + F * F
  → id + id * F
  → id + id * id

5.2 案例2：括号表达式

推导 (id + id) * id：
E → T
  → T * F
  → F * F
  → (E) * F
  → (E + T) * F
  → (T + T) * F
  → (F + T) * F
  → (id + T) * F
  → (id + F) * F
  → (id + id) * F
  → (id + id) * id

6. 自测问题

什么是上下文无关文法？
终结符和非终结符有什么区别？
什么是产生式规则？
请写出一个简单的算术表达式文法。
为什么需要区分表达式、项、因子？

7. 下集预告

下一集我们将学习推导与语法树！

参考资料

《编译原理》（龙书）
《现代编译原理》（虎书）