新的一年来了，打算赶紧把去年没做的事情都填了吧。

于是就想起了这篇文章，还有那篇孤苦伶仃的Gentoo安装：我的Gentoo都已经换成了Arch系统了，结果那篇讲述如何安装的还没有写完。

不过还是先把这篇完成好了。这个当时弃掉的原因是因为发现了有比自己总结做得更好的版本了: 我是在这里看到的作者遗留的博客。我觉得讲得实在比我的要好得多，也专业的多了。这里不要脸的还是再过一遍吧。

这里重新介绍的是编译原理。作为一门刚刚在期末考试两天一学期学完的课程、恰好也是一种复习吧。

我们将要看chibi-scheme的词法分析器和语法分析器。应该入手的地方是eval.c中的eval interface部分：现在我们只关注sexp_eval_string函数就好了。

这里面除去gc相关的部分就只有两个函数，恰好对应词法分析器和语法分析器两个部分。

词法分析器

词法分析器的任务是接受一些语言的句子、返回这个句子所包含的记号流。但是需要清楚的是：词法分析跟语法没有关系…因而并没有Lisp的特殊语法使得词法分析变得简单这种说法。chibi-scheme代码中，词法分析器和语法分析器是相互独立进行工作的。源代码中，词法分析主要由sexp.c中的sexp_read_raw函数完成。有些时候它会被一个sexp_read_one的函数包着：其实这个函数内部只是增加了对于错误的处理代码。通过这两个函数的交替使用可以区分是否进行错误处理，从而部分地提高代码的效率。

在sexp_read_raw中的逻辑很简单：就是一个循环的switch-case。根据输入的第一个字符判断后面使用怎样的语法来解析它。

在switch-case里面存在这些情况：

  • 根据'判断 quote
  • 根据"判断 字符串
  • 根据(判断 原子（也就是sexp）
  • 根据#判断各种禁止的数字
  • 根据;和|判断 注释
  • 根据 数字 判断数字
  • 如果都不是就认为它是某个变量或者函数(标识符)

它们都会被以sexp的形式提供给后面的语法分析处理。在sexp_read这个函数（其本体是sexp_read_op）中，会第一次调用sexp_read_one，而且在这个函数调用的前后会有垃圾回收(gc)的相关操作。再一步会被包装成sexp_read_from_string，这回是解析一个完整的句子了。

语法分析器

语法分析器是将词法分析器得到的记号流解析成语法树。chibi-scheme中，这个过程在eval.c文件中的analyze函数中，以

1
sexp_eval_string sexp_eval sexp_eval_op sexp_compile_op sexp_analyze analyze

的顺序被sexp_eval_string 所引用。由于Lisp的语法简单、所以这里其实也是一个switch-case的结构。

它的基本运作也是通过输入的sexp的car来决定以何种形式来解析之后的记号流。

最开始是判断是否是列表：(多数情况都是）。然后开始判断sexp列表的第一个元素是什么，如果是关键字，就调用相应的函数去处理它，包括有：define/set/if等关键字，它们对应调用的函数，我们之后将一一予以介绍。对于第一个元素是宏定义的情况，就需要将宏展开、然后重新去解释它，在这里的实现是使用了goto语句跳到了判断的最开始：重新解释这个sexp，而且如果最初仍是宏的话还能被继续展开。第三种情况是操作码的，将会解析后面的内容，然后连在一起，最后作为结果交给vm。如果这样调用是合法的，它们就是一个直接的操作码了。最后它会认为这个sexp可以是一个app，否则就会在app这里出现报错。

这里值得注意的是，在chibi这段解析列表代码中，没有出现解析id的情况，因此如果你给进去一个用括号括起来的id，它会给出一个错误，就像下面这样：

1
2
3
4
5
6
> (3)
WARNING: invalid operator in application: (3)
ERROR in final-resumer: non procedure application: 3
> (define x 3)
> (x)
ERROR in final-resumer: non procedure application: 3

在输入不是列表的情况下：可能输入是一个id，调用解析id的函数去分析。可能输入是一个synclo，那需要新建一个上下文，然后用新的上下文解析这个synclo。也有可能就是空，那会给出一个错误。

1
2
> ()
ERROR: empty application in source: ()

上面所说的synclo指的是符号闭包syntax closure，之后会再有介绍。

结语

简单地介绍了一下chibi-scheme中词法分析和语法分析的实现。惭愧的是，这么短短的一篇东西，已经被我改了好多次了。说实话，做这个源码分析真的是太累了，chibi-scheme的代码注释不是很好，文档也就只有那么长。要冥思苦想作者这里到底想表示什么；很多东西并没有见过，到处查资料请教别人焦头烂额；也有一些做到后面才发现前面说的是错的，又回去重新改一遍。

但是毕竟收获还是不少，我在此前还没有亲眼见过一门Lisp语言是如何被实现的。现在的所见，与我当初所想实在有很大分别，感觉里面代码的一些做法实在让我有些开了眼界。毕竟完全不走弯路哪里又能见到道路外的风景呢，希望自己加油好了。