Vantaggi di Antlr (rispetto a dire, lex / yacc / bison) [chiuso]

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

  •  03-07-2019
  •  | 
  •  

Domanda

Ho usato lex e yacc (più spesso bisonti) in passato per vari progetti, di solito traduttori (come un sottoinsieme di EDIF trasmesso in streaming in un'app EDA). Inoltre, ho dovuto supportare il codice basato su grammatiche lex / yacc risalenti a decenni fa. Quindi conosco il mio modo di aggirare gli strumenti, anche se non sono un esperto.

Ho visto commenti positivi su Antlr in varie sedi in passato e sono curioso di sapere cosa potrei perdere. Quindi, se hai usato entrambi, per favore dimmi cosa c'è di meglio o di più avanzato in Antlr. I miei attuali vincoli sono che lavoro in un negozio C ++ e qualsiasi prodotto che spediamo non includerà Java, quindi i parser risultanti dovrebbero seguire quella regola.

È stato utile?

Soluzione

Aggiornamento / avviso: questa risposta potrebbe non essere aggiornata!

Una delle principali differenze è che ANTLR genera un parser LL (*), mentre YACC e Bison generano entrambi parser LALR. Questa è una distinzione importante per una serie di applicazioni, i più ovvi sono gli operatori: 

expr ::= expr '+' expr
       | expr '-' expr
       | '(' expr ')'
       | NUM ;

ANTLR è totalmente incapace di gestire questa grammatica così com'è. Per usare ANTLR (o qualsiasi altro generatore di parser LL), devi convertire questa grammatica in qualcosa che non è ricorsivo a sinistra. Tuttavia, Bison non ha alcun problema con le grammatiche di questo modulo. Dovresti dichiarare "+" e "-" come operatori associativi di sinistra, ma ciò non è strettamente necessario per la ricorsione di sinistra. Un esempio migliore potrebbe essere l'invio: 

expr ::= expr '.' ID '(' actuals ')' ;

actuals ::= actuals ',' expr | expr ;

Nota che entrambe le regole expr e actuals sono ricorsive a sinistra. Questo produce un AST molto più efficiente quando arriva il momento della generazione del codice perché evita la necessità di più registri e fuoriuscite inutili (un albero inclinato a sinistra può essere compresso mentre un albero inclinato a destra non può).

In termini di gusti personali, penso che le grammatiche LALR siano molto più facili da costruire e da debug. Il rovescio della medaglia è che devi affrontare errori in qualche modo criptici come il cambio-riduzione e (il temuto) ridurre-ridurre. Questi sono errori che Bison rileva durante la generazione del parser, quindi non influisce sull'esperienza dell'utente finale, ma può rendere il processo di sviluppo un po 'più interessante. ANTLR è generalmente considerato più facile da usare rispetto a YACC / Bison proprio per questo motivo.

Altri suggerimenti

La differenza più significativa tra YACC / Bison e ANTLR è il tipo di grammatiche che questi strumenti possono elaborare. YACC / Bison gestiscono le grammatiche LALR, ANTLR gestisce le grammatiche LL.

Spesso, le persone che hanno lavorato con le grammatiche LALR per molto tempo, troveranno più difficile lavorare con le grammatiche LL e viceversa. Ciò non significa che le grammatiche o gli strumenti siano intrinsecamente più difficili da lavorare. Lo strumento che trovi più facile da usare dipenderà principalmente dalla familiarità con il tipo di grammatica.

Per quanto riguarda i vantaggi, ci sono aspetti in cui le grammatiche LALR presentano vantaggi rispetto alle grammatiche LL e ci sono altri aspetti in cui le grammatiche LL presentano vantaggi rispetto alle grammatiche LALR.

YACC / Bison genera parser guidati da tabella, il che significa che la "logica di elaborazione" è contenuto nei dati del programma parser, non tanto nel codice del parser. Il risultato è che anche un parser per un linguaggio molto complesso ha un footprint di codice relativamente piccolo. Ciò era più importante negli anni '60 e '70, quando l'hardware era molto limitato. I generatori di parser guidati da tabelle risalgono a questa era e il footprint di codice ridotto era un requisito fondamentale allora.

ANTLR genera parser di discesa ricorsivi, il che significa che la "logica di elaborazione" è contenuto nel codice del parser, poiché ogni regola di produzione della grammatica è rappresentata da una funzione nel codice del parser. Il vantaggio è che è più facile capire cosa sta facendo il parser leggendo il suo codice. Inoltre, i parser di discesa ricorsivi sono in genere più veloci di quelli guidati da tabella. Tuttavia, per linguaggi molto complessi, l'impronta del codice sarà maggiore. Questo è stato un problema negli anni '60 e '70. All'epoca, solo linguaggi relativamente piccoli come Pascal, per esempio, erano implementati in questo modo a causa di limitazioni hardware.

I parser generati da ANTLR sono in genere nelle vicinanze di 10.000 righe di codice e altro ancora. I parser di discesa ricorsivi scritti a mano sono spesso nello stesso campo. Il compilatore Oberon di Wirth è forse il più compatto con circa 4000 righe di codice inclusa la generazione di codice, ma Oberon è un linguaggio molto compatto con solo circa 40 regole di produzione.

Come qualcuno ha già sottolineato, un grande vantaggio per ANTLR è lo strumento grafico IDE, chiamato ANTLRworks. È un laboratorio completo di progettazione grammaticale e linguistica. Visualizza le tue regole grammaticali mentre le digiti e se trova dei conflitti ti mostrerà graficamente qual è il conflitto e cosa lo causa. Può anche refactoring e risolvere automaticamente conflitti come la ricorsione a sinistra. Una volta che hai una grammatica libera da conflitti, puoi consentire ad ANTLRworks di analizzare un file di input della tua lingua e creare un albero di analisi e AST per te e mostrarlo graficamente nell'IDE. Questo è un grande vantaggio perché può farti risparmiare molte ore di lavoro: troverai errori concettuali nella progettazione del tuo linguaggio prima di iniziare a scrivere codice! Non ho trovato nessuno strumento simile per le grammatiche LALR, sembra che non esista tale strumento.

Anche per le persone che non desiderano generare i loro parser ma che li codificano manualmente, ANTLRworks è un ottimo strumento per la progettazione / prototipazione del linguaggio. Molto probabilmente il miglior strumento disponibile. Sfortunatamente, questo non ti aiuta se vuoi costruire parser LALR. Passare da LALR a LL semplicemente per trarre vantaggio da ANTLRworks può essere utile, ma per alcune persone, cambiare tipo di grammatica può essere un'esperienza molto dolorosa. In altre parole: YMMV.

Un paio di vantaggi per ANTLR:

  • può generare parser in varie lingue - Java non è richiesto per eseguire il parser generato.
  • La straordinaria GUI semplifica il debug della grammatica (ad esempio puoi vedere gli AST generati direttamente nella GUI, non sono necessari strumenti extra)
  • Il codice generato è in realtà leggibile dall'uomo (è uno degli obiettivi di ANTLR) e il fatto che genera parser LL sicuramente aiuta in questo senso.
  • la definizione di terminali è anche libera dal contesto (al contrario di regex in (f) lex) - permettendo così, ad esempio, la definizione di terminali contenente parentesi ben chiuse

Il mio .02 $

Un altro vantaggio di ANTRL è che puoi utilizzare ANTLRWORKS , anche se non posso dire che questo è un vantaggio rigoroso, poiché potrebbero esserci strumenti simili anche per altri generatori.

  • Bison e Flex producono un ingombro di memoria ridotto, ma non si ha un IDE grafico.
  • antlr utilizza più memoria, ma hai antlrworks, un IDE grafico.

L'uso della memoria Bison / Flex è in genere un mbyte o giù di lì. Contrastalo con antlr - supponendo che utilizzi 512 byte di memoria per ogni token nel file che vuoi analizzare. 4 milioni di token e la memoria virtuale è esaurita su un sistema a 32 bit.

Se il file che si desidera analizzare è grande, antlr potrebbe esaurire la memoria, quindi se si desidera solo analizzare un file di configurazione, sarebbe una soluzione praticabile. Altrimenti, se vuoi analizzare un file con molti dati, prova Bison.

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