编程语言与编译器

默认只展示每周独有的知识重点；节奏、考核、Tutorial 和避坑信息按需展开。

1. 1

   编译器概述与词法分析导论

   📖核心知识点：编译器的整体架构——前端（词法分析→语法分析→语义分析）、中间表示（IR）、后端（代码生成→优化）；编译与解释的区别；词法分析器（Scanner/Lexer）的角色——将字符流转换为Token流；Token的定义（类型+属性值）；正则表达式到有限自动机的转换思想。⏰本周节奏：第一周以全局视角理解编译流水线为主，重点记忆各阶段的输入输出和职责边界。🎯考试关联：编译器各阶段的功能描述是期末简答题必考点；正则表达式→NFA→DFA的转换是计算题高频考点。🧪Tutorial/Lab：搭建课程编译器项目环境（通常基于Java），了解项目框架结构；编写简单的正则表达式匹配Token。📌作业关联：Assignment 1要求实现完整的Scanner，本周必须理解Token定义规范和项目代码框架。⚠️易错点：混淆编译器前端与后端的职责分界；忽略词法分析中的最长匹配原则（Maximal Munch）。

2. 2

   有限自动机与词法分析器构造

   📖核心知识点：确定性有限自动机（DFA）vs非确定性有限自动机（NFA）的形式化定义；Thompson构造法——正则表达式→NFA；子集构造法——NFA→DFA（ε-closure计算）；DFA最小化算法（等价类合并）；词法分析器生成工具（JFlex/Lex）的使用原理。⏰本周节奏：NFA→DFA转换是本周核心，建议手动完成3-4个完整的RE→NFA→DFA→最小化DFA练习。🎯考试关联：子集构造法的手动执行过程是期末必考大题（15-20分），要求画出完整的状态转移表和DFA状态图。🧪Tutorial/Lab：用Thompson构造法将给定正则表达式转换为NFA，再用子集构造法转换为DFA；开始使用JFlex为课程语言生成Scanner。📌作业关联：Assignment 1的Scanner实现需要理解DFA驱动的词法分析原理，JFlex规格文件编写是核心任务。⚠️易错点：ε-closure计算遗漏可达状态；子集构造时的死状态（dead state）处理；DFA最小化时初始划分搞错。

3. 3

   上下文无关文法与语法分析基础

   📖核心知识点：上下文无关文法（CFG）的形式化定义——终结符、非终结符、产生式、起始符号；推导（Derivation）——最左推导vs最右推导；语法树（Parse Tree）与抽象语法树（AST）的区别；文法的二义性（Ambiguity）判定与消除方法——优先级和结合性的编码。⏰本周节奏：从词法分析过渡到语法分析，概念跨度大，建议重点理解CFG如何描述语言结构，练习画语法树和判定二义性。🎯考试关联：给定文法判断是否有二义性并消除二义性是期末常考题；最左推导与最右推导的区别是选择题高频考点。🧪Tutorial/Lab：为简单的算术表达式语言编写CFG；消除算术表达式文法的二义性（通过引入优先级层级）。📌作业关联：Assignment 2（Parser）需要理解课程语言的CFG规格说明，文法规则是Parser实现的直接依据。⚠️易错点：混淆语法树和AST——语法树保留所有文法符号，AST只保留语义相关节点；二义性消除时引入过多层级导致文法不必要的复杂。

4. 4

   自顶向下语法分析：递归下降与LL(1)

   📖核心知识点：自顶向下分析策略——从起始符号出发尝试推导输入串；递归下降解析器（Recursive Descent Parser）的实现模式——每个非终结符对应一个函数；LL(1)文法的定义与判定——FIRST集和FOLLOW集的计算方法；LL(1)分析表的构造；左递归消除与左公因子提取。⏰本周节奏：FIRST/FOLLOW集计算是本周核心硬技能，建议做5-6道完整的FIRST/FOLLOW/LL(1)表构造练习直到手熟。🎯考试关联：FIRST/FOLLOW集计算和LL(1)分析表构造是期末必考计算题，占15-20分。🧪Tutorial/Lab：为课程语言的子集计算FIRST和FOLLOW集；实现递归下降解析器的核心框架。📌作业关联：Assignment 2要求实现递归下降Parser，FIRST/FOLLOW的理解直接影响如何处理各个非终结符的解析函数。⚠️易错点：FOLLOW集计算中遗漏ε产生式的传播；左递归消除后的文法等价性验证；LL(1)冲突的判定（FIRST集交集非空或nullable时FIRST∩FOLLOW非空）。

5. 5

   自底向上语法分析：LR分析

   📖核心知识点：自底向上分析策略——从输入串出发通过归约（Reduce）得到起始符号；移进-归约（Shift-Reduce）解析过程；LR(0)项（Item）与LR(0)自动机的构造——closure和goto操作；SLR(1)分析表的构造方法；LR(1)与LALR(1)的区别与联系；YACC/Bison工具的使用原理。⏰本周节奏：LR分析是全课最难的理论部分之一，建议先理解直觉（「句柄Handle的识别「），再看形式化的项集构造，至少手工构造2个完整的SLR(1)分析表。🎯考试关联：SLR(1)分析表的手工构造是期末压轴计算题（20+分），需要画LR(0)自动机+构造ACTION/GOTO表。🧪Tutorial/Lab：手工构造简单文法的LR(0)自动机和SLR(1)分析表；识别Shift-Reduce和Reduce-Reduce冲突。📌作业关联：理解LR分析有助于调试Assignment 2中的语法错误恢复逻辑。⚠️易错点：closure操作遗漏间接展开的项；SLR(1)表中FOLLOW集导致的虚假冲突（LR(1)可解决但SLR不行）。

