Notes@Tsukino

课程总结

16分钟阅读

编译原理与设计 课程总结

  • 授课教师：冯凯宇
  • 学分：4
  • 平台：乐学（作业/测验）、CC平台（实验）、i北理/钉钉（通知/课件）
  • 成绩构成：期末70% + 实验20% + 作业/出勤10%

复习优先

考试/复习重点

  • 考试时间：7月3日
  • 卷面70分：10选择(1分) + 10填空(2分) + 4大题(10分)
  • 总成绩：卷面 + 实验20 + 平时10；卷面过30分（实验满分前提下）= 总60分
  • 不考范围：运行环境、代码生成、YACC、LEX自动生成
  • 代码优化大题不考（代码外提/强度削弱/归纳变量删除有小题）
  • 大题分布（往年惯例70分）：每章对应一大题
  • 概念类题目多为填空题
  • ⚠️ 环环相扣，前步错后步全错（语法分析/LR分析）
  • PPT是复习核心，理解不要死记硬背

作业

  • CG平台实验（有查重检测），抄袭0分无法申诉
  • 乐学平台有在线作业/测验，注意截止时间非统一23:59
  • CC平台有实验（第7周发布，共80+天）
  • 实验必须自己写，不要网上下载改改
  • 实验无官方答案，只能自己做
  • 实验助教信息后续发布到群
  • ⚠️ 第一次作业常见错误：NFA转换序列写状态序列而非状态集合序列

考勤/签到/小测

  • 无明确签到记录
  • 出勤占10%成绩构成

其他

  • 所有计分系统自动完成，教师不干预
  • 截止日期全校统一，无法延期
  • 课件PPT在钉钉群共享
  • 第10周白噪音空堂，无教学内容

课程索引

课次笔记视频点名作业考试概述
第1周 星期二 第2大节notes/第1周_星期二_第2大节.mdscreen_编译原理与设计_第1周_星期二_第2大节.mp4”有”课程导论+编译器全景+成绩规则+难度警告
第2周 星期二 第2大节notes/第2周_星期二_第2大节.mdscreen_编译原理与设计_第2周_星期二_第2大节.mp4”””正规式定义+DFA/NFA五元组+ε-闭包
第3周 星期二 第2大节notes/第3周_星期二_第2大节.mdscreen_编译原理与设计_第3周_星期二_第2大节.mp4”有”NFA→DFA确定化+DFA最小化+正规式⇔FA等价+词法分析器实现
第4周 星期二 第2大节notes/第4周_星期二_第2大节.mdscreen_编译原理与设计_第4周_星期二_第2大节.mp4”””词法分析器实现（表驱动/程序中心）+语法分析入门（文法四元组/推导/二义性）
第5周 星期二 第2大节notes/第5周_星期二_第2大节.mdscreen_编译原理与设计_第5周_星期二_第2大节.mp4””有二义性消除+Chomsky分类+左递归消除+FIRST集
第6周 星期二 第2大节notes/第6周_星期二_第2大节.mdscreen_编译原理与设计_第6周_星期二_第2大节.mp4”””LL(1)完整流程：FIRST/FOLLOW/分析表/递归下降+短语/句柄
第7周 星期二 第2大节notes/第7周_星期二_第2大节.mdscreen_编译原理与设计_第7周_星期二_第2大节.mp4”有”LR分析入门：短语/句柄/活前缀/LR(0)项目+实验通知
第8周 星期二 第2大节notes/第8周_星期二_第2大节.mdscreen_编译原理与设计_第8周_星期二_第2大节.mp4”””LR(0)→SLR(1)→LR(1)递进+句柄精细化理解+冲突解决
第9周 星期二 第2大节notes/第9周_星期二_第2大节.mdscreen_编译原理与设计_第9周_星期二_第2大节.mp4”””LALR(1)+四种LR方法对比+二义性文法+错误处理+YACC
第10周 星期二 第2大节notes/第10周_星期二_第2大节.mdscreen_编译原理与设计_第10周_星期二_第2大节.mp4”””白噪音空堂，无教学内容
第11周 星期二 第2大节notes/第11周_星期二_第2大节.mdscreen_编译原理与设计_第11周_星期二_第2大节.mp4”有”语义分析+语法制导翻译+属性文法+中间语言+符号表+语句翻译
第12周 星期二 第2大节notes/第12周_星期二_第2大节.mdscreen_编译原理与设计_第12周_星期二_第2大节.mp4”””语句翻译（拉链反填/if/while/for/switch/数组/函数）+运行环境
第13周 星期二 第2大节notes/第13周_星期二_第2大节.mdscreen_编译原理与设计_第13周_星期二_第2大节.mp4”””运行环境收尾+代码优化：基本块/控制流图/DAG构造
第14周 星期二 第2大节notes/第14周_星期二_第2大节.mdscreen_编译原理与设计_第14周_星期二_第2大节.mp4””有循环优化核心：必经节点集/回边/循环查找+数据流分析入门
第15周 星期二 第2大节notes/第15周_星期二_第2大节.mdscreen_编译原理与设计_第15周_星期二_第2大节.mp4”有有数据流方程+循环优化（代码外提/强度削弱/归纳变量删除）+作业题讲解
第16周 星期二 第2大节notes/第16周_星期二_第2大节.mdscreen_编译原理与设计_第16周_星期二_第2大节.mp4”有有期末总复习：全课程各章串讲+考试信息

