Compiler

编译器 分析部分（前端）+ 综合部分（后端） 趟（Pass）：每趟读入一个输入文件，产生一个输出文件 字符流 (词法分析器) 符号流 词法分析/扫描 (Lexical analysis/scanning)：读入字符流，输出词素（Lexeme）<token name, attribute value 符号流 (语法分析) 语法树 语法分析/解析 (Syntax...

词法分析器的作用 读入字符流，组成词素，输出词法单元 过滤空白、换行、制表符、注释 将词素添加到符号表 逻辑上独立于语法分析，但通常和语法分析处于同一趟 独立词法分析 简化设计 提高编译器效率 增强编译器的可移植性 概念 词法单元 Token：<单元名，属性 模式 Pattern：描述了一类 Token 可能具有的形式 词素 Lexeme：源程序中的字符序列...

上下文无关文法 语法描述 上下文无关文法 CFG BNF 上下文无关文法 终结符号 非终结符号 开始符号 产生式 推导：$A\rightarrow\gamma$，则 $\alpha A\beta\Rightarrow \alpha\gamma\beta$ 最左推导：$\alpha$ 中不包含非终结符 $\overset{ }{\Rightarrow} {\t...

属性规则 语义描述 上下文相关文法：过于复杂 属性文法：上下文无关文法和属性规则的结合 综合属性(SA)：通过 $N$ 的子结点或 $N$ 本身的属性值定义 继承属性(IA)：依赖于父节点，本身和兄弟结点的属性值 终结符号无继承属性 语义规则的副作用：影响其它属性的求值 SDD 语法制导定义(SDD)：将文法符号和某些属性关联，通过语义规则来描述如何计算属性...

三地址代码 指令集合 运算/赋值：x=y op z, x=op z 复制：x=y 无条件转移指令：goto L 条件转移指令：if x goto L, if False x goto L 条件转移指令：if x relop y goto L 过程调用/返回：param $x i$, call p,n 带下标的复制：x=y[i], x[i]=y 地址/指针赋值...

控制栈 实在参数 返回值 控制链 访问链 保存的机器状态 局部数据 临时变量 垃圾回收 基于引用计数的垃圾回收（存在循环垃圾） 基于跟踪的垃圾回收 标记 清扫式垃圾回收 标记并压缩垃圾回收 拷贝垃圾回收

目标语言 代码生成器的任务 指令选择 寄存器分配和指派 指令排序 地址 静态分配 call callee return name 栈式分配 call callee return 基本块与流图 确定 leader 第一个三地址指令 任一个跳转指令 任一个跳转目标指令 活跃性 开始时非临时变量活跃 反向扫描 i: x = y + z x: 不活跃（之前的值不使用...

优化 公共子表达式消除 复制传播 死代码消除 常量折叠 数据流分析