🟡 理解#

• 三种翻译程序的区别
  • 翻译程序：把源语言程序转换成功能等价的目标语言程序。
  • 编译程序：源=高级语言，目标=低级语言，一次性生成目标程序，执行快。
  • 解释程序：逐句翻译边翻边执行，不生成目标程序，便于调试但慢。
• 编译的六个阶段（必背顺序） 词法分析 → 语法分析 → 语义分析 → 中间代码生成 → 代码优化 → 目标代码生成
• 各阶段的输入/输出与任务（重点前四个）
  • 词法分析：源程序 → 单词符号序列（二元组）。
  • 语法分析：单词序列 → 语法树/语法单位。
  • 语义分析：类型检查、收集类型信息、语义查错。
  • 中间代码生成：生成四元式等中间形式。
• 两个贯穿始终的辅助模块：符号表（表格）管理、出错处理。
• 前端 / 后端划分
  • 前端：与源语言有关、与目标机无关（1~4 阶段）。
  • 后端：与目标机有关（第 6 阶段）。
  • 代码优化（第 5 阶段）可前可后。
• 遍 / 趟 (Pass)：对源程序或中间结果从头到尾扫描一次；分遍的多少取决于源语言与目标机特征。

🟢 了解#

• 高级语言处理流程：预处理 → 编译 → 汇编 → 装配/连接 → 绝对机器代码。
• 前后端组合的两种用途（换后端支持多机器；换前端支持多语言，共用后端）。
• 多遍优缺点：优点结构清晰省内存；缺点增加 I/O、降效率。

⚠️ 易错点#

• 把汇编语言翻成机器码的是汇编器，不是编译器。

🔴 核心#

• 文法四元组 G = (V_N, V_T, P, S) 各分量含义。

• Chomsky 文法分类（必背表）

  型	名称	限制条件	对应自动机
  0	短语结构文法	α→β，α 中至少含一个非终结符	图灵机
  1	上下文有关文法	|β| ≥ |α|	线性界限自动机
  2	上下文无关文法(CFG)	A→β（左部单非终结符）	下推自动机
  3	正规/正则文法	A→a 或 A→aB	有穷自动机

  包含关系：3型 ⊂ 2型 ⊂ 1型 ⊂ 0型。

• 短语 / 直接短语 / 句柄（第 5、6 章反复用，必须吃透）

  • 短语：S ⇒* αAδ 且 A ⇒⁺ β，则 β 是相对 A 的短语。
  • 直接短语：A ⇒ β（一步推导），β 是直接短语。
  • 句柄 = 最左直接短语。

• 给句型求全部短语/直接短语/句柄（计算题，务必练）。

🟡 理解#

• 研究语言三方面：语法(Syntax) / 语义(Semantics) / 语用(Pragmatics)。
• 符号串运算：连接、方幂（x⁰=ε）、正闭包 A⁺、闭包 A*=A⁺∪{ε}。
• 推导：直接推导 ⇒、推导 ⇒*；最左推导 / 最右推导（=规范推导）。
• 句型（S⇒x）/ 句子（句型且 x∈V_T）/ 语言 L(G)={x | S⇒x, x∈V_T}。
• 二义性：一个句子存在两棵不同语法树（或两个不同最左/最右推导）；二义性不可判定。
• 句型分析两大类：自顶向下（推导）、自底向上（归约，找可归约串）。

🟢 了解#

• 文法实用性：不得含有害规则（U→U）、多余规则（不可达/不可终止）；慎用 ε 规则。

⚠️ 易错点#

• 短语 β 必须是所分析句型 αβδ 的一部分（要在句型内）。
• 直接短语强调”一步推导”，短语是”一步或多步”。

🔴 核心（词法大题一条龙，20 分）#

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

🟡 理解#

• DFA 五元组 M=(K, Σ, f, S, Z)，f: K×Σ→K（单值、单初态、无 ε）。
• NFA：f: K×Σ→2^K（幂集），可多初态、可有 ε 弧。
• DFA 是 NFA 的特例；NFA、正规式、正规文法三者等价可互转。
• 正规式代数规则：分配律 s(r|t)=sr|st 成立；rs≠sr（连接不满足交换律）。
• 单词五大类：基本字、标识符、常量、运算符、界符；输出二元组 (单词种别, 值/指针)。
• “字符串集是正规集 ⟺ 存在 DFA 识别它”。

