[闲来没事]写个代码解释器

说点闲话

工作已经五年了，自己从c++到php python的过程中，一直都是往高级编程语言的路子走着。学得越深，未知的越多，很多事务如今却觉得知其然不知所以然。回想大学课程里的编译原理，词法分析、句法分析，计算机底程的东西一直觉得很难。以致于在算法设计、架构设计等高难度点的工作上就有点力不从心。我们一直都在学习的路上，却更多时候是在重复的路上。千万行代码，重复的比例自己心知肚明。曾以为自己很懂计算机，却连编译、解释原理都没深刻掌握。 于是，马上动手准备出一个『闲来没事』系列，第一个出品的是代码解释器。接下来可能是各种形态的代码解释器，各种形态的编译器，然后算法等等。涉及的语言不限，更新时间不限，我会尽我所能，还有网友们的意见。然后，虽然都是些娱乐性的小项目，仅供自己和大伙学习，但也会把项目代码发布的GitHub上。这次的玩具是pyScheme

什么是代码解释器

我们写的代码要在计算机中执行，都需要翻译成机器语言才能被计算机懂得去执行。教程上对于编译器和解释器的明确定义及区别都很详细，只是能不能被读者理解是另外一回事。我从来不喜欢羞涩难懂的定义，喜欢活泼明了的比喻。

老公老婆是两个不同国家的人，老公只会阿拉伯语言，老婆只会韩语。老公要怎么跟老婆讲话？请一个中间人。中间人有两种，一种解释型的，我们称为解释人；一种编译型的，我们称为编译人。

老公要逗老婆，说一段笑话给她听，这时候解释人和编译人的处理方式不一样。

老公说完笑话，解释人就把口译给老婆听，老婆很开心。老婆还想再听一次那个笑话，老公再讲一次，解释人又要再口译一次。累！

编译人听完笑话，把翻译结果用录音机录下来，给她老婆。老婆还想听那个笑话的时候，听录音就好了。如果老公的笑话一直不换，显然编译人的做法是更有效率的。

OK，所谓解释和编译就是有没有录音机的区别。我们讲的解释器就是没有录音机的解释人，它要把我们的话解释给计算机听，即使我们说的话一样的，也还需要它解释一次。

常见的编译型语言有C、C++、Pascal等。 常见的解释型语言有PHP、Python、JavaScript等。

词法分析最简单的语言 Scheme

这是本文的主角，Scheme是Lisp语言的一个重要分支，它是极简主义哲学在编译语言里面的极品。Lisp的设计初衷是用来进行学校内教学的，谁知道会火。废话少点… 当然我没精力把Scheme所有的语法、功能都实现了，都实现了你们也没精力看吧。好吧，学习就应该从小麻雀开始，虽小五脏俱全。解释型语言的步骤：词法分析、句法分析、执行。真的只有三步，一个解释型语言很简单的。

我们继续看我们的项目，初学者别太难，所以我们虽然也是三步，却是：简单词法分析、简单句法分析、简单执行。简单的错误提示和错误处理，简单的类型，简单的操作。我希望我的文章和代码会显示简单，好明白。

我们的解释器

上节讲到Scheme，是的，我们要写一个Scheme语言的解释器，只是不会得Scheme那么强大，那没有意义，我们的目的是学习怎么写一个解释器。

首先，明确我们的可以写怎么样的代码。写怎么样的代码是一个代码设计人做的事情，其中水是非常深的，比如有没有Class、支持什么Types、怎么定义变量、怎么定义函数等，你想得越复杂这个解释器(编译器)的词法、句法分析就越复杂。当然，我是个挑软柿子捏的人，Scheme的词法和句法法分析是最简单的，所以我才拿它当例子。我们来假设以下是一个解释器的输入输出过程。>>代表输入，<<代表输出。

