translation - 在基本操作中分解表达式:ANTLR + StringTemplate

Question

我正在尝试为类似Java的语言编写多种语言的翻译器。

现在，我面临两个问题：

首先是按照一系列基本操作分解复杂的表达式，然后将其翻译为目标语言。

例如，我的起始语言可以是：

var a = (ln(b) + avg(c))*2

我想这样翻译：

var x1 = log_N(b);
var x2 = average(c);
var x3 = sum(x1, x2);
var a = multiply(x3, 2);

我想我必须使用Tree解析器，但我不确定如何将其与StringTemplate集成。
此外，我添加了额外的变量，例如x1，x2和x3，我不知道如何处理这种情况。

第二个问题是我的目标语言之一是类似plsql的语言。
在这种情况下，需要确保所有输出变量都成为游标并将它们传递给函数。

例如表达式：

var a = (ln(b) + avg(c))*2

应该这样翻译：

log_N(x1, b);
average(x2, c);
sum(x3, x1, x2);
multiply(a, x3, 2);

其中x1，x2，x3和a将成为输出游标。

谁能帮助我找到正确的解决方案？

谢谢

Answer 1

我认为我必须使用Tree解析器，但是我不确定如何将其与StringTemplate集成。


将StringTemplate集成到树解析器中基本上与将其集成到令牌解析器中相同：将output选项定义为template，然后相应地编写规则生成。

以下是使用模板进行输出的小树语法。请注意，此语法与the one I described in a previous answer之间唯一有意义的区别是，此语法在树节点而不是令牌上运行。模板的工作原理相同。

tree grammar AstToTemplateParser;

options { 
    output = template;
    tokenVocab = JavaLikeToAst;
    ASTLabelType = CommonTree;
}


program
    : ^(PROGRAM decls+=decl+) -> write(text={$decls})
    ;

decl
    : ^(DECL ID ^(op args+=arg*)) -> assign(name={$ID.text}, op={$op.st}, args={$args})
    | ^(DECL ID ^(CALL method args+=arg*)) -> assign(name={$ID.text}, op={$method.st}, args={$args})
    ;

arg 
    : ID -> write(text={$ID.text})
    | INT -> write(text={$INT.text})
    ;

method
    : ID -> op(name={$ID.text})
    ;

op  : STAR  -> op(name={$STAR.text})
    | DIV   -> op(name={$DIV.text})
    | PLUS  -> op(name={$PLUS.text})
    | MINUS -> op(name={$MINUS.text})
    ;

此外，我添加了额外的变量，例如x1，x2和x3，我不知道如何处理这种情况。


那就是踢腿。我知道的最简单的方法（这并不容易）是首先使用令牌解析器生成基线AST，然后使用树解析器将AST展平为声明列表，每个声明代表来自原始输入的表达式-您问题中的 x1， x2和 x3。

中间阶段如下所示：

原始输入

var a = (ln(b) + avg(c))*2

基准AST



扁平化AST



应用标准模板

 var var0 = log_N(b);
 var var1 = average(c); 
 var var2 = add(var0, var1);
 var a = multiply(var2, 2);

已应用PLSQL模板

  log_N(var0, b);
  average(var1, c);
  add(var2, var0, var1);
  multiply(a, var2, 2);

这是一个令牌解析器语法，它只是生成一个与您的问题类似的基准AST。这里没有真正值得注意的东西，它只是生成典型的AST。

grammar JavaLikeToAst;

options { 
    output = AST;
}

tokens { 
    PROGRAM; DECL; CALL; 
}

compilationUnit : statement* EOF -> ^(PROGRAM statement*);
statement       : decl;
decl            : VAR ID EQ expr -> ^(DECL ID expr);
expr            : add_expr;
add_expr        : mul_expr ((PLUS|MINUS)^ mul_expr)*;
mul_expr        : call_expr ((STAR|DIV)^ call_expr)*;
call_expr       : ID LPAR arglist? RPAR -> ^(CALL ID arglist?)
                | primary_expr;
arglist         : expr (COMMA! expr)*;
primary_expr    : ID | INT | LPAR! expr RPAR!; 

VAR     : 'var';
ID      : ('a'..'z'|'A'..'Z')('a'..'z'|'A'..'Z'|'_'|'0'..'9')*;
INT     : ('0'..'9')+;
COMMA   : ',';
SEMI    : ';';
LCUR    : '{';
RCUR    : '}';
LPAR    : '(';
RPAR    : ')';
EQ      : '=';
PLUS    : '+';
MINUS   : '-';
STAR    : '*';
DIV     : '/';
WS      : (' '|'\t'|'\f'|'\r'|'\n'){skip();};