🟢 了解#

• 扫描器（词法分析程序）作为语法分析的子程序被调用。
• LEX：词法分析程序自动构造工具（正规式定义+动作 → 生成分析器）。

⚠️ 易错点#

• ε-closure 一定包含状态自身。
• 最小化第一步是”终态/非终态”两分，不是一上来全拆。

🔴 核心（20 分大题）#

1. 求 FIRST / FOLLOW / SELECT 集
   • FIRST(α)：α 能推出的串的首终结符集（若 α⇒*ε 则含 ε）。
   • FOLLOW(A)：句型中紧跟 A 之后的终结符集；#∈FOLLOW(S)。
   • SELECT：
     • α 不能⇒ε：SELECT(A→α)=FIRST(α)。
     • α⇒*ε：SELECT(A→α)=(FIRST(α)−{ε})∪FOLLOW(A)。
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 进栈起；栈顶终结符与输入匹配则弹栈前移；栈顶非终结符则查表展开（逆序压右部）。

🟡 理解#

• LL(1) 含义：从左到右扫描(L)、生成最左推导(L)、向前看 1 个符号(1)。
• 自顶向下 = 面向目标，寻找最左推导，从根构造语法树。
• 引起回溯的三个原因：右部 FIRST 相交、能推空且 FOLLOW 与其他右部 FIRST 相交、含左递归。
• 递归下降法：为每个非终结符写一个子程序；优点直观易扩充，缺点效率低、要求 LL(1)、难自动生成。
• 左递归类型：直接（A→Aβ）、间接（A→Bβ 且 B→Aα）。

🟢 了解#

• EBNF：{α}=α*，[α]=可选 0/1 次；语法图与化简（提左/右因子、循环化简）。
• 分析方法总览：自顶向下（递归下降、预测）/ 自底向上（算符优先、LR）。

⚠️ 易错点#

• α⇒*ε 时 SELECT 一定要并上 FOLLOW。
• 消左递归/提公因子后常产生不可达（多余）产生式，必须删除。
• 递归下降要求文法必须是 LL(1)；直接左递归导致死循环。

🔴 核心（20 分大题）#

1. 给句型求 5 种短语：短语、直接短语、句柄、素短语、最左素短语（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 → 取相等；收敛为止（超过 2n 则无优先函数）。

🟡 理解#

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

🟢 了解#

• 简单优先分析法：按所有文法符号（含非终结符）间优先关系确定句柄；缺点效率低、适用面窄、常存在多种优先关系。
• 优先函数缺点：无优先关系的空格无法体现出错位置。

⚠️ 易错点#

• 素短语必须至少含一个终结符（纯非终结符短语不算）。
• 算符优先去掉了单非终结符归约（如 T→F），可能把错句子误判为正确。

🔴 核心（20 分大题）#

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

🟡 理解#

• LR(k)：L=从左到右扫描，R=最右推导的逆（规范归约），k=向前看符号数。

• 活前缀 / 可归前缀：S′⇒*αAγ⇒αβγ，αβ 为可归前缀，其前缀为活前缀（不含句柄之后的符号）。

• LR(0) 项目四类：移进 A→α·aβ、待约 A→α·Bβ、归约 A→αβ·、接受 S′→α·。

• 冲突：移进-归约冲突、归约-归约冲突；无冲突=相容。

• 四种方法区别（核心对照）

  方法	归约时机	特点
  LR(0)	对所有终结符归约	最弱
  SLR(1)	仅对 a∈FOLLOW(A) 归约	用 FOLLOW 解冲突
  LR(1)	项目带搜索符，对 a=搜索符归约	最强、表最大
  LALR(1)	合并同心集（心相同、搜索符取并）	实用主流，状态数同 LR(0)

• 能力关系（必背）：LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1)。

• 同心集：心（LR(0) 部分）相同的 LR(1) 项目合并，搜索符取并集；合并只可能引入归约-归约冲突。

🟢 了解#

• 求可归前缀的一般算法（LC(A)=[A] 方程组法）。
• LALR(1) 与 LR(1) 分析能力接近，但状态数远少于 LR(1)。

⚠️ 易错点#

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