将解析树转换为XML

Question

我有一个编译好的语法，希望用它将输入序列转化为XML。请注意，在我的情况下，我有一份非常庞大的语法规则，我想避免在代码中覆盖每个语法规则。

为了避免混淆，我将使用一个例子。让我们看一个以下的语法规则。

grammar expr;

prog: stat+ ;

stat: expr NEWLINE
 | ID '=' expr NEWLINE
 | NEWLINE
;

expr:  expr ('*'|'/') expr
 | INT
 | ID
 | '(' expr ')'
;

ID : [a-zA-Z]+ ; // match identifiers
INT : [0-9]+ ; // match integers
NEWLINE:'\r'? '\n' ; // return newlines to parser (is end-statement signal)
WS : [ \t]+ -> skip ; // toss out whitespace

输入序列

A = 10
B = A * A

预期输出

<prog> 
    <stat> 
        A = 
        <expr> 10
        </expr> 
        \r\n
    </stat>  
    <stat> 
        B = 
        <expr>
            <expr>A</expr> 
            * 
            <expr> A</expr>
        </expr> 
        \r\n
    </stat>
</prog>

这对应于解析树

目前，我使用一种方法创建一个ParseTree，并使用toStringTree方法生成以下字符串

(prog (stat A = (expr 10) \r\n) (stat B = (expr (expr A) * (expr A)) \r\n))

我将其转换为上面展示的XML格式（我使用适用于任何语法的简单通用代码）。我发现这种方法有些笨拙。是否有可能不使用toStringTree来解决它？我想避免需要在我的Visitor中覆盖每个语法规则。（我有数百个语法规则。）

编辑：

基本上，我需要一种通用的ParseTree序列化方法，以XML格式呈现。主要目标是我不必为每个规则编写特殊的Java序列化方法。

- Radim Bača

---

使用静态方法printXml(ParseTree tree)对ParseTree进行递归下降打印，这个方案怎么样？ - Stefan Haustein

@StefanHaustein 我会检查一下，谢谢。我对Antlr没有太多经验。 - Radim Bača

生成XML并不是一个好主意。你将如何操作它？XSLT在大型树上并不是很好，而且对于中等大小的Java程序，你会得到巨大的树。更糟糕的是，XSLT不能很好地进行上下文敏感检查，而所有的Java构造都是上下文敏感的（变量的含义取决于它们的声明）。请参阅解析后的生活，了解为什么你需要更多的东西而不仅仅是AST：http://www.semdesigns.com/Products/DMS/LifeAfterParsing.html - Ira Baxter

@IraBaxter 我的树会比较小（有几十到几百个元素），我打算使用 XQuery 引擎进行搜索和操作。 - Radim Bača

@RadimBača：好的，小树...也许XML本身不会淹死你。但是根据语言的上下文敏感性对这些树进行严格操作... XQuery可能行不通。请阅读有关解析后生活的部分。 - Ira Baxter

Answer 1

也许这种方法适合你的需求。我为了易读性，使用额外的标签t包装终端符号，并跳过带空格的符号。如果需要的话，调整输出应该不是什么大问题。

final exprLexer lexer = new exprLexer(CharStreams.fromString("A=10\nB = A * A\n"));
final CommonTokenStream tokens = new CommonTokenStream(lexer);
final exprParser parser = new exprParser(tokens);
final ParseTree tree = parser.prog();
ParseTreeWalker.DEFAULT.walk(new exprBaseListener()
{
    final String INDENT = "    ";
    int level = 0;
    @Override
    public void enterEveryRule(final ParserRuleContext ctx)
    {
        System.out.printf("%s<%s>%n", indent(), parser.getRuleNames()[ctx.getRuleIndex()]);
        ++level;
        super.enterEveryRule(ctx);
    }

    @Override
    public void exitEveryRule(final ParserRuleContext ctx)
    {
        --level;
        System.out.printf("%s</%s>%n", indent(), parser.getRuleNames()[ctx.getRuleIndex()]);
        super.exitEveryRule(ctx);
    }

    @Override
    public void visitTerminal(final TerminalNode node)
    {
        final String value = node.getText();
        if (!value.matches("\\s+"))
        {
            System.out.printf("%s<t>%s</t>%n", indent(), node.getText());
        }
        super.visitTerminal(node);
    }

    private String indent()
    {
        return String.join("", Collections.nCopies(level, INDENT));
    }
}, tree);