课程内容

第1周 星期二 第2大节

  • 01:03 课程介绍（教师/学分/平台）；05:07 成绩构成（70+20+10）；07:07 课程难度警告
  • 17:38 PL发展史（机器→汇编→高级）；31:50 语言分类（命令式/声明式、静态/动态、强/弱类型）
  • 59:56 编译器定义和分类；01:22:05 七阶段架构；01:27:23 词法分析入门
  • 02:09:00 字母表/字符串基础概念

概括：第一堂导论课。讲清课程安排、成绩构成（期末70%+实验20%+出勤10%）、难度警告。内容覆盖编译器全景、PL史、编译vs解释、七阶段架构。

第2周 星期二 第2大节

  • 04:23 字符串集合运算（乘积/方幂/闭包）；23:21 正规式递归定义
  • 40:15 有符号整数/浮点数正规式设计；51:00 简化C词法正规式
  • 58:28 有限自动机模型；01:01:49 DFA五元组及三种表示
  • 01:34:27 NFA引入；02:00:52 ∀NFA→DFA定理；02:06:47 ε-闭包

概括：词法分析理论核心。正规式定义和代数性质、DFA/NFA五元组、ε-闭包和IA计算。打好子集构造法基础。

第3周 星期二 第2大节

  • 16:06 NFA→DFA子集构造法；30:31 DFA最小化动机
  • 36:00不可达状态检测+划分法合并等价状态
  • 01:21:14 正规式↔FA等价（双向）；01:41:06 RE→NFA→DFA→最小化DFA全流程
  • 01:55:51 词法分析器实现设计

概括：密度最高一节。子集构造法（NFA确定化）、划分法（DFA最小化）、正规式↔FA等价证明、词法分析器实现。⚠️ NFA→DFA嵌入大题，前错全错。

第4周 星期二 第2大节

  • 09:27 表驱动法实现；25:21 程序中心法；31:11 LEX/flex原理
  • 38:00 最长匹配规则；56:24 语法分析过渡
  • 01:01:51 文法四元组；01:27:51 推导序列；01:34:13 最左/最右推导
  • 01:50:09 递归文法；02:15:57 语法树和二义性定义

概括：词法分析实现收尾+语法分析入门。LEX/yacc不考，最长匹配规则重要。开始语法分析：文法四元组、推导、递归文法、二义性。

第5周 星期二 第2大节

  • 21:10 运算符优先级消除二义性；25:05 Chomsky文法分类
  • 39:50 文法↔语言互相设计练习
  • 01:02:11 自上而下vs自下而上；01:27:50 消除左递归（直接+间接）
  • 02:03:57 FIRST集定义和计算

概括：二义性消除（无形式化算法）、Chomsky四分类、左递归消除（直接公式+间接算法）、FIRST集。⚠️ 二义性消除、根据语言设计文法常考，FIRST集必须掌握。

第6周 星期二 第2大节

  • 12:19 FIRST集计算；33:49 提取左公因子
  • 36:25 LL(1)定义和结构；41:05 分析算法；44:23 I+I*I完整走表
  • 58:38 分析表构造（仅FIRST）；01:06:28 FOLLOW集
  • 01:25:15 LL(1)表构造（FIRST+FOLLOW）；01:43:38 悬挂else
  • 01:57:03 递归下降分析；02:17:50 短语/直接短语/句柄

概括：LL(1)完整流程（消除左递归→提取公因子→FIRST/FOLLOW→分析表→递归下降）。⚠️ LL(1)分析表构造核心必考，FIRST/FOLLOW计算错则全表错。

