编译技术4-1

Review from Last Time / 上一讲回顾

Goal of syntax analysis: Recover the syntax structure of the program. 语法分析的目标: 恢复程序的语法结构。
Idea:
- Use a context-free grammar (CFG) to describe the programming language. 思路: 使用上下文无关文法 (CFG) 来描述编程语言。
- Given a sequence of tokens, look for a parse tree that represents the syntax structure of those tokens. Recovering this syntax tree is called parsing. 给定一系列的词法单元，寻找一个解析树来表示这些词法单元的语法结构。恢复该语法树的过程称为解析**。

Different Types of Parsing / 解析的不同类型

Top-Down Parsing (this section) / 自顶向下解析（本节）: Start with the start symbol and try to guess the productions that should be applied to eventually derive the input string. 从起始符号开始，尝试猜测应该应用哪些产生式来推导出输入字符串。
Bottom-Up Parsing (next section) / 自底向上解析（下一节）: Start from the input string and work backwards, applying productions in reverse to reduce the input string to the start symbol. 从输入字符串开始，反向操作，应用产生式来将输入字符串归约为起始符号。

Top-Down Parsing / 自顶向下解析

Grammar Example: Let's consider a simple grammar: 文法示例:
1
2
3
4
E → T
E → T + E
T → int
T → (E)

E → T + E
   → int + E
   → int + T 
   → int + (E)
   → int + ( T + E )
   → int + ( int + E )
   → int + ( int + T )
   → int + ( int + int )

Definition of Top-Down Parsing / 自顶向下解析的定义

Parsing begins with the start symbol of the grammar, and by applying the grammar's production rules step by step, it tries to find the leftmost derivation of the input string. 解析从文法的起始符号开始，通过逐步应用文法的产生规则，尝试找到输入字符串的最左推导。
Construction of Parse Tree / 解析树的构造: The start symbol of the grammar is the root of the parse tree. The parse tree is constructed from the root to the leaves in preorder. The leaves of the parse tree correspond to the input string (tokens). 解析树的构造: 文法的起始符号是解析树的根。解析树从根到叶子的构造是先序遍历的。解析树的叶子对应于输入字符串（词法单元）。

Key Points / 关键要点

Top-Down Parsing starts with the start symbol and tries to guess the correct production rules to apply in order to derive the string. 自顶向下解析从起始符号开始，尝试猜测应该应用哪些产生式来推导出字符串。
The parse tree is built in preorder traversal. 解析树是通过先序遍历构建的。
Parse trees are essential for representing the structure of the input string according to the grammar. 解析树对于表示根据文法构造的输入字符串的结构至关重要。
Top-Down Parsing is often used in predictive parsers, where we look ahead at the tokens to decide which rule to apply next. 自顶向下解析通常用于预测分析器，我们通过预览接下来的词法单元来决定应用哪个规则。

✅ Top-Down Parsing 示例详解 / Top-Down Parsing Example Explanation

🔸给定文法 / Given Grammar G：

1
2
3

S → cAd  
A → ab  
A → a

🔸输入字符串 / Input String:

cabd

🔸自顶向下解析过程 / Top-Down Derivation of “cabd”:

S → cAd 初始从 S 开始推导，使用产生式 S → cAd ⇒ cAd
A → ab 对非终结符 A 应用规则 A → ab ⇒ cabd

此时得到的字符串与输入字符串“cabd”完全匹配。

✅ Derivation Summary / 推导总结

推导过程： S ⇒ cAd ⇒ cabd 这是一个合法的解析过程。

🔍 Parsing as a Graph Search / 将解析视为图搜索问题

📌核心思想 / Core Idea:

我们可以将语法解析（parsing）看作图搜索（graph search）问题来处理。

📌定义 / Definitions:

节点（Node）：一个由起始符号开始，通过一系列推导得到的句型（sentential form），也就是包含终结符和非终结符的字符串。
边（Edge）：如果某个句型 α 可以通过一个产生式一步推导成另一个句型 β（即 α ⇒ β），那么就在图中从 α 到 β 连一条边。

🌐图搜索视角解析流程 / Parsing as Traversing the Graph

