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

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

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

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

Ответы

Ответ 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;}
  ;

генерируется следующее дерево разбора:

enter image description here

(т.е. только плоский, 1-мерный список токенов)

Вы хотите сказать 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:

enter image description here

Теперь вы можете переписать грамматику следующим образом:

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))":

enter image description here

Связанные ссылки ANTLR wiki:

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

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

Никогда не делал ничего подобного, но ИМО первое, что вам нужно, это АСТ от источника, так что да, я думаю, ты на правильном пути!:)

ИЗМЕНИТЬ

Здесь вы можете использовать сгенерированный лексер и парсер:

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