虚拟机随谈（一）：解释器，树遍历解释器，基于栈与基于寄存器，大杂烩

其实学习很多之后回头再看，就会觉得“同声翻译”和“翻译书”的比喻还挺形象的：前者是interpret，后者是translate，在英文资料里要区分解释与编译就会碰到这两个词。例如顶楼提到的那本虚拟机的书里就把我觉得叫翻译的技术成为binary translation，在讲到HLL VM的实现时书中也提到这个也被成为compilation。

不过要体会“同声翻译”和“翻译书”恐怕需要自己有经验有感觉了才行。初学的时候恐怕怎么说也很难理解清楚。诶，所以针对初学者来写资料太困难，要么容易写错（写的例子想要形象点却容易引起初学者混淆概念），要么写了初学者看不懂。我觉得真要有为初学者写什么东西的心，自己必须非常有经验、有非常深的体会才行。所以我还不行……

编译器方面……嗯我最近在写的两个编译器都在怠工中。反正不是assignment，没期限，我也就是悠着在写写停停。有一个我想先成型了再说，另一个是纯娱乐的brainf*ck编译器，试试看在这么奇怪的语言上应用优化技巧是啥样子。作为初步试验的一个bison文件如下：

%{
#include <stdio.h>

#define TRUE  1
#define FALSE 0

/* function forward declarations */
int yyerror(const char* msg);
int yylex();

/* GLOBAL VARIABLES */

/* the tape of memory cells */
char tape[30000]; /* using fixed size tape */

/* initialize function pointers */
typedef int (*p_putchar_t)(int); /* int putchar(int c) */
typedef int (*p_getchar_t)();    /* int getchar() */

p_putchar_t pputchar = &putchar;
p_getchar_t pgetchar = &getchar;

int a = 0; // value of consecutive arith_cmd
int p = 0; // value of consecutive ptr_cmd

%}

%token PLUS MINUS GT LT COMMA DOT LBRACK RBRACK

%%

prog
    : cmds
    | /* emty program */
    ;

cmds
    : cmd
    | cmds cmd
    ;

cmd
    : arith_cmd { /* emit a packed arithmetic command */ printf("arith: %d\n", a); a = 0; }
    | ptr_cmd   { /* emit a packed pointer command */ printf("ptr: %d\n", p); p = 0; }
    | loop_cmd  { /* do nothing */ }
    | io_cmd    { /* ? */ }
    ;

arith_cmd
    : PLUS            { a++; }
    | arith_cmd PLUS  { a++; }
    | MINUS           { a--; }
    | arith_cmd MINUS { a--; }
    ;

ptr_cmd
    : GT         { p++; }
    | ptr_cmd GT { p++; }
    | LT         { p--; }
    | ptr_cmd LT { p--; }
    ;

loop_cmd
    : LBRACK { /* push stack */ printf("[\n"); }
        cmds
      RBRACK { /* pop stack */ printf("]\n"); }
    | LBRACK { printf("[\n"); } RBRACK { printf("]\n"); }
    ;

io_cmd
    : COMMA { /* emit input call */ printf("in\n"); }
    | DOT   { /* emit output call */ printf("out\n"); }
    ;

%%

int main() {
    return yyparse();
}

int yyerror(const char* s) {
    fprintf(stderr, "%s\n", s);
    return 1;
}

int yylex() {
    int c;
    while (TRUE) {
        c = getchar();
        switch (c) {
        case '+': return PLUS;
        case '-': return MINUS;
        case '>': return GT;
        case '<': return LT;
        case '[': return LBRACK;
        case ']': return RBRACK;
        case ',': return COMMA;
        case '.': return DOT;
        case EOF: return EOF; /* EOF == 0 */
        }
    }
    
    fprintf(stderr, "shouldn't reach here: yylex");
    return c;
}

看起来很乱是因为我原本想试着直接在这个文件上改造出一些东西，后来放弃了另外写了个文件。其实这里就是把连续的算术给合并到一起，使中间代码跟一般的语言差不多。然后的话准备在基本块上先想想办法，之后再想点别的有趣的来玩。后面的代码等我整体完成了或许会放出来……吧 =_=|||

又想起了学习编译原理的那段时光。

LZ真用心，佩服。绝对精华。。。

我理解的解释器和楼主不同。
我认为解释器就是直接对AST进行解释然后返回结果，没有从源语言到目标语言的过程，但是实在想不起来这条定义来源。与楼主所说的可以从源代码直接返回结果的黑箱还是有区别的。
不过近年来解释和编译的概念越来越模糊了，很多解释型语言也变成生成字节码或中间码然后JIT编译执行了（比如Python)。

按楼主的说法，JIT Compilation也符合解释的定义...虽然我知道不应该纠缠概念，但是实在有点混乱。

python不jit的。。。。

CPython目前是不JIT，不过有带JIT的Python实现，例如PyPy和Psyco；IronPython在纯编译模式中是做源码->AST->ETv2->MSIL->native code这样的编译，而CLI的两个主流实现，CLR与Mono都JIT，所以可以把IronPython也看为带JIT的；Jython类似，虽然JVM的主流实现之一的HotSpot默认是以混合模式运行。

幸存者提到的那种定义方式我也见过，不过比较之后我还是选择接受顶楼里写的那种，把解释器看成黑盒子，只以其输入与输出来定义它。希望码字中的下一篇能再展开讨论一下这个问题。不过这几天搬家等杂事把时间都占了，恐怕下一篇要好一段时间后才能再开始写了 T T

RednaxelaFX太牛B了，不知道你从开始学习这些语言到现用了多久，要达到你这种层度很多人一辈子都难以做到，历史上的中国软件20人中都找不到像你这样的，当然里面很多不是纯以技术得名，我认为你将来一定是个传奇人物，至少你拥有能影响中国甚至世界软件界的潜力，不知道有没有规划将来做些什么...

那天跑去看了看Parrot与LLVM，发现都是基于寄存器的。

现在Python on Parrot与Ruby on Parrot都在做，Python on LLVM是Google在做。

然后Yarv虽然是没有JIT，但是在github看到有yarv2llvm……

嗯，那MacRuby就可以算是Ruby on LLVM，虽然只是针对Mac的。关于YARV与JIT我之前也发过一帖 ^_^

好像哪天在InfoQ看到Apple在做Ruby on LLVM，实在找不着了……

http://www.infoq.com/news/2009/03/macruby-llvm-speed

找着了...