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

Question

我正在为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 characters
Space
  :  (' ' | '\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 characters
Space
  :  (' ' | '\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);
  }
}