Как вывести AST, построенный с использованием ANTLR?

Question

Я делаю статический анализатор для C. Я сделал лексер и парсер, используя ANTLR, в котором генерируется код Java.

ANTLR автоматически строит AST для нас options {output=AST;}? Или я должен сделать дерево сам? Если это так, то как выплюнуть узлы на этом AST?

В настоящее время я думаю, что узлы в этом AST будут использоваться для создания SSA с последующим анализом потока данных для создания статического анализатора. Я на правильном пути?

Answer 1

Рафаэль писал:

Antlr автоматически создает для нас AST с помощью опции {output = 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:

• Конструкция дерева
• Разбор дерева
• Средства построения дерева

Рафаэль писал:

В настоящее время я думаю, что узлы в этом 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);
  }
}