如何输出使用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可以通过两种方式完成：使用如下所示的重写规则：foo : A B C D -> ^(D A B);，哪里foo是与令牌匹配的解析器规则A B C D。所以事后的一切->都是实际的重写规则。如您所见，令牌C未在重写规则中使用，这意味着它在AST中被省略。直接放在后面的令牌^(将成为树的根;使用树操作符^，! 在解析器规则中的一个标记后，^将令牌作为根，并!从树中删除一个标记。等效于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);   }}