- yegodm

---

太好了，我知道有更好的解决方案。非常感谢你。 - Radim Bača

Answer 2

你可以利用ANTLR4的访问者功能。根据你使用的工具，你可能需要在生成类时添加-visitor命令行参数。

为了使其正常工作，我在解析器规则中添加了一些标签：

prog
 : stat+ EOF
 ;

stat
 : expr NEWLINE        #exprStat
 | ID '=' expr NEWLINE #assignStat
 | NEWLINE             #emptyStat
 ;

expr
 : lhs=expr op=('*'|'/') rhs=expr #multExpr
 | INT                            #intExpr
 | ID                             #idExpr
 | '(' expr ')'                   #nestedExpr
 ;

您的访问者可能看起来像这样：

public class XmlVisitor extends exprBaseVisitor<String> {

  @Override
  public String visitProg(exprParser.ProgContext ctx) {
    StringBuilder builder = new StringBuilder("<prog>");
    for (exprParser.StatContext stat : ctx.stat()) {
      builder.append(super.visit(stat));
    }
    return builder.append("</prog>").toString();
  }

  @Override
  public String visitExprStat(exprParser.ExprStatContext ctx) {
    return "expr";
  }

  @Override
  public String visitAssignStat(exprParser.AssignStatContext ctx) {
    return "<stat>" + ctx.ID() + " = " + super.visit(ctx.expr()) + "\\r\\n</stat>";
  }

  @Override
  public String visitEmptyStat(exprParser.EmptyStatContext ctx) {
    return "\\r\\n";
  }

  @Override
  public String visitMultExpr(exprParser.MultExprContext ctx) {
    return "<expr>" + super.visit(ctx.lhs) + ctx.op.getText() + super.visit(ctx.rhs) + "</expr>";
  }

  @Override
  public String visitIntExpr(exprParser.IntExprContext ctx) {
    return "<expr>" + ctx.INT().getText() + "</expr>";
  }

  @Override
  public String visitIdExpr(exprParser.IdExprContext ctx) {
    return "<expr>" + ctx.ID().getText() + "</expr>";
  }

  @Override
  public String visitNestedExpr(exprParser.NestedExprContext ctx) {
    return "<expr>" + super.visit(ctx.expr()) + "</expr>";
  }
}

要测试此访问者，请运行以下代码：

String source = "A = 10\nB = A * A\n";
exprLexer lexer = new exprLexer(CharStreams.fromString(source));
exprParser parser = new exprParser(new CommonTokenStream(lexer));
ParseTree tree = parser.prog();
String xml = new XmlVisitor().visit(tree);
System.out.println(xml);

这将打印：

<prog><stat>A = <expr>10</expr>\r\n</stat><stat>B = <expr><expr>A</expr>*<expr>A</expr></expr>\r\n</stat></prog>

- Bart Kiers

---

非常感谢您的努力。但请注意我的最后一句话：“我想避免在我的访问者中覆盖每个语法规则（我有数百个规则）。”此外，如果语法发生变化，访问者必须相应地进行更改，这在我目前的解决方案中是不必要的。 - Radim Bača

如果你的语法规则发生了变化，你总是需要改变其他东西。不管是在你编写的访问者还是静态方法中。我认为这是解决你问题最好（最干净）的方法，这就是我发布它的原因。随意使用或不使用：我相信它会对某些人有所帮助。当然，欢迎你！ :) - Bart Kiers

