Sto scrivendo un lexer/parser per un piccolo sottoinsieme di C in ANTLR che verrà eseguito in un ambiente Java. Sono nuovo nel mondo delle grammatiche linguistiche e in molte delle esercitazioni ANTLR, creano un AST - Abstract Syntax Tree, sono costretto a crearne uno e perché?Che cos'è un parser ad albero in ANTLR e sono obbligato a scriverne uno?
Ho trovato this answer alla domanda su jGuru scritta da Terence Parr, che ha creato ANTLR. Ho copiato questa spiegazione dal sito collegato here:
Solo traduzioni semplici, cosiddette di sintassi diretta possono essere eseguite con azioni all'interno del parser. Questi tipi di traduzioni possono solo sputare costrutti che sono funzioni di informazioni già viste in quel momento nel parse. I parser degli alberi consentono di percorrere una forma intermedia e di manipolare quell'albero, trasformandolo gradualmente in più fasi di traduzione in una forma finale che può essere facilmente stampata come nuova traduzione.
Immagina un semplice problema di traduzione in cui desideri stampare una pagina html il cui titolo è "Ci sono n elementi" dove n è il numero di identificatori che hai trovato nel flusso di input. Gli id devono essere stampati dopo il titolo come questo:
<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>
dall'input
Dog
Cat
Velociraptor
Quindi, con semplici azioni nella tua grammatica come si può calcolare il titolo? Non puoi senza leggere l'intero input. Ok, ora sappiamo che abbiamo bisogno di un modulo intermedio. Il migliore è di solito un AST che ho trovato dal momento che registra la struttura di input. In questo caso, è solo una lista ma dimostra il mio punto.
Ok, ora sai che un albero è una cosa buona per tutto tranne le traduzioni semplici. Dato un AST, come si ottiene output da esso? Immagina alberi di espressione semplici. Un modo è quello di rendere i nodi nelle classi specifiche dell'albero come PlusNode, IntegerNode e così via. Quindi basta chiedere a ciascun nodo di stamparsi.Per l'input, 3 + 4 si dovrebbe avere albero:
+ | 3-4
e classi
class PlusNode extends CommonAST {
public String toString() {
AST left = getFirstChild();
AST right = left.getNextSibling();
return left + " + " + right;
}
}
class IntNode extends CommonAST {
public String toString() {
return getText();
}
}
Dato un albero di espressione, si può tradurre in testo con t.toString(). COSÌ, cosa c'è di sbagliato in questo? Sembra funzionare bene, giusto? Sembra funzionare bene in questo caso perché è semplice, ma sostengo che, anche per questo semplice esempio, le grammatiche degli alberi sono più leggibili e sono descrizioni formalizzate di esattamente ciò che hai codificato in PlusNode.toString().
expr returns [String r]
{
String left=null, right=null;
}
: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT {r=i.getText();}
;
Nota che la classe specifica ("AST eterogenea") approccio in realtà codifica per un parser completo ricorsiva-discesa per # (+ INT INT) a mano in toString(). Come gente del generatore di parser, questo dovrebbe farti rabbrividire. ;)
Il principale punto debole dell'approccio AST eterogeneo è che non può accedere comodamente alle informazioni di contesto. In un parser ricorsivo-discendente, il contesto è facilmente accessibile perché può essere passato come parametro. Sai anche quale regola può invocare quale altra regola (ad esempio, questa espressione è una condizione WHILE o una condizione IF?) Osservando la grammatica. La classe PlusNode sopra esiste in un mondo distaccato e isolato in cui non ha idea di chi invocherà il suo metodo toString(). Peggio ancora, il programmatore non può dire in quale contesto verrà invocato leggendolo.
In sintesi, l'aggiunta di azioni ai tuoi lavori ingresso parser per le traduzioni molto semplici dove:
Oltre a questo, è necessario un modulo intermedio - l'AST è la forma migliore di solito. L'uso di una grammatica per descrivere la struttura dell'AST è analogo all'utilizzo di una grammatica per analizzare il testo inserito. Le descrizioni formalizzate in un linguaggio di alto livello specifico del dominio come ANTLR sono migliori dei parser codificati a mano. Le azioni all'interno di una grammatica ad albero hanno un contesto molto chiaro e possono comodamente accedere alle informazioni trasmesse dal richiamo di rlues. Le traduzioni che manipolano l'albero per le traduzioni multipass sono anche molto più semplici usando una grammatica ad albero.
Creazione di un AST con ANTLR è incorporato nella grammatica. Non devi farlo, ma è un ottimo strumento per requisiti più complicati. Questo è un tutorial sulla costruzione di alberi che è possibile utilizzare.
Fondamentalmente, con ANTLR quando viene analizzata la sorgente, sono disponibili alcune opzioni. Puoi generare codice o un AST usando le regole di riscrittura nella tua grammatica. Un AST è fondamentalmente una rappresentazione in memoria della tua fonte. Da lì, c'è molto che puoi fare.
C'è molto da ANTLR. Se non lo hai già, mi consiglia di ottenere the book.
Penso che la creazione di AST sia facoltativa. Lo Abstract Syntax Tree è utile per l'elaborazione successiva come l'analisi semantica del programma analizzato.
Solo tu puoi decidere se devi crearne uno. Se il tuo unico obiettivo è la convalida sintattica, non è necessario generarne uno. In javacc (simile a ANTLR) è disponibile l'utilità denominata JJTree che consente di generare l'AST. Quindi immagino che questo sia opzionale anche in ANTLR.