EagleBear2002 的博客

这里必须根绝一切犹豫，这里任何怯懦都无济于事

编译原理-考前速通

发表于 更新于 分类于 ，
本文字数： 2.7k 阅读时长 ≈ 2 分钟

面向考前冲刺：优先覆盖“老师最爱考、最容易丢分”的题型与结论。

编译器全流程（先背骨架）

源程序 -> 词法分析 -> 语法分析 -> 语义分析与中间代码生成 -> 代码优化 -> 目标代码生成 -> 汇编/链接

  • 前端：词法 + 语法 + 语义（与目标机无关）
  • 后端：优化 + 目标代码（与目标机相关）
  • 符号表：几乎全流程都会访问
  • 出错处理：各阶段都要有（词法/语法/语义错误）

高频问答：

  • 解释器 vs 编译器：解释器边翻译边执行；编译器先整体翻译再执行
  • 一遍编译 vs 多遍编译：多遍更利于优化与模块化
  • 交叉编译：在 A 平台生成 B 平台可执行文件

词法分析（正则、自动机、手算题）

必考概念

  • 字母表、串、语言、正则表达式、正规文法、NFA、DFA
  • 识别优先级：关键字通常通过“先按标识符识别，再查保留字表”实现
  • 最长匹配原则（maximal munch）+ 规则优先级

高频手算

  • 正则 -> NFA（Thompson 构造）
  • NFA -> DFA（子集构造）
  • DFA 最小化（等价状态合并）

常见扣分点：

  • 忘记 epsilon-closure
  • 子集构造时漏了某个输入符号转移
  • 最小化时把“终态和非终态”错误合并

词法错误恢复

  • 跳过非法字符直到分隔符
  • 报错并尝试继续扫描，避免“一错全挂”

语法分析（FIRST/FOLLOW、LL(1)、LR）

文法基础

  • 二义性：同一串有不止一棵语法树
  • 消除左递归：
    • A -> Aalpha | beta
    • 改写为 A -> betaA', A' -> alphaA' | epsilon
  • 左因子提取：把公共前缀提出来，便于预测分析

FIRST / FOLLOW（必会手算）

  • FIRST(X)：X 能推出串的首终结符集合（含 epsilon 可能）
  • FOLLOW(A)：句型中 A 后可能出现的终结符集合，开始符号含 $

易错点：

  • FOLLOW 传播条件漏掉“后继可推出 epsilon”
  • FIRST(alpha) 计算时遇到可空符号后没有继续看下一个

LL(1) 判定与分析表

文法是 LL(1) 的核心条件：

  • 对同一非终结符的两个候选式 alpha, beta：
    • FIRST(alpha) ∩ FIRST(beta) = 空
    • 若 epsilon in FIRST(alpha)，则 FIRST(beta) ∩ FOLLOW(A) = 空（反之同理）

构造分析表 M[A, a]：

  • 对 a in FIRST(alpha)，填 A -> alpha
  • 若 epsilon in FIRST(alpha)，对 b in FOLLOW(A)，填 A -> alpha

LR 系列（概念题高频）

  • LR(0) 项、闭包 closure、GOTO
  • SLR(1)：用 FOLLOW 约束归约动作
  • LR(1)：项目携带展望符，能力最强（表更大）
  • LALR(1)：合并同心 LR(1) 项集，工程常用（如 Yacc/Bison 思想）

对比背诵：

  • 能力：LR(1) > LALR(1) > SLR(1) > LR(0)
  • 表规模：LR(1) 最大，LALR(1) 兼顾能力和规模

语义分析与语法制导翻译（属性文法）

属性文法

  • 综合属性（S-attributed）：自底向上易实现
  • 继承属性：依赖父/兄弟节点信息
  • L-attributed：可在自顶向下时按从左到右计算

类型检查与作用域

  • 静态语义错误：未声明、重复声明、类型不匹配、函数参数不匹配
  • 符号表常见内容：名字、类型、作用域层次、偏移量、存储类别
  • 作用域实现：进入块开新层，退出块弹栈

