$\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \emptyset$
若 $\epsilon \in \text{FIRST}(\alpha)$ ，则 $\text{FIRST}(\beta) \cap \text{FOLLOW}(A) = \emptyset$

FIRST 集计算：

$\text{FIRST}(A) = \{a \mid A \xRightarrow{*} a\alpha\} \cup \{\epsilon \mid A \xRightarrow{*} \epsilon\}$

FOLLOW 集计算：

$\text{FOLLOW}(A) = \{a \mid S \xRightarrow{*} \alpha Aa\beta\}$

LL(1) 分析表构造：

对每个产生式 $A \to \alpha$ ：

对每个 $a \in \text{FIRST}(\alpha)$ ： $M[A, a] = A \to \alpha$
若 $\epsilon \in \text{FIRST}(\alpha)$ ：对每个 $b \in \text{FOLLOW}(A)$ ： $M[A, b] = A \to \alpha$

2.2 LR 分析（自底向上）

LR 分析器结构：

输入 ──→ ┌──────────┐ ──→ 动作
          │  栈      │
          │ 状态+符号 │
          └──────────┘

动作类型：

Shift $s$ ：移进，压入状态 $s$
Reduce $A \to \alpha$ ：归约，弹出 $|\alpha|$ 个状态，压入 $\text{GOTO}[t, A]$
Accept：接受
Error：报错

2.3 SLR 分析

使用 FOLLOW 集确定归约动作：

对项目 $A \to \alpha \cdot$ ，仅在 $a \in \text{FOLLOW}(A)$ 时添加 $M[s, a] = \text{Reduce}$

SLR 的不足：FOLLOW 集可能过大，导致归约-归约冲突。

2.4 LALR 分析

合并同心项目集（核心相同的项目集）。

LALR 表大小与 SLR 相同，但分析能力更强。

大多数实用解析器生成器（Yacc、Bison）使用 LALR(1)。

2.5 LR 分析器对比

类型	状态数	分析能力	冲突
SLR	最少	最弱	最多
LALR	少	中等	较少
LR(1)	最多	最强	最少

3. 语法制导翻译

3.1 语法制导定义（SDD）

为文法的每个产生式关联语义规则：

$A \to X_1 X_2 ... X_n \quad \{语义规则\}$

3.2 综合属性与继承属性

综合属性：在分析树中，由子节点属性计算父节点属性（自底向上）。

$A.syn = f(X_1.syn, X_2.syn, ...)$

继承属性：由父节点或兄弟节点属性计算（自顶向下）。

$X_i.inh = f(A.inh, X_1.syn, ...)$

3.3 S 属性文法

仅使用综合属性的 SDD，可在 LR 分析中自底向上计算。

3.4 L 属性文法

每个继承属性 $X_i.inh$ 仅依赖于：

$A$ 的继承属性
$X_i$ 左侧兄弟的属性

L 属性文法可在 LL 或 LR 分析中单遍计算。

4. 中间代码生成

4.1 中间表示形式

三地址码：

t1 = a + b
t2 = t1 * c
x = t2

静态单赋值（SSA）：

每个变量只被赋值一次，使用 $\phi$ 函数合并控制流：

if condition:
    x1 = a + b
else:
    x2 = a - b
x3 = φ(x1, x2)

四元式：(op, arg1, arg2, result)

三元式：(op, arg1, arg2)，通过位置引用结果

4.2 类型检查

类型表达式：

基本类型：integer, real, boolean
构造类型：array(n, T), pointer(T), record(fields)
函数类型： $T_1 \times T_2 \to T_3$

类型等价：

名字等价：类型名相同
结构等价：类型结构相同

5. 代码优化

5.1 基本块优化

常量折叠：

x = 3 + 5  →  x = 8

常量传播：

x = 5
y = x + 1  →  y = 6

死代码消除：

x = 5
x = 10     →  删除 x = 5

代数化简：

x = y + 0  →  x = y
x = y * 1  →  x = y

5.2 循环优化

循环不变代码外提：

// 优化前
for (i = 0; i < n; i++) {
    t = a * b;  // 循环不变
    c[i] = t + d[i];
}

// 优化后
t = a * b;
for (i = 0; i < n; i++) {
    c[i] = t + d[i];
}

强度削弱：

// 优化前
for (i = 0; i < n; i++) {
    a[i*4] = 0;
}

// 优化后
t = 0;
for (i = 0; i < n; i++) {
    a[t] = 0;
    t = t + 4;  // 乘法 → 加法
}

归纳变量删除：

当存在基本归纳变量和派生归纳变量时，可删除其中一个。

5.3 全局优化

数据流分析：

分析	方向	信息
到达定义	前向	变量在哪里被定义
活跃变量	后向	变量未来是否使用
可用表达式	前向	表达式是否已计算
常量传播	前向	变量是否为常量