编译原理文法语言的相关概念

文法与语言

2.1 引言：文法的“编译角色”

文法是编译过程“语法分析阶段”的形式化工具，核心作用是将“自然语言式的语法规则”转化为“机器可推导的严格规则”。

• 编译流程中，词法分析处理“正则文法（3型）”（描述标识符、关键字等词法单元的模式）；语法分析处理“上下文无关文法（2型）”（描述表达式、语句等语法结构）。

• 程序设计语言需“无歧义”：若语法存在歧义（如“id+id*id有两种解释”），编译器无法确定代码的逻辑结构，因此必须用“形式化文法”严格约束语法。

2.2 字母表-符号串-运算（形式语言基础）

这是“用数学符号描述语言”的底层逻辑，需明确集合、序列、运算的形式化定义：

（1）字母表（Σ）

• 定义：非空有限的符号集合。例：Σ₁ = {0, 1}（二进制字母表）；Σ₂ = {a, b, ..., z}（小写字母表）；Σ₃ = {id, +, *, (, )}（某算术表达式的终结符集合）。

（2）符号串（String）

• 定义：设Σ为字母表，符号串x是Σ中符号的有限序列。

  • 长度：|x|表示符号串的符号个数。例：x = abc，则|x| = 3；
  • 空串：ε（长度为0的符号串，|ε| = 0）。

（3）符号串的运算

• 连接（Concatenation）：若x = "ab"，y = "cd"，则x·y = "abcd"（简记为xy）。性质：不满足交换律（xy ≠ yx，除非x=y或特殊构造）。

• 幂（Power）：

  • x⁰ = ε（空串）；
  • x¹ = x；
  • xⁿ = xⁿ⁻¹ · x（递归定义，例：x="ab"，则x²="abab"）。

• 闭包（Closure）：

  • 星闭包（Σ*）：Σ中符号组成的**所有可能的符号串（含空串ε）**的集合。例：Σ = {a, b}，则Σ* = {ε, a, b, aa, ab, ba, bb, aaa, ...}。
  • 正闭包（Σ+）：Σ中符号组成的所有非空符号串的集合（即Σ* - {ε}）。例：Σ = {a, b}，则Σ+ = {a, b, aa, ab, ba, bb, ...}。

2.3 文法模型★（形式化四元组）

文法是描述语言语法的四元组 G = (V_N, V_T, P, S)，各组件需结合“算术表达式文法”实例理解：

（1）非终结符（V_N：Non-terminal Symbols）

• 定义：语法变量，表示“语法范畴/中间推导结果”，最终不会出现在“语言的句子”中。

• 例：描述“算术表达式”的文法中，V_N = {E, T, F}（E表示“表达式”，T表示“项”，F表示“因子”）。

（2）终结符（V_T：Terminal Symbols）

• 定义：语法的最小单位，是语言的“最终符号”，无法再被推导分解。

