编译原理
Lec10: Liveness Analysis
为寄存器分配做准备:控制流图、定义/使用集合、活跃变量数据流方程,以及干涉图(interference graph)的构建。
约 4,423 字24 min read
共 47 篇笔记,用心写下的每一页
共 30 篇文章
为寄存器分配做准备:控制流图、定义/使用集合、活跃变量数据流方程,以及干涉图(interference graph)的构建。
把 canonical IR Tree 翻译成具体目标机器的 abstract assembly:树覆盖算法(Maximal Munch / Dynamic Programming)、指令模板与开销估计。
大学课程笔记的首页，包含了编译原理课程的相关内容。
在 AST 上做语义检查:类型系统、符号表的层级与作用域、变量声明与使用一致性,以及类型推导的基础。
把前端友好的 IR Tree 改写成对后端友好的 canonical form:消除 ESEQ、切分基本块、再用 traces 把跳转重排为顺序流,为指令选择铺路。
从 parser 走向 AST:语义动作如何在归约时构建抽象语法树、AST 节点设计、Visitor 模式与多 pass 遍历框架,以及把 parser 与 frontend 其余阶段解耦。
把 typed AST 翻译成 IR Tree:ESEQ / CJUMP / CALL 等节点的设计,以及前端友好的中间表示如何为后续优化与代码生成铺路。
编译原理课程的第三章，介绍了语法分析的基本概念、上下文无关文法以及LR(1)分析方法。语法分析器根据上下文无关文法构建解析树，检查程序的语法正确性。课程还介绍了LR(0)、SLR、LR(1)和LALR(1)等不同类型的LR分析器，以及如何处理歧义文法和错误恢复。最后，介绍了Yacc工具，用于自动生成语法分析器。
从语义合法的 typed AST 走向运行时:函数调用如何在栈上铺开、frame 与 register 如何分配、嵌套作用域与变量访问的实现。
编译原理课程的第二章，介绍了词法分析的基本概念、正则表达式以及有限自动机。词法分析器将源代码转换为 token 流，使用正则表达式描述 token 模式，并通过 NFA 和 DFA 实现。课程还介绍了 Lex 工具，用于自动生成词法分析器，以及 DFA 最小化算法，优化状态数量。
编译原理课程的第一章，介绍了编译器的基本概念、模块化设计以及常用工具。编译器是将一种语言转换为另一种语言的程序，分为多个阶段，每个阶段处理不同的抽象表示形式。课程还介绍了正则表达式和上下文无关文法，以及相应的工具Lex和Yacc，用于词法分析和语法分析。
编译原理课程的第一堂课，介绍了课程的分数构成、习题课安排以及实验目标。学生需要编写一个编译器，将源语言SysY编译成RISC-V 32汇编语言。实验报告需要详细描述实验思路，并且需要独立完成，禁止使用AI工具。
从 Model-based 走向 Model-free:用蒙特卡洛采样估计动作价值,介绍 MC Basic、Exploring Starts 与 ε-Greedy 等同策略 MC 方法。
求解 Bellman 最优方程的两条经典路径:Value Iteration 直接迭代 Bellman 算子,Policy Iteration 在策略评估与改进之间交替,并讨论二者的等价性与收敛性。
Bellman 最优方程及其压缩映射性质,Banach 不动点定理保证收敛唯一解,以及最优策略的存在性。
从回报的递推性出发推导 Bellman 方程:状态价值函数的定义、矩阵形式的封闭解,以及策略评估在 MDP 上的意义。
以方格世界为例,构建强化学习的基础数学框架:状态、动作、奖励、状态转移、策略、轨迹与回报,以及引入折扣率后的折扣回报,最终统一为马尔可夫决策过程(MDP)。
磁盘结构与调度算法(FCFS/SSTF/SCAN/C-SCAN)、磁盘管理、RAID 与 SSD,以及现代存储接口。
文件系统分层结构、磁盘上的元数据组织、目录实现、空闲空间管理、分配方法,以及效率与性能。
文件与目录的概念、访问方式、共享与保护、文件系统挂载,以及目录结构(单层/两层/树形/无环图/通用图)。
请求调页、页面置换算法(FIFO/Optimal/LRU/Clock)、帧分配策略、抖动与工作集模型。
内存管理基础、地址绑定、连续内存分配与分段、分页机制、TLB、共享与保护。
死锁的四个必要条件、资源分配图、死锁预防/避免(银行家算法)、检测与恢复。
临界区问题、Peterson 解、硬件原子指令、互斥锁、信号量、管程,以及经典同步问题(生产者-消费者/读者-写者/哲学家就餐)。
CPU 调度的基本概念、各类调度算法(FCFS/SJF/RR/优先级/多级反馈队列),以及多核与实时调度。
为什么需要线程、多线程模型、Pthreads/Java/OpenMP 等线程库,以及隐式线程与线程相关问题。
进程的概念、PCB 结构、进程状态转换、进程调度,以及进程间通信(IPC)。
操作系统能提供哪些服务、系统调用与 shell 接口、内核结构(单体/分层/微内核/模块化)。
操作系统第一章:操作系统是什么、它管理哪些资源、为什么需要它,以及本课程关注的三大 Management(进程/内存/存储)。
操作系统课程的开场:主要内容总览、实验与考试评分规则、推荐教材与参考资料。