Vantaggi di Antlr (rispetto ad esempio, lex/yacc/bison)

Vantaggi di Antlr (rispetto ad esempio, lex/yacc/bison)

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 che sono LALR. Questa è una distinzione importante per un certo numero di applicazioni, la più ovvia sono gli operatori:

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

ANTLR è del tutto incapace di gestire questa grammatica così com'è. Per utilizzare ANTLR (o qualsiasi altro generatore di parser LL), dovresti convertire questa grammatica in qualcosa che non sia ricorsivo a sinistra. Tuttavia, Bison non ha problemi con le grammatiche di questa forma. Dovresti dichiarare '+' e '-' come operatori associativi a sinistra, ma ciò non è strettamente richiesto per la ricorsione a sinistra. Un esempio migliore potrebbe essere la spedizione:

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

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

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

In termini di gusto personale, penso che le grammatiche LALR siano molto più facili da costruire ed eseguire il debug. Il rovescio della medaglia è che devi affrontare errori alquanto criptici come shift-reduce e (il temuto) reduce-reduce. 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 di YACC/Bison proprio per questo motivo.


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

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

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

YACC/Bison genera parser guidati da tabelle, il che significa che la "logica di elaborazione" è contenuta nei dati del programma del parser, non tanto nel codice del parser. Il vantaggio è che anche un parser per un linguaggio molto complesso ha un footprint di codice relativamente piccolo. Questo era più importante negli anni '60 e '70, quando l'hardware era molto limitato. I generatori di parser guidati da tabelle risalgono a quest'epoca e all'epoca il ridotto ingombro del codice era un requisito principale.

ANTLR genera parser discendenti ricorsivi, il che significa che la "logica di elaborazione" è contenuta 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 tabelle. Tuttavia, per linguaggi molto complessi, l'impronta del codice sarà maggiore. Questo era un problema negli anni '60 e '70. All'epoca, solo linguaggi relativamente piccoli come Pascal, ad esempio, venivano implementati in questo modo a causa di limitazioni hardware.

I parser generati da ANTLR sono in genere in prossimità di 10.000 righe di codice e oltre. I parser di discesa ricorsivi scritti a mano si trovano spesso nello stesso campo di gioco. Il compilatore Oberon di Wirth è forse il più compatto con circa 4000 righe di codice inclusa la generazione del 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 grammatica e design del linguaggio. 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 senza conflitti, puoi lasciare che ANTLRworks analizzi un file di input della tua lingua e costruisca un albero di analisi e AST per te e mostri l'albero 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 programmare! Non ho trovato alcuno strumento del genere per le grammatiche LALR, sembra che non ci sia alcuno strumento del genere.

Anche per le persone che non desiderano generare i propri parser ma codificarli 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. Può essere utile passare da LALR a LL semplicemente per sfruttare ANTLRworks, 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 vari linguaggi - Java non è richiesto per eseguire il parser generato.
  • La straordinaria GUI semplifica il debug della grammatica (ad es. puoi vedere gli AST generati direttamente nella GUI, senza bisogno di strumenti aggiuntivi)
  • Il codice generato è effettivamente leggibile dall'uomo (è uno degli obiettivi di ANTLR) e il fatto che generi parser LL aiuta sicuramente in questo senso.
  • Anche la definizione di terminali è priva di contesto (al contrario di regex in (f)lex) - consentendo così, ad esempio, la definizione di terminali contenente parentesi ben chiuse

I miei 0,02$