第3章 上下文无关文法及分析

语法分析（Syntax Analysis）确定程序的语法结构，上下文无关文法（CFG）是定义程序语言语法的标准工具。

3.1 分析过程

  • 输入：记号流（来自扫描程序）
  • 输出：分析树/语法树
  • 语法由上下文无关文法（CFG） 定义
  • 与正则表达式不同，CFG 支持递归规则，能描述嵌套结构（如 if 嵌套、匹配括号）

3.2 上下文无关文法（CFG）

形式定义

CFG 由四部分组成：

  1. 终结符集合 T（token 集合）
  2. 非终结符集合 N（语法变量）
  3. 产生式集合 P（规则 A → α，其中 A∈N，α∈(N∪T)*）
  4. 开始符号 S（S∈N）

表示法

  • BNF（Backus-Naur Form）：<stmt> → if <expr> then <stmt>
  • 常用约定：非终结符用尖括号或大写字母，终结符用等宽/小写

推导

  • 最左推导：每一步替换最左边的非终结符
  • 最右推导：每一步替换最右边的非终结符
  • 归约：推导的逆过程
  • 递归规则：A → Aa | a 生成语言 {a^n | n≥1}

文法分类（Chomsky 层次）

类型 名称 产生式限制 对应的自动机
0 型 无限制文法 无限制 图灵机
1 型 上下文有关文法 αAβ → αγβ（γ≠ε） 线性有界自动机
2 型 上下文无关文法 A → γ 下推自动机（PDA）
3 型 正则文法 A → aB 或 A → a 有穷自动机（FA）

包含关系： 3型 ⊂ 2型 ⊂ 1型 ⊂ 0型

3.3 分析树与抽象语法树

分析树（Parse Tree）

![[编译原理/attachments/figures/ch03_s34_3.3.1 Parse trees.png]]

图中英文：parse tree=分析树，exp=expression（表达式），op=operator（运算符），term=项，factor=因子，id=identifier（标识符），number=数字

  • 内部节点：非终结符标记
  • 叶子节点：终结符标记
  • 完整反映推导过程（信息量大）

![[编译原理/attachments/figures/ch03_s36_3.3.1 Parse trees.png]]

图中英文：stmt=statement（语句），stmt-sequence=语句序列，if-stmt=if语句，repeat-stmt=repeat语句，assign-stmt=赋值语句，read-stmt=读语句，write-stmt=写语句

抽象语法树（AST）

![[编译原理/attachments/figures/ch03_s39_3.3.2 Abstract syntax trees.png]]

图中英文：syntax tree=语法树，assign=赋值，op=运算，id=标识符，const=常量

![[编译原理/attachments/figures/ch03_s41_3.3.2 Abstract syntax trees.png]]

图中英文：abstract syntax tree=抽象语法树，OpK=运算符节点，ConstK=常量节点，IdK=标识符节点，StmtK=语句节点，ExpK=表达式节点

  • 浓缩的分析树
  • 去除对语法分析无意义的节点（如括号、分隔符）
  • 更紧凑，便于后续处理

3.4 二义性

二义性文法

  • 定义：一个文法允许同一串有两个或更多不同的分析树
  • 二义性 ≠ 文法有语法错误，但给编译器带来问题

经典例子：悬挂 else（dangling else）

stmt → if expr then stmt | if expr then stmt else stmt

输入 if E1 then if E2 then S1 else S2 有两种解释

消除二义性的方法

  1. 消除二义性规则：不改变文法，规定优先级和结合性
    • 例：规定乘法优先级高于加法，减法左结合
  2. 重写文法：将二义结构在文法层面消除
    • 优先级联（precedence cascade）：将不同优先级的算符放在不同产生式层次
// 通过优先级联消除二义性
exp → exp addop term | term
term → term mulop factor | factor
factor → (exp) | number
  1. 悬挂 else 消除：
stmt → matched_stmt | unmatched_stmt
matched_stmt → if expr then matched_stmt else matched_stmt | other
unmatched_stmt → if expr then stmt | if expr then matched_stmt else unmatched_stmt
  1. 无关紧要的二义性：产生相同 AST 的二义性可忽略

3.5 扩展的表示法：EBNF 和语法图

EBNF（Extended BNF）

  • [...] 表示可选部分
  • {...} 表示重复 0 次或多次
  • (...) 用于分组
if-stmt → if (expr) statement [else statement]

语法图（Syntax Diagram）

  • 图形化的文法表示
  • 流程图风格，直观易懂

3.6 上下文无关语言的形式特性

形式定义

上下文无关文法 G = (T, N, P, S)

  • 直接推导：αAβ ⇒ αγβ（若 A→γ∈P）
  • 推导：⇒*（零步或多步直接推导）
  • 句子：仅由终结符组成的串
  • 语言：L(G) = {w ∈ T* | S ⇒* w}

乔姆斯基范式和格雷巴赫范式

  • CNF（乔姆斯基范式）：A → BC 或 A → a
  • GNF（格雷巴赫范式）：A → aα

区别要点

  • 正则语言（3 型）可用 DFA 识别，不能处理嵌套结构
  • 上下文无关语言（2 型）可处理嵌套结构（如匹配括号、嵌套 if）
  • 典型非正则语言：{a^n b^n | n ≥ 0}（无法用正则表达式描述）

3.7 TINY 语言的语法

  • 程序 → 语句序列（分号分隔）
  • 语句类型：if-stmt, repeat-stmt, read-stmt, write-stmt, assign-stmt
  • 表达式：算术（+ - * /）和布尔比较（= <）
  • 语法树节点类型：StmtNode（If, Repeat, Assign, Read, Write）、ExpNode（Op, Const, Id）

考试重点

★★★ 第一梯队

考点 典型题型
画分析树和语法树 给出一段代码，画出分析树和 AST
二义性判定 判断文法是否二义，说明原因

★★☆ 第二梯队

考点 典型题型
消除二义性 改写文法消除悬挂 else 或运算符优先级问题
最左/最右推导 写出给定串的推导过程
CFG 写法和识别 根据语言描述写出文法

★☆☆ 第三梯队

考点 典型题型
EBNF 与 BNF 的相互转换 转换题
Chomsky 文法分类 分类题