第7周 星期二 第2大节

  • 00:54 实验通知（CC平台第一次实验发布）
  • 09:17 自下而上概念：短语/直接短语/句柄
  • 50:55 LR分析结构：ACTION+GOTO+状态栈+符号栈
  • 57:38 移进/规约/接受/出错操作
  • 01:23:29 LR(0)项目和活前缀；01:43:06 四种项目分类
  • 01:48:31 项目集规范族

概括：LR分析入门。自下而上核心概念、LR分析器结构、LR(0)项目四分类。⚠️ 句柄=最左直接短语。

第8周 星期二 第2大节

  • 12:11 句柄需指定所属句型（经典学生疑问）
  • 28:00 项目集规范族直接构造法
  • 34:51 LR(0)表构造算法；38:52 5状态填表示例
  • 54:18 冲突（移进-规约/规约-规约）
  • 59:47 SLR(1)解决冲突；01:30:20 LR(1)项目引入搜索符
  • 01:57:40 LR(1)项目集规范族构造

概括：LR(0)→SLR(1)→LR(1)递进对比。SLR(1)用FOLLOW解决冲突，LR(1)引入搜索符精确控制。⚠️ 句柄精细化理解很重要。

第9周 星期二 第2大节

  • 05:40 LR(1) 14状态完整填表
  • 35:00 四种方法选择流程；50:54 LALR(1)同心项目集合并
  • 01:11:01 综合例题判断文法类型
  • 01:30:00 二义性文法；01:49:52 错误处理
  • 02:12:05 语法分析总结+YACC

概括：语法分析收尾。四种LR方法完整对比、LALR(1)合并、二义性文法、错误处理。⚠️ YACC不考。

第10周 星期二 第2大节

白噪音空堂，无实际教学内容。

第11周 星期二 第2大节

  • 00:53 实验通知（西晋平台两个实验、乐学作业截止提醒）
  • 23:55 语法制导翻译；33:54 综合/继承属性
  • 56:35 中间语言（逆波兰式/三元式/四元式）
  • 01:08:28 中缀→后缀算法；01:32:22 符号表
  • 01:57:39 语句翻译（说明类/赋值/控制流/拉链反填）

概括：语义分析和中间代码生成。语法制导翻译、属性文法、中间语言。⚠️ 复合类型文法可能考，中缀转后缀考试常见，实验必须自己写。

第12周 星期二 第2大节

  • 14:56 拉链反填详细演示；16:56 if/if-else/while翻译
  • 20:52 条件短路；31:19 for循环；43:51 switch-case
  • 57:29 数组（符号表/内情向量表/地址计算）
  • 01:24:49 函数翻译；01:41:00 运行环境（存储分配/AR/SL/DL）

概括：语句翻译深入（拉链反填/if/while/for/switch/数组/函数）+运行环境。⚠️ 还剩3-4次课，目标代码生成和运行环境不考。

第13周 星期二 第2大节

  • 02:13 Display表；07:52 堆分配
  • 10:47 代码优化定义和原则；22:17 常见优化技术
  • 53:59 基本块定义和划分；01:10:55 控制流图
  • 01:26:24 DAG构造算法及示例

概括：运行环境收尾+代码优化全面展开。⚠️ 基本块/控制流图考试常见，DAG构造往年易错。

第14周 星期二 第2大节

  • 33:50 循环定义（强连通+唯一入口）；43:14 必经节点定义和迭代算法
  • 01:05:14 回边定义和查找；01:09:57 循环查找栈算法
  • 01:50:37 到达定值；01:55:48 UD链/DU链
  • 02:06:56 活跃变量

概括：循环优化核心+数据流分析入门。必经节点集→回边→循环查找三步。⚠️ 基本块画错全题错。

第15周 星期二 第2大节

  • 03:07 ⚠️ 7月3日考试
  • 08:56 数据流方程 out=(in-kill)∪gen；25:21 可用表达式
  • 35:31 代码外提/强度削弱/归纳变量删除
  • 42:57 不变运算查找算法；59:50 外提两个大条件
  • 02:00:15 作业题讲解（考试重要参考）

概括：数据流方程+循环优化算法详解+作业题讲解。⚠️ 7月3日考试，代码生成不考，作业题讲解是考试重要参考。

第16周 星期二 第2大节

  • 01:22 考试题型（10选择+10填空+4大题=70分）
  • 02:36-02:10:45 全课程各章总复习串讲
  • 02:10:40 运行环境不考
  • 02:22:05 PPT是复习核心，理解不要死记硬背

概括：期末总复习课。全课程各章串讲+考试信息。⚠️ PPT是复习核心，不考范围：运行环境/代码生成/YACC/LEX。

关系图谱