Esercitazione per camminare con ANTLR AST in C#?

Question

Qualcuno è a conoscenza delle esercitazioni per la guida di AST generati da ANTLR in C#? Il più vicino che sono stato in grado di trovare è this, ma non è molto utile.

Il mio obiettivo è quello di camminare tra gli alberi che sto generando in base a un linguaggio specifico del dominio su cui sto lavorando e di utilizzare gli alberi per generare il codice C# generato.

Anche un tutorial basato su Java può essere utile: qualsiasi cosa che fornisca esempi chiari su come attraversare gli AST ANTLR.

Answer 1

Sono riuscito a capirlo adattando l'esempio alla fine di Manuel Abadia's article.

Ecco la mia versione, che mi è capitato di utilizzare per convertire il codice analizzato in C#. Questi sono i passi:

1. istanziare un ANTLRStringStream o sottoclasse con il vostro ingresso (che può essere un file o una stringa).
2. Istanzia il tuo lexer generato, passando in quello stream di stringhe.
3. Istanzia un flusso di token con il lexer.
4. Istanzia il parser con quel flusso di token.
5. Ottieni il valore di primo livello dal parser e trasformalo in CommonTree.
6. attraversare l'albero:

Per ottenere il testo letterale di un nodo, utilizzare node.Text. Per ottenere il nome del token di un nodo, utilizzare node.Token.Text.

Nota che node.Token.Text solo vi darà il nome effettivo del token se si tratta di un token immaginario con nessuna stringa corrispondente. Se si tratta di un vero token, quindi node.Token.Text restituirà la stringa.

Ad esempio, se si ha il seguente nella tua grammatica:

tokens { PROGRAM, FUNCDEC } 

EQUALS : '=='; 
ASSIGN : '='; 

allora avrai "PROGRAM", "FUNCDEC", "==", e "=" dai corrispondenti accessi di node.Token.Text.

Puoi vedere parte del mio esempio qui sotto, oppure puoi sfogliare lo full version.

---

public static string Convert(string input) 
{ 
    ANTLRStringStream sStream = new ANTLRStringStream(input); 
    MyGrammarLexer lexer = new MyGrammarLexer(sStream); 

    CommonTokenStream tStream = new CommonTokenStream(lexer); 

    MyGrammarParser parser = new MyGrammarParser (tStream); 
    MyGrammarParser.program_return parserResult = parser.program(); 

    CommonTree ast = (CommonTree)parserResult.Tree; 

    Print(ast); 
    string output = header + body + footer; 

    return output; 
} 

public static void PrintChildren(CT ast) 
{ 
    PrintChildren(ast, " ", true); 
} 

public static void PrintChildren(CT ast, string delim, bool final) 
{ 
    if (ast.Children == null) 
    { 
     return; 
    } 

    int num = ast.Children.Count; 

    for (int i = 0; i < num; ++i) 
    { 
     CT d = (CT)(ast.Children[i]); 
     Print(d); 
     if (final || i < num - 1) 
     { 
      body += delim; 
     } 
    } 
} 

public static void Print(CommonTree ast) 
{ 
    switch (ast.Token.Text) 
    { 
     case "PROGRAM": 
      //body += header; 
      PrintChildren(ast); 
      //body += footer; 
      break; 
     case "GLOBALS": 
      body += "\r\n\r\n// GLOBALS\r\n"; 
      PrintChildren(ast); 
      break; 
     case "GLOBAL": 
      body += "public static "; 
      PrintChildren(ast); 
      body += ";\r\n"; 
      break; 

     .... 
    } 
} 

Answer 2

Normalmente si cammina con gli AST con ricorsione e si eseguono azioni diverse in base al tipo di nodo. Se stai usando nodi ad albero polimorfici (cioè sottoclassi differenti per nodi diversi nell'albero), allora il doppio invio nel pattern Visitor potrebbe essere appropriato; tuttavia, di solito non è molto conveniente con Antlr.

In pseudocodice, camminando di solito si presenta un po 'come questo:

func processTree(t) 
    case t.Type of 
     FOO: processFoo t 
     BAR: processBar t 
    end 

// a post-order process 
func processFoo(foo) 
    // visit children 
    for (i = 0; i < foo.ChildCount; ++i) 
     processTree(foo.GetChild(i)) 
    // visit node 
    do_stuff(foo.getText()) 

// a pre-order process 
func processBoo(bar) 
    // visit node 
    do_stuff(bar.getText()) 
    // visit children 
    for (i = 0; i < foo.ChildCount; ++i) 
     processTree(foo.GetChild(i)) 

I tipi di trattamento sono altamente dipendenti sulla semantica del linguaggio. Ad esempio, la gestione di una IF dichiarazione, con struttura (IF <predicate> <if-true> [<if-false>]), quando la generazione di codice per una macchina di stack come la JVM o CLR, potrebbe apparire un po 'come questo:

func processIf(n) 
    predicate = n.GetChild(0) 
    processExpr(predicate) // get predicate value on stack 
    falseLabel = createLabel() 
    genCode(JUMP_IF_FALSE, falseLabel) // JUMP_IF_FALSE is called brfalse in CLR, 
             // ifeq in JVM 
    if_true = n.GetChild(1) 
    processStmt(if_true) 
    if_false = n.ChildCount > 2 ? n.GetChild(2) : null 
    if (if_false != null) 
     doneLabel = createLabel() 
     genCode(JUMP, doneLabel) 
    markLabel(falseLabel) 
    if (if_false != null) 
     processStmt(if_false) // if-false branch 
     markLabel(doneLabel) 

In generale tutto è fatto in modo ricorsivo a seconda del tipo di corrente nodo, ecc.

Answer 3

Si dovrebbe esaminare la scrittura di un TreeParser; può rendere il compito di interpretare l'albero molto più semplice.

Per 2.x ANTLR vedere http://www.antlr2.org/doc/sor.html Per 3.x ANTLR vedere (ad esempio parser e albero parser basato su Java) http://www.antlr.org/wiki/display/ANTLR3/Tree+construction

Answer 4

ho fatto qualcosa di simile (ma non proprio) e ho finito con un TreeParser.

Suggerisco inoltre di acquistare il libro ANTLR. Ho trovato che è più prezioso di qualsiasi risorsa web. Potrebbe non avere tutte le risposte, ma sicuramente aiuta con le basi.