Wie kann der mit ANTLR erstellte AST ausgegeben werden?

Ich mache einen statischen Analysator für C. Ich habe den Lexer und Parser mit ANTLR erstellt, in dem Java-Code generiert wird.

Baut ANTLR den AST automatisch für uns durch options {output=AST;}? Oder muss ich den Baum selbst machen? Wenn ja, wie spuckt man dann die Knoten auf diesem AST aus?

Ich denke derzeit, dass die Knoten auf diesem AST zum Erstellen von SSA verwendet werden, gefolgt von einer Datenflussanalyse, um den statischen Analysator zu erstellen. Bin ich auf dem richtigen Weg?

Raffael schrieb:

Baut Antlr den AST für uns automatisch per Option {output=AST;}? Oder muss ich den Baum selbst machen? Wenn ja, wie spuckt man dann die Knoten auf diesem AST aus?

Nein, der Parser weiß nicht, was Sie als Wurzel und als Blätter für jede Parser-Regel wollen, also müssen Sie etwas mehr tun, als nur put options { output=AST; } in deiner Grammatik.

Zum Beispiel beim Parsen der Quelle "true && (false || true && (true || false))" mit dem aus der Grammatik generierten Parser:

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

Der folgende Analysebaum wird generiert:

(dh nur eine flache, eindimensionale Liste von Tokens)

Sie sollten ANTLR mitteilen, welche Token in Ihrer Grammatik zu Wurzeln, Blättern oder einfach aus dem Baum ausgelassen werden.

Das Erstellen von ASTs kann auf zwei Arten erfolgen:

1. Verwenden Sie Rewrite-Regeln, die wie folgt aussehen: foo : A B C D -> ^(D A B);wo foo ist eine Parser-Regel, die mit den Token übereinstimmt A B C D. Also alles nach dem -> ist die eigentliche Umschreibungsregel. Wie Sie sehen können, das Token C wird in der Rewrite-Regel nicht verwendet, was bedeutet, dass es aus dem AST weggelassen wird. Der Token, der direkt nach dem platziert wird ^( wird die Wurzel des Baumes werden;
2. Verwenden Sie die Baumoperatoren ^ und ! nach ein Token in Ihren Parser-Regeln, wo ^ wird ein Token zum Stamm machen, und ! löscht ein Token aus dem Baum. Das Äquivalent für foo : A B C D -> ^(D A B); wäre foo : A B C! D^;

Beide foo : A B C D -> ^(D A B); und foo : A B C! D^; erzeugt die folgende AST:

Nun könnten Sie die Grammatik wie folgt umschreiben:

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

wodurch der folgende AST aus der Quelle erstellt wird "true && (false || true && (true || false))":

Zugehörige ANTLR-Wiki-Links:

• Baumkonstruktion
• Baum-Parsing
• Baumbauanlagen

Raffael schrieb:

Ich denke derzeit, dass die Knoten auf diesem AST zum Erstellen von SSA verwendet werden, gefolgt von einer Datenflussanalyse, um den statischen Analysator zu erstellen. Bin ich auf dem richtigen Weg?

Ich habe so etwas noch nie gemacht, aber meiner Meinung nach ist das erste, was Sie wollen, ein AST von der Quelle, also ja, ich denke, Sie sind auf dem richtigen Weg! 🙂

BEARBEITEN

So können Sie den generierten Lexer und Parser verwenden:

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