这是丑陋的地方（至少我选择这样做的方式是）。下面的树语法将上面产生的基线AST转换为与AST的表达式（即扁平AST）相对应的声明列表。在此之下，我将逐步介绍语法中的有趣之处。

tree grammar AstToFlatAstParser;

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

@header { 
    import java.util.HashMap;
}

@members {
    private int currentId = 0;
    private HashMap<Integer, Object> exprs = new HashMap<Integer, Object>();
    private boolean newDecls = false;

    private int nextId() { 
        return currentId++;
    }

    private Object generateId(int id) { 
        return adaptor.create(ID, "var" + id);
    }  

    private void saveExpr(int id, Object expr){
        newDecls = true;
        exprs.put(id, expr);
    }

    private Object buildNewDecls() {
        Object newDecls = adaptor.nil();

        for (int i = 0; i < currentId; ++i){
            if (!exprs.containsKey(i)){
                continue; //This id was generated but not used.
            }

            Object expr = exprs.get(i);
            Object decl = adaptor.create(DECL, tokenNames[DECL]);
            adaptor.addChild(decl, adaptor.create(ID, "var" + i));
            adaptor.addChild(decl, expr);
            adaptor.addChild(newDecls, decl);
        }

        exprs.clear();

        return newDecls;
    }
}

bottomup
    : exit_program
    | exit_op
    ;

exit_op
    @init {
        int myId = nextId();
    }
    : ^(binary_op reduced reduced)
        {$start.parent != null && $start.parent.getType() != DECL}? 
        {saveExpr(myId, $start);} 
        -> {generateId(myId)}
    | ^(CALL ID .*) 
        {$start.parent != null && $start.parent.getType() != DECL}? 
        {saveExpr(myId, $start);} 
        -> {generateId(myId)}
    ;   

binary_op       : STAR | DIV | PLUS | MINUS;

reduced         : ID | INT; 

exit_program
    //Only rebuild PROGRAM if a new declaration is going to be built, that is, when "newDecls" is true.
    //Otherwise PROGRAM is considered changed when it isn't and the processing never ends.
    : {newDecls}? ^(PROGRAM old+=.*) {newDecls = false;} 
        -> ^(PROGRAM {buildNewDecls()} $old*)
    ;

首先，请注意语法主要是Java代码。解析器规则只有五个，其中大多数都很简单。这是一个 filter树语法，因此规则 bottomup和 topdown是入口点。在这种情况下，仅需要 bottomup，因此未指定 topdown。重复规则 bottomup直到输出树不变，这对我们来说意味着没有更多的声明要产生并且树已完全展平。

其次，请注意规则 exit_program是新声明被写到AST的地方。我正在使用语义谓词（ {newDecls}?）以确保仅在添加新声明时才修改 PROGRAM。还记得我说过 bottomup叫什么直到没有更多更改吗？没有此语义谓词， exit_program将始终修改 PROGRAM，并且树解析将永远不会停止处理 bottomup。对于这种特殊情况，这是一种粗略的解决方法，但是它可以工作。新的声明会插入 PROGRAM的开头，以确保它们在被引用之前就出现了。在预期的十行后定义 x1不好。

第三，请注意，规则 exit_op用声明（例如 ln(b)）替换了表达式（例如 var0）。如果满足以下条件之一，则替换表达式：


该表达式是一个二进制运算，其操作数都“减少”（即它们都是整数或变量id），并且不是 DECL节点的子代。 var a = 1 + 2不会更改，因为 1 + 2是声明的子级。之所以更改 var b = a + (2 + c)是因为 (2 + c)具有两个“精简”操作数，并且不是 DECL节点的子代（它是 +中 a + ...的子代）。
该表达式是一个 CALL，它不是 DECL节点的子级。 var a = ln(b)未被触动，但是 var a = ln(b) + 3被更改，因为 ln(b)是 +的子级。


表达式存储在 exprs中，然后将其替换为ID。当规则调用 exit_program时，它将在 buildNewDecls规则中重构。 buildNewDecls仅使用解析器的内置 TreeAdaptor成员（名为 adaptor）来生成出现在扁平化AST中的 DECL节点。适配器方法的Javadoc可以很好地解释调用的作用，因此我将不赘述。

