parser LALR vs LL

Question

Ho usato lex/yacc e ora sto cercando di passare a ANTLR. La principale preoccupazione è che ANTLR è un parser LL (*) a differenza di yacc che è LALR. Sono abituato a pensare dal basso e non so esattamente quale sia il vantaggio delle grammatiche LL. La gente dice che le grammatiche LL sono più facili da capire e più popolari in questi giorni. Ma sembra che i parser LR siano più potenti per es. I parser LL non sono in grado di gestire le ricorsioni a sinistra, anche se sembrano esserci alcuni rimedi.

Quindi la domanda è qual è il vantaggio delle grammatiche LL su LALR? Lo apprezzerei se qualcuno potesse darmi qualche esempio. Anche i collegamenti ad articoli utili sarebbero fantastici.

Grazie per il vostro aiuto in anticipo!

(vedo questa è una grande risorsa:. What advantages do LL parsers have over LR parsers?, ma sarebbe stato meglio con alcuni esempi)

Answer 1

Il più grande vantaggio che vedo a LL parser è che sono così facili da capire e da implementare! Puoi scrivere a mano i parser recursive descent con codice che corrisponde strettamente alla grammatica.

LR sono generalmente considerati più potente e anche molto più veloce, ma ci sono alcuni compromessi che conosco:

• parser LR possono utilizzare solo attributi sintetizzati; non possono passare attributi ereditati.
• Le azioni in una grammatica LR possono causare non determinismo grammaticale ma non in LL.

Tuttavia, troverete che LL (*) sono anche molto potenti.

Answer 2

I parser LR sono molto più potenti dei parser LL e inoltre, i parser LALR possono essere eseguiti in O (n) come i parser LL. Quindi non troverai alcun vantaggio funzionale di LL su LR.

Quindi, l'unico vantaggio di LL è che le macchine a stati LR sono un po 'più complesse e difficili da comprendere, e gli analizzatori LR non sono particolarmente intuitivi. D'altra parte, il codice parser LL che viene generato automaticamente può essere molto facile da capire e correggere.