编译原理基础：词法/语法/语义分析

• FIRST 集与 FOLLOW 集的计算
• LL(1) 冲突的判断
• FIRST 与 FOLLOW 交集非空导致分析表项出现多重入口

FIRST 集是某个文法符号能推导出的所有终结符集合；FOLLOW 集是某个非终结符在推导中可能紧跟的终结符集合。计算 FIRST：对终结符、非终结符按产生式递归求首终结符；计算 FOLLOW：把 $ 加入开始符号的 FOLLOW，对形如 A→αB 加 β 的 FIRST（除 ε），对 A→αB 或 A→αBβ（β 可空）加 FOLLOW(A)。构造 LL(1) 分析表时，对每个产生式 A→α，若 α 可推导出 a，则在表[A][a] 填入该产生式；若 α 可推出 ε，则在表[A][b]（b∈FOLLOW(A)）填入。若 FIRST 集与 FOLLOW 集交集非空（即某产生式能推导出 a 且该产生式可推出 ε 且 a∈FOLLOW(A)），则表项出现多重入口，是 LL(1) 冲突（first/follow 冲突），说明文法不是 LL(1)。工程价值：FIRST/FOLLOW 是预测分析表构造的基石，冲突意味着文法需改写。

冲突本质是"表项多重入口"。当某非终结符的 FIRST 与 FOLLOW 交叠，同一表项可能填入多个产生式，无法唯一预测，需改写文法消除。

• 符号表的语义检查
• 语法分析与语义分析的边界
• 基于上下文与符号表做类型检查与作用域分析

语义分析在前端用符号表（symbol table）进行语义检查：符号表记录变量、函数、类型等声明及其属性（类型、作用域、存储类）。语义分析据此检查：类型匹配（如赋值两侧类型兼容、函数实参类型匹配）、作用域（变量引用是否在作用域内）、未声明变量（引用未在符号表登记的标识符即报错）、操作数类型合法性等。职责边界：语法分析只检查"语法结构"（是否符合文法，如语句的拼接），语义分析检查"语义正确性"（如类型、作用域、声明）。语法分析基于文法，语义分析基于上下文与符号表，二者分层，语法分析产生语法树，语义分析在树上做类型检查与作用域分析。

边界是"结构 vs 语义"。语法分析验文法，语义分析用符号表验类型/作用域/声明，二者分工，符号表是语义分析的核心数据结构。

• 词法分析的正则表达
• 语法分析的上下文无关文法
• 正则无法表达对称嵌套，故需 CFG 描述语句结构

词法分析处理单词（token）识别，token 结构（标识符、数字、关键字）可用正则表达式描述，对应有限自动机（DFA/NFA），识别能力强、实现简单高效，一次扫描即可分词。语法分析处理语言的嵌套结构（表达式、语句、程序），需要上下文无关文法（CFG），因为 CFG 能描述递归与嵌套（如括号匹配、嵌套 if），而正则无法表达对称嵌套（如配对括号）。表达能力差异：正则文法（3 型）只能描述有限状态可识别的语言，不能表达嵌套递归；CFG（2 型）用递归产生式描述嵌套结构，能力更强。工程价值：用正则+DFA 做词法分析高效，用 CFG+解析器做语法分析，二者按语言结构分层，是编译器的经典分工。

差异是"单词 vs 嵌套结构"。token 是正则级，句法结构是 CFG 级，正则无法表达配对嵌套，故二者采用不同描述/识别机制。

• DFA 与 NFA 的驱动差异
• 最长匹配消歧
• DFA 确定性无回溯让词法扫描线性且高效

词法分析用 DFA 而非直接驱动 NFA，因为 DFA 每个状态只有一个确定转移，输入一个字符只需一次状态转移，无回溯、无 ε 转移，扫描效率高、实现简单；NFA 有多个转移与 ε 转移，需回溯或子集模拟，效率低。故实践中把 NFA 子集构造为 DFA 再驱动。最长匹配（maximal munch）规则解决"一个输入串可被多个 token 匹配"的歧义：当扫描到多个可行的 token 时，选择匹配最长的那个（如 <= 匹配 <= 而非先匹配 <），从而保证 token 划分唯一且符合语言直觉。工程价值：DFA 高效扫描 + 最长匹配消歧，是词法分析器正确且高效的关键。

DFA 确定性快，最长匹配保证"取最长 token"消除歧义。二者结合让词法分析线性高效且划分唯一。

• SSA 与 φ 函数
• 支配边界与 φ 放置
• φ 函数在使用点明确指向唯一定义，保证每值一定义

SSA 形式要求每个变量只被赋值一次，且每个使用点明确指向唯一的定义。但控制流汇合点（如 if 分支汇合）处，变量的值可能来自多个分支，无法确定唯一定义，因此引入 φ 函数：在汇合点选择性地把各分支传入的值合并为一个 SSA 值，从而保持"每值一定义"且使使用点可确定定义。φ 的放置由支配边界决定：控制流图中，某节点 x 的支配边界是"x 支配其所有前驱但 x 不支配该节点本身"的节点集合；当变量在 x 定义后，需在 x 的支配边界处放置 φ 函数，因为那里是"定义可能到达但不同时支配"的汇合点。工程价值：φ 函数 + 支配边界使 SSA 正确表示控制流汇合，是 SSA 构造（如 Cytron 算法）的核心。