>> 3 ; 常量3<< 3>> (def a 5) ; 定义变量a<< 5>> a ; 变量a<< 5>> (+ a a 3) ; 基本运算 a+a+3<< 13>> (- a 1 2 3) ; 基本去处 a- 1-2-3>> (and 0 2 3 4) ; 逻辑操作 1 and 2 and 3 and 4<< False>> (def mul (func (x y) (* x y))) ; 自定义乘法函数: mul<< (func (x y) (* x y))>> (mul 7 5) ; 使用自定义函数mul<< 35>> (def mul7 (mul 7)) ; 自定义高阶函数mul7<< (func (x y) (* x y))>> (mul7 5) ; 使用高阶函数mul7<< 35>> (def alist (list 1 2 3 4)) ; 定义列表<< (list 1 2 3 4)

先这样子吧，已经够复杂了，复杂都是有简单堆砌起来的。我们来开始吧！确定完语法，我们就可以进行分析和实现。语言不重要，重要的是你用你的思考把它实现了！我偏爱Python，所以就用Python。当然，使用不同的语言的实现复杂度也不一样，所需要的代码量也不一样。我尽量偏理论一些，然后各位看观可以用自己熟悉的语言来实现。然后分享出来，这是个有趣的过程。

这里我会实现一些简单的概念：函数、列表、作用域。不会实现变量类型，只支持数值运算，不支持字符串等。能简化的都简化掉。

我们进入一下章节！

词法分析

上节让大家了解了一下Scheme语法，可能大家会说，这语法太复杂了，看不懂，比神马语言的语法都复杂，然后就开始卖楼主了。别急，它的语法就是这样的一个格式(不用范式，太难理解了！) (操作符/函数名等 参数1 参数2 参数3 …) 操作符/函数名和参数都可以是上面的格式，你想多复杂就多写几个括号内的东西。 例：

((func (x y z) (* x y z)) (def a 4) (def b (+ a 6)) (+ a b 9)) 

换成熟悉的语法大概如下

function afun(x, y, z) { return x*y*z} var a = 4, b = a + 6 afun(a, b, a+b+9) // 输出920

懂了么，不懂好好理解一下再往下看。 这样看起来复杂的语法却是语法分析中最简单的。为什么呢，因为它最接近语法树的语法。也就是所谓的句法分析！

看下图，为什么语法树这样子的，因为我们拿到一个语句，要先知道是什么函数、什么操作符，然后才知道它需要多少个参数。所以语法树都是操作符在前，参数在后。 我们举的栗子是：

(def x (if (> a 1) a 1))

a 1) a 1))的语法树” />

以上语法树让我很直观的明白，我们要怎么去处理那复杂的代码，而且scheme语法的括号让我们无需去处理运算符的优先顺序，什么先乘除后加减，这里没这玩意，想办法把括号里的值求出来就好了！

好的，看着这棵树，我们就想到递归，遇到父结点就调用递归函数求值。好像好简单啊，的确，问题就是这么简单。然后想想怎么把作用域加进来？操，好复杂！

哈，差不多分析完成！我们来想办法完成吧！

一步一步写解释器

我尽量写伪代码，实际Python代码到GitHub去看吧。

词法分析

词法分析的目的是把代码中所有的元素找出来，并按顺序存好。元素包括函数、运算符、操作符、函数名、变量名、数值等。去掉写代码执行无关的东西：如换行、空格、注释(pyScheme没考虑它)等。scheme语法，空格是关键。按空格切开字符串就可以找到所有元素了。”(“,”)”前后是没有空格的，怎么办，那就创造出空格来。

定义 词法分析-tokenize(code)    list = code.replace("(", " ( ").replace(")", " ) ").split([" ","\n", "\t", "\r"])    ret_list = []    for i = 0; i < list.length; i++        if list[i].length > 0 then ret_list.append(list[i])    return ret_list

于是，运行”tokenize(‘(def x (if (> a 1) a 1))’)”的结果是 [‘(‘, ‘def’, ‘x’, ‘(‘, ‘if’, ‘(‘, ‘>’, ‘a’, ‘1’, ‘)’, ‘a’, ‘1’, ‘)’, ‘)’]。 很简单的完成了。

句法分析

