虽然已经上过编译原理课程, 并且也实现了一个支持C语言的子集的编译器, 但是实验总体过程还是比较混沌的, 而且比较重要的翻译策略基本都是按照实验讲义来的, 对于编译器到底该怎么实现, 还是没有一个十分清醒的认识. 所以我觉得再了解几种编译器实现是比较有必要的.

不过, 相比于直接去看工业级产品的源代码, 我觉得暂时还是从一些简单的, 玩票的实现开始入手比较好. 从 这里 发现《自制编程语言》似乎还不错的样子, 两个语言实现, 一个是树遍历解释器, 一个是字节码虚拟机. 在学校里的实验最终是直接生成汇编代码的, 虽然树遍历解释器看起来比较low的样子, 但是没有碰过的东西还是值得一试的, 便入手了一本. 准备是在寒假(2016-01-17至2016-02-21)将其大致通读一番.

虽然说是阅读笔记, 但是实际上大部分内容估计会是关于语言实现和编程方面的记录和小结.

我在正式放假前大致翻阅了一下, 从第一个语言 crowbar 词法分析部分的讲解看来, 大概是直接说明代码片段的, 完整的代码自行下载, 而不是像实验讲义那样引导性地给出策略. 颇有些懊恼, 因为读了源代码就要被牵着鼻子走了, 不读源代码自己干的话, 这本书的价值就只剩几页语法说明了. 不过在课程实验里编译器时就感受到了, 我对复杂软件设计的驾驭能力还是很不足的, 我的编译器 的模块设计就跟 shit 一样, 向别人学习也是应该的, 就像 Ruby on Rails 的教条里提到的那样, 尝尝”店长推荐(omakase)”. 另外根据 R大这篇文章 的指导意见, 我决定不光要阅读代码, 还要把代码重头拷贝一遍. 虽说不算原创性的工作了, 但是对于加深理解, 提高练度应该还是有所裨益的.

2016-01-23

将前面计算器的实现抄了一遍, 并且发现了个别小 bug, 不少时间花在折腾 Makefile 上了 XD.

正式开干 crowbar, 上来直接日了狗了, CRB_Interpreter 模块基本只是简单介绍了下几个重要的数据结构, flex 和 bison 的文件简单跳过倒是可以理解, 不过缺少思路还是非常影响阅读. 看来边看一节码一段代码的方法有些吃力. 目前将 crowbar.l 和 crowbar.y 中与 crowbar 实现相关的内容跳过, 把词法分析和语法分析先单独码出来. 就跟实验一开始写好 bison 代码一样, 只能用来判断语法是不是合法.

本想迭代式地开发(抄), 不过目前看来还是得自顶向下地分析了.

2016-01-24

实现了 MEM 模块里最基本的部分, 结果还因为做单元测试发现了自己的一个 BUG…..

MEM 模块里MEM_malloc, MEM_realloc, MEM_free等函数实际上是对应的函数名加上后缀_func的宏, 设置了默认的参数, 主要是为了使用__FILE__和__LINE__记录调用处信息.

MEM_controller_tag在最基本的内存块结构之上, 存储了错误处理的相关内容.

memory.c 中的Align的作用是使Header占用的空间是8字节的倍数(64 位机器且 double 为 64 位), 且一定比HeaderStruct要多, 暂时无法理解为什么要这么做, 因为删掉这部分代码似乎也能正常编译执行的样子. 而且查看整个 MEM_malloc 在 DEBUG 模式下分配的数据, 在 64 位的机器上, 加不加 Align 都是一样的, 不过还没有在 32 位机器上测试.

MEM_create_controller最后将全局块链表头赋值给了新建的块链表头. 这样相当于有两个插入锚点了. 只看头部插入的没什么问题, 但是如何界定一个MEM_Controller负责的链表的尾部呢? 不过目前没有连续 free 的需求, 针对一个分配空间的 free, 只需要利用双向链表自删除就行了.

rechain_block用于 MEM_realloc, realloc 虽然能保证原来的数据是保留的, 但是不能保证还是原来的指针, 而这个指针值被存储在了前驱的 next 和后继的 prev 域上, 所以需要重新链接, 不过作者在实现中使用了栈上的结构体保存将要被 realloc 的头部, realloc 完成后再赋值过去. 但是由于 realloc 后原来的头部数据保留的, 所以我觉得没必要做这一个备份.