φ 解决"汇合点的多值来源"，支配边界确定"哪里需要 φ"。二者保障 SSA 的每值一定义与正确地到达定义信息。

• 机器无关中间表示
• 可移植性与多目标优化
• 前后端解耦使换目标只需换后端、优化一次实现多目标复用

中间代码（IR）设计成与机器无关，是为了把前端（语言相关）与后端（目标机相关）解耦：前端把源语言翻译成统一 IR，后端把 IR 翻译成目标机器码。工程价值在于：1）可移植性——换目标机只需换后端，语言前端无需改动，支持多语言多目标；2）多目标优化——优化在 IR 层做一次，所有目标机共享，避免为每个目标重复实现优化；3）便于维护——前后端边界清晰。IR 层优化（如循环、内联、SSA）与机器无关，后端再针对目标做指令选择等。这是编译器"前端-中端-后端"三阶段架构的核心，让编译器可扩展、可复用。

意义是"解耦前端/后端 + 共享优化"。机器无关 IR 让优化一次实现、多目标复用，换目标只换后端，实现可移植与多目标编译。

• 短路求值的跳转翻译
• 与整体求值的差异
• 短路求值按控制流按需求值并避免多余副作用

短路求值（short-circuit）的布尔表达式（如 a && b、a || b）翻译为条件跳转：a && b 先求 a，若 a 为假则直接跳转到结果假处，不再求 b；a || b 先求 a，若 a 为真则直接跳转结果真处，不再求 b。这样把布尔表达式翻译为基于控制流的跳转代码，而非先求值再逻辑运算。与整体求值不同：整体求值先计算 a 和 b 的值，再做逻辑运算，两侧都求值；短路求值按序求值，可提前终止，且只有当 a 不足以确定结果时才求 b。工程价值：短路求值符合 C/C++ 语义（避免副作用、可提前返回），翻译为跳转代码效率高、语义正确。

差异是"控制流 vs 值运算"。短路用跳转按需求值，可提前终止并避免副作用，整体求值两端都算，语义与效率不同。

• LL 自顶向下与 LR 自底向上
• 识别能力差异
• LR 归约时持有更多上下文信息，故识别能力更强

LL(k) 是自顶向下分析器：从开始符号出发，用前瞻 k 个符号预测应用哪个产生式，逐步展开；LR(1) 是自底向上分析器：从输入符号开始，用移进-归约逐步归约到开始符号，用 1 个前瞻符号决定动作。识别能力上，LR(1) 比 LL(k) 强：LR 在归约时才决定用哪个产生式，持有更多上下文信息（右部状态），而 LL 在展开时就要预测，需更强的前瞻与更受限的文法。因此 LR 能处理更多文法（如 LL(1) 无法处理的左递归、左公因子文法），表达能力更强。工程价值：LL 适合递归下降的简单实现，LR 适合需要用工具生成、能处理更广语法（如编程语言）的场景。

差异是"方向与信息量"。LR 自底向上、归约时决策、信息更足，故识别能力更强；LL 自顶向下、展开时预测、受限于前瞻。

• 两类冲突的成因
• SLR/LALR/规范 LR 的递进
• 从 SLR 用 FOLLOW 粗判到规范 LR 用精确前瞻，冲突消解递增

移进-归约冲突：某项目集中，对同一前瞻符号既可移进又可归约（如 A→α· 与 B→β·xγ 在同一项目集，前瞻 x 属 FOLLOW(A) 又允许移进）；归约-归约冲突：同一项目集中对同一前瞻符有两个归约动作（如两个归约项目使用相同前瞻）。解决能力的递进：SLR 用 FOLLOW 集判断归约（较粗，可能仍有冲突）；规范 LR(1) 用带前瞻的 LR(1) 项目（更精确的 lookahead），几乎无冲突但状态多；LALR(1) 合并规范 LR(1) 的同心项（核心相同仅前瞻不同），逼近规范 LR 的识别能力但状态少得多。因此识别能力 LALR(1) ≥ SLR，规范 LR(1) ≥ LALR，逐步用更精确的前瞻消解冲突。

递进是"前瞻精度递进"。SLR 用 FOLLOW 粗判，规范 LR 用精确 LR(1) 前瞻，LALR 合并同心项在精度与状态数间折中，冲突消解能力递增。

• 递归下降的手写实现
• 表驱动解析的生成
• 递归下降直观可定制、表驱动易维护可自动生成

