compiler-construction - 如何管理编译器生成的代码中使用的堆栈？

Question

我正在开发一个为堆栈机器生成“类似汇编器”指令的编译器。（更准确地说，我以文本形式生成 Java 字节码指令，例如，我可以将其嵌入到一个文件中，然后我可以使用Jasmin将其编译为一个 java .class 文件）。我做这一切完全是为了教育目的。

假设以下类似 java 的表达式：

a = 1+2

ANTLR 将生成一个看起来像这样的解析树：

走树后顺序给了我“1,2,+,a=”，我将其转换为：

lcd 1 // push integer 1 on top of stack
lcd 2 // push integer 2 on top of stack
iadd  // remove the top two numbers from stack, perform addition with those numbers, and push the result on stack
istore 0 // pop top element from stack and store it in variable space number zero.

指令从一个空堆栈开始，最后堆栈又是……空的。这是我的编译器目前可以做的。它通过遍历 ANTLR 为我生成的语法树生成这些指令。

现在的问题：假设我有以下表达式：

a = b = 1+2

甚至

callToSomeFunctionWhichReturnsAValue();

在第一个表达式中，生成了两个“istore”指令，都试图从堆栈中弹出一个值。第一个将成功，第二个找到一个空堆栈，一切都淹没了下水道。

另一方面，第二个示例将一个值添加到从不弹出的堆栈中。如果我碰巧在一个循环中这样做，我最终会得到一个堆栈溢出（我不是在谈论一个问答网站）。

解决方案当然是添加“dup”指令（复制堆栈顶部的项目）或“pop”指令（丢弃堆栈顶部的值）。但我怎么知道何时何地？

score 2 · Accepted Answer

如果不看一些语法，很难确切地知道要建议什么。我在这里对您所写的内容做出了一些假设，这些假设可能不正确。但是，我认为您遇到的问题很笼统，可以这样解决，即使我没有严格解决您的问题。如果不出意外，我希望提供的示例能够满足您的需求。

从左到右计算算术运算符。您似乎遇到的问题是正在从左到右评估=运算符，因为这是节点出现在 AST 中的顺序，也是您访问它们的顺序。a = b = 1 + 2

但是=操作数表达式是从右到左计算的。可以通过更改节点顺序使您的树表示这一点。但我认为更有意义的是改变 tree walker 以适应所需的评估顺序，同时保留 AST 中输入的自然顺序。

例如，假设您的 AST 如下所示：

以正确的顺序评估运算符按以下步骤进行：

树步行者击中第一个=。它知道首先计算右侧，因此它跳过处理a。它继续到第二个孩子，=。
它击中了第二个=。它评估第二个孩子 ( +)，现在跳过b。
被+评估。现在3在堆栈上，它是堆栈上唯一的东西。
待处理的逻辑在最后一个子 ( ) 评估=后接管。被呼唤，被呼唤。在堆栈上。+dupistoreb3
待处理的逻辑在最后一个子 ( ) 评估=后接管。被呼唤，被呼唤。在堆栈上。=dupistorea3
语句结束，因此pop被调用。堆栈现在是空的。

注意：在这个过程中，每条语句——无论它是否执行赋值——都应该以堆栈上的一个且只有一个值结束。只有语句的结尾才会弹出它。没有自然推送价值的表达式，例如对的调用void foo()，仍然期望推送一些东西，即使它是null、0或某些保留void对象。确保不分配这些表达式是早期编译器阶段的工作。

下面是一个简短的示例令牌解析器和一个树解析器，以及一些测试输入和输出，演示了如何在 ANTLR (v3) 中完成此操作。为了简单起见，我使用了伪指令，并没有尝试优化输出。

有序.g

grammar Ordered;

options 
{
    output = AST; 
}

tokens {
 COMPUNIT;
 STAT;
 REFID;
}

compilationUnit : statement* EOF -> ^(COMPUNIT statement*);
statement: assign_expr SEMI -> ^(STAT assign_expr)
         | expr SEMI -> ^(STAT expr)
         ;
assign_expr: ID EQ^ (assign_expr | expr); //call recursively to keep the tree simple.
expr : add_expr;
add_expr : primary_expr (PLUS^ primary_expr)*;
primary_expr 
    : NUM 
    | (ID -> REFID[$ID.text]) //An ID expr is a reference to the thing named in ID. 
    | LPAR! expr RPAR!
    ;

SEMI: ';';
EQ : '=';
LPAR : '(';
RPAR : ')';
PLUS : '+';
ID : ('a'..'z'|'A'..'Z')+;
NUM: ('0'..'9')+;
WS : (' '|'\t'|'\f'|'\r'|'\n')+ {skip();};

OrderedTreeParser.g

tree grammar OrderedTreeParser;

options { 
    output = AST;
    tokenVocab = Ordered;
    ASTLabelType = CommonTree;
    filter = true;
}

@members {
    private java.util.LinkedList<String> assigningIds = new java.util.LinkedList<String>(); 
}

topdown
    : enter_assign
    ;

enter_assign
    : ^(EQ ID {assigningIds.push($ID.getText());} .+) //Push our ID and handle assignment during bottomup.
    ;   

bottomup 
    : NUM {System.out.println("lcd " + $NUM.getText());}
    | EQ 
        {
            System.out.println("dup");
            System.out.println("istore " + assigningIds.pop());
        }
    | PLUS {System.out.println("iadd");}
    | REFID {System.out.println("iload " + $REFID.getText());}
    | STAT {System.out.println("pop");}
    ;

OrderedTest.java

import java.io.IOException;
import org.antlr.runtime.ANTLRStringStream;
import org.antlr.runtime.CharStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.RecognitionException;
import org.antlr.runtime.tree.CommonTreeNodeStream;
import org.antlr.runtime.tree.Tree;

public class OrderedTest {
    public static void main(String[] args) throws Exception {

        test("a = 1;");
        test("a = 1 + 2;");
        test("a = b = 1 + 2;");
        test("a = b = 1 + c;");
        test("x = y = z = 1 + 2;");
        test("1 + 2;"); //no assignment
    }

    private static void test(String str) throws RecognitionException, Exception, IOException {
        CharStream input = new ANTLRStringStream(str);
        OrderedLexer lexer = new OrderedLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);

        OrderedParser parser = new OrderedParser(tokens);

        OrderedParser.compilationUnit_return result = parser.compilationUnit();

        if (lexer.getNumberOfSyntaxErrors() > 0 || parser.getNumberOfSyntaxErrors() > 0){
            throw new Exception("Syntax Errors encountered!");
        }

        OrderedTreeParser tparser = new OrderedTreeParser(new CommonTreeNodeStream(result.getTree()));
        tparser.downup(result.getTree());
        System.out.println("---------");
    }

}

测试用例

输入

a = 1;

输出

lcd 1
dup
istore a
pop

输入

a = 1 + 2;

输出

lcd 1
lcd 2
iadd
dup
istore a
pop

输入

a = b = 1 + 2;

输出

lcd 1
lcd 2
iadd
dup
istore b
dup
istore a
pop

输入

a = b = 1 + c;

输出

lcd 1
iload c
iadd
dup
istore b
dup
istore a
pop

输入

x = y = z = 1 + 2;

输出

lcd 1
lcd 2
iadd
dup
istore z
dup
istore y
dup
istore x
pop

输入

1 + 2;

输出

lcd 1
lcd 2
iadd
pop

compiler-construction - 如何管理编译器生成的代码中使用的堆栈？

1 回答 1

有序.g

OrderedTreeParser.g

OrderedTest.java

测试用例

Related

Reference