2016-02-01

总结一下对于 MEM 模块代码的理解. MEM 模块的目的在于检查动态分配空间的正确性. 一块动态分配空间正确性, 即分配区域两端不被修改, 这样便需要保存空间大小以及额外的两片区域用来填充标记. 此外, 出了错时要能知道这个动态空间是在源代码的何处申请的, 所以要记录文件名和行号. 最后, 为了能够进行批量检查, 需要访问所有被分配的空间, 所以各个分配空间需要被串成一个链表, 通过 controller 来访问这个链表进行批量检查.

今天实现了 Storage 模块和 DBG 模块. Storage 模块相当于一个内存池. 即空间申请发生时, 自己会额外多申请一些, 之后的申请如果空间够用, 就直接分配出去, 减少实际向系统申请空间的次数. 不过 C runtime 的 malloc 大抵是有内存池的, 在其基础之上额外增加内存池, 反而对减少系统调用这一点没有帮助. 但确实如书中所说, 在解释器中, 经常会出现内存一点一点申请并且在一个阶段后前面申请的所有内存都可以保证不需要了. 统一回收, 可能是 Storage 模块有实际意义的地方.

Storage 模块将内存划分为页(page), 而页又划分为块(cell), 页以链表的形式串联起来. 内存分配总是在页内进行的, 如果页内剩余 cell 数量不及需要的数量, 则会插入一个新页, 使用统一的页大小和申请空间大小中较大的那个以保证分配. 这样的话, 如果频繁地大块和小块交替申请, 则会有大量的页空间被浪费.

DBG 模块没有什么特别的数据结构, 所以理解难度比较低. DBG 模块具有一些基本的高级调试工具, 比如打印日志所需的文件名, 行号, 格式字符串等. 根据优先级打印日志这一点是我以前所没有想到的, 感觉是个减少冗余日志的好办法. 不过文件名, 行号, 断言表达式这些, 都使用全局变量记录, 在实际的 assert 或者 panic 前, 都要调用函数去设置这些全局变量, 我觉得没有必要, 直接传参数就好了. 此外, 从宏传可变参数, 在 gcc 下可以使用 __VA_ARGS__, 可空可变参数使用 , ## __VA_ARGS__ 来消除多余的逗号.

支援设施终于看完了, 之后可以专心看跟语言实现有关的部分了, exciting!

2016-02-03

这几天断断续续地把前端基本码完了. 先是实现没有没有额外功能代码的 flex 和 bison 文件, 这样就可以测试输入文件合不合乎词法和文法了.

之后开始添加语法树结点的各种构造函数, 这里纯粹是体力活, 有大量的重复代码, 不过这里就体现了 vim 文本编辑的强大了, 各种 copy 和录制宏. 做学校编译原理实验时, 我为了这部分节省精力, 直接用兄弟子女树构造成 parsing tree, 后来费了很大的力气才把它修正到 ast 上, 但是依然是兄弟子女树, 所以每个语句结点可以使用同一个构造函数. 当然这对分析造成了很大的不方便.

构造语法树这部分代码, 主要依赖于 create.c, string.c, util.c 这三个文件提供的函数. util.c 为前者提供了一些基础的工具, 主要是解释器指针的 getter, setter, 以及封装好存储器使用的 crb_malloc. 最后要将前端跑起来还需要实现 interface.c 中的函数, 这部分函数如文件名所述, 是面向用户的接口, 其声明也要放到 CRB.h 中. 从解释器的构造函数来看, 解释器自己也被放置在了存储器中, 并拥有了这个存储器, 根据 crb_malloc, 这个存储器主要存储语法树结点. 不过现在看来只有执行彻底结束时才能释放这个存储器. 树遍历解释器肯定要把树一直留着的, 想着分析完了就销毁那是代码生成的思路……

话说最后与到了一个苦笑不得的问题. 测试时无论怎么输入, 随便一个 token 都能处罚语法错误. 这时候自然要检查yylex的返回值. 在 flex 文件中, 输出 return 之前的枚举值, 同时在 y.tab.c 中调用yylex的地方输出返回值. 结果发现 flex 文件中枚举值是正常的, 但 y.tab.c 中就变成了一个非常小的数字. 这个数字虽然小, 但是随着枚举值的增大而增大. 当时不知道什么原因, 只能用类似二分法的方法排查是那一部分新增的代码导致了这个问题. 最终我发现是yylex的声明写错了: char yylex(void). 为了和 ascii 区分, 符号的枚举值自然是大于 255 的, 这样就会溢出到一个比较小的数值. 虽然我也不知道我为什么要没事找事声明yylex……