递归下降解析器为每个非终结符写一个函数，函数内按产生式手工选择与递归调用，实现直观、可读性强、易调试、易扩展（可插入语义动作、错误处理），但需手工消除左递归与左公因子，且文法改动需改代码。表驱动解析（如 yacc/bison 生成 LR 表）用预生成的分析表 + 通用驱动循环，文法改动只需更新文法文件重新生成，维护方便、能处理更广的 LR 文法，但表与生成器"黑盒"难读、难调试、错误信息差。取舍上：递归下降适合可读、可定制、LL 文法的手写场景；表驱动适合文法复杂、需工具维护、高效生成的生产场景。工程上二者按可读性与可维护性权衡。

取舍是"可读性 vs 可维护性/能力"。递归下降直观可定制，表驱动易维护、处理更广文法但难读，按需求选择。

• 左递归的无限递归
• 消除左递归的改写
• 改写为右递归与迭代保持语言等价并消除无限递归

左递归产生式形如 A→Aα|β，自顶向下分析器（递归下降/LL）在展开 A 时需先调用 A 自身，而 A 又需先调用 A，形成无限递归，无法终止。改写消除左递归：把左递归改写为右递归 + 迭代。对 A→Aα|β，改写为 A→βA'，A'→αA'|ε（右递归）。这样展开时先处理 β，再用迭代处理 α，避免无限递归。更一般地，对多左递归产生式做消除算法（替换+去左递归）。工程价值：消除左递归使自顶向下分析器可用，是 LL/递归下降解析的前提，改写后文法等价但用右递归/迭代表达。

左递归=自调用无限，改写为右递归+迭代消除。让自顶向下分析器可终止，是 LL 文法改造的核心。

• 可区分状态对的标记
• 等价状态合并
• 反复迭代标记直到无新标记，不可区分对即等价

DFA 最小化用 table-filling（填表）算法：初始把所有状态对标记为"未区分"，然后反复标记可区分对：若两状态一个是接受态一个不是，则可区分；若两状态在某个输入符号下转移到已标记可区分的状态对，则当前状态对也可区分。反复迭代直到没有新标记。未被标记的（不可区分）状态对即等价状态，可合并为同一状态，得到最小 DFA。用手工改进：先按接受性分组，再逐步细分。工程价值：最小化消除冗余状态，生成最小 DFA，减少词法分析器状态数与内存，是正则/DFA 处理的关键（如 lex 工具）。

原理是"迭代标记可区分对"。不可区分对即等价，合并得最小 DFA；标记规则基于接受性与转移目标，保证最小化正确。

• 各级 LR 的识别能力
• 同心项合并
• LALR 合并仅前瞻不同的同心项以控制状态规模

识别能力排序：LR(0) ⊂ SLR ⊆ LALR(1) ⊆ 规范 LR(1)。LR(0) 无前瞻最弱；SLR 用 FOLLOW 集做归约前瞻，强于 LR(0)；LALR(1) 用 LR(1) 前瞻但合并同心项，能力接近规范 LR(1)；规范 LR(1) 用完整 LR(1) 项目，能力最强但状态最多。LALR 通过合并"同心项"（core 相同、仅 lookahead 不同的 LR(1) 项目集）压缩状态：把多个仅前瞻不同的状态合并为一个，大幅减少状态数（与 SLR 状态数相近），同时保留 LR(1) 的精确前瞻，只在"合并后产生归约-归约冲突"时才比规范 LR(1) 弱。工程价值：LALR 在状态数与识别能力间取得最佳折中，是 yacc 等工具的选择。

排序是"前瞻精度递增"。LALR 合并同心项（core 同、lookahead 异）压缩状态，在能力接近规范 LR(1) 的同时控制状态规模。

• 直接左递归的处理
• 左公因子提取去回溯
• 左递归改迭代消化后缀、左公因子提取公共前缀消除回溯

递归下降解析器处理直接左递归通常不直接递归调用来左递归，而是改用循环/迭代：把 A→Aα|β 改写为 A→βA'、A'→αA'|ε，用 while 循环处理 α 部分，或直接在代码中用循环匹配后缀。提取左公因子消除回溯：当多个产生式有相同前缀（如 A→αβ|αγ），递归下降无法确定用哪个，需回溯；提取左公因子改写为 A→αA'、A'→β|γ，先匹配公共前缀 α，再按后续符号选择，从而避免回溯，实现确定性预测。工程价值：处理左递归与左公因子是递归下降/LL 解析可用性的关键，保证线性、无回溯的解析。

左递归用迭代消化后缀，左公因子用公共前缀+分支消除回溯。二者让递归下降解析确定、线性、无回溯。

• 预测分析表与递归下降对比
• 表驱动的优势
• 表驱动以统一驱动循环与自动生成换可维护性

预测分析表（表驱动）用预生成的分析表 + 通用栈驱动循环，按表和栈决定动作；递归下降为每个非终结符手写函数。取舍上：递归下降实现直观、可读、易加语义动作与错误处理，但需手写、文法改动需改代码、易出错；表驱动实现简洁、统一（同一驱动循环），文法改动只需更新表（重新生成），便于用工具维护，且可处理更规范化的 LL 文法。表驱动优势：逻辑统一、不易因手写错漏出错、可由文法自动生成、便于验证与扩展（如错误恢复）。代价是抽象难读、调试不便。工程价值：按可读性还是可维护性选择，表驱动适合工具化、规范化的场景。

