如何展开(编译)解释器循环？

Question

我听说有些语言通过"展开解释器循环"从解释到编译.

假设我为ast树提供了以下伪c代码解释器.

int interpret(node)
{
    switch(node) {
        case PLUS:
             return interpret(child(0))+interpret(child(1));
        case MINUS:
             return interpret(child(0))-interpret(child(1));       
    }
}

如何展开此循环以创建已编译的程序？

我看到你们所有人都在低调,因为我不知道我在说什么,但这里有一篇来自维基百科的文章,其中说明了我所描述的内容.

"因子最初只被解释,但现在已完全编译(非优化编译器基本上解开了解释器循环"

Answer 1

"展开循环"通常意味着用一系列动作替换重复.循环:

for (int i = 0; i < 4; ++i) {
    a[i] = b[i] + c[i];
}

将展开相应的:

a[0] = b[0] + c[0];
a[1] = b[1] + c[1];
a[2] = b[2] + c[2];
a[3] = b[3] + c[3];

在我看来,被维基百科引用的任何人都在某种隐喻意义上使用这个短语.所以,从那个意义上说......

您的示例通常会在遍历AST节点树的解释器中调用,这可能看起来像这样:

 ASSIGN
    |
 +--+---+
 |      |
REF   MINUS
 |      |
 x   +--+---+
     |      |
    VAR    PLUS
     |      |
     a   +--+--+
         |     |
        VAR  CONST
         |     |
         b     3

该interpret功能还有其他选择:

int interpret(node) {
    switch(node) {
        case PLUS:
             return interpret(child(0))+interpret(child(1));
        case MINUS:
             return interpret(child(0))-interpret(child(1));       
        case ASSIGN:
             return set(child(0), interpret(child(1));
        case VAR:
             return fetch(child(0));
        case CONST:
             return value(child(0));
        ...
    }
}

如果您使用该interpet功能行走AST (实际执行操作),那么您就是在解释.但是,如果函数记录要执行的操作,而不是执行它们,那么您正在编译.在伪代码中(实际上,伪代码两次,因为我假设一个假设的堆栈机器作为编译目标):

string compile(node) {
    switch(node) {
        case PLUS:
             return(compile(child(0))) + compile(child(1)) + ADD);
        case MINUS:
             return(compile(child(0))) + compile(child(1)) + SUB);
        case ASSIGN:
             return(PUSHA(child(0))) + compile(child(1)) + STORE);
        case REF:
             return(PUSHA(child(0)));
        case VAR:
             return(PUSHA(child(0)) + FETCH);
        case CONST:
             return(PUSHLIT + value(child(0)));
        ...
    }
}

调用compile那个AST(忽略任何伪代码错误;-)会吐出类似的东西:

PUSHA x
PUSHA a
FETCH
PUSHA b
FETCH
PUSHLIT 3
ADD 
SUB
STORE

FWIW,我倾向于认为这是展开AST,而不是展开翻译,但是如果不在上下文中阅读它,就不会批评别人的比喻.