笔记:《自制编程语言》

这本书在我这已经沉睡了快一年了。一直以自己能力不够为借口。不过这个学期开了编译原理课程,想着顺带着就把这本书看看。

现在编译原理也上了一个月了,各方面也都了解了一些,发现这本书其实跟编译原理的教科书的侧重点完全不一样,相互之间算是互补。

教科书主要教了一些算法和概念,而这本书的主要路线就是实战,两门语言,涵盖了目前的主流语言的诸多特性,都是通过实现来讲。

基于lex/yacc的语言开发在本书中所表现出来的路线是

  1. 词法分析,此处lex将一个正则表达式映射为一个语句块,可以直接在语句块里对token实现解释。
  2. 语法分析,此处直接利用上一步骤的token串,根据语法定义(同lex,此处有产生式到语句块的映射)生成相应的语法分析树。
  3. 值得注意的是上面两步中的token和语法法分析树中的非终结符似乎都是有类型的。这一块类型映射没有深究。
  4. 接下来
    • crowbar的语法树生成后就可以开始解释执行了。
    • Diskam则有语法树修正,编译为虚拟机字节码,执行等过程。

这是利用到了工具(lex/yacc)的部分,实际上,这只是整个编译工作中的一小部分 ,lex/yacc的作用其实十分有限。

现在称所设计的语言为目标语言,而实现目标语言的语言为底层语言

设计语言(的运行系统)的主要工作是设计底层语言对目标语言中各种结构(值,表达式,控制结构)的表示,以及如何将这些结构转化为底层语言的计算过程。

lex/yacc所完成的只不过是自动化的结构搭建工作。


学习 Diksam

从crowbar到Diksam,难度跨度有点大,而作者对内容的讲述却越来越简练。

不过也不能怪作者,这本书进行到Diksam,在很大程度上要靠读者自己去读源码,而我现在耐心不足,贪心有余。

昨天耐下心来,将前半本书又看了一遍,熟悉作者在Diksam部分几乎不再提的那些基础部分。

Diksam0.1

这里一切还都不难理解(吹牛了,看了半天才看懂)。

比较有难度的有

  • 派生类型:这是处理数组和函数的类型的机制,乍看一眼难倒我了。
  • 函数调用机制:这一部分感觉作者说了几次都没有说透。

这一部分的主要流程

  1. 分析源代码,生成语法树
  2. 修正语法树,在应该插入类型转换的地方插入类型转换,表达式的类型信息在此时添加
  3. 生成字节码,此处产生的是一个DVM_Executable
  4. 将DVM_Executable绑定到已给DVM_VirtualMachine
  5. 执行

值得注意的是此处有三个在后来十分重要的结构(以下列出的只是主要成员):

  • DVM_Compiler:分类储存分析结果
    • 变量声明的集合
    • 函数定义的集合
    • 顶层语句序列
  • DVM_Executable:储存Compiler的编译结果(字节码),一个文件对应一个Executable
    • 常量池
    • 全局变量(只是形式)
    • 函数集合(包括字节码)
    • 顶层语句的字节码
  • DVM_VirtualMachine:Executable储存的是“程序”(字节码等)的不变部分,要运行一个“程序”,还要给它提供一套可变部分的系统
    • 全局变量的实际储存空间
    • 运行时栈
    • 函数登记表

这里最绕的部分就是函数集合(DVM_Function *function)和函数登记表(Function *function)了。

在生成字节码的时候,push_function的参数是DVM_Function表的参数,DVM_Function存放了文件中出现的所有函数(本地声明的和原生函数)。

挂载到VirtualMachine后,会用Function的对应索引替换DVM_Function索引,在Function中实现对原生函数的登记。

所以Function的内容有两种

  1. 指回DVM_Function
  2. 指向原生函数

这几个结构的成员的功能一定要记好, 它们三个的成员之间的相互联系(特别是与函数有关的部分)也一定要记好,否则后面的链接机制很难看懂。

Diksam0.2

这里没遇见特别难以理解的部分,

Diksam0.3 require

我觉得这一部分可以分成两部分,因为包引入机制是我认为这本书里最难理解的部分,这里没有细讲,让对整体认识把握不足的读者(我)完全摸不着头脑。

