Como gerar o AST construído usando o ANTLR?

Eu estou fazendo um analisador estático para C. Eu fiz o lexer e parser usando ANTLR em que gera código Java.

O ANTLR constrói o AST para nós automaticamente pelas options {output=AST;} ? Ou eu tenho que fazer a tree eu mesmo? Em caso afirmativo, como cuspir os nós nessa AST?

Atualmente, estou pensando que os nós nessa AST serão usados ​​para fazer o SSA, seguido pela análise do stream de dados para fazer o analisador estático. Eu estou no caminho certo?

Raphael escreveu:

A antlr constrói o AST para nós automaticamente pela opção {output = AST;}? Ou eu tenho que fazer a tree eu mesmo? Em caso afirmativo, como cuspir os nós nessa AST?

Não, o analisador não sabe o que você quer como root e como deixa para cada regra do analisador, então você terá que fazer um pouco mais do que apenas colocar options { output=AST; } options { output=AST; } na sua gramática.

Por exemplo, ao analisar a origem "true && (false || true && (true || false))" usando o analisador gerado a partir da gramática:

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

a seguinte tree de análise é gerada:

insira a descrição da imagem aqui

(ou seja, apenas uma lista de tokens plana e unidimensional)

Você vai querer dizer ao ANTLR quais são os tokens em sua gramática que se tornam raízes, folhas ou simplesmente deixados de fora da tree.

A criação de ASTs pode ser feita de duas maneiras:

  1. use rewrite regras que se parecem com isto: foo : ABCD -> ^(DAB); , em que foo é uma regra de analisador que corresponde aos tokens ABCD . Então tudo depois do -> é a regra real de reescrita. Como você pode ver, o token C não é usado na regra de reescrita, o que significa que ele é omitido da AST. O token colocado diretamente após o ^( se tornará a raiz da tree;
  2. use os operadores de tree ^ e ! depois de um token dentro das regras do analisador, onde ^ fará um token a raiz e ! irá apagar um token da tree. O equivalente para foo : ABCD -> ^(DAB); seria foo : ABC! D^; foo : ABC! D^;

Ambos foo : ABCD -> ^(DAB); e foo : ABC! D^; foo : ABC! D^; irá produzir o seguinte AST:

insira a descrição da imagem aqui

Agora, você pode rewrite a gramática da seguinte maneira:

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

que irá criar o seguinte AST da fonte "true && (false || true && (true || false))" :

insira a descrição da imagem aqui

Links do wiki ANTLR relacionados:

  • Construção de trees
  • Análise de tree
  • Instalações de construção de trees

Raphael escreveu:

Atualmente, estou pensando que os nós nessa AST serão usados ​​para fazer o SSA, seguido pela análise do stream de dados para fazer o analisador estático. Eu estou no caminho certo?

Nunca fiz nada parecido, mas IMO a primeira coisa que você quer é um AST da fonte, então sim, eu acho que você está no caminho certo! 🙂

EDITAR

Veja como você pode usar o lexer e o analisador gerados:

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