Как вывести 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);
  }
}