L10 算符优先分析 · 编译原理冲刺

二、FIRSTVT 与 LASTVT

FIRSTVT(P) = { a | P ⇒⁺ a… 或 P ⇒⁺ Qa… } —— P 推出的串里"第一个终结符"（可越过开头一个非终结符）规则：① P→a… 或 P→Qa… ⟹ a∈FIRSTVT(P) ② P→Q… ⟹ FIRSTVT(Q) ⊆ FIRSTVT(P) LASTVT(P) = { a | P ⇒⁺ …a 或 P ⇒⁺ …aQ } —— 对称地取"最后一个终结符" 规则：① P→…a 或 P→…aQ ⟹ a∈LASTVT(P) ② P→…Q ⟹ LASTVT(Q) ⊆ LASTVT(P)

⚑ 三条规则（a、b 是终结符，Q 是非终结符）

① 右部出现 …ab… 或 …aQb… ⟹ a ≐ b。

② 右部出现 …aQ… ⟹ 对每个 b∈FIRSTVT(Q)：a ⋖ b。

③ 右部出现 …Qb… ⟹ 对每个 a∈LASTVT(Q)：a ⋗ b。

四、老师示范一题

例题　文法 E→E+T|T, T→T*F|F, F→(E)|i。求 FIRSTVT/LASTVT 并构造优先关系表。

FIRSTVT：

FIRSTVT(F) = { ( , i }
FIRSTVT(T) = { * , ( , i }
FIRSTVT(E) = { + , * , ( , i }

LASTVT：

LASTVT(F) = { ) , i }
LASTVT(T) = { * , ) , i }
LASTVT(E) = { + , * , ) , i }

由三条规则推关系（举几条）：

E→E+T：+ 后是 T ⟹ + ⋖ FIRSTVT(T)={*,(,i}  ；T 前… E 后是 + ⟹ LASTVT(E) ⋗ +
T→T*F：* 后是 F ⟹ * ⋖ FIRSTVT(F)={(,i}    ；F 前… T 后是 * ⟹ LASTVT(T) ⋗ *
F→(E)：( 与 ) 夹 E ⟹ ( ≐ ) ；( ⋖ FIRSTVT(E) ；LASTVT(E) ⋗ )
句子括号 #：# ⋖ FIRSTVT(E) ；LASTVT(E) ⋗ #

优先关系表（行=栈顶终结符，列=当前输入终结符）：

	+	*	(	)	i	#
+	⋗	⋖	⋖	⋗	⋖	⋗
*	⋗	⋗	⋖	⋗	⋖	⋗
(	⋖	⋖	⋖	≐	⋖
)	⋗	⋗		⋗		⋗
i	⋗	⋗		⋗		⋗
#	⋖	⋖	⋖		⋖	≐

(

)

⋗

⋖

⋗

⋖

⋗

⋖

⋗

⋖

⋗

(

⋖

≐

⋖

)

⋗

⋖

≐

💡 记忆抓手：i（操作数）对一切运算符都 ⋗（它最该先归约）；( 对里面一切都 ⋖、# 对里面一切都 ⋖；* ⋗ + 体现"乘优先于加"。

五、用关系表分析 + 优先函数

分析规则：比较"栈顶终结符"与"当前输入终结符"——遇 ⋖ 或 ≐ 就移进，遇 ⋗ 就归约（归约被 ⋖…⋗ 夹住的最左素短语）。简析 i+i#（N 代表归约出的非终结符）：

# ⋖ i 移进 → #i ; i ⋗ + 归约 i → #N #(N) ⋖ + 移进 → #N+ ; + ⋖ i 移进 → #N+i i ⋗ # 归约 i → #N+N ; + ⋗ # 归约 N+N → #N # ≐ # 接受 ✔

优先函数 f、g：用两个数值函数代替整张关系表（省空间）。对应关系：

构造法（图法）：为每个终结符设 f_a、g_a 两个结点；按关系连边后取最长路径长度作函数值。缺点：本来"无关系（空格）"的两个终结符，被函数强行比出了大小，损失了查错能力。

六、你来做

1. 算符文法 (OG) 的特征是？

2. 算符优先的三种优先关系？

3. 求 FIRSTVT 时，若 P→Q…（Q 为非终结符），则？

4. 算符优先分析中，"移进还是归约"由什么决定？

5. 引入优先函数 f、g 的主要作用是？

得分：0 / 5

FIRSTVT 看"前头终结符"，LASTVT 看"末尾终结符"
aQ→a⋖FIRSTVT(Q)；Qb→LASTVT(Q)⋗b；aQb→a≐b ｜ ⋖≐移进、⋗归约

📺 主源推荐　哈工大《编译原理》自底向上（算符优先）讲 — 中国大学MOOC^[1]。

🙋 优先关系表逐格容易抄错。想要这套文法的完整优先函数 f/g 数值表，或 i+i*i# 的完整分析过程，跟我说，我马上给你逐步推。

[1] 算符文法、FIRSTVT/LASTVT、优先关系表、优先函数：陈火旺《程序设计语言编译原理》5.2。本课 FIRSTVT/LASTVT 与优先关系表为该文法的标准结果。

算符优先分析

一、几个前提概念

二、FIRSTVT 与 LASTVT

三、构造优先关系表

四、老师示范一题

五、用关系表分析 + 优先函数

六、你来做