〇、战略：题型与分值分布#

复习优先级：第 4/5/6 章（算法最重、最易丢分）＞ 第 3 章 ＞ 第 1/2 章（背概念保底）。

一、第1章 编译程序概论 ☆#

必背概念

• 翻译程序 / 编译程序（高级→低级，一次性生成目标程序）/ 解释程序（逐句翻译边翻边执行、不生成目标程序）。
• 编译六阶段：词法分析 → 语法分析 → 语义分析 → 中间代码生成 → 代码优化 → 目标代码生成。
• 贯穿始终的两个辅助模块：符号表管理、出错处理。
• 前端（与源语言相关、与机器无关，1~4阶段）/ 后端（与目标机相关，第6阶段）；优化可前可后。
• 遍/趟(pass)：对源程序（或中间结果）从头到尾扫描一次。

常考题型

• 简答：编译分哪几个阶段，各阶段功能（4分必考）。
• 填空/选择：编译与解释的根本区别；分”遍”的优缺点；符号表的作用。

易错点

• 把汇编语言翻译成机器码的是汇编器，不是编译器。
• 编译方式生成目标程序、执行快；解释方式不生成目标程序、便于调试但慢。
• 多遍：优点=结构清晰、功能单一、省内存；缺点=增加 I/O、降低效率。

二、第2章 文法和语言 ☆#

必背概念

• 研究语言三方面：语法(Syntax)/语义(Semantics)/语用(Pragmatics)。
• 符号串运算：连接、方幂 x⁰=ε、正闭包 A⁺、闭包 A*=A⁺∪{ε}。
• 文法四元组 G=(V_N, V_T, P, S)。
• Chomsky 分类（必背表）：

• 推导：直接推导 ⇒、推导 ⇒*；最左推导 / 最右推导=规范推导。
• 句型（S⇒x）/ 句子（句型且 x∈V_T）/ 语言 L(G)。
• 短语、直接短语、句柄（第5、6章反复用，务必吃透）：
  • 短语：S⇒*αAδ 且 A⇒⁺β，则 β 是相对 A 的短语。
  • 直接短语：A⇒β（一步），β 是直接短语。
  • 句柄 = 最左直接短语。
• 二义性：一个句子存在两棵不同语法树（或两个不同最左/最右推导）。二义性不可判定。

常考题型

• 填空：规范归约用句柄刻画可归约串；自顶向下的问题是递归(左递归)和回溯；3型文法又称正规文法。
• 简答：什么是二义性 + 为什么不可判定。
• 计算：给文法句型求全部短语/直接短语/句柄；求文法生成的语言（如 S→1S|2S|ε 生成 {1,2}*）。

三、第3章 词法分析 ★#

必背概念

• 正规文法（3型，右线性 A→aB / A→a）、正规式、正规集。
• 正规式代数规则：s(r|t)=sr|st（分配律成立）；rs≠sr（连接不满足交换律）。
• DFA 五元组 M=(K,Σ,f,S,Z)，f: K×Σ→K（单值、单初态）。
• NFA：f: K×Σ→2^K（幂集）、可多初态、可有 ε 弧。
• ε-闭包 ε-closure(I)、move(I,a)、I_a=ε-closure(move(I,a))。

★必练算法（词法大题一条龙）

1. 语言描述 → 正规式（如”倒数第二个字符为a”→ (a|b)*a(a|b)）。
2. 正规式 → NFA（Thompson 构造：ε、a、st 连接、s|t 并、s* 闭包）。
3. NFA → DFA 确定化（子集构造/造表法：算 ε-closure 和各输入的 I_a，新状态补到表尾，直到不再产生新状态）。
4. DFA 最小化（分割法：先分终态组 / 非终态组，再按转移目标所属组逐步细分，直到不可再分，合并等价态、去多余态）。
5. 正规式 ↔ 正规文法 互相转换（S→r 逐步分解 / A→xB,B→y 合并回 A=xy）。

常考题型

• 20分大题：给语言 → 写正规式 → 构造NFA → 确定化DFA → 最小化DFA。
• 证明题：用集合思想证正规式恒等式（如 s(r|t)=sr|st）。

易错点

• ε-closure 一定包含状态自身。
• 最小化第一步必须是”终态/非终态”两分，不是一上来全拆。
• DFA 是 NFA 的特例；NFA、正规式、正规文法三者等价可互转。

四、第4章 自顶向下语法分析 ★#

必背概念

• LL(1)：从左到右扫描、最左推导、向前看1个符号。
• FIRST(α)：α 能推出的串的首终结符集（含 ε 若 α⇒*ε）。
• FOLLOW(A)：句型中紧跟 A 之后的终结符集；对开始符 S 有 #∈FOLLOW(S)。
• SELECT：A→α 非空则 =FIRST(α)；α⇒*ε 则 =(FIRST(α)−{ε})∪FOLLOW(A)。
• LL(1) 充要条件：同一非终结符任意两候选式 SELECT 交集为空。

★必练算法

1. 求各符号 FIRST 集、FOLLOW 集、SELECT 集。
2. 判断是否 LL(1)（同左部候选 SELECT 是否相交）。
3. 消除左递归：
   • 直接：A→Aα|β ⟹ A→βA′, A′→αA′|ε。
   • 间接：先代入化成直接左递归再消。
4. 提取左公因子：A→αβ|αγ ⟹ A→αA′, A′→β|γ。
5. 构造预测分析表 M[A,a]：a∈SELECT(A→α) 处填 →α，空格填 error。
6. 预测分析过程（栈 / 剩余输入 / 所用规则；#S 进栈起，匹配终结符弹栈、非终结符查表展开）。

