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

我正在为C做一个静态分析器。我使用ANTLR来完成词法分析器和分析器，其中生成Java代码。

ANTLR是否通过options {output=AST;}自动为我们构buildAST？ 还是我必须自己做树？ 如果是这样，那么如何吐出AST上的节点呢？

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

Answer 1

拉斐尔写道：

antlr是否通过选项{output = AST;}自动为我们创buildAST？ 还是我必须自己做树？ 如果是这样，那么如何吐出AST上的节点呢？

不，parsing器不知道你想要什么作为根和叶为每个parsing器规则，所以你不得不做一些比options { output=AST; } options { output=AST; }在你的语法。

例如，当使用从语法生成的parsing器parsing源"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 characters Space : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ; 

会生成以下分析树 ：

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

你要告诉ANTLR你的文法中的哪些标记变成了根，叶，或者干脆离开树。

创buildAST的方法有两种：

1. 使用看起来像这样的重写规则： foo : ABCD -> ^(DAB); 其中foo是与令牌ABCD匹配的parsing器规则。 所以->之后的所有内容都是实际的重写规则。 正如你所看到的，令牌C在重写规则中没有使用，这意味着从AST中省略。 直接放在^(之后的标记^(将成为树的根;
2. 使用树操作符^和! 在你的parsing器里面的一个标记规则里， ^会使一个标记成为根，而! 将从树中删除一个令牌。 相当于foo : ABCD -> ^(DAB); 会是foo : ABC! D^; foo : ABC! D^;

foo : ABCD -> ^(DAB); 和foo : ABC! D^; foo : ABC! 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 characters Space : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ; 

它将从源代码创build以下AST "true && (false || true && (true || false))" ：

相关ANTLR维基百科链接：

• 树build设
• 树parsing
• 树木施工设施

拉斐尔写道：

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

从来没有做过这样的事情，但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); } }