• 例：算术表达式文法中，V_T = {id, +, *, (, )}（id为标识符，+/*为运算符，()为括号）。

（3）产生式（P：Productions）

• 形式：α → β（读作“α定义为β”），表示“用β替换α”。

  • α（左部）：至少包含一个非终结符（否则无法推导）；
  • β（右部）：可由“终结符、非终结符的任意组合”或空串ε组成。

• 例：算术表达式的核心产生式：

  • E → E + T（“表达式可以是‘表达式 + 项’”）；
  • T → T * F（“项可以是‘项 * 因子’”）；
  • F → (E)（“因子可以是‘括号中的表达式’”）；
  • F → id（“因子可以是‘标识符’”）。

（4）开始符号（S：Start Symbol）

• 定义：V_N中指定的“起始语法变量”，所有推导从S开始。

• 例：算术表达式文法中，S = E（推导从“表达式E”开始）。

2.4 推导与句型（文法的“动态推导过程”）

推导是“从开始符号出发，用产生式逐步替换非终结符”的过程；句型和句子是推导的“中间/最终结果”，需用推导符号（⇒、⇒*、⇒+）形式化描述：

（1）推导符号

• α ⇒ β：一步推导（用一条产生式，将α中的某部分替换为β）；

• α ⇒* β：零步或多步推导（α可直接等于β，或经若干步推导得到β）；

• α ⇒+ β：一步或多步推导（α经至少一步推导得到β）。

（2）推导类型

• 最左推导：每次优先替换“最左侧”的非终结符；

• 最右推导（规范推导）：每次优先替换“最右侧”的非终结符（编译中“语法分析”的核心方式，对应“规范归约”）。

（3）句型与句子

• 句型：若S ⇒* α且α ∈ (V_N ∪ V_T)*（α含终结符或非终结符），则α是句型；

• 句子：若S ⇒* α且α ∈ V_T*（α仅含终结符），则α是句子（语言的“合法最终形式”）。

实例：算术表达式的最左推导

文法：E → E+T | T；T → T*F | F；F → (E) | id。推导句子id+id*id的最左推导过程：

1. E ⇒ E+T（用E→E+T，替换最左的E）；

2. T+T ⇒ F+T（用T→F，替换最左的T）；

3. id+T ⇒ id+T*F（用T→T*F，替换最左的T）；

4. id+F*F ⇒ id+id*F（用F→id，替换最左的F）；

5. id+id*id（用F→id，替换最左的F）。

• 中间结果如E+T、T+T、id+T、id+T*F、id+F*F、id+id*F都是句型（含非终结符）；

• 最终结果id+id*id是句子（仅含终结符）。

2.5 文法的类型（乔姆斯基分类）

乔姆斯基将文法分为4类（限制逐渐严格，呈“包含关系：3型 ⊂ 2型 ⊂ 1型 ⊂ 0型”），核心区别是“产生式的限制规则”，需结合自动机、语言类型联动理解：

文法类型	别称	产生式限制	生成的语言	对应自动机	编译中的应用
0型（无限制）	短语结构文法（PSG）	α→β，其中α至少含一个非终结符，β为(V_N∪V_T)*中任意串（可含ε）	递归可枚举语言	图灵机	理论基础，无直接编译应用
1型（上下文有关）	上下文有关文法（CSG）	α→β满足`	α	≤	β
2型（上下文无关）	上下文无关文法（CFG）	产生式左部为单个非终结符（即A→β，A∈V_N，β∈(V_N∪V_T)*）	上下文无关语言	下推自动机（PDA）	描述程序设计语言的语法核心（如表达式、语句、函数定义）
3型（正则文法）	正则文法（RG）	产生式为左线性（A→Ba 或 A→a）或右线性（A→aB 或 A→a），其中A,B∈V_N，a∈V_T∪{ε} 右侧最多一个非终结符且必须在最左或最右	正则语言	有限自动机（FA）	描述词法规则（如标识符、关键字、常数的模式）

2.6 文法的构造与简化★

（1）文法构造：“自然语言→产生式”的转化

需将“语法规则的自然描述”转化为“形式化产生式”，核心是设计非终结符同步语法结构。

• 例1：构造语言 L = {aⁿbⁿ | n≥1}（“n个a后跟n个b”的所有串）的文法。思路：用非终结符S同步a和b的数量，产生式需保证“每生成一个a，就对应生成一个b”。文法：G = ({S}, {a, b}, {S→aSb | ab}, S)。推导验证：n=1时，S⇒ab；n=2时，S⇒aSb⇒aabbb，符合aⁿbⁿ。

• 例2：构造“以字母开头，后跟字母或数字”的标识符文法。思路：用I表示“标识符”，L表示“字母”，D表示“数字”，通过产生式串联结构。文法：G = ({I, L, D}, {a,...,z,0,...,9}, {I→LI | L, L→LI | LD | L | D}, I)（L可推导为字母或数字，I以L开头，后跟L或D）。

（2）文法简化：消除冗余，便于分析

需消除无用符号、ε产生式、单产生式，使文法更简洁。

• 消除无用符号：无用符号包括“不可达符号”（从S推导不出的符号）和“不可终止符号”（无法推导出终结符串的符号）。例：文法G = ({S, A, B, C}, {a, b}, {S→aA, A→bB, B→aA, C→aB}, S)。

  • “不可达符号”：C（S无法推导出C），需删除含C的产生式；
  • 简化后文法：G' = ({S, A, B}, {a, b}, {S→aA, A→bB, B→aA}, S)。

• 消除ε产生式：若产生式含A→ε（A非开始符号），需将其他产生式中A的出现替换为ε的可能。例：文法G = ({S, A}, {a, b}, {S→aA | ε, A→b | ε}, S)。

  • 因A→ε，S→aA可推导出S→a（当A→ε时）；
  • 简化后文法：G' = ({S, A}, {a, b}, {S→aA | a | ε, A→b}, S)。

• 消除单产生式（形如A→B，A,B∈V_N）：需将A的产生式替换为B的所有“非单产生式”。例：文法G = ({S, A, B}, {a, b}, {S→A, A→B | a, B→b | A}, S)。

  • S→A等价于S→B | a（因A→B | a）；
  • A→B等价于A→b | a（因B→b | A，但A→A是无用循环，最终保留A→b | a）；
  • 简化后文法：G' = ({S, A, B}, {a, b}, {S→B | a, A→b | a, B→b | a}, S)。

2.7 语法树（推导的“可视化表示”）

语法树（推导树）是直观展示推导层次结构的树结构，各节点与文法组件一一对应：

• 根节点：开始符号S；

• 内部节点：非终结符（对应产生式左部）；

• 叶节点：终结符或空串ε（对应产生式右部的符号）。

实例：表达式id+id*id的语法树

基于文法E→E+T | T；T→T*F | F；F→(E) | id，语法树结构为：

graph TD
    E --> E1[E]
    E --> op_plus[+]
    E --> T1[T]
    E1 --> T2[T]
    T2 --> F1[F]
    F1 --> id1[id]
    T1 --> T3[T]
    T1 --> op_mul[*]
    T1 --> F2[F]
    T3 --> F3[F]
    F3 --> id2[id]
    F2 --> id3[id]

语法树的作用：

• 直观展示“语法层次”（如“乘法先于加法”的结构）；

• 判断文法二义性（若一个句子对应多棵语法树，文法是二义的）。

2.8 文法的二义性（关键问题与解决）

若一个文法存在某个句子有“多棵语法树”或“多种最左/最右推导”，则称该文法是二义的。

（1）二义性实例：表达式文法

文法G = ({E}, {id, +, *, (, )}, {E→E+E | E*E | (E) | id}, E)对句子id+id*id存在两种最左推导：

• 推导1（先加后乘）：E ⇒ E+E ⇒ id+E ⇒ id+E*E ⇒ id+id*E ⇒ id+id*id。

• 推导2（先乘后加）：E ⇒ E*E ⇒ E+E*E ⇒ id+E*E ⇒ id+id*E ⇒ id+id*id。

对应的两棵语法树也不同，因此该文法是二义的。

（2）消除二义性：改写文法（规定优先级/结合性）

通过“分层产生式”让产生式隐含“运算符优先级/结合性”，从而消除歧义。

例：规定“*优先级高于+，且均为左结合”，改写文法为：

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，且仅对应一棵语法树，消除了二义性。