怎样写一个编译器/解释器

本文算是对编译原理入门的一点总结,因为我很菜,所以相信你们看完以后也会写了 :p

发明一个语言并为其编写一个编译器/解释器其实并没有什么难点,任何学过一门普通编程语言的人都可以轻松做到,难的是优化(当然这里并不会涉及)。希望本文可以帮助那些语言初学者少浪费一点时间在编译器上,做点别的有意义的事情不是更好(逃

我们不指望一步到位地解决这个问题,一般来说 eval() 要经历以下步骤:

  1. 识别词法元素 (lex)
  2. 识别语法元素 (parse)
  3. (可选) 预处理
  4. 编译 (compile) / 解释 (interpret)

lex. 识别词法元素

所谓词法元素就是把源码中每个单独的字面拆出来理解,例如 "hello, world!\n" 应当被当作一个字符串123 应当被当作一个整数。因此首先要做的事情就是字符串匹配,一步步来:

先考虑一个只包含 + * 整数 的表达式,

enum TokenType {
    T_Error,
    T_Int,
    T_Op,
};

struct Token {
    enum TokenType type;
    int offset, length;  // 在源码中的位置
};

int pos;             // 正在扫描的源码位置
const char *source;  // 源码, 形如 "print 3 + 5"
char peek() { return source[pos]; }
void skip() { ++pos; }

struct Token nextToken() {  // 从 pos 处开始匹配下一个 token
    int temp;
    bool b1, b2;
    // 跳过空格
    while (isspace(peek())) skip();
    if (source[pos] == '\0') return (struct Token){ T_Error, pos, 0 };
    // 匹配数字
    b1 = isdigit(source[pos]);                            // 非负数
    b2 = source[pos] == '-' && isdigit(source[pos + 1]);  // 负数
    if (b1 || b2) {
        for (temp = pos++; isdigit(source[pos]); ++pos)
            ;
        return (struct Token){ T_Int, temp, pos - temp };
    }
    // 匹配运算符
    if (strchr("+*", source[pos])) return (struct Token){ T_Op, pos++, 1 };
    return (struct Token){ T_Error, pos, 0 };
}

测试代码,

const char *nameOfTokenType(enum TokenType type) {
    switch (type) {
        case T_Int:
            return "Int";
        case T_Op:
            return "Op";
        default:
            return "$";
    }
}

void testLex(const char *code) {
    source = code;
    struct Token token;
    while ((token = nextToken()).type != T_Error) {
        printf("(%d, %d) %s\n", token.offset, token.length,
               nameOfTokenType(token.type));
    }
}

parse. 识别语法元素

我们现在有了一串 token,还可以借助上面匹配的思想,尝试将语法结构匹配出来。

首先稍微改造一下 nextToken() 函数,为他增加一个 peekToken() 用于向前看一个 token。编译原理中的 LL(1), LL(k) 说的就是向前看 1 个或者 k 个 token 的意思,目前我们只需要看一个。

bool existTempToken;
struct Token tempToken;
struct Token nextToken() {  // 从 pos 处开始匹配下一个 token
    if (existTempToken) {
        existTempToken = false;
        return tempToken;
    }
...
struct Token peekToken() {
    if (!existTempToken) {
        tempToken = nextToken();
        existTempToken = true;
    }
    return tempToken;
}

然后直接递归下降,

// 读到一个 Int token,返回值
int parseInt() {
    struct Token token = nextToken();
    assert(token.type == T_Int);
    return strtol(source + token.offset, NULL, 10);
}

// 读一个连续乘表达式,每个子表达式都是 Int
int parseMul() {
    int a = parseInt();
    struct Token token = peekToken();
    while (token.type == T_Op && source[token.offset] == '*') {
        nextToken();
        a *= parseInt();
        token = nextToken();
    }
    return a;
}

// 类似的,加法表达式的每个子表达式都是乘法表达式
// 可以看到这个函数直接就是上面 parseMul 改了几个字
int parseAdd() {
    int a = parseMul();
    struct Token token = peekToken();
    while (token.type == T_Op && source[token.offset] == '+') {
        nextToken();
        a += parseMul();
        token = nextToken();
    }
    return a;
}

上面在解析过程中直接计算出了表达式结果,如果把这个操作改为构建树的话,就能得到一个程序的抽象语法树 (AST)。我们先来试一下效果,

int testParse(const char *code) {
    source = code;
    return parseAdd();
}

int main() {
    char code[256];
    printf("? ");
    while (fgets(code, sizeof code, stdin)) {
        printf("= %d\n? ", testParse(code));
    }
    return 0;
}
? -3 + 5 * 9
= 42
? ^Z

不算测试代码,只花了不到一百行(毕竟 C 语言表达起来还是比较繁琐的),而且支持的语法能力十分有限。如果要识别一些复杂的表达(如浮点数、各种进制、字符串),可以去学习和使用一下正则,这里就先不展开了。

上文中这种直接进行匹配的写法叫做递归下降,也叫 LL,90% 的语法规则都可以直接使用递归写法完成解析。还有另一种写法是 LR,是利用一个符号栈以及规约操作来解析的,但是口算符号转移表十分繁琐,一般都是交给计算机推导(yacc 的工作)。【话说编译原理课考试就是口算这个表 qwq

还缺什么?我们只保证了输入绝对正确才这么写,实际情况下还要对每个出错位置进行报告才算得上一个完整的语法解析过程。


tree walker. 从语法树到机器码

上文中我们获得了一棵树,并且还能递归地执行出结果(这个过程就叫解释),那么编译是怎么回事呢?你的 CPU 并不认识什么 Token 或者 AST,它只会按照机器码来运算、搬运数据,大概像这样:

_add:
8b 44 24 08       # 把第一个参数赋值给寄存器1
03 44 24 04       # 把第二个参数加给寄存器1
c3                # 返回

编译器也要把你的语法树翻译成 CPU 能读懂的语言(机器码)才行,也就是从一个语法集合翻译到另一个指令集合。如果我们手上有个栈(也就是汇编里的那个),这个工作也很容易,还是递归跑一遍整棵树:

void ast2asm(根节点) {
  if (根节点 is 整数) {
    push(根节点.value);
  } else if (根节点 is 加法表达式) {
    ast2asm(根节点.左边);
    ast2asm(根节点.右边);
    从栈中 pop 出两个值,相加,再 push 回去。
  } else ...
}

这样 3 + 5 * 4 就可以翻译为,

push 3
push 5
push 4
mul
add

这样的翻译算不上高效,不过确实解决了问题,优化就交给编译器吧!

类似的工作在引入变量和函数时会变得麻烦起来——我们要把变量和函数内容都保存到栈上,因此通常人们不会直接使用 CPU 的机器模型,而是先实现一个有附带功能的虚拟机,例如我们会引入一个环境变量 env={} 来保存环境(变量,函数可见性等)信息,再在该虚拟机的基础上实现翻译到字节码,最后用编译型语言直接翻译到目标程序(例如 mruby,ruby 的一种实现)。

实际上,不管是解释型还是编译型,现代语言通常都会实现一个虚拟机来跑一个小型的指令集(区别于庞大的 CPU 指令集)。我们甚至可以基于相同的虚拟机来实现不同的语言:Java/Scala/Kotlin,C#/F#/VB.NET,python/mulan/dongbei。或者用不同的技术实现相同的语言:Lua/LuaJIT。

上面说了如果我们手上有个栈,其实是指基于栈的虚拟机,可以看到他产生的指令往往不够高效。还有另一类虚拟机是基于寄存器的,想象你有无数多个寄存器(变量)可以使用,那么相同的表达式就可以翻译为 r1 = 3; r2 = 5; r2 *= 4; r1 *= r2,在这种表达下,进行优化处理将容易得多,于是就更容易产生高效的指令,实际上 Lua5.3 就是因为这个将虚拟机改为了寄存器式的。


codegen. 另一个捷径

如果我们把生成的目标从字节码/机器指令换成任何一个已经存在的语言(例如 C),就可以直接跳过手写编译器/解释器的环节,毕竟 gcc 通常比人类聪明,手工写的机器码不如现成编译器生成的很正常。不过翻译语言的难度比翻译字节码要高(因为每个语言的语义模型不同),一个现在比较出名的语言例子是 Nim,它可以生成到 C/C++/JS 三种语言,并且极大地保留了运行时效率。


继续阅读

@lotabout 有系列博客 手把手教你构建 C 语言编译器,里面基于 c4 (c in 4 functions) 重新实现了一遍 C 语言(子集)编译器,涉及到了递归下降解析和虚拟机指令生成。

yinwang 的 怎样写一个解释器,因为是付费内容所以就不打广告了(