取舍是"直观可定制 vs 统一可维护"。表驱动以统一驱动与自动生成换简洁与可维护，递归下降以手写换可读与灵活。

• SLR 的 FOLLOW 局限
• LALR(1) 的精确前瞻
• LALR 用当前状态下的可行前瞻而非全局 FOLLOW 判断归约

SLR 用 FOLLOW 集判断归约：若某项目集中的归约项目 A→α· 且前瞻符号在 FOLLOW(A) 中，则归约。但 FOLLOW(A) 是"所有可能紧跟 A 的符号"，过于宽泛——在实际上下文（到达该状态的具体路径）中，A 后面可能只有 FOLLOW(A) 的子集。因此 SLR 可能误归约产生冲突，而 LALR(1) 用精确的"当前状态下 A 的可行前瞻"（LR(1) 项目携带的 lookahead）判断，更精确，能消解 SLR 的冲突。典型例子：文法 S→L=R | R、L→*R | id、R→L，SLR 在 L→· 与 R→L· 等状态因 FOLLOW 过宽产生冲突，而 LALR(1) 用精确前瞻可区分（= 归约 L 不归约 R），从而消解冲突。工程价值：LALR 用精确前瞻弥补 SLR 的 FOLLOW 过宽，是处理真实语言（如 C 表达式）的关键。

SLR 的 FOLLOW 是"全局最宽"，LALR 的 lookahead 是"局部精确"。后者依据实际上下文，能消解 SLR 因 FOLLOW 过宽导致的冲突。

• 类型等价与类型相容
• 隐式转换的陷阱
• 按名与按结构等价各有误报漏报，隐式转换可能损失精度

类型检查中，类型等价有两种：按名等价（name equivalence，类型名相同才等价）与按结构等价（structural equivalence，结构相同即等价）。类型相容（assignment compatibility）往往比等价更宽（允许隐式转换）。语义陷阱：按名等价会拒绝结构相同但名不同的类型（如两个 typedef 别名），可能误报；按结构等价会把结构相同但语义不同的类型混同（如 meters 与 seconds 若都是 int 结构则兼容），可能漏报；隐式转换（如 int→float、char→int、指针转换）可能改变精度、丢失信息或产生意外行为，且多层/DAG 继承下的隐式转换可能产生歧义或多个候选。工程价值：类型等价/相容/转换的规则需精确设计，避免误报或语义损失，是静态类型检查正确性的关键。

陷阱源于"等价标准 + 隐式转换的语义"。按名与按结构各有误报/漏报，隐式转换可能损失精度或意外，需谨慎权衡。

• 多维数组地址计算
• 行优先/列优先布局
• 布局决定访问局部性，地址系数随行优先或列优先变化

二维数组 a[R][C]（行优先）的元素 a[i][j] 地址 = base + (iC + j)elemsize。中间代码中展开为：先计算 iC，再加 j，乘以元素大小，加到 base。编译器据此生成乘加运算。行优先（row-major，如 C）按行存储，a[i][j] 的地址 = base + (iC+j)size，访问同一行元素连续；列优先（column-major，如 Fortran）按列存储，a[i][j] = base + (jR+i)*size，访问同一列元素连续。工程影响：布局决定访问局部性——行优先下按行访问（如内层循环遍历列）缓存友好，列优先下按列访问缓存友好；地址计算公式中的系数（C 或 R）由布局决定，影响索引计算与优化（如强度削减、索引展开）。工程价值：布局与访问模式匹配可提升缓存命中，地址计算展开是循环/索引优化的基础。

影响是"缓存局部性与地址公式"。行优先按行连续、列优先按列连续，访问模式与布局匹配则缓存友好，地址系数随布局变化。

• Chomsky 分层与自动机
• 正则文法与有限自动机
• 正则产生式形式与状态转移一一对应故等价于有限自动机

Chomsky 分层：0 型（无约束文法，递归可枚举语言，对应图灵机）；1 型（上下文有关文法，上下文有关语言，对应线性有界自动机）；2 型（上下文无关文法，上下文无关语言，对应下推自动机）；3 型（正则文法，正则语言，对应有限自动机）。正则文法等价于有限自动机，因为正则文法（右线性/左线性）的产生式形式 A→aB、A→a 恰好对应有限自动机的状态转移：非终结符对应状态，A→aB 表示从 A 读 a 到 B，A→a 表示从 A 读 a 到接受态，ε 对应接受。因此正则语言与有限状态可达性一一对应，无需栈或记忆，故有限自动机正好识别正则语言。工程价值：Chomsky 分层给出了语言描述能力与自动机的对应，指导词法（正则）与语法（CFG）的分层实现。

等价性源于"正则产生式=状态转移"。正则文法无需记忆，与有限状态一一对应，故正则语言由有限自动机识别，这是词法分析用 DFA 的理论基础。

• NFA 与 DFA 的等价性
• 子集构造的状态爆炸
• DFA 用状态集合模拟 NFA 并行状态，最坏指数膨胀

