3

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

现在我面临2个问题：

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

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

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 将成为输出光标。

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

谢谢

4

1 回答 1

4

我想我必须使用 Tree 解析器，但我不确定如何将它与 StringTemplate 集成。

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

下面是一个使用模板进行输出的小树语法。请注意，此语法与我在上一个答案中描述的语法之间唯一有意义的区别是该语法在树节点上而不是令牌上运行。模板的工作方式相同。

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

扁平化 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十行并不好。

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

  • 该表达式是一个二元运算，其操作数都是“约简”（即它们都是整数或变量 id）并且不是节点的子DECL节点。var a = 1 + 2没有改变，因为1 + 2它是一个声明的孩子。var b = a + (2 + c)被更改是因为(2 + c)有两个“缩减”操作数并且不是节点的子DECL节点（它是+in的子节点a + ...）。

  • 表达式是 a CALL，它不是节点的子DECL节点。var a = ln(b)未触及，但由于是 的孩子而var a = ln(b) + 3被更改。ln(b)+

表达式在exprs被 id 替换之前存储在其中。当exit_program规则调用buildNewDecls. buildNewDecls只需使用解析器的内置TreeAdaptor成员（名为adaptor）来生成DECL出现在展平 AST 中的节点。适配器方法的 Javadoc 可以很好地解释调用的作用，因此我不会详细介绍。

警告：上述语法生成的解析器适用于您提出的非常有限的情况。我不知道它们在应用于任何更广泛的场景时会产生什么错误。

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

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

您将把扁平化的 AST 传递给一个基于模板的树解析器，例如顶部的解析器，以生成您列出的不同文本版本。在这种情况下，模板将接受声明的所有部分——变量名称、操作/方法名称和操作数/参数——并根据所使用的模板生成类似variable = method(arg0, arg1)or 或的文本。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，但我认为使用操作/方法赋值作为指南添加代码来处理它会很容易。

于 2012-12-12T01:03:22.760 回答