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

Question

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

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

a = 1+2

ANTLR 将生成一个解析树，其外观应如下所示:

          a=
           |
           |
           +
          / \
         /   \
        1     2

遍历树后顺序给出“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”指令(丢弃堆栈顶部的值)。但我怎么知道何时何地呢？

Answer 1

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

---

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

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

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

      =
     / \
    a   =
       / \
      b   +
         / \
        1   2

按正确的顺序评估运算符的步骤如下:

• 树行者击中了第一个=。它知道首先计算右侧，因此它跳过处理 a。它继续到第二个子元素 =。
• 它击中了第二个=。它评估第二个子级 (+)，暂时跳过 b。
• 对 + 进行求值。现在3在堆栈上，并且它是堆栈上唯一的东西。
• 待处理的 = 逻辑在最后一个子级 (+) 求值后接管。调用dup，为b调用istore。 3 在堆栈上。
• 待处理的 = 逻辑在最后一个子级 (=) 计算完成后接管。调用dup，为a调用istore。 3 在堆栈上。
• 语句结束，因此调用 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