1、编译器构造课程计划 上课次数：次左右 截止日期：月日前后 评分政策：基础分 代码提交： 期末答辩： 助教 陈乐群、游宇榕、徐晓骏、徐世超、谢天成、李慧琛 通过 帮助大家解决问题 网站 分组 论坛 日程表 数据 语法说明 评分细则参考书籍 自制编译器自制编译器青木峰郎青木峰郎 虎书虎书现代编译程序实现现代编译程序实现 程序设计语言程序设计语言实践之路实践之路 编程语言实现模式编程语言实现模式 . . 编译器设计编译器设计 . . 编译器的各个阶段词法分析源代码语法分析词素（）流语义分析抽象语法树（）活性分析寄存器分配代码生成中间代码目标代码语言的精神 信任程序员 不要阻止程序员去做需要的事 保持
2、语言的小巧和简单 为效率可以牺牲可移植性 , 只要能让程序员干的活编译器一律不管语言的精神（里番）为什么这么设计 先申明再使用 不能向后看 信任程序员 优化神马的做不到呀现代语言的一些特性 垃圾收集 面向对象 隐式指针 原生 一种语言包打天下的时代已经过去了：假设所有的编译器都坏了，而且所有的源代码都不见了，但电脑都能工作，我们需要多少时间来重建编译器？（这个问题轮子哥在知乎上的回答是错误的）造轮子的时候能不能用轮子？自展 源语言源语言编译器语言编译器语言目标语言目标语言组汇编机器语言机器语言组汇编汇编组组“用语言来写一个语言的编译器” 假设 ; 假设 如果内存泄漏一次扣一分的话，全班的分数还
3、不够给一个人扣的 假设 已经过时了 假设 抄袭太容易了 结论 （不强迫） 新的语言，代号 * 交错数组 谈论一些和分数有关的小事分数结构 客观分：分 主观分：分分 客观分中： “低保”：分 “天梯”：分“低保” 数据公开，由助教给出 编译时间和运行时间合理即可 合理稍作优化 扣分： 晚交：第一天扣分，第二天扣分，第三天扣分 超时：天梯 每个学生必须贡献一个数据，这个数据会以该同学的名字命名并公开，而且会流传到下一届 这个数据必须符合规范，不涉及任何未定义的内容 目标 卡其他人的编译时间和运行时间 让自己编译时间和运行时间尽量短 双原则: 自己的编译时间 自己的运行时间天梯排名的计算依据天梯排名
4、活动结束之后获得的分数 第一名：分 第二名：分 第三名：分 第四名、第五名：分 第六名、第七名：分 第八名第十名：分 第十一名第十五名：分 第十六名第二十名：分 之后：分约定 所有测试程序都需要公开 测试程序公开截止日期：月日 如果认为数据不合适，会联系修改 排名开始日： 月日 排名结束日最晚提交截止日 会每天公布每人的分数明细，但不公布运行时间 最后一天的排名是有用，前几天都只作为参考 所有编译器的源代码在排名结束之后，也必须公开测试数据参数 编译时间 运行时间 源文件大小 目标文件运行时大小); ( ) ;（词素） 保留字 运算符，分隔符（如;） 标识符() 常数(, ) ，和需要更多信息
5、 和 用于编译器报错定位 , ; ; ; () () 空格 (); () ; () , : (); ; : (); () 运算符 (); ; ; . : (); . : (); ” : (); : 异常 () (); () 字母,数字,下划线 (); ( 关键字) 用会更自然一点其他要点 单行注释 大嘴法 假设源代码中反复出现一段字符串常量 是否需要压缩 ？ 最高效： 最优雅：() 最方便：不理他语法分析 非终结符小写 终结符，大写 * 推倒推导() * * 语法分析树语法语句 () () ; ; ; () (; ; ) 语法表达式 左：符合阅读习惯，但不能表示优先级 下：能表示优先级，但不能
6、表示结合性 .语法表达式 “”() , , 和 语法类和函数声明 ; ; () () , 语法 ; ;语法 细节 避免左递归 () () 是否允许一个和为空？ 语法可参考 (很老的资料在这里) 一下的抽象语法树 ( (), (, ), (, )抽象语法树 词法分析去除了一部分冗余 换行，空白，注释 但还有一部分冗余存在 各种关键字、分隔符 去除所有冗余之后，用树来表示程序的数据结构成为抽象语法树 具体语法树？就是哪些冗余还在 抽象语法树（）是个很重要的东西 承上启下，前端的最终产物，后端的开始 是研究设计方法论的非常好的一个实例（ ）任务一：设计，分清继承关系 基类： 子类 表示一条语句 表示
7、一条表达式 表示一条申明ProgDecFuncDecClassDecVarDecStmtVarDecExpBinaryExpUnaryExpPrimaryExpIndexAccessExpFieldAccessExpStringExpIntExpIfStmtWhileStmt虚线 抽象类 变量声明语句 可以在函数中出现 是 可以在顶层出现 是如何优雅地避免泛型？ ; ; ; 组合模式 , ;继承：继承了组合：的两个成员也是组合和继承如何取舍，是设计里永恒的话题支持多继承吗？支持啊 不支持啊 需要同时继承和 法一：把和中一个变成 公共祖先必须是，就不能有这个成员了，用代替 法二：不继承，修改的代
8、码： ; ; 法三：【继承和组合】 新建一个继承， 继承，除了持有外什么都没有备查：其他没有在图上出现的 任务二：设计的方法 () 的时候，一般需要把打印出来看看有没有出错 () 检查语义是否有问题二目运算符两侧类型是否一致，函数调用时参数数量和类型是否一致等等 () 将翻译成中间代码 () 支线任务，输出排版优美的源代码方法一：内嵌式 , ; ; ( ) () “” “” () (); ; ; ( ) () (); ?.是的文法糖，意思是如果不为空，调用 , , ; ; ( ) () “” “” ( ) ( ) ( ) ( ); ; ; ( ) () (); 用于声明类的成员内嵌式的设计缺陷
9、 维护不便 每个里面都要写上各自的种方法 ：的语法有种，而有多个 我们希望最好是把写死，而不是在开发到一半的时候，经常往上加东西 实际上这些指责都有些吹毛求疵 , ; ; ( ) () () () ; ; ( ) () () () 方法二： ( , ) () “” “” (, ); ( , ) () “” “” (, ) (, ); . ( , ) 没有 , 编译器不会自动 ( ) () , ); ( ) () , ); ( ) () , ); ( ) () , ); ( ) () , ); (); (); 选择的时候仅根据的运行时型别（ ）简单的多态概念和只支持这个 不但要根据的类别，还要根
10、据的运行时类别 所有参数都考虑方法三：访问者（）模式 主要目的 () 隔离“遍历过程”和“树的定义” “使用或就很容易做到，因为支持运行时动态添加方法”， 访问者模式是用来克服或的固有缺陷的 总的来说，很多设计模式就是用来解决语言的先天问题的 （陈乐群）和只支持 是为了效率的折衷树的定义 ( ); 基类的调度方法是抽象的 , ; ; ( ) (); ( ) (); 小白：为何不把基类的方法写成具体的呢？这样子类不就可以直接继承基类的方法而不必到处重写了？ ( ) (); ; ; ( ) () “” “”); ; () 变相做到了 ; 树的遍历总结 内嵌式 直接但不优雅，参考编程语言实现模式的模
11、式 方法 参考虎书第一版（第一版，第二版）可以在 下到电子版以及原书附送的代码，看包 ，的和 访问者 号称是最复杂的设计模式，炫酷屌炸天，用起来还是有点痛苦的 究极方法是用个 来自动生成各种，比如符号表 ()三个概念 名字 变量名，函数名，类型名 类型 基础类型，数组，结构 作用域 全局，函数作用域，类作用域，局部作用域 符号表在某个作用域里，找某个名字对应的类型和其他信息 资料 ” 虎书第二版 构造的时候，为每个字符串分配一个唯一的 优势 比较比较字符串快 相同字符串只需要存储一份 ; ; ( ) ; 私有化构造函数 ( ) (); 虎书上有这句话。游宇榕指正，这句话其实可以不要 (); 陈
12、乐群进一步指出，如果要，可以用 ( ) (); (, ); 问题：说好的唯一在哪里？ 的内存地址就是唯一虎书第二版类型的好处 安全：确保运行时安全 类型推断：为每个表达式确定类型的过程 隐式转换显式转换：我们要求显示 表达力：提高表达能力 但我们不允许用户重载运算符 效率：生成更好的代码 内建类型 复合类型 数组 结构类型的组件符号类型的声明 ; ; ; 如果允许枚举类型做下标，还需要记录下标的类型; ; ; 如果有，那么每种类型还有个类型 例如 这个类型的类型其实是 () ; 求时，不要忘了路径压缩（类似于并查集）符号表的接口设计虎书版 ( , ); ( ); (); (); 是一个全局变量
13、 一个典型的表可持久化的数据结构 当执行的时候， 需要和最近一次配对，消除之间的所有操作双链表实现，虎书源代码 ; ; () (); ; () ( ) (); ( ) 如果外层作用域还存在 (, ); (); 若否，从符号表中直接删除 ; (); (); ( ) (); ; ( , ) (, (, , (); ; ; ; 连接了同层作用域的下个名字 ; 连接了上层作用域的同个名字 ( , , ) ; ; ; 记录了外层作用域的符号表是唯一的么？ 变量，函数和类型可以分不同的命名空间 的结构名和变量名可以重复 如果区分命名空间，应该有多个符号表 , 类型环境，变量环境 语言变量，类型，函数都共用
14、一个命名空间，不支持 (); 规范的写法应该是 ();可持久化红黑树 参见虎书 “函数化”编程风味更重一点 不能加分！ 不能加分！ 不能加分！符号表的接口设计版本 ( ); ( ); (); 返回外层符号表 (); (); (); (); (); (名字, 类型); (); 类型 (名字); ( ) (); ( ) ; ();类的设计 普通设计 ; ; 文艺设计 将和设计成接口 让我们来烧脑欣赏这个超变态复杂设计的实例名字名字类型类型作用域作用域内层 ( ) () 关于符号表的阅读指南 模式：没有函数，没有类，只有和 模式：有函数，没有类 模式：有函数，有结构，有成员函数 模式：支持继承处理的
15、声明 (); ( ) (); 处理声明时 (, );(); ; 离开声明时 (); 时如何处理 ; : 检查的类型和的类型是否一致 先得到的符号 (“”); (“”); (“”); 检查和的类型是否一致 总结 关于符号表，简单的写法见虎书 这是一个面向过程的符号表，简单直接高效 优雅的，真正面向对象的符号表见 比较烧脑子语义分析提纲 需要在抽象语法上走几遍 这是因为我们支持类和函数的“前向引用” 第一遍第二遍 将和先放到符号表里去 但很多东西还没办法确定，比如一个函数的返回值是一种类，这种类的声明在函数申明的后面 第三遍 解析所有类型：变量类型，返回值类型。一旦确定了变量的类型，就立即更新相关
16、符号表对象。寄存器 通用寄存器 $ $ $ $, $ $ $ $指令集的体系结构 数据移动 计算 控制转移 ( ) 特殊 用不到推荐开发编译器后端的顺序 第一步 顺序 条件 循环 第二步 函数调用 第三步 数组 字符串 结构中间表示四种中间表示的区别 汇编指令 寄存器数量有限，立即数比较小 三地址码的 寄存器数量无限， 立即数大小合理 树形虎书的，或中的低级 不需要临时寄存器，分叉灵活 作用域有四种写法有四种写法IR.JumpIR.BranchIR.SeqIR.ExpIR.ConstIR.LabelIR.TempIR.MemIR.BinaryIR.CallIR.ESeqIR.Move是，不是是
17、逗号表达式的内存模型 寄存器无限多 内存无限大 内存地址 通过获得绝对地址（只用在字符串上） 通过获得相对地址翻译 ; 测试表达式 ; 循环体 (); 测试通过，开始循环体的位置 (); 测试不通过，循环体结束的位置 () ( (), , ), (, (), ( (), );翻译 ; ; () ( (), 需要一个机制获得变量所在的位置 () );变量存在哪里？内存模型 适用（可用寄存器只有两三个） 所有变量在内存里都有一个对应位置，容易找到变量在哪里 取值和写入都需要同步到内存 适用（因为寄存器多） 变量能存在寄存器里，就不要放到内存里 缺点：个寄存器不可能分配给个变量，需要活性分析寄存器分
18、配 也有一种做法是，遇到寄存器不够用的时候就拒绝编译好架构可以做到在这两种模型上切换 ; ( ) ( ( ( , , (); (); ( ) ; 基本块构造 将重写成 构造成基本块 然后找到，按照（虎书）的要求调整基本块的顺序 消去和结点 对每个函数的结点，父亲必须形如(, () 如果是过程，无所谓 这是因为，和都难以由指令选择翻译成线性代码 . 形式上看 第一句是（方便跳进来） 最后一句是或者 基本块之间怎么排列都可以 我们需要让每个的 跟在的下一句 直接构造指令选择苟利国家生死以，岂因祸福避趋之 第二步 第一步只考虑顺序，循环和条件 第二步考虑函数调用 先调试考虑简单的调用 然后调试递归
19、第三步考虑数组字符串结构（运行时结构）活动记录 调用前 保存寄存器, 传参数 执行 进入前 保存寄存器，和 调整 离开前 恢复寄存器， 恢复 调用后 恢复寄存器区分和有意义么？ ; ( ); ( ); ( ); ( ); ( );申明变量的方法 ( ); 新开一个局部变量 表示逃逸变量 语言里没有 里有引用 里有函数层叠 逃逸的变量必须放在内存里，不逃逸的先放在抽象寄存器里，如果寄存器分配溢出，自然会放到内存里栈上分配变量 ( , ) () (, ); ; 和占用的字节不同 ; (); 的构造 ( , ) 参数超过四个需要放在栈里三个一些基本常识 每个函数是一个独立王国 永远考虑其他函数的最坏
20、情况 内存无限 基地址为$ 通过$访问内存活性分析 动机 变量的颜色表示变量的活跃区间 的活跃区间不重叠 可以分配在同一个寄存器里 每个点是一条三地址码 : 这个点所使用的变量 : 这个点所定义的变量 变量 从这条边出发存在一条路径 通向一个“中有”的点 而且路上没有“中有”的点 一个变量 结点（一行汇编） , 属于 , 属于 （从后向前推） ( )进前活跃的需要用的出时活跃的且没在里被定义过 () 计算需要向后看后继结点的计算需要向后看后继结点的朴素算法：朴素算法： 一开始和都是空集一开始和都是空集不断循环直到没有变化不断循环直到没有变化正确性：能证明有解且有唯一解正确性：能证明有解且有唯一解复杂度：复杂度：()，存在更好的算法，存在更好的算法干涉图 变量和不能分配在一个寄存器里 和之间有一条边 构建方法： 非指令： 和连边 指令： 设指令为 （也就是）和 （也就是）连边分块完成活性分析（稍微高级一点） : : 将每个块看做一个点，用 : （建图） * “”. ? .寄存器分配参考资料 不错的网站，有也有实验项目寄存器分配 图染色分配比较繁琐 有更简单的分配方法，叫做 搜索一下论文有很多学习编译器设计的收获 有的时候让程序来写程序比人来写程序更快更方便 OO Programming needs design 一些算法问题有其理论背景