初始节点 / Initial Node：S
第一步 / First Step：S ⇒ cAd 在图中从 S 到 cAd 有一条边。
第二步 / Second Step：cAd ⇒ cabd 选择 A → ab，继续前进。图中从 cAd 到 cabd 有一条边。
终止节点 / Terminal Node：cabd 一个全由终结符构成的句子，完成解析。

🧠图搜索策略 / Graph Search Strategies

深度优先（DFS）：优先深入某条路径，适用于回溯分析。
广度优先（BFS）：同时探索多个路径，有助于找到最短推导。
受限搜索（带预测集的搜索）：配合 First/Follow 集，排除不可能的路径，提高效率。

✅ 总结 / Summary（中英文对照）

内容	英文	中文
解析方法	Top-Down Parsing	自顶向下解析
示例字符串	`cabd`	示例输入
推导路径	`S ⇒ cAd ⇒ cabd`	合法推导过程
图搜索视角	Sentential forms as nodes; derivation steps as edges	句型是图的节点，推导步骤是边
搜索策略	DFS / BFS / Predictive Search	深度优先 / 广度优先 / 预测搜索

✅ Top-down Parsing 的关键问题

🔑 The Key of Top-down Parsing（自顶向下解析的核心问题）

英文： The key problem of top-down parsing is how to choose the correct production in each derivation step. If the leftmost nonterminal is B, and there are n productions for B:

B → A₁ | A₂ | … | Aₙ How do we determine which production to use based on the current input?

中文： 自顶向下解析的关键在于：如何在每一步推导中选择正确的产生式（production）。如果当前最左边的非终结符是 B，而 B 有多个产生式：

B → A₁ | A₂ | … | Aₙ 我们如何根据当前的输入符号判断使用哪一个产生式？

📚 Top-down Parsing 的分类 / Categories of Top-down Parsing

① 回溯解析（Backtracking Parsing）

英文解释：

Backtracking is a depth-first parsing approach.
If a nonterminal has more than one production and the parser cannot determine which one to apply, it tries them one by one.
If one branch fails, it backtracks and tries another.
This can be very slow and inefficient in complex grammars.

中文解释：

回溯解析是一种深度优先的语法解析方式。
当某个非终结符有多个产生式，且无法根据当前输入判断使用哪个产生式时，就依次尝试所有可能。
一条路径失败后，退回并尝试另一条路径。
对于复杂语法来说，效率很低，解析速度慢。

② 预测解析（Predictive Parsing）

英文解释：

Predictive parsing uses look-ahead tokens to decide which production to use.
It avoids backtracking by predicting the next steps.
Requires grammar to be non-ambiguous and ideally in LL(1) form.
Two types:
- Recursive-descent Parsing
- LL(1) Parsing

中文解释：

预测解析通过向前看一个或多个符号（look-ahead tokens）来选择正确的产生式。
它不需要回溯，更高效。
要求语法是无二义性（unambiguous）的，且最好是 LL(1) 形式。
有两种类型：
- 递归下降解析（Recursive-descent Parsing）
- LL(1) 解析器

✅ 总结 / Summary（中英文对照）

内容	英文	中文
解析问题	Choose the correct production for a nonterminal	选择正确的产生式
回溯解析	Try all options, backtrack if needed	尝试所有选项，失败回溯
预测解析	Use look-ahead to decide	使用向前看符号进行预测
效率	Backtracking is slow, Predictive is fast	回溯慢，预测快
预测类型	Recursive-descent, LL(1)	递归下降，LL(1)

📘 4.1 The Condition of Predictive Parsing

🔍 什么是预测解析的条件？

✅ Predictive Parsing 的基本条件 / Basic Idea

英文：

Parsing begins with the start symbol.
If at each step, the parser can uniquely choose a production based on the next k tokens (lookahead), then it is predictive parsing.
Predictive parsers work with LL(k) grammars.

中文：

解析从文法的开始符号（start symbol）开始。
如果在每一步推导中，可以通过查看输入中的前 k 个符号（lookahead）唯一确定使用哪条产生式，那么这种解析称为 预测解析（predictive parsing）。
预测解析器适用于 LL(k) 文法。

📌 什么是 LL(k)？