句法分析的目的就是把词法分析的结果变成语法树，然后程序根据语法树去遍历执行。先不忙着定义句法分析函数，先想想这个语法树怎么来实现。这个Node在代码里叫SExpression

  Struct 语法树结点-Node       var value = ''       var parent = None       var children[]  定义 句法分析-parse(tokens)      var program = new Node()      var current = program      for i=0; i<tokens.length; i++          switch(tokens[i])          case '(':              var newNode = new Node()              newNode.value = '('              newNode.parent = current              current = newNode          case ')':              current = current.parent          default:              var newNode = new Node()              newNode.value = tokens[i]              newNode.parent = current              current.child.append(newNode)      return program.children[0]

OK, 句法分析也够简单的，谢谢scheme，如果是C++体系的语法，写三天代码估计还有很大的bug。anyway, 恭喜你，进入男生权利：撸一局！好吧，顺道做个广告，鄙人在艾欧尼亚叫转坑艾欧尼亚，挺坑的不怕死的加我。

执行

句法分析完就可以执行了，执行过程中需要存储一些过程变量，如自定义变量、自定义函数等。我们引入一个作用域的概念。我们把它设计成一个单向链表，当前在末端，如果找不到就向上搜索，直到根本，如果找不到就不存在了。

  Struct 作用域-Scope:       var parent = None       var vars = {} //这是一个字典       Scope(parent) // 构造函数，你的语言体系中没有这个的话，就多写几行代码吧           this.parent = parent  定义 找变量-find(scope, name)       current = scope       while current != null:           if is_exist(current[name])               return current[name]           current = current.parent       return null

OK有这个概念后，我们进入执行的实现。

  定义 求值-evaluate(expression, scope):       if expression.children.length <= 0           // 不是数值就是变量           if tryParse2Float(expression.value)                return tryParse2Float(expression.value)           return scope.find(name)        first = expression.children[0]        if first.value = '(':            // 递归的节奏啊            func = evaluate(first, new Scope(scope))            arguments = []            for i = 1; i < self.children.length;i++                 argument.append(evaluate(self.children[i], scope))            return evaluate(func, scope)         // 内置函数         // 这个解释器好像没什么功能啊，强大的功能都是在内置函数里了。         // 我们设置一个全局变量，就叫builtInFuncs吧, evluate         if is_exist(builtInFuncs[first.value])             return execute(builtInFuncs[first.value], self.childrens, scope)

OK，强大的语法树求值，搞定了。善后善一下。

// 我们定义一个函数原型定义 function (args, scope) {}定义 执行函数-execute(function, arguments, scope)      return evaluate(function, arguments, scope)

PS：写到这里的时候，为了减少(mul7 5) = 35这个高阶函数给大家带来的理解困难，所以突然想简化成不支持此类高阶函数。但是，思路有点混乱，感觉怪怪的，却还看不出哪里不对，先这样子吧，想到了再发。

OK：真的结束了么？还差一点，说好的内置函数库来了。

内置函数库

前面，那么多功夫，都是没有结果，直接推出会被人扔火鸡蛋的。操，这是解释器框架，懂吗？仍然有人表示不理解。我也不废话，先来定义个加法吧。回顾一下加法的语法

（+ 1 2 3 4 5 6）builtInFuncs["+"] = function(args, scope) {     var ret = 0     for i = 1; i < args.length; i++          ret += evaluate(args[i], scope)     return ret}builtInFuncs["if"] = function(args, scope) {     if evaluate(args[1], scope):         return evaluate(args[2])     else         return evaluate(args[3])}

其他的操作，大家花飞自己的想像和码代码的能力自己添加，实在搞不定吧，就看我的代码吧。还是有问题，而且代码不是python，烦请你建一个gist或github仓库，把代码链接发给我看看吧。

最后怎么玩

main ()    var code    var scope = new Scope()    while(true)        cout<< "pySch>> "        cin>> code        if code and code != "quit"            cout<< "pySch>> "<< evaluate(parse(tokenize(code)), scope)        if code == 'quit'            break

写在最后

好了，串完了。写代码容易，码字难，好像没写长文了，保持这个冲劲，继续加油～老感觉代码写不好就算了，文章也写不好。 算了～

( 完 )