NFA 与 DFA 识别能力等价，因为任一 NFA 都可通过子集构造法（subset construction）转换为等价的 DFA：NFA 的每个状态集合被映射为 DFA 的一个状态，转移按 NFA 的转移（含 ε 闭包）计算，接受态为包含 NFA 接受态的集合。DFA 能模拟 NFA 的所有可能状态（用集合表示），故识别语言相同。子集构造的状态爆炸最坏为 O(2^n)（n 为 NFA 状态数），因为可能出现 2^n 个不同的状态子集。虽然 NFA 状态数少，但 DFA 可能指数膨胀。工程价值：DFA 确定快速但可能膨胀，NFA 紧凑但需回溯，实践中常做 subset 构造并最小化，或权衡用 NFA 模拟。

等价性源于"子集模拟"。DFA 用状态集合模拟 NFA 的并行状态，最坏 2^n 爆炸，这是 NFA→DFA 转换的代价权衡。

• 正则表达式/文法/自动机转换
• Thompson 构造与子集构造
• 构成从表达式到高效可扫描 DFA 的完整词法处理链

三者相互转换：正则表达式经 Thompson 构造转为 NFA（每个正则操作符对应 NFA 子结构，如并、连接、Kleene 星）；NFA 经子集构造转为 DFA；DFA 经最小化得最小 DFA，也可反向转为正则表达式（可通过状态消除法）。正则文法与正则表达式互相转换（正则文法产生式对应正则表达式，反之亦可），正则文法也可转为 NFA。Thompson 构造解决"正则表达式→NFA"（把表达式结构映射为 NFA 子图），子集构造解决"NFA→DFA"（消除不确定性，合并状态集合）。工程价值：转换链让正则语言可用表达式描述、NFA 紧凑表达、DFA 高效识别，是词法分析器（lex）的生成流程。

分工是"Thompson 构造表达式→NFA，子集构造 NFA→DFA"。三者互转构成正则语言的完整处理链，各步骤产物不同。

• 派生树与推导
• 二义性文法
• 无二义时每个句子有唯一派生树与唯一最左推导

上下文无关文法的派生树（parse tree）表示语法结构，最左推导（每次替换最左非终结符）与最右推导（每次替换最右非终结符）都能生成同一棵派生树（若存在），即同一语法结构可有不同推导顺序但对应同一棵树。若文法无二义（unambiguous），则每个句子有唯一的派生树、唯一的最左推导；若文法二义（ambiguous），则同一句子存在多棵不同的派生树，相应地存在多个不同的最左推导（或最右推导），因为不同展开方式产生不同树。工程价值：二义文法导致解析树不唯一，语义可能歧义（如悬空 else），需用优先级/结合性或改写消除，保证唯一解析。

关系是"一棵树=多种推导顺序之一"。二义使同一句子有多棵派生树，故最左推导不唯一，需消除二义保证语义确定。

• 泵引理的应用
• 泵引理的局限
• 泵引理是必要条件，违反即非正则、满足不能证明正则

泵引理指出：任何正则语言 L 都存在一个泵长 p，使得任意长度 ≥p 的串 w 可分解为 xyz（|xy|≤p，|y|≥1），且对任意 i≥0，xy^iz 仍在 L 中。证明某语言不是正则的：反证法，假设它是正则的，取泵长 p，构造一个长度 ≥p 的串 w，证明无论如何分解 xyz，都存在某个 i 使 xy^iz 不在该语言中，从而违反泵引理，矛盾，故非正则。泵引理只能证伪不能证实：它是正则语言的必要条件，不是充分条件。即"满足泵引理"不能推出正则（有些非正则语言也满足泵引理），只有"违反泵引理"确定非正则。因此它只能用于排除正则性，不能证明正则性。工程价值：泵引理是判断语言非正则的经典工具。

泵引理是"必要条件"，违反即非正则，满足不一定正则。故只能证伪（证明非正则）不能证实（证明正则性）。

• ε-闭包
• ε 转移的消除
• ε-闭包把 ε 转移并入转移，消除 ε 转移保持语言等价

ε-NFA 含 ε 转移（不消费输入即可跳转）。ε-闭包（ε-closure）是"从某状态出发仅经 ε 转移能到达的所有状态集合"，在子集构造中用于：DFA 的起始状态 = ε-closure(起始状态)，DFA 状态在输入 a 下的转移 = ε-closure(从当前状态经 a 到达的状态的 ε 闭包)。ε-闭包保证 ε 转移被正确消化，把 ε 转移并入 DFA 转移。去除 ε 转移不会改变识别的语言：虽然 ε-NFA 与无 ε 的 NFA 结构不同，但可以消除 ε 转移（用 ε 闭包合并转移）得到等价 NFA，再子集构造为 DFA，识别的语言与原 ε-NFA 相同。工程价值：ε-闭包是子集构造的关键，ε 转移消除保证等价性，支持无缝转换。