符号	含义（英文）	含义（中文）
L	Left-to-right scan	从左到右读取输入
L	Leftmost derivation	执行最左推导
k	k tokens lookahead	向前看 k 个符号

➡️ 实际中我们大多数使用的是 LL(1) 文法，也就是 只需要向前看一个符号 的预测解析。

✅ Predictive Parsing 的条件总结 / Summary

英文： To allow predictive parsing, the grammar must satisfy:

The grammar must be an LL(1) grammar.
For a nonterminal A, at most one production can be chosen for any lookahead token.
This depends on the definitions of First and Follow sets.

中文： 为了实现预测解析，文法必须满足以下条件：

文法必须是 LL(1) 的。
对于某个非终结符 A，在任意的 lookahead 符号下，最多只能有一个产生式可以被选择。
这个选择依赖于两个集合的定义：First 集 和 Follow 集（将在后续讲解中介绍）。

🔑 预测解析的核心问题 / The Key Problem

✅ 给定一个非终结符 A 和多个产生式 A → α1 | α2 | … | αn，如何判断应该使用哪一个产生式？

答案：必须使用 lookahead token（向前看的输入符号） 来判断。这就引出了我们接下来要讲的两个重要集合：

First(α)：判断某个串 α 能够以什么符号开始
Follow(A)：判断 A 之后可能出现哪些符号

📝 总结 / Summary（中英文对照）

项目	英文解释	中文解释
Predictive Parsing	Choose production based on lookahead	基于向前看符号选择产生式
LL(k) Grammar	Left-to-right scan, Leftmost derivation, k-token lookahead	从左到右扫描，最左推导，向前看 k 个符号
LL(1) Grammar	Needs only 1 lookahead symbol	只需向前看一个符号
条件	Must use First and Follow sets	必须使用 First 和 Follow 集

LL(1) Grammar Notes

一、预测分析的条件（The Condition of Predictive Parsing）

目标（Goal）：预测分析从文法的开始符号开始解析输入串，如果在每一步都能仅靠输入的前瞻符号（lookahead token）确定使用哪个产生式，则该文法是可以预测分析的（predictive）。
LL(k) 文法定义：
- L：表示从左到右扫描输入串（Left-to-right）。
- L：表示构建最左导出（Leftmost derivation）。
- k：表示最多需要前瞻 k 个符号。
实际中我们通常使用的是 LL(1) 文法（只需要一个前瞻符号）。

二、前瞻符号集的定义（Definition of Lookahead Sets）

1. FIRST 集（First Sets）

定义：对任意符号串 β（可以是终结符或非终结符的组合）：

FIRST(β) = { a ∈ VT | β ⇒∗ a... }
- 如果 β 可以推导出空串 ε，则 ε ∈ FIRST(β)
- 简单来说：FIRST(β) 是从 β 推导出的句型中，第一个出现的终结符的集合（包含 ε）
例子（Example G[S]）：

S → Ap
S → Bq
A → a
A → cA
B → b
B → dB

FIRST(Ap) = { a, c }
FIRST(Bq) = { b, d }
FIRST(a) = { a }
FIRST(cA) = { c }
FIRST(b) = { b }
FIRST(dB) = { d }
预测分析条件：若非终结符 A 有多个产生式：A → α | β | …，只要满足：

FIRST(α) ∩ FIRST(β) = ∅

则对于任意输入符号，都可以唯一决定选择哪个产生式。

2. FOLLOW 集（Follow Sets）

定义： FOLLOW(A) 是所有能出现在某个句型中 A 之后的终结符的集合。

FOLLOW(A) = { a ∈ VT | S ⇒* ...Aa... } 如果 A 出现在句子的末尾，则加入 $（表示输入结束）。
例子（Example G3[S]）：

1 2	S → aA \| d A → bAS \| ε

A 有两个产生式：A → bAS 和 A → ε
推导分析：
- S ⇒ aA ，所以 $ ∈ FOLLOW(A)
- S ⇒ abAS ⇒ abAaA，说明 a ∈ FOLLOW(A)
- S ⇒ abAd ⇒ ...，说明 d ∈ FOLLOW(A)
所以 FOLLOW(A) = { $, a, d }
如何使用 FOLLOW：
- 当前输入符号为 x
  - 如果 x ∈ FIRST(bAS) = { b }，则选择产生式 A → bAS
  - 如果 x ∈ FOLLOW(A) = { $, a, d }，则选择 A → ε