6. 6

   语义分析与类型检查

   📖核心知识点：语义分析的任务——类型检查、作用域解析、常量折叠；属性文法（Attribute Grammar）——综合属性（S-属性）vs继承属性（L-属性）；符号表（Symbol Table）的设计与作用域管理——块结构语言的嵌套作用域处理；类型系统——静态类型vs动态类型、强类型vs弱类型；类型检查规则与类型推断基础。⏰本周节奏：Flex Week前的最后新内容，语义分析连接了语法结构与实际含义，建议重点理解符号表的栈式作用域管理。🎯考试关联：属性文法的求值（给定语法树标注属性值）是期末计算题考点；类型检查规则的形式化描述可能出现在简答题中。🧪Tutorial/Lab：实现符号表的嵌套作用域查找逻辑；为课程语言添加类型检查遍历（type checking pass）。📌作业关联：Assignment 3要求实现语义分析阶段，符号表和类型检查是核心交付物。⚠️易错点：嵌套作用域中内层变量遮蔽外层同名变量的处理；综合属性与继承属性的求值顺序搞错导致属性值未定义。

7. 7

   中间代码生成

   📖核心知识点：中间表示（IR）的设计选择——三地址码（Three-Address Code）、静态单赋值（SSA）形式；三地址码指令类型——赋值、二元运算、一元运算、条件跳转、无条件跳转、函数调用；表达式的三地址码翻译——临时变量分配策略；控制流语句的翻译——if-else、while、for的跳转目标回填（Backpatching）技术。⏰本周节奏：中间代码生成是从前端到后端的桥梁，重点掌握表达式和控制流的翻译模式，建议对每种语句类型都手写翻译示例。🎯考试关联：给定源代码翻译为三地址码是期末常考题；Backpatching的过程描述可能出现在简答题中。🧪Tutorial/Lab：为课程语言的表达式和控制流语句实现三地址码生成器；处理短路求值（Short-circuit Evaluation）的跳转逻辑。📌作业关联：Assignment 3/4的代码生成模块直接依赖本周的三地址码翻译技术。⚠️易错点：短路求值的跳转目标搞错——&&的假出口vs||的真出口；Backpatching时遗漏需要回填的跳转指令。

8. 8

   运行时环境与代码生成

   📖核心知识点：运行时内存布局——代码区、静态数据区、堆（Heap）、栈（Stack）；活动记录（Activation Record/Stack Frame）结构——返回地址、动态链、静态链、局部变量、参数；函数调用约定——调用者保存vs被调用者保存寄存器；目标代码生成——从三地址码到汇编指令的映射；寄存器分配的基本策略。⏰本周节奏：运行时环境连接了编译器和操作系统知识，活动记录的详细结构是本周重点，建议画出函数调用链的栈帧变化图。🎯考试关联：活动记录结构和函数调用时栈帧变化是期末画图题/简答题考点；嵌套函数的静态链访问是高频考点。🧪Tutorial/Lab：手动追踪递归函数调用的栈帧创建与销毁过程；实现简单的栈式目标代码生成器。📌作业关联：Assignment最终阶段的代码生成需要正确管理活动记录和参数传递。⚠️易错点：静态链与动态链的混淆——静态链追踪词法作用域，动态链追踪调用顺序；尾递归优化的适用条件判断。

9. 9

   代码优化

   📖核心知识点：代码优化的层次——局部优化（基本块内）、全局优化（函数内跨基本块）、过程间优化；基本块与控制流图（CFG）的构造；局部优化技术——常量折叠、常量传播、死代码消除、公共子表达式消除；数据流分析框架——到达定义（Reaching Definitions）、活跃变量分析（Live Variable Analysis）；循环优化——循环不变量外提、强度削弱。⏰本周节奏：优化是编译器后端的精华，重点掌握数据流分析的不动点迭代思想，建议手动做2-3个到达定义分析的完整示例。🎯考试关联：数据流分析的手动执行过程（标注每个基本块的IN/OUT集合）是期末计算题考点。🧪Tutorial/Lab：构造给定程序的基本块和CFG；手动执行到达定义分析和活跃变量分析的不动点迭代。📌作业关联：如果Assignment包含优化阶段，数据流分析是实现基础。⚠️易错点：数据流分析的方向搞错——到达定义是前向分析，活跃变量是后向分析；不动点迭代的初始值设置（全集vs空集取决于分析类型）。

10. 10

    高级主题与全课总结

    📖核心知识点：寄存器分配——图着色算法的基本思想（干涉图构造→K-着色→溢出处理）；垃圾回收（GC）机制概览——标记-清除、引用计数、分代收集；JIT编译与解释器优化（选修扩展）；全课知识图谱回顾——源代码→词法分析→语法分析→语义分析→中间代码→优化→目标代码的完整编译流水线串联。⏰本周节奏：最后一周以整合复习为主，建议绘制编译器全流程图，标注每个阶段的输入、输出、关键算法和数据结构。🎯考试关联：期末综合题可能要求给定源代码，追踪其通过编译器各阶段的变换过程；图着色寄存器分配的原理是简答题考点。🧪Tutorial/Lab：完成课程编译器项目的最终集成测试；做全课综合模拟题。📌作业关联：所有Assignment截止前的最终检查——确保Scanner、Parser、语义分析、代码生成各模块正确集成。⚠️易错点：复习时只记算法步骤不理解设计动机；图着色中溢出节点的选择策略（通常选度数最大或使用频率最低的）。