ε-闭包"消化 ε 可达状态"，是子集构造的步骤。消除 ε 转移保持语言等价，因为 ε 转移可被合并进转移，不改变识别能力。

• 上下文有关语言的可判定性
• 递归可枚举语言的停机问题
• 有界空间保证上下文有关语言总能停机判定成员

上下文有关语言（1 型）由线性有界自动机识别，其成员判定（某串是否属于该语言）是可判定的（decidable）：因为线性有界自动机的带长受输入长度限制，其计算空间有界，总能停机并给出确定答案。递归可枚举语言（0 型）由图灵机识别，但图灵机可能不永远停机（对不属于语言的串可能无限循环），其成员问题是半可判定的（recognizable/recursively enumerable）：属于语言可验证，不属于（可能）无法判定。根本区别：上下文有关语言是可判定的（总能停机判定成员），递归可枚举语言是半可判定的（可接受但可能不停机），停机问题不可判定是其根源。工程价值：区分可判定与半可判定，理解语言与计算能力边界。

区别是"可判定 vs 半可判定"。有界空间保证上下文有关语言停机可判，图灵机可无限循环使递归可枚举仅半可判，停机不可判定是根因。

• 正则语言的封闭性
• 构造交集的自动机
• 交集用两 DFA 的笛卡尔积同步构造，补用 DFA 取反

正则语言在并、连接、Kleene 星、补、交等运算下封闭：并、连接、Kleene 星可用 NFA 构造（对应正则操作符），补可用对 DFA 的接受态取反实现，交可用笛卡尔积构造（两个 DFA 的状态对构成新 DFA 状态，转移同步，接受态为两都被接受）。构造识别交集的自动机：对 L1、L2 的 DFA D1、D2，构造 D = D1 × D2，状态为 (q1,q2)，转移 (q1,q2)--a-->(δ1(q1,a), δ2(q2,a))，接受态为 (q1,q2) 且 q1∈F1 且 q2∈F2，则 D 识别 L1∩L2。工程价值：封闭性保证正则语言的组合运算仍正则，笛卡尔积构造用于交集，是正则处理与自动机构造的基础。

封闭性保证"合成的仍是正则语言"。交集用笛卡尔积同步构造，补用 DFA 取反，是语言运算与自动机构造的关键。

• 转换流程的产物
• 各步骤开销
• 各步骤开销从 NFA 线性到 DFA 指数，最小化再压缩

完整流程：正则表达式 →（Thompson 构造）→ NFA →（子集构造）→ DFA →（最小化）→ 最小 DFA。产物：Thompson 构造产出带 ε 转移的 NFA，状态数约 O(n)（n 为表达式长度，每个操作符产生恒定子结构）；子集构造产出 DFA，状态数最坏 O(2^n)（状态集合爆炸），但一般远小于；最小化产出最小 DFA，状态数 ≤ 子集构造结果。开销：Thompson 构造 O(n) 时间与空间；子集构造时间/空间与 DFA 状态数相关，最坏指数；最小化（table-filling）O(n²) 或更优。工程价值：整套流程把表达式转为可线性扫描的高效 DFA，词法分析器（lex）据此生成，各步骤开销权衡决定实现策略。

产物是"表达式→NFA→DFA→最小 DFA"。开销从 NFA 线性到 DFA 指数，最小化压缩，是正则→DFA 生成流程的复杂度分析。

• FIRST/FOLLOW 计算
• 多重入口冲突
• 可空产生式使 FIRST 与 FOLLOW 交叠导致同一表项多产生式

FIRST 集计算：对终结符 a，FIRST(a)={a}；对非终结符 A，考察产生式 A→X1...Xn，把 FIRST(X1) 加入（除 ε），若 X1 可空继续 FIRST(X2)，直到遇到非空或结束（若全可空则 ε 加入）。FOLLOW 集计算：起点非终结符加 $；对 A→αBβ，把 FIRST(β)（除 ε）加入 FOLLOW(B)；若 β 可空或缺失，把 FOLLOW(A) 加入 FOLLOW(B)。用不动点迭代至稳定。FIRST/FOLLOW 冲突导致分析表多重入口：当某非终结符 A 有产生式 A→α（α 可推出 ε）且 FIRST(A) 与 FOLLOW(A) 有交集（某个符号 b 既在 FIRST(A) 又在 FOLLOW(A)），则 A→α 既在表[A][b]（因 b∈FIRST 经 α 展开）又在表[A][b]（因 a 可空，按 b∈FOLLOW 归约）填入，产生多重入口，非 LL(1)。工程价值：多重入口即冲突，需改写文法消除。

冲突根源是"可空产生式与 FOLLOW 交叠"。FIRST 与 FOLLOW 交集非空时，同一表项被多个产生式填入，无法唯一预测，破坏 LL(1)。

• 两类冲突的情形
• 定位到项目集
• 冲突定位到具体项目集与前瞻符号以追溯产生式原因