注意：以上语法产生的解析器可以很好地解决您所介绍的情况。我不知道将它们应用于任何更广泛的场景时，它们将产生什么错误。


第二个问题是我的目标语言之一是类似plsql的语言。在这种情况下，需要确保所有输出变量都成为游标并将它们传递给函数...


如上所示，一旦AST只是声明的简单列表，模板就可以为您管理。

您将把展平的AST传递给基于模板的树解析器（例如一个树顶的树解析器），以生成与您列出的文本版本不同的文本版本。在这种情况下，模板将接受声明的所有部分（变量名称，操作/方法名称以及操作数/参数），并根据所使用的模板生成诸如 variable = method(arg0, arg1)或 method(variable, arg0, arg1)之类的文本。关键是要确保输入是平坦的，并且模板可以接收与声明有关的所有内容。



这是一个将所有内容捆绑在一起的测试应用程序。

JavaLikeToAstTest.java

public class JavaLikeToAstTest {

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

        final String code = "var a = (ln(b) + avg(c))*2";

        CharStream input = new ANTLRStringStream(code);
        JavaLikeToAstLexer lexer = new JavaLikeToAstLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);

        JavaLikeToAstParser parser = new JavaLikeToAstParser(tokens);

        JavaLikeToAstParser.compilationUnit_return result = parser
                .compilationUnit();

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

        CommonTree tree = (CommonTree) result.tree;

        System.out.printf("Baseline AST: %s%n%n", tree.toStringTree());

        tree = flatten(tree);

        System.out.printf("Flattened AST: %s%n%n", tree.toStringTree());

        translate(tree, "AstToPlsql.stg");
        translate(tree, "AstToGlobal.stg");
    }

    private static CommonTree flatten(CommonTree tree) {
        AstToFlatAstParser parser = new AstToFlatAstParser(
                new CommonTreeNodeStream(tree));
        return (CommonTree) parser.downup(tree, true);
    }

    private static void translate(CommonTree tree, String templateResourceName)
            throws Exception {
        AstToTemplateParser parser = new AstToTemplateParser(
                new CommonTreeNodeStream(tree));
        InputStream stream = JavaLikeToTemplateTest.class
                .getResourceAsStream(templateResourceName);
        Reader reader = new InputStreamReader(stream);
        parser.setTemplateLib(new StringTemplateGroup(reader));
        reader.close();
        stream.close();

        System.out.printf("Result for %s%n%n%s%n%n", templateResourceName,
                parser.program().st.toString());

    }

这是两个简单的StringTemplate组文件来处理翻译过程。

AstToGlobal.stg

group AstToGlobal;

methods ::= ["*":"multiply", "/":"divide", "+":"add", "-":"subtract", "avg":"average", "ln":"log_N", default:key]

assign(name, op, args) ::= <<var <name> = <op>(<args;separator=", ">) >>

op(name) ::= "<methods.(name)>"

write(text) ::= << <text;separator="\n"> >>

AstToPlsql.stg

group AstToPlsql;

methods ::= ["*":"multiply", "/":"divide", "+":"add", "-":"subtract", "avg":"average", "ln":"log_N", default:key]

assign(name, op, args) ::=<< <op>(<name>, <args;separator=", ">) >>

op(name) ::= "<methods.(name)>"

write(text) ::= << <text;separator="\n"> >>

该应用程序产生以下输出：

Baseline AST: (PROGRAM (DECL a (* (+ (CALL ln b) (CALL avg c)) 2)))

(CALL ln b) -> var0
(CALL avg c) -> var1
(+ var0 var1) -> var2
(PROGRAM (DECL a (* var2 2))) -> (PROGRAM (DECL var0 (CALL ln b)) (DECL var1 (CALL avg c)) (DECL var2 (+ var0 var1)) (DECL a (* var2 2)))
Flattened AST: (PROGRAM (DECL var0 (CALL ln b)) (DECL var1 (CALL avg c)) (DECL var2 (+ var0 var1)) (DECL a (* var2 2)))

Result for AstToPlsql.stg

  log_N(var0, b ) 
  average(var1, c ) 
  add(var2, var0 , var1 ) 
  multiply(a, var2 , 2 )  

Result for AstToGlobal.stg

 var var0 = log_N(b ) 
 var var1 = average(c ) 
 var var2 = add(var0 , var1 ) 
 var a = multiply(var2 , 2 )  

AstToTemplate.g或模板中没有代码可以处理像 var a = 3这样的简单任务，但是我认为使用op / method任务作为指导来添加代码来处理它很容易。