只要满足：

FIRST(bAS) ∩ FOLLOW(A) = ∅

就能唯一决定该选择哪个产生式。

三、LL(1) 文法的定义（Definition of LL(1) Grammar）

文法 G 是 LL(1) 的，当且仅当对所有非终结符 A 的产生式 A → α1 | α2 | … | αn，满足以下两个条件：
1. 对任意 i ≠ j，有：
  
  FIRST(αi) ∩ FIRST(αj) = ∅
2. 如果 FIRST(αi) 包含 ε，那么：
  
  FIRST(αi) ∩ FOLLOW(A) = ∅

例子（Example G[S]）：

S → aAS
S → b
A → bA
A → ε

FIRST(A) = { b, ε }
FOLLOW(A) = { a, b }
FIRST(A) ∩ FOLLOW(A) = { b } ≠ ∅

因此该文法不是 LL(1)，因为当遇到终结符 b 时，无法判断应选择 A → bA 还是 A → ε。

四、总结（Summary）

预测分析的核心是提前决定使用哪个产生式。
需要使用 FIRST 和 FOLLOW 集来帮助选择。
一个文法是 LL(1) 的，当它的每个选择都不会造成冲突。
预测分析不需要回溯，效率高，但需要文法满足 LL(1) 条件。

理解帮助

🌱 一、什么是 FIRST 集？

🧠 直觉理解（中文）：

FIRST(α) 表示：一个符号串 α 开头可能出现的终结符号（token）有哪些。

也可以理解为：如果我们从 α 推导（展开），第一个出现的终结符可能是哪些？

这个集合是为“预测”而生的。

✅ FIRST(终结符号) 很简单：

例子说明

FIRST(a) = { a } 因为 a 本身就是终结符

FIRST(+) = { + } + 是终结符

✅ FIRST(非终结符) 的规则（稍复杂，但我们分步骤）：

假设有文法：
1
2
A → aB | c
B → b
我们想求 FIRST(A)

第一步：看 A 的产生式（也就是 A → ... 的右边）

A → aB：右边第一个符号是 a（终结符），所以 a ∈ FIRST(A)

A → c：右边第一个符号是 c，所以 c ∈ FIRST(A)

所以：
1
FIRST(A) = { a, c }
🧩 复杂情况：右边第一个是非终结符怎么办？

看这个例子：
1
2
A → B
B → b
想求 FIRST(A)

A → B，得看 B 的 FIRST 集，所以：
1
FIRST(B) = { b } ⇒ 所以 FIRST(A) = FIRST(B) = { b }
⭐ 特殊情况：如果某条产生式能推导出 ε（空串），那么也要把 ε 加进去！

比如：
1
C → ε | d
那么：
1
FIRST(C) = { ε, d }
🌱 二、什么是 FOLLOW 集？

🧠 直觉理解（中文）：

FOLLOW(A) 表示：在整个推导过程中，可能跟在 A 后面出现的终结符有哪些？

如果我们已经处理完 A，下一步可能看到的符号是什么？

✅ FOLLOW 集的规则（用简单话来说）：

先看这两个产生式：
1
2
S → A b
A → a
我们来求 FOLLOW(A)：

在 S → A b 中，A 的右边是 b，所以 b ∈ FOLLOW(A)

✅ FOLLOW 集一定包含 $（结束符号）？

是的！如果 A 能推导到文法的最末尾位置，那么 $ ∈ FOLLOW(A)

比如：
1
S → A
那么 FOLLOW(S) = { $ }，而因为 A 在最后，所以：
1
FOLLOW(A) = FOLLOW(S) = { $ }
🧩 复杂点：FOLLOW 中也可能来自 FIRST 集！

看例子：
1
2
3
S → A B
A → a | ε
B → b
我们要找 FOLLOW(A)

因为 S → A B，而 A 可能推 ε，所以 B 紧跟在 A 后面

