编译原理 · 核心算法与公式速查

各章关键算法、公式和判定条件的集中整理，便于考前快速回顾。

第2章 词法分析

ε-闭包计算

ε-闭包(T):
   将 T 中所有状态入栈
   栈非空时:
      出栈 → t
      对 t 的每条 ε 转移到达 u:
          若 u 不在闭包中:
              添加 u, u 入栈
   返回闭包集合

NFA → DFA 子集构造法

DFA_state = ε-闭包(NFA 初始状态)
对每个未处理的 DFA 状态 T:
    对每个输入字符 a:
        U = ε-闭包(所有从 T 中状态经 a 到达的状态)
        若 U 不在 DFA 状态集中 → 添加
        设置 δ(T, a) = U

DFA 最小化（划分法）

1. 初始分两组: 接受状态组 F, 非接受状态组 S-F
2. 重复:
      对每组 G, 若存在字符 a 使组内状态经 a 转移
      到不同的组 → 拆分 G
3. 直到无法继续拆分

正则 → NFA（Thompson 构造）

正则表达式代数定律

Lex 输入文件结构

定义部分
%%
规则部分（模式 { 动作 }）
%%
用户子程序

第4章 自顶向下分析

First 集合

1. X ∈ T → First(X) = {X}
2. X → ε ∈ P → ε ∈ First(X)
3. X → Y1Y2...Yk ∈ P:
   for Yi in Y1..Yk:
       First(Yi)-{ε} ⊆ First(X)
       若 ε ∉ First(Yi) → break
   若所有 Yi 都有 ε → ε ∈ First(X)

Follow 集合

1. $ ∈ Follow(S)
2. A → αBβ → First(β)-{ε} ⊆ Follow(B)
3. A → αB 或 A → αBβ 且 ε∈First(β)
   → Follow(A) ⊆ Follow(B)

SELECT 集合

SELECT(A → α) =
  - 若 α 不能推导出 ε: SELECT = First(α)
  - 若 α ⇒* ε: SELECT = (First(α) - {ε}) ∪ Follow(A)

LL(1) 判定条件

对任意 A → α | β:
1. First(α) ∩ First(β) = ∅
2. 若 β ⇒* ε, 则 First(α) ∩ Follow(A) = ∅

等价形式（SELECT 集）:
   SELECT(A → α) ∩ SELECT(A → β) = ∅

消除左递归

原始: A → Aα | β
改写: A → βA'
      A' → αA' | ε

提取左因子

原始: A → αβ | αγ
改写: A → αA'
      A' → β | γ

第5章 自底向上分析

LR(0) 项目集闭包

Closure(I):
    重复:
        若 [A → α·Bβ] ∈ I 且 B → γ ∈ P
        → 添加 [B → ·γ] 到 I
    直到 I 不再变大

LR(0) GOTO

goto(I, X) = Closure({[A → αX·β] | [A → α·Xβ] ∈ I})

SLR(1) 归约条件

状态 s 含项目 A → α·:
    仅当 lookahead ∈ Follow(A) 时才归约

LR(1) 项目

格式: [A → α·β, a]
闭包: 若 [A → α·Bβ, a] ∈ I, B → γ ∈ P
      则 ∀b ∈ First(βa): [B → ·γ, b] ∈ I

文法包含关系

LR(1) ⊇ LALR(1) ⊇ SLR(1) ⊇ LR(0)
LL(1) ⊂ LR(1)

第6章 语义分析

属性分类

属性计算顺序

1. S-属性文法: 后序遍历（子 → 父）
2. L-属性文法: 深度优先（左 → 右）
3. 通用: 依赖图拓扑排序

第7章 运行时环境

活动记录布局

高地址
  ┌──────────────┐
  │    参数       │
  ├──────────────┤
  │  返回地址     │
  ├──────────────┤
  │  控制链 (FP)  │← FP
  ├──────────────┤
  │  访问链       │
  ├──────────────┤
  │  局部变量     │
  ├──────────────┤
  │  临时变量     │
  └──────────────┘← SP
低地址

第8章 代码生成

数组地址计算

行主序（C）:
  A[i][j] = base + (i × cols + j) × elem_size

列主序（FORTRAN）:
  A[i][j] = base + (j × rows + i) × elem_size

TM 机关键指令速记

LDC r, c    →  r = c
LD  r, c(r1) →  r = mem[r1 + c]
LDA r, c(r1) →  r = r1 + c
ST  r, c(r1) →  mem[r1 + c] = r
ADD r1, r2, r3 → r1 = r2 + r3
SUB r1, r2, r3 → r1 = r2 - r3
MUL r1, r2, r3 → r1 = r2 * r3
JEQ r1, c(r2) →  if r1 == 0 goto c+r2
JLT r1, c(r2) →  if r1 < 0  goto c+r2

控制语句代码模式

if (cond) then_part else else_part:

    cond 求值代码
    JEQ result, else_label
    then_part 代码
    JMP end_label
else_label:
    else_part 代码
end_label: