① 编译概念〔L01〕
- 编译程序 compiler
- 把高级语言源程序翻译成等价目标程序的程序。
- 解释程序 interpreter
- 边翻译边执行、不产生目标程序。
- 编译的 5 个阶段
- 词法分析 → 语法分析 → 语义分析与中间代码产生 → 代码优化 → 目标代码生成。
- 表格管理 / 出错处理
- 登记名字属性 / 报错恢复；两者贯穿编译全过程，非单独阶段。
- 前端 / 后端 front / back end
- 前端与源语言相关、与机器无关（词法~中间代码）；后端与目标机相关（目标代码生成）。
- 遍（趟） pass
- 对源程序或中间结果从头到尾扫描一次。阶段是逻辑划分，遍是物理扫描次数。
② 文法〔L02〕
- 文法 grammar
- 四元组
G=(VN, VT, P, S)：非终结符集、终结符集、产生式集、开始符号。
- 推导 / 归约 derivation
- 用右部替换非终结符叫推导（⇒）；反向叫归约。最左推导每次替换最左非终结符；最右推导＝规范推导。
- 句型 / 句子 / 语言
- 句型：S 推出的串（可含非终结符）；句子：只含终结符的句型；语言 L(G)＝全部句子。
- 语法树（推导树）
- 根为 S、叶子拼成句型的树，表示推导结构。
- 二义性 ambiguity
- 存在某句子有两棵不同语法树（或两个不同最左/最右推导）。
- Chomsky 分类
- 0型短语 / 1型上下文有关(|α|≤|β|) / 2型上下文无关(A→β，描述语法) / 3型正规(A→aB|a，描述单词)。3⊂2⊂1⊂0。
③ 词法分析与有限自动机〔L03 / L04〕
- 正规式 / 正规集 regular expression
- 由 ε、单字符、
|、连接、* 构成；优先级 * > 连接 > |。它表示的串集合叫正规集。
- DFA / NFA
- 有限自动机
(S,Σ,δ,s₀,F)。DFA 无 ε、每输入唯一转移；NFA 可有 ε 边、一输入达多状态。二者及正规式三者等价。
- ε-closure(I)
- 从 I 出发只沿 ε 边可达的状态集（含 I）。
- move(I, a)
- I 中状态沿一条 a 边到达的状态集。
- 子集构造法 subset construction
- NFA→DFA：DFA 一状态＝NFA 一子集；初态＝ε-closure(s₀)，转移＝ε-closure(move(·,a))，含原终态的子集为终态。
- DFA 最小化（分割法）
- 先分终态/非终态两组，再按"同输入是否转入同组"反复细化，每组并为一状态。
- 状态转换图 / 超前搜索
- 词法分析器用状态图识别单词；多读一字符定边界、再退回叫超前搜索。
- 单词 token
- 常表示为二元组
(种别码, 属性值)；五类：关键字、标识符、常数、运算符、界符。
④ 自顶向下分析〔L05–L08〕
- 左递归 left recursion
P→Pα。消除：P→Pα|β ⟹ P→βP′, P′→αP′|ε。间接左递归先代入再消。- 回溯 / 左公因子
- 候选有公共开头 α 导致试错；提取左公因子
A→αβ₁|αβ₂ ⟹ A→αA′, A′→β₁|β₂ 消除回溯。
- FIRST(α)
- α 能推出的串的首终结符集；若 α⇒*ε 则含 ε。
- FOLLOW(A)
- 句型中紧跟 A 之后的终结符集；A 可在末尾则含 #。不含 ε。
- SELECT(A→α)
- ε∉FIRST(α) 时＝FIRST(α)；否则＝(FIRST(α)\{ε})∪FOLLOW(A)。
- LL(1) 文法
- 各候选 SELECT 两两不相交（左扫描·最左推导·看1符号）。
- 预测分析表 M[A,a]
- FIRST 进对应列、含 ε 再按 FOLLOW 进列；空白＝出错，冲突＝非 LL(1)。
- 递归下降 / 分析栈
- 每个非终结符写一子程序（需无左递归无回溯）；表驱动预测分析用栈，栈底 #、栈顶非终结符查表逆序压栈，双 # 接受。
⑤ 自底向上 与 算符优先〔L09 / L10〕
- 移进-归约
- 用栈，从输入串反复归约到 S。四动作：移进、归约、接受、报错。
- 短语 / 直接短语 / 句柄
- 子树叶子＝短语；只有两代的子树叶子＝直接短语；最左直接短语＝句柄。
- 规范归约 / 规范句型
- 每步归约句柄，是最右推导（规范推导）的逆；规范推导得到的句型为规范句型。
- 算符文法 OG
- 产生式右部无两个相继非终结符。
- 优先关系 ⋖ ≐ ⋗
- a⋖b（低于）、a≐b（相等）、a⋗b（高于）；不对称。⋖/≐ 移进，⋗ 归约（最左素短语）。
- FIRSTVT(P) / LASTVT(P)
- P 推出串的首/末终结符（可越过开头/结尾一个非终结符）。
- 优先关系表 / 优先函数
- 由 FIRSTVT/LASTVT 与三规则构造表；优先函数 f、g 用数值代替表(
a⋖b⟺f(a)<g(b))省空间，但损失查错能力。
⑦ 中间代码〔L11〕
- 逆波兰式（后缀式）
- 运算符在操作数之后，无括号。如
a+b*c → abc*+。
- 三元式 / 间接三元式
(op,arg1,arg2) 用序号引用；间接三元式另设间接码表存执行顺序，便于优化调整。- 四元式 quadruple
(op, arg1, arg2, result)，最常用。赋值 (:=, b, _, a)，跳转 (j, _, _, L)。- 临时变量 T
- 翻译时存放中间结果的新变量 T1、T2…。
⑩ 代码优化〔L12〕
- 基本块 basic block
- 单入口、单出口、中间无跳转进出的语句序列。
- 入口语句
- 程序首条 / 转移语句的目标 / 紧跟转移语句之后的语句。
- DAG（无环有向图）
- 表示基本块计算，相同子表达式共享结点 → 发现公共子表达式与无用赋值。
- 循环不变式外提（代码外提）
- 循环内每次结果不变的运算，提到循环外只算一次。
- 强度削弱
- 把强运算换弱运算，常把循环内乘法换成加法（如 4*i 改 +4）。
- 归纳变量
- 随循环规律变化的变量；只用于控制循环时可删除/替换。