常考题型（模拟卷四：20分）

• 改写文法使其适合自顶向下（消左递归 + 提公因子）。
• 判断改写后是否 LL(1)（写依据）。
• 构造预测分析表；分析输入串。

易错点

• α⇒*ε 时 SELECT 要并上 FOLLOW，别忘。
• 消左递归后常出现不可达/多余产生式，必须删。
• 递归下降要求文法必须是 LL(1)；直接左递归会导致死循环。

五、第5章 自底向上——算符优先分析 ★#

必背概念（名词解释高频）

• 自底向上 = 归约（RHS→LHS）；移进-归约、可归约串。
• 短语 / 直接短语 / 句柄（同第2章）。
• 素短语：至少含一个终结符、且不再包含其他素短语的短语。
• 最左素短语：句型中最左边的素短语。
• 算符文法 OG：无形如 U→…VW…（两非终结符相邻）的规则。
• 算符优先文法 OPG：OG + 任意两终结符间至多一种优先关系。OPG 无二义。
• 优先关系 < = > 有次序，≠数学大小；只看终结符之间。

★必练算法

1. 给句型求 短语、直接短语、句柄、素短语、最左素短语（务必练熟，5项都要写）。
2. 求每个非终结符 FIRSTVT / LASTVT：
   • FIRSTVT(A)={ b | A⇒⁺b… 或 A⇒⁺Bb… }（往下推能露出的第一个算符）。
   • LASTVT(A)={ a | A⇒⁺…a 或 A⇒⁺…aB }（最后一个算符）。
3. 构造算符优先关系表：
   • A→…aB…：a < FIRSTVT(B) 每个元素。
   • A→…Ba…：LASTVT(B) 每个元素 > a。
   • A→…ab… / A→…aBb…：a = b。
   • 补界符：# < FIRSTVT(S)、LASTVT(S) > #、# = #。
4. 算符优先分析过程（栈 / 优先关系 / 当前符号 / 输入 / 动作）：栈顶终结符 vs 输入符，< 或 = 移进，> 归约（找最左素短语，非终结符不影响）。
5. 优先函数（Floyd 算法）：初值 f=g=1；按 a>b→f(a)=g(b)+1、a<b→g(b)=f(a)+1、a=b→取等 迭代到收敛。

常考题型（模拟卷五：20分）

• 名词解释：句柄、素短语。
• 给文法句型求 5 种短语。
• 构造优先关系表（写步骤）；分析输入串。

易错点

• 素短语必须至少含一个终结符（纯非终结符的短语不算）。
• 算符优先分析去掉了单非终结符归约（如 T→F），可能把错句子误判为正确。
• 优先函数缺点：无优先关系的空格无法体现出错位置。

六、第6章 自底向上——LR 分析 ★#

必背概念

• LR(k)：L=从左到右扫描，R=最右推导的逆（规范归约），k=向前看符号数。
• 活前缀 / 可归前缀：S′⇒*αAγ⇒αβγ，αβ 为可归前缀，其前缀为活前缀（不含句柄之后的符号）。
• LR(0) 项目（圆点位置）四类：
  • 移进项目 A→α·aβ、待约项目 A→α·Bβ、归约项目 A→αβ·、接受项目 S′→α·。
• CLOSURE（闭包）、GO(I,X)（转移）、项目集规范族。
• 冲突：移进-归约冲突、归约-归约冲突；无冲突=相容。
• 能力关系（必背）：LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1)。

四种方法的区别（核心）

★必练算法

1. 拓广文法 S′→S，构造 LR(0) / LR(1) 项目集规范族（画识别活前缀的 DFA）。
   • LR(1) 闭包关键：A→α·Bβ,a 引出 B→·η,b，其中 b∈FIRST(βa)。
2. 构造分析表 ACTION / GOTO（sj 移进、rj 归约、acc 接受、空 error）。
3. 分析输入串（状态栈 / 符号栈 / 输入串 / action / goto）。
4. 判断文法属于哪类 LR（看冲突：有移进-归约冲突→非LR(0)；FOLLOW 能否解→SLR；合并同心集有无归约-归约冲突→LALR）。

常考题型（模拟卷六：20分）

• 画 LR(1) 识别所有活前缀的 DFA。
• 构造 LR(1) 分析表。
• 写输入串分析过程。
• 简答：LR 分析器 vs 优先关系分析器识别句柄的异同。

易错点

• LR(0) 归约项目对所有终结符都填 rj；SLR 只在 FOLLOW 集列填。
• LR(1) 构造闭包别漏”继承的后继符”（β⇒ε 时 b=a）。
• LALR 合并同心集只可能引入归约-归约冲突，不会引入移进-归约冲突。
• 拓广文法 S′→S 是为了有唯一接受态。

七、必会手算算法总清单（考前自测）#

• 语言 → 正规式（第3章）
• 正规式 → NFA（Thompson）
• NFA → DFA（子集构造/造表）
• DFA 最小化（分割法）
• 正规式 ↔ 正规文法
• 求 FIRST / FOLLOW / SELECT
• 消除左递归（直接+间接）、提取左公因子
• 判断 LL(1) + 构造预测分析表 + 分析串
• 求短语/直接短语/句柄/素短语/最左素短语
• 求 FIRSTVT / LASTVT + 构造算符优先关系表 + 分析串
• 优先函数（Floyd）
• 构造 LR(0)/LR(1) 项目集规范族（画DFA）
• 构造 LR 分析表 + 分析串
• 判断文法属于 LR(0)/SLR(1)/LALR(1)/LR(1)

八、高频概念对照（易混）#