为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

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

1 回答

?
Smart猫小萌

TA贡献1911条经验 获得超7个赞

拉斐尔写道:

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);
  }}



查看完整回答
反对 回复 2019-09-09
  • 1 回答
  • 0 关注
  • 344 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信