那么 B 的 FIRST 集 就是 FOLLOW(A) 的候选

所以：
1
2
FIRST(B) = { b }
⇒ FOLLOW(A) ⊇ { b }
✅ 一个完整示例（FIRST 和 FOLLOW 都有）

文法：
1
2
S → a A c
A → b | ε
我们求：

1️⃣ FIRST(A)

A → b ⇒ b ∈ FIRST(A)

A → ε ⇒ ε ∈ FIRST(A)

所以：
1
FIRST(A) = { b, ε }
2️⃣ FOLLOW(A)

在 S → a A c 中，A 的后面是 c，所以：
1
c ∈ FOLLOW(A)
1
FOLLOW(A) = { c }
🧠 总结记忆口诀（中文）：

集合意义小口诀

FIRST(X) 推导 X 开头可能出现的终结符 “展开看看能出啥”

FOLLOW(X) X 后面可能跟着什么终结符 “X 后会遇到谁”

例子	说明
FIRST(a) = { a }	因为 a 本身就是终结符
FIRST(+) = { + }	+ 是终结符

集合	意义	小口诀
FIRST(X)	推导 X 开头可能出现的终结符	“展开看看能出啥”
FOLLOW(X)	X 后面可能跟着什么终结符	“X 后会遇到谁”

编译技术4-1

Review from Last Time / 上一讲回顾

Different Types of Parsing / 解析的不同类型

Top-Down Parsing / 自顶向下解析

Definition of Top-Down Parsing / 自顶向下解析的定义

Key Points / 关键要点

✅ Top-Down Parsing 示例详解 / Top-Down Parsing Example Explanation

🔸给定文法 / Given Grammar G：

🔸输入字符串 / Input String:

🔸自顶向下解析过程 / Top-Down Derivation of “cabd”:

✅ Derivation Summary / 推导总结

🔍 Parsing as a Graph Search / 将解析视为图搜索问题

📌核心思想 / Core Idea:

📌定义 / Definitions:

🌐图搜索视角解析流程 / Parsing as Traversing the Graph

🧠图搜索策略 / Graph Search Strategies

✅ 总结 / Summary（中英文对照）

✅ Top-down Parsing 的关键问题

🔑 The Key of Top-down Parsing（自顶向下解析的核心问题）

📚 Top-down Parsing 的分类 / Categories of Top-down Parsing

① 回溯解析（Backtracking Parsing）

② 预测解析（Predictive Parsing）

✅ 总结 / Summary（中英文对照）

📘 4.1 The Condition of Predictive Parsing

🔍 什么是预测解析的条件？

✅ Predictive Parsing 的基本条件 / Basic Idea

📌 什么是 LL(k)？

✅ Predictive Parsing 的条件总结 / Summary

🔑 预测解析的核心问题 / The Key Problem

📝 总结 / Summary（中英文对照）

LL(1) Grammar Notes

一、预测分析的条件（The Condition of Predictive Parsing）

二、前瞻符号集的定义（Definition of Lookahead Sets）

1. FIRST 集（First Sets）

2. FOLLOW 集（Follow Sets）

三、LL(1) 文法的定义（Definition of LL(1) Grammar）

例子（Example G[S]）：

四、总结（Summary）

理解帮助

🌱 一、什么是 FIRST 集？

🧠 直觉理解（中文）：

✅ FIRST(终结符号) 很简单：

✅ FIRST(非终结符) 的规则（稍复杂，但我们分步骤）：

第一步：看 A 的产生式（也就是 A → ... 的右边）

🧩 复杂情况：右边第一个是非终结符怎么办？

⭐ 特殊情况：如果某条产生式能推导出 ε（空串），那么也要把 ε 加进去！

🌱 二、什么是 FOLLOW 集？

🧠 直觉理解（中文）：

✅ FOLLOW 集的规则（用简单话来说）：

✅ FOLLOW 集一定包含 $（结束符号）？

🧩 复杂点：FOLLOW 中也可能来自 FIRST 集！

✅ 一个完整示例（FIRST 和 FOLLOW 都有）

1️⃣ FIRST(A)

2️⃣ FOLLOW(A)

🧠 总结记忆口诀（中文）：