Scheme 解释器

最近重读王垠的博客，每天地铁上就刷个一两篇，然后再看《编译原理》就豁然开朗了。琢磨着Scheme语法简洁规范，前缀表达式是天然的树状语法，写个Scheme的解释器似乎没想象中那么难了，便动手用Java实现一个Scheme的编译器前端。

推荐读一下王垠的文章 http://www.yinwang.org/blog-cn/2012/08/01/interpreter

编译器前端工作一般包括两个大步骤：词法分析和语法分析，再就是解释执行或者生成中间代码，其中还有符号表（有的地方也称环境）贯穿这两个步骤，上述文章里的符号表是用单链表实现，简单易懂，方便教学，我们也可以试着用链式哈希表实现。源程序一般以字符串的形式输入，对输入字符逐个扫描分析，生成抽象语法树（abstract syntax tree），再根据每个树节点的符号、类型去进行语法分析，解释执行出最后结果。如果是用Scheme自举的话，词法分析几乎不需要做。

词法分析

如果是复杂的程序，词法分析是需要预读后面多个字符，书中也提到了一些预读缓存优化方案。我开始也尝试着使用预读判断的方案，Java中的PushbackInputStream可以手动实现预读单个字符，但对于Scheme语言这么规整的格式，我们完全可以不用预读，通过对输入字符串的整体处理，按空格分开，生成有意义的字符串数组。

对于"(+"中没有空格的情况，参考 https://github.com/jpdong/pytudes/blob/master/py/lis.py 中的方式，可以先将"("替换成" ( "，前后分别添加空格解决。

private List<Type> parse(String program) {
        Queue<String> queue = tokenize(program);
        List<Type> astList = new ArrayList<>();
        while (!queue.isEmpty()) {
            astList.add(readFromTokens(queue));
        }
        return astList;
    }

    private Queue<String> tokenize(String s) {
        String string = s.replace("(", " ( ").replace(")", " ) ");
        String[] strings = string.split("\\s+");
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < strings.length; i++) {
            if (!"".equals(strings[i])) {
                queue.offer(strings[i]);
            }
        }
        return queue;
    }

语法分析

ast.png

对于每一个括号对，我们可以把它看做是树的一个节点。和二叉树略有不同的是，父节点的子节点的个数是不确定的，需要通过语法分析最终决定，所以在这里我们可以考虑用数组全部存下来。

private Type readFromTokens(Queue<String> tokens) {
        if (tokens.isEmpty()) {
            throw new RuntimeException("unexpected end while reading");
        } else {
            String s = tokens.poll();
            if (s.equals("(")) {
                Node node = new Node();
                while (!")".equals(tokens.peek())) {
                    node.list.add(readFromTokens(tokens));
                }
                tokens.poll();
                return node;
            } else if (")".equals(s)) {
                throw new RuntimeException("unexpected ) while reading");
            } else {
                return atom(s);
            }
        }
    }

括号对里的单个元素当作基础类型处理，目前涉及到布尔型（Bool）、整数型（Int）、字符型（Char）、字符串型（Str）,这里我们把函数也看做类型，函数型（Func）。

private Type atom(String s) {
        if (isMatchChar(s)) {
            return new Char(s.charAt(2));
        } else if (isMatchString(s)) {
            return new Str(s.substring(1,s.length()-1));
        } else if (isInt(s)) {
            return new Int(Integer.valueOf(s));
        } else {
            return new Symbol(s);
        }
    }

语法分析就是将代码字符串处理成数据结构抽象语法树，只涉及到常用的字符串处理和一些简单的正则匹配，接下来就是要对语法树进行语言特性上的实现。

符号表

在语言特性分析之前，先说一下符号表。

在计算机科学中，符号表是一种用于语言翻译器（例如编译器和解释器）中的数据结构。在符号表中，程序源代码中的每个标识符都和它的声明或使用信息绑定在一起，比如其数据类型、作用域以及内存地址。

可以简单理解为对当前代码环境的实现，多用于查找变量。最简单的可以用单链表实现，但链表查找效率很低，链式哈希表是个很好的解决方案。

scheme_env.png

如图所示，每进入一个函数域，或者是每次声明局部变量，都会新建一个符号表，作为当前的计算环境，并存储上一个环境的地址。在需要查找符号表的时候，先在当前环境查找，找不到再到前一个环境中查找。每个域都只保存自己的环境地址，所以不会影响到其它域的使用。

解释执行

由于没有做尾递归优化，很容易就栈溢出了，在这里能用循环就尽量用循环。
分别对Scheme中的操作符作处理。

• quote

if ("quote".equals(symbol.id)) {
                return list.get(1);
            }

• if

if ("if".equals(symbol.id)) {
                Node test = (Node) list.get(1);
                Type trueBody = list.get(2);
                Type falseBody = list.get(3);
                Bool result = (Bool) eval(test, env);
                if (result.value) {
                    ast = trueBody;
                    continue;
                } else {
                    ast = falseBody;
                    continue;
                }
            }

• let

if ("let".equals(symbol.id)) {
                Node field = (Node) list.get(1);
                Type body = list.get(2);
                EnvFrame extEnv = new EnvFrame(env);
                for (int i = 0; i < field.typeList.size(); i++) {
                    Node pair = (Node) field.typeList.get(i);
                    Symbol s = (Symbol) pair.typeList.get(0);
                    Type result = eval(pair.typeList.get(1), extEnv);
                    extEnv.put(s.id, result);
                }
                ast = body;
                env = extEnv;
                continue;
            }

• define

if ("define".equals(symbol.id)) {
                Symbol s = (Symbol) list.get(1);
                Type type = list.get(2);
                env.frameMap.put(s.id, eval(type, env));
                break;
            }

• lambda

if ("lambda".equals(symbol.id)) {
                Node parms = (Node) list.get(1);
                Node body = (Node) list.get(2);
                return new Procedure(parms, body, env, this);
            }

• cond

if ("cond".equals(symbol.id)) {
                Node elseCase = (Node) list.get(list.size() - 1);
                Symbol elseTag = (Symbol) elseCase.typeList.get(0);
                if (!"else".equals(elseTag.id)) {
                    throw new RuntimeException("wrong cond case");
                }
                Type tempAst = elseCase.typeList.get(1);
                for (int i = 1; i < list.size() - 1; i++) {
                    Node currentCase = (Node) list.get(i);
                    Type predicate = currentCase.typeList.get(0);
                    if (((Bool) eval(predicate, env)).value) {
                        tempAst = currentCase.typeList.get(1);
                        break;
                    }
                }
                ast = tempAst;
                continue;
            }

完整代码见项目 https://github.com/jpdong/SchemeInterpreter

小结

大学的时候对编译原理这门课是望而生畏，当时也没有接触到Scheme这么简洁的语言，学完了对编译器也没有概念。现在回看，有了些不同语言的积累，开始渐渐地能理解那些概念了，边实现边理解，就能豁然开朗了。虽然这只是实现了一个简单语言的编译器前端，真正的精华还在后面后端的实现与优化，但这是从零到一的过程，后面还需要一步一个脚印，学习那些本质的东西。