移进-归约冲突：在同一项目集中，既有移进项目（如 B→β·aγ）又有归约项目（如 A→α·），且前瞻符号 a 同时满足"可移进"和"属于归约的可行前瞻"（FOLLOW(A) 或 LR(1) 前瞻），则对该符号既有移进又有归约动作，冲突。归约-归约冲突：同一项目集中有两个归约项目（如 A→α·、B→β·）对同一前瞻符号都要求归约，冲突。定位：冲突出现在特定项目集（状态）中，该状态由文法某前缀可达；通过分析生成器（yacc/bison）报告冲突时，指出冲突的项目集与前瞻符号，开发者据此查看该状态的项目，追溯到产生冲突的产生式。工程价值：定位冲突状态与项目，帮助改写文法（如提取左公因子、调整优先级）消除冲突。

冲突是"一状态一前瞻的多个动作"。移进-归约冲突是移进与归约竞争，归约-归约是两归约竞争，定位到项目集与前瞻以追溯原因。

• 综合属性与继承属性
• 边分析边计算
• 依赖单向且适时可算，保证一遍扫描即可计算语义

S-属性文法（S-attributed）只使用综合属性（synthesized attributes），属性值由子节点向上聚合，在自底向上分析（LR）中，归约时即可计算父属性的值，无需前瞻子节点以外的信息，天然支持"边分析边计算"。L-属性文法（L-attributed）是 S-属性的扩展，除综合属性外，允许继承属性（inherited），但限制：继承属性只能从左兄弟或父节点继承，且依赖方向沿从左到右。这种限制保证在自顶向下/递归下降的从左到右的分析中，属性值在需要时已经可计算（左兄弟、父节点的属性已算好），无需回看右侧。因此二者便于"边分析边计算语义"：单向依赖、无需回溯，分析的每一步都能立即计算属性，实现语法制导翻译的一遍扫描。

限制的实质是"依赖单向且适时可算"。S-属性偏自底向上聚合，L-属性限制继承方向，保证一遍扫描即可计算语义，无需两遍。

• 优先级与结合性
• 悬空 else 的消歧
• 用优先级与结合性声明式消歧，避免改写复杂文法

二义性文法（如悬空 else、运算符优先级）可通过优先级与结合性规则在解析器中消歧，无需改写文法。悬空 else：if a if b s1 else s2 中 else 与哪个 if 配对，按"最近匹配"规则（else 与最近的未匹配 if 配对），解析器据此消歧。运算符优先级与结合性：通过声明优先级（如 * 高于 +）与结合性（左结合/右结合），yacc/bison 等用优先级声明消解移进-归约冲突，决定运算符的归约顺序。工程价值：优先级与结合性声明提供声明式消歧，避免改写文法产生复杂等价文法，让解析器按操作符语义正确解析表达式，是 yacc 处理运算符的标准手段。

消歧是"用规则约束偏好"。悬空 else 用最近匹配，运算符用优先级/结合性声明，在冲突处选择，避免改写文法。

• dangling else 的悬空配对
• 改写文法消除
• 让 else 与最近未匹配 if 配对，保证配对唯一

dangling else 问题：if a if b s1 else s2 中 else 可与内层 if 或外层 if 配对，产生二义。用优先级/结合性声明消除：yacc 中把 else 与 if 的优先级声明为"else 与最近的 if 结合"（即 else 优先归约到最近的未匹配 if），通过声明优先级消解冲突。改写文法消除：把 if 语句分为"匹配语句"（matched）与"未匹配语句"（unmatched），如果语句必须是匹配语句，从而保证 else 只能与最近的未匹配 if 配对，消去二义。工程价值：优先级声明是声明式、改文法结构式，二者都消除 dangling else 的二义，保证 else 配对唯一，符合语言直觉。

消除是"让 else 与最近 if 配对"。优先级声明或改写为 matched/unmatched 文法，都使 else 配对唯一，消除二义。

• 算符优先分析的适用场景
• 与 LR 的能力差异
• 算符优先分析限于运算符文法、实现简单但能力弱于 LR

算符优先分析（operator precedence parsing）适合处理表达式文法——基于运算符优先级与结合性，用"最左素短语"（最左的、可归约的、不含运算符优先级歧义的短语）进行归约，适合一大类表达式（算术、布尔）的解析。它与 LR 的差异：算符优先分析限制在运算符文法（无相邻非终结符、无 ε 产生式、无两非终结符相邻），不需要栈上保存完整上下文，通过算符优先关系表归约，实现简单、速度快，但能力有限（不能处理某些表达式约束，如 - 一元与二元冲突、某些赋值）；LR 分析用完整状态栈与前瞻，能处理更广的文法（含运算符文法的超集），但需生成 LR 表、状态多。能力上算符优先 ⊆ LR（算符优先文法类是 LR 的子集）。工程价值：算符优先适合快速表达式解析，LR 适合通用/复杂文法。

差异是"受限 vs 通用"。算符优先做运算符文法、简单快速但能力受限，LR 状态栈更通用，算符优先文法 ⊆ LR 文法。

• 活前缀与项目
• 栈内容合法性
• 状态由活前缀可达的项目集给出下一步动作，保证栈合法