这一部分的困难在于

  1. 相对于0.1版,各结构的功能有变化
  2. 各结构的内容有变化
  3. 所有这些变化都是相关联的

VM(VirtualMachine)和Exe(Executable)的关系

0.1版中VM和Exe是一一对应的,VM管理了Exe所需的“内存”(栈,堆,静态区)

现在VM和多个Exe对应了,多个Exe公用一个栈,一个堆。

不过Exe们要各自私有一个静态区。所以通过一个ExecutableEntry结构将静态区附加到Exe上, 而VM的管理单位从Exe变成了ExecutableEntry。

函数,函数登记表,函数关联

对于Exe中的DVM_Function,它有两个作用

  1. 记录本地函数的内容(字节码等),有一个is_implemented的字段,为真时表示当前项具有这一功能。
  2. 记录本文件对所有函数的使用,原因是当要生成字节码的时候(此时还未加载到VM,对外界一无所知),我们依然要给每一个被呼叫的函数分配编号。

对于VM中的Function

  1. 全局的函数登记:所有VM中被使用的Exe的函数都会登记在此(原生函数也登记在此)。
  2. 动态加载:这个功能要求登记表中的具体链接可以为空,所有一个is_implemented字段。
  3. 因为动态加载是按函数名称来的,所以Function要保存函数的名称。

核心问题是多个文件的函数如何关联彼此,这一部分我感觉极其杂乱,还未能完全理解。

大体思路是从一个文件开始,会递归编译文件和它的require(.dkh),组成一组Exe,将这一组Exe逐个加入VM,就可以执行了,

执行时会发生dkh要求加载dkm,发生动态加载,动态加载就是跟据需要编译对应dkm,然后刷新Function。

应用篇

异常处理

实现异常的核心(与其他控制结构,比如if-else的不同)就是对栈的非常规操作,所以如果是自己完全实现了目标语言的栈,则比较方便的写出异常。

而crowbar中的解释器依赖于宿主语言C的递归执行,所以之前在实现基本的crowbar时break等流程跳转需要一些辅助的控制(返回执行状态标志)。

到了要实现异常了,作者祭出了杀手锏:setjump/long_jmp,这两个函数虽然是标准的,不过我之前也从来没见过有谁用它们。这次也算是开眼了。


总结

首先吐槽一下这本书的翻译,感觉用词跟我之前习惯的用词不太一样,不知道是不是日文原文就是这样。

这本书在crowbar部分还是很耐心的讲解各个部分的,到了diksam部分感觉作者是假定读者以源代码阅读为主,当你不懂得时候,来看书,提点一下。

几点收获:

  1. 先有宿主语言,在宿主语言中实现目标语言的控制结构和基本类型。

  2. 表达式与语句的不同

    • 逻辑目标:表达式是与运算相关的,而语句是与流程控制相关的
    • 函数调用是表达式,不是显式的流程控制对应
    • 层次关系:表达式可以构成语句,而语句不能构成表达式
  3. 类型是一个语言的高层逻辑,(这个不太好表达),类型不是运行的特征,而是面向编译器的辅助检查手段。

  4. 异常是一种控制结构(跟if-else同级),特点是具有对栈的读取能力。

  5. 虚拟机提供的是面向目标语言的最小基本操作集

    • 对各种基本类型的操作
    • 栈模型
    • 几个“内存空间”,栈,堆,静态区(全局变量)之间的相互传递,
    • 流程控制:顺序,goto
  6. 最痛苦的就是Diksam中包引入的部分。说实话我现在也没有特别透彻的理解,只是把几个影响阅读的地方搞懂了。

    • 个人认为这里的几个核心结构(DVM_Function, Function, DVM_Exectuable)都承担了多重功能,之间的关系和通信手段感觉比较杂乱。
    • 不过收获也蛮大的,之前都没有思考过多个文件的整合到底要怎么来,了解了作者的一个VM对应多个Exe(共用一个栈,堆)之后感觉这样挺好。
  7. 类的处理其实比较简单,属性就是一组变量,而函数不过是普通函数附加一个this参数。

  8. 类相关的概念中比较复杂的是(接口)多继承。不过这也只是需要一个比较强大的上/下转型时虚表替换而已。

教训:要提升自己的代码阅读能力