Quali vantaggi hanno i parser LL rispetto ai parser LR?

Question

Quali vantaggi hanno i parser LL su parser LR per garantire la relativa popolarità in today's parser generator tools?

Secondo Wikipedia, LR analisi sembra avere vantaggi rispetto LL:

LR analisi in grado di gestire una gamma più ampia di lingue diverse LL analisi, ed è anche meglio a segnalazione degli errori, vale a dire che rileva gli errori sintattici quando l'input non è conforme alla grammatica il prima possibile. Questo è in contrasto con un LL (k) (o anche peggio, un parser LL (*)) che può differire il rilevamento degli errori in un ramo diverso della grammatica a causa del backtracking, spesso rendendo gli errori più difficili da localizzare attraverso disgiunzioni con lunghi prefissi comuni .

Nota: questo non è compito. Sono stato sorpreso quando ho scoperto che Antlr è un generatore di parser LL (nonostante abbia "LR" nel suo nome!).

Answer 1

GLR è ottimo se si desidera un albero/foresta di analisi e non si preoccupa delle scatole nere. Ti consente di digitare qualsiasi cosa CFG a costo di verificare le ambiguità in fase di analisi tramite test approfonditi, invece di risolvere i conflitti LR/LALR in modo statico. Alcuni dicono che è un buon compromesso. Lo strumento DMS di Ira Baxter o Elkhound, che ha una grammatica C++ libera, è utile per questa classe di problemi. ANTLR è utile anche per un'ampia classe di applicazioni linguistiche, ma utilizza un approccio top-down, generando parser di discesa ricorsivi chiamati LL (*) che consentono i predicati semantici. Qui dichiarerò senza prove che i predicati consentono di analizzare i linguaggi sensibili al contesto oltre i CFG. Ai programmatori piace inserire azioni in grammatiche, come una buona gestione degli errori, e come il debug in un unico passaggio.LL è buono a tutti e tre. LL è ciò che facciamo a mano, quindi è più facile da capire. Non credere allo wikipedia nonsense about LR being better at handling errors. Detto questo, se si esegue un backtrack molto con ANTLR, gli errori sono effettivamente peggiori con LL (*) (i PEG hanno questo problema).

Re backtracking. GLR specula (vale a dire backtrack) anche, proprio come PEG, ANTLR e qualsiasi altra strategia non deterministica. In qualsiasi stato LR non deterministico, i sotto-parser GL "forks" consentono di provare qualsiasi percorso percorribile. Ad ogni modo, LL ha un buon contesto per la gestione degli errori. Dove LR sa che corrisponde ad un'espressione, LL sa che è un'espressione in un compito o IF -conditional; LR sa che potrebbe essere in entrambi ma non è sicuro - e che l'incertezza è dove ottiene il suo potere.

GLR è O(n^3) caso peggiore. packrat/PEG è il peggior caso O(n). Le ANTLR sono O(n^2) a causa del DFA lookahead ciclico ma in pratica O(n). Non importa davvero GLR è abbastanza veloce.

ANTLR è AN altro T ool per L ang R eCognition non anti-LR, ma mi piace anche quello;)

Francamente, come un sacco di giovani programmatori negli anni '80, non capivo LALR e non mi piacevano le scatole nere (ora scavo la bellezza del motore GLR ma preferisco comunque LL). Ho costruito un compilatore commerciale basato su LL (k) e ho deciso di creare uno strumento per generare ciò che avevo costruito a mano. ANTLR non è per tutti e casi limite come C++ potrebbero essere meglio gestiti con GLR ma molte persone trovano ANTLR adatto alla loro zona di comfort. Dal gennaio 2008, ci sono stati 134.000 download del barattolo binario di ANTLR, all'interno di ANTLRWorks, e il totale delle zips di origine (secondo Google Analytics). Vedi our paper su LL (*) con molti dati empirici.

Answer 2

Una ragione che viene in mente è che è molto più facile fare un linguaggio che ha bisogno backtracking arbitraria (tosse C++) in un paradigma LL.

Answer 3

Dalla mia esperienza personale (l'ho usato sia per varie situazioni), la differenza più pratica è che, con un LL (k), è possibile definire la grammatica in un modo più semplice (poiché è dall'alto verso il basso) senza preoccuparsi molti possibili conflitti di riduzione-riduzione o riduzione-spostamento che si verificano spesso con parser LR. L'unica cosa di cui ti devi preoccupare è la ricorsione a sinistra che deve essere trasformata in quella giusta.

Un'altra cosa è che l'approccio top-down di solito implica una complessità più alta (rispetto allo spazio o al tempo), perché deve memorizzare l'intero albero durante l'analisi e può crescere molto finché non si risolvono le ambiguità.

Answer 4

Se si ha a portata di mano il codice uno, la discesa ricorsiva (LL) è qualcosa che si può fare realisticamente; le persone non possono costruire manualmente parser L (AL) R praticamente a mano.

Dato che i moderni generatori di parser gestiranno tutta la struttura del parser per te, e che lo spazio non è un gran problema, preferisco i parser LR perché non devi combattere con le grammatiche tanto per renderle valide per il tuo particolare generatore di parser (nessuna "rimozione di tutte le sciocchezze di sinistra").

In effetti, preferisco lo GLR parsers, che analizzerà praticamente qualsiasi cosa con una grammatica senza contesto. Nessun problema di ricorsione a sinistra. Nessuno spostamento/riduzione delle preoccupazioni sui conflitti. Nessun limite di lookahead.

Se volete vedere la gamma di lingue che uno GLR motore di parsing in grado di gestire (tra cui il famoso hard-to-parse-con-LL/lingua LALR, C++), si può guardare here.

Answer 5

L'unico vantaggio che ho mai avuto è che puoi facilmente codificare i parser LL a mano. I parser LR sono MOLTO più difficili da codificare a mano (di solito si usa un generatore di parser).

Answer 6

LL La peggiore complessità delle analisi è O (n^4), mentre la peggiore complessità di LR parsing è migliore, O (n^3).

(. Ma nessuno avrebbe mai scrivere O (n^4) grammatica)

https://en.wikipedia.org/wiki/Top-down_parsing