布尔表达式翻译

  • 短路求值：A && B，A 假则不算 B；A || B，A 真则不算 B
  • 回填（backpatching）三件套：truelist/falselist/nextlist

中间代码（四元式、三地址码）

常见形式：

  • 三地址码：x = y op z, x = op y, if x relop y goto L
  • 四元式：(op, arg1, arg2, result)
  • 三元式/间接三元式（了解即可）

控制流语句翻译常考：

  • if-else
  • while
  • do-while
  • for（拆成初始化 + 条件 + 循环体 + 迭代）

代码优化（考试最爱“判断是否优化正确”）

基本块与流图

  • 基本块：单入口单出口
  • DAG 可做局部公共子表达式消除

常见机器无关优化

  • 常量折叠、常量传播
  • 公共子表达式消除
  • 复制传播
  • 死代码删除
  • 强度削弱（乘法转移位/加法）
  • 循环优化：代码外提、归纳变量消除

数据流分析（概念）

  • 到达定义（Reaching Definitions）
  • 活跃变量（Live Variable）
  • 可用表达式（Available Expressions）

常见陷阱：

  • 进行了“看起来合理”但破坏语义的重排（忽视副作用/别名）

运行时存储组织与目标代码生成

活动记录（栈帧）

  • 典型内容：实参区、返回地址、控制链、访问链、局部变量、临时变量
  • 控制链（dynamic link）与访问链（static link）区别要会说

参数传递

  • 值传递、引用传递、值-结果传递、名字传递（了解）
  • 递归函数为何需要栈帧隔离

寄存器分配

  • 图着色思想（会解释即可）
  • 溢出（spill）：寄存器不够时落内存

错误处理（简答题高频）

  • 词法层：删除/插入字符，跳过到合法起点
  • 语法层：
    • 恐慌模式（panic mode）：跳到同步记号
    • 短语层恢复（phrase-level）
  • 语义层：类型不匹配、未定义标识符等继续检查并收集更多错误

高频“对比题”速记

  • 最左推导 vs 最右推导：推导顺序不同，语言不变
  • 语法树 vs 抽象语法树 AST：AST 去掉语法噪声，更适合后续处理
  • LL vs LR：LL 自顶向下，LR 自底向上；LR 能处理更广文法
  • S 属性定义 vs L 属性定义：前者更适合 LR，后者可用于 LL

考场手算模板

FIRST/FOLLOW 模板

  1. 先找所有可空非终结符
  2. 迭代求 FIRST，直到不再增大
  3. 初始化 FOLLOW(S) = {$}
  4. 按产生式扫描并迭代传播 FOLLOW
  5. 最后逐项检查 LL(1) 冲突

LR 项集模板

  1. 增广文法 S' -> S
  2. 从 I0 = closure({S' -> .S}) 出发
  3. 对每个项目集按符号做 GOTO，得到 DFA
  4. 生成 ACTION/GOTO 表
  5. 检查冲突（shift/reduce, reduce/reduce）

最后一小时背诵清单

  • 编译器六大阶段与前后端划分
  • 正则/NFA/DFA/最小化流程
  • 消左递归、提左因子
  • FIRST/FOLLOW 与 LL(1) 判定条件
  • LR(0)/SLR/LALR/LR(1) 区别
  • 属性文法（综合/继承/L 属性）
  • 三地址码与控制流翻译
  • 常见优化与“不能乱优化”的原因
  • 栈帧结构、静态链/动态链
  • 错误恢复策略

临考建议（提分关键）

  • 先做“确定会做的手算题”：FIRST/FOLLOW、LL(1) 表、简单中间代码
  • 概念题答法：先下定义，再给对比，最后给一句应用场景
  • 看到 LR 冲突先别慌：先判断是哪种冲突，再写产生原因
  • 每道手算题最后留 30 秒自查：
    • 集合是否漏 $ 或 epsilon
    • 分析表是否有重复填项
    • 跳转标签是否遗漏

祝你考试顺利，稳稳拿下。