2016-02-08

这几天完成了语句的遍历函数和部分表达式求值的函数，以及采用引用计数的字符串垃圾回收模块。

解释器的树遍历策略与编译器做语义分析时的遍历行为还是很像的。不过由于没有类型，而且没有引入数组，结构体和数组这两个分析时的难点都得以回避。整体来说树遍历执行这部分感觉上比较熟悉而且实现也颇套路化，给我留下特别印象的有两个地方：

  1. elsif 链表
  2. break、continue、return对执行流的影响

elsif 链表是脱离通用 Statement 类型的存在。虽然作者在书中说else if是独立的语法单元，但是在学校实现的类 C 编译器里，else if (...) { ... }确实就是省略了花括号的else { if (...) { ... } }，以至于可以产生else for、else while、else do等新奇的写法。所以这里不能像处理if语句那样通用地处理分支，让我有些不爽。解析语句的函数的签名都十分冗长，但是可以用宏统一处理，可是elsif链表就不行了。我觉得比较好的做法是直接将if语句结点链表化，一个结点包含条件和语句块。当前结点条件不成立，自动前往下一个结点进行判断。如果条件为空而语句块不为空，那么是else结点，否则就是没有else，这样就能够统一处理了。

break、continue我暂时没有在编译器中尝试实现，因为似乎要记录额外的标签信息。但是这里已经让我感受到了实现这些中断结构需要注意的地方。中断执行流的实现思路就是对每个语句做标记，在语句链表的遍历执行过程中，检查执行的语句类型，对影响控制流的语句进行特殊处理。return、break 和 continue 的差异主要的语句中体现。循环语句自身有一个需要遍历的语句链表。如果内部遇到了 return，那么就要一直向上返回到顶层，推出函数体。而如果遇到了 break，那么这个循环也不能执行了，但是不会影响到与这个循环同级的语句的执行，所以推出前要修改类型。而 continue 则中断了链表的遍历，循环行为本身不受影响。

此外，在实现有垃圾回收的字符串变量管理上，有一个无奈的地方。那就是为了实现动态的销毁，不能使用存储器，即内存页的管理方式。内存页总是分配超过需求的空间，不能通过申请对象来释放空间，而只能通过销毁存储器来统一释放。为了动态释放，字符串脱离了存储器而直接申请内存，总觉得有些破坏设计的一致性。

另外，在实现时，为了更好地模块化，我本想让每个 c 文件对应一个头文件，这样 corwbar.h 也不必那么冗长。但是实际操作过程中我发现，模块间的交叉引用过多，一不小心甚至能造成头文件的循环引用。最后还是将所有的声明塞到 crowbar.h 中（好像 windows.h），这样各个模块依赖简单，想要的很容易满足。

2016-02-13

今天完成了字符串运算、取负和逻辑与/或的处理。字符串的运算，包含加法和比较运算。加法运算就是将两个字符串串接，返回一个新的字符串变量，对于非字符串变量，则格式化，并构造一个新的字符串用于进行加法运算。比较运算只要利用strcmp的返回值即可。值得注意的是，字符串变量是值引用，每使用一次就要释放一次。有些场合不一定是字符串类型，比如判断是不是 null，也要考察类型然后进行释放。

与和或的逻辑放到一个函数里处理，结果我发现短路求值之后，无论是与表达式还是或表达式，都跟右边的操作数的真值是一致的，这一点以前一直没注意到。

2016-02-14

今天完成了函数调用的执行。源码定义的函数调用比较简单，内置函数倒是要添加一系列代码。我一开始还担心格式化输出如何传递可变参数，后来发现完全是多虑了。因为格式化是通过字符串的加法运算实现的（如果只有非字符串类型，内部还会进行一次格式化），所以print函数本质上只会有一个参数。

执行测试用例时发生了一些bug，主要是 tagged union 的 tag 没有标对；还遇到一个段错误，表达式求值的表达式为空，错误地点在 for 循环语句的循环条件判断。源代码中出错的位置是for(;;)，即条件为空，我实现时没有判断条件为空的情况，而作者的源码中是有的，真是照抄都抄不对。