一个静态方法，其中您检查树并发出节点，可能会变成一堆混乱的代码。在访问者中，每个节点都在自己的方法中发出，保持整洁。而且非常容易进行单元测试！ - Bart Kiers

我同意你关于静态方法的看法。我有一种感觉，我的toStringTree结果解析是目前这个问题最简单、最通用的解决方案。我真的不想现在为所有语法规则编写访问者（因为它们可能非常多）。 - Radim Bača

ANTLR节点必须被标记，以便可以将它们区分开来。因此，生成XML相当简单：遍历树，检查节点，确定其类型，为该根及其（递归）子级生成XML。ANTLR可以打印类似LISP的版本的事实告诉您，生成等效的XML必须是很容易实现的；只需窃取那段代码并进行修改即可。（我们使用DMS软件重构工具包从中生成XML。大约需要50行代码）。 - Ira Baxter

Answer 3

我创建了一个ANTLR语法，可以读取由ParseTree.toStringTree方法生成的LISP风格树。该项目可以在这里访问。它包括以下部分：

语法

grammar str;

expr:
 STRING expr                                # exprString
 | LR_BRACKET expr RR_BRACKET expr          # exprParenthesis
 | LR_STRING_BRACKET expr RR_BRACKET expr   # exprRule 
 | <EOF>                                    # exprEnd
 | EOF_MARK                                 # exprEOF
 |                                          # exprEpsilon
;

EOF_MARK:            '<EOF>' ;
LR_STRING_BRACKET:  '(' ~[ ()]+;
LR_BRACKET:         '(';
RR_BRACKET:         ')';
STRING:             ~[ ()]+;
SPACE:              [ \t\r\n]+    -> skip; // toss out whitespace

strXMLVisitor.java

public class strXMLVisitor extends strBaseVisitor<String> {

  @Override
  public String visitExprString(strParser.ExprStringContext ctx) 
  {
    return ctx.STRING().getText() + super.visit(ctx.expr());
  }

  @Override
  public String visitExprParenthesis(strParser.ExprParenthesisContext ctx) {
    return "(" + super.visit(ctx.expr(0)) + ")" + super.visit(ctx.expr(1));
  }

  @Override
  public String visitExprRule(strParser.ExprRuleContext ctx) {
    String value = ctx.LR_STRING_BRACKET().getText().substring(1);
    return "<" + value + ">" + super.visit(ctx.expr(0)) + "</" + value + ">" + super.visit(ctx.expr(1));
  }

  @Override
  public String visitExprEnd(strParser.ExprEndContext ctx) {
    return "";
  }

  @Override
  public String visitExprEOF(strParser.ExprEOFContext ctx) {
    return "";
  }

  @Override
  public String visitExprEpsilon(strParser.ExprEpsilonContext ctx) {
    return "";
  }  
}

main.java

import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;

public class main {
    public static void main(String[] args) throws Exception {
       // create a CharStream that reads from standard input
       ANTLRInputStream input = new ANTLRInputStream(System.in);
       // create a lexer that feeds off of input CharStream
       strLexer lexer = new strLexer(input);
       // create a buffer of tokens pulled from the lexer
       CommonTokenStream tokens = new CommonTokenStream(lexer);
       // create a parser that feeds off the tokens buffer
       strParser parser = new strParser(tokens);
       ParseTree tree = parser.expr(); // begin parsing at init rule

       String xml = "<?xml version=\"1.0\"?>" + new strXMLVisitor().visit(tree);
       System.out.println(xml);      
    }
}

一旦您准备好了antlr4（并且在CLASSPATH中也有引用），您可以使用以下命令来运行它：

 antlr4 -visitor str.g4
 javac *.java
 java main < file

文件必须包含LISP树格式的输入，结果将在标准输出中以XML形式呈现。

- Radim Bača

---

文件中的"("和")"符号存在问题。 如果其中一个存在，生成的XML将无效。 - Dmitry JJ