活前缀（viable prefix）是"某个右句型（最右推导的某个前体）的前缀"，且该前缀不越过句柄的右端。项目（item）是带位置点的产生式（如 A→α·β），表示"已识别 α、待识别 β"。LR 分析中，分析栈内容始终是某个活前缀的符号序列，且这个状态正是由该活前缀经自动机到达的项目集。项目集定义"在该活前缀下所有可能的下一步"，据此决定移进/归约。合法性保证：LR 分析只允许栈内容为活前缀，因为状态转移只从活前缀可达；若栈内容不是活前缀（如错误归约），则无对应状态或动作，分析报错。工程的"栈内容始终合法"由 LR 自动机的确定性转移与活前缀闭包保证，避免非法归约。

关系是"栈=活前缀，状态=项目集"。活前缀保证栈符号有合法后续，项目集给出下一步动作，二者确保栈内容始终是合法前缀。

• S-属性与 L-属性区别
• L-属性与自顶向下
• L-属性继承方向与自顶向下展开顺序一致，可一遍翻译

S-属性文法（S-attributed）只使用综合属性，属性值从子节点向上聚合，适合自底向上（LR）分析中归约时计算。L-属性文法（L-attributed）除综合属性外允许继承属性，但限制继承属性只能从左兄弟或父节点继承，依赖方向从左到右。区别：S-属性只综合、自下而上传递（子→父）；L-属性含继承、但限制从左到右。L-属性适合自顶向下翻译：自顶向下（递归下降）按从左到右展开产生式，当处理节点时，其父节点与左兄弟的继承属性已经计算完成，可以直接使用，无需回看右侧或两遍扫描；因此 L-属性文法在递归下降中可一遍从左到右计算所有属性，实现边分析边翻译。

L-属性限制继承方向为"从左到右"，与自顶向下展开顺序一致，故递归下降中父/左兄弟属性已就绪，可一遍翻译。

• 作用域链与符号表
• 遮蔽与作用域维护
• 查找自顶向下逐层进行，内层声明遮蔽外层同名符号

符号表用作用域链（scope chain）支持嵌套块：每个作用域有自己的符号表，嵌套作用域形成链/栈。进入作用域时，为新作用域创建符号表并压入链顶；退出时弹出。查找标识符时从链顶向下逐层查找，找到即返回，因此内层遮蔽（shadowing）外层同名符号（内层定义优先）。遮蔽语义：内层符号覆盖外层同名符号，作用域内引用内层。维护机制：进入作用域 push 新表，声明时在当前表插入符号，退出作用域 pop 当前表，期间若符号被遮蔽则在外层表仍保留。工程价值：作用域链实现嵌套词法作用域与遮蔽的正确语义，是类型检查与名字解析的基础，常用哈希表 + 链实现。

作用域链是"嵌套作用域的符号表栈"。查找自顶向下、内层遮蔽外层，push/pop 维护进入退出，实现词法作用域语义。

• 三地址码的表示
• 四元式/三元式差异
• 四元式结果显式便于重排，三元式结果靠序号重排易错

三地址码（TAC）每条指令最多三个操作数，如 x = y op z，用临时变量表示中间结果。四元式（quadruple）用四元组 (op, arg1, arg2, result) 表示，result 是显式的结果位置，临时变量用显式结果表示，便于代码重排（indirect 引用结果，移动指令不会破坏共享结果）。三元式（triple）用三元组 (op, arg1, arg2) 表示，结果用该三元式的序号（位置）引用，不显式命名结果；但若重排代码，用序号引用的结果会错位（序号随位置变化），故三元式不便于代码重排。差异：四元式结果显式、重排安全；三元式结果隐式（序号）、重排易错；TAC 是通用形式，四元式是其常见实现。工程价值：四元式便于优化（重排、复制传播），三元式紧凑但重排难，选择影响优化方便性。

差异在"结果如何命名"。四元式显式结果可重排，三元式结果靠位置序号、重排会错位，故四元式更利于优化。

• 属性求值顺序
• 循环依赖
• 依赖图无环才有拓扑序求值，循环依赖使无求值切入点

属性求值顺序受依赖图约束：属性间依赖形成有向图，求值顺序必须是依赖图的一个拓扑序（先求被依赖的，再求依赖者）。综合属性由子节点属性决定（依赖子节点），继承属性由父/兄弟属性决定（依赖父/左兄弟）。若依赖图无环（有向无环图 DAG），则存在拓扑序，可按序求值；若存在环（循环依赖），则无拓扑序，无法求出任何属性值——因为每个属性都依赖另一个未求值的属性，形成循环，无切入点。循环依赖导致翻译无法进行：没有任何属性可先求值，无法确定求值起点。故属性文法需保证依赖无环（如 S-属性、L-属性天然无环），才能一遍遍历求值。工程价值：依赖无环是属性翻译可执行的前提，经典属性文法（S/L）保证这一点。

约束是"拓扑序求值"。依赖图无环才有求值顺序，环使无切入点、无法求值，S/L-属性文法天然无环保证可执行。