Che cosa è un albero parser in ANTLR e sono costretto a scrivere?

StackOverflow https://stackoverflow.com/questions/697755

Domanda

Sto scrivendo un lexer/parser per un piccolo sottoinsieme di C ANTLR che verrà eseguito in ambiente Java.Io sono nuovo del mondo di lingua grammatiche e in molti ANTLR tutorial, creare un AST - Albero di Sintassi Astratta, sono costretto a creare e perché?

È stato utile?

Soluzione 2

Ho trovato questa risposta alla domanda su jGuru scritto da Terence Parr, che ha creato ANTLR.Ho copiato questa spiegazione dal sito collegato qui:

Solo semplice, i cosiddetti sintassi per la regia di traduzioni può essere fatto con azioni entro il parser.Questi tipi di traduzioni possono sputare fuori costrutti che sono funzioni di informazioni già visto a che punto l'analisi.Albero parser permetterà di raggiungere a piedi una forma intermedia e manipolare come un albero che, gradualmente morphing molti di traduzione fasi di una forma finale che può essere facilmente stampato torna come nuova traduzione.

Immaginate un semplice problema di traduzione in cui si desidera stampare una pagina html il cui titolo è "Ci sono n elementi", dove n è il numero di identificatori che si trova nel flusso di input.L'id deve essere stampato dopo il titolo di questo genere:

<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>

da ingresso

Dog
Cat
Velociraptor

Così, con semplici azioni in grammatica come si calcola il titolo?Non è possibile senza leggere tutta la voce.Ok, ora sappiamo che abbiamo bisogno di una forma intermedia.Il migliore è di solito un AST ho trovato il dato che si registra l'ingresso della struttura.In questo caso, è solo un elenco, ma dimostra il mio punto.

Ok, ora si sa che un albero è una buona cosa per nulla, ma di semplici traduzioni.Dato un AST, come si ottiene in uscita da esso?Immaginate semplice espressione di alberi.Un modo è quello di rendere i nodi nell'albero classi specifiche come PlusNode, IntegerNode e così via.Poi basta chiedere a ciascun nodo di stampare da sé.Per l'ingresso, 3+4 si avrebbe 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();
  }
}

Data una struttura ad albero dell'espressione, si può tradurre in testo con t.toString().QUINDI, cosa c'è di sbagliato in questo?Sembra funzionare alla grande, giusto?Sembra funzionare bene, in questo caso, perché è semplice, ma io sostengo che, anche per questo semplice esempio, l'albero di grammatiche sono più leggibili e sono formalizzate le descrizioni di esattamente ciò che è codificato nel PlusNode.toString().

expr returns [String r]
{
    String left=null, right=null;
}

: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT                       {r=i.getText();}
;

Si noti che la classe specifica ("eterogenei AST") strategia di codifica per una completa ricorsiva-discesa parser per #(+ INT INT) a mano in toString().Come generatore di parser gente, questo dovrebbe far rabbrividire.;)

La principale debolezza dell'eterogeneo AST approccio è che si può comodamente accedere alle informazioni di contesto.In un ricorsiva-discesa parser, il contesto è facilmente accessibile perché può essere passato come parametro.Inoltre sapete proprio che regola può invocare, quale altra regola (per esempio, è questa espressione un po di condizione o di una condizione IF?) guardando la grammatica.Il PlusNode classe di cui sopra esiste in una villetta isolata mondo in cui si ha idea di chi si invoca il metodo toString ().Peggio, il programmatore può dire in che contesto, è richiamato da lettura.

In sintesi, l'aggiunta di azioni di input funzionamento del parser molto semplice traduzioni dove:

  1. l'ordine di uscita dei costrutti è lo stesso come input ordine
  2. tutti i costrutti possono essere generate dalle informazioni analizzate fino al punto che quando hai bisogno di loro sputare

Al di là di questo, avrete bisogno di una forma intermedia--l'AST è la migliore forma di solito.Utilizzando una grammatica per descrivere la struttura dell'AST è analogo all'utilizzo di una grammatica per analizzare il testo di input.Formalizzate le descrizioni in un dominio specifico di linguaggio di alto livello come ANTLR sono migliori di mano codificato parser.Azioni all'interno di un albero di grammatica hanno molto chiaro il contesto e la comodità di poter accedere alle informazioni passate da invocare rlues.Traduzioni di manipolare l'albero per multipass anche le traduzioni sono molto più semplice utilizzando un albero di grammatica.

Altri suggerimenti

La creazione di un AST con ANTLR è incorporato nella grammatica. Non è necessario per fare questo, ma è un ottimo strumento per le esigenze più complesse. Si tratta di un tutorial su costruzione albero è possibile utilizzare.

In sostanza, con ANTLR quando la sorgente è sempre analizzato, avete alcune opzioni. È possibile generare il codice o un AST utilizzando regole di riscrittura nella tua grammatica. Un AST è fondamentalmente un nella rappresentazione di memoria della vostra sorgente. Da lì, c'è molto che si può fare.

C'è molto da ANTLR. Se non l'hai già, io vi consiglio di prendere il libro .

Credo che la creazione del AST è opzionale. Il Abstract Syntax Albero è utile per la successiva elaborazione come l'analisi semantica del programma analizzato.

Solo tu puoi decidere se è necessario creare uno. Se il vostro unico obiettivo è la convalida sintattica, allora non è necessario per generare uno. In JavaCC (simile a ANTLR) c'è un utility chiamato JJTree che permette la generazione di AST. Quindi immagino che questo è facoltativo in ANTLR pure.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top