如何输出使用ANTLR构建的AST？

Question

如何输出使用ANTLR构建的AST？我正在为C做一个静态分析器。我已经使用ANTLR完成了词法分析器和解析器，其中生成了Java代码。ANTLR会自动为我们构建AST options {output=AST;}吗？或者我必须自己制作树？如果是，那么如何吐出AST上的节点？我目前认为AST上的节点将用于制作SSA，然后进行数据流分析以制作静态分析器。我在正确的道路上吗？

Answer 1

拉斐尔写道：

antlr是否通过选项{output = AST;}自动为我们构建AST？或者我必须自己制作树？如果是，那么如何吐出AST上的节点？

不，解析器不知道你想要什么作为root和每个解析器规则的叶子，所以你必须做的不仅仅是放入options { output=AST; }你的语法。

例如，"true && (false || true && (true || false))"使用从语法生成的解析器解析源时：

grammar ASTDemo;options { 
  output=AST; }parse  :  orExp  ;orExp  :  andExp ('||' andExp)*
  ;andExp  :  atom ('&&' atom)*
  ;atom  :  'true'
  |  'false'
  |  '(' orExp ')'
  ;// ignore white space charactersSpace
  :  (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;}
  ;

生成以下解析树：

（即只是一个扁平的，一维的令牌列表）

你想要告诉ANTLR你的语法中的哪些标记成为根，离开或者只是从树中删除。

创建AST可以通过两种方式完成：

1. 使用如下所示的重写规则：foo : A B C D -> ^(D A B);，哪里foo是与令牌匹配的解析器规则A B C D。所以事后的一切->都是实际的重写规则。如您所见，令牌C未在重写规则中使用，这意味着它在AST中被省略。直接放在后面的令牌^(将成为树的根;

2. 使用树操作符^，! 在解析器规则中的一个标记后，^将令牌作为根，并!从树中删除一个标记。等效于foo : A B C D -> ^(D A B);将foo : A B C! D^;

双方foo : A B C D -> ^(D A B);并foo : A B C! D^;会产生以下的AST：

现在，您可以按如下方式重写语法：

grammar ASTDemo;options { 
  output=AST; }parse  :  orExp  ;orExp  :  andExp ('||'^ andExp)* // Make `||` root
  ;andExp  :  atom ('&&'^ atom)* // Make `&&` root
  ;atom  :  'true'
  |  'false'
  |  '(' orExp ')' -> orExp // Just a single token, no need to do `^(...)`, 
                            // we're removing the parenthesis. Note that
                            // `'('! orExp ')'!` will do exactly the same.
  ;// ignore white space charactersSpace
  :  (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;}
  ;

这将从源创建以下AST"true && (false || true && (true || false))"：

相关的ANTLR wiki链接：

• 树的建设

• 树解析

• 树木施工设施

拉斐尔写道：

我目前认为AST上的节点将用于制作SSA，然后进行数据流分析以制作静态分析器。我在正确的道路上吗？

从来没有做过这样的事情，但IMO首先想要的是来自源头的AST，所以是的，我猜你正走在正确的道路上！:)

编辑

以下是如何使用生成的词法分析器和解析器：

import org.antlr.runtime.*;import org.antlr.runtime.tree.*;import org.antlr.stringtemplate.*;public class Main {
  public static void main(String[] args) throws Exception {
    String src = "true && (false || true && (true || false))";
    ASTDemoLexer lexer = new ASTDemoLexer(new ANTLRStringStream(src));
    ASTDemoParser parser = new ASTDemoParser(new CommonTokenStream(lexer));
    CommonTree tree = (CommonTree)parser.parse().getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }}