Quali sono i principali vantaggi e svantaggi dell'analisi LL e LR?

Contrasto l'analisi LL e LR per una serie di criteri:

Complessità

LL vince qui, a mani basse. Puoi facilmente scrivere a mano un parser LL. In realtà, questo è comunemente fatto: il compilatore Microsoft C # è un parser di discesa ricorsivo scritto a mano (fonte qui , cerca un commento fatto da Patrick Kristiansen - anche il post sul blog è molto interessante.

L'analisi LR utilizza un metodo piuttosto intuitivo per analizzare un testo. Funziona, ma mi ci è voluto un po 'di tempo per capire come funziona esattamente. Scrivere a mano un parser di questo tipo è quindi difficile: dovresti implementare più o meno un generatore di parser LR.

Generalità

LR vince qui: tutte le lingue LL sono lingue LR, ma ci sono più lingue LR rispetto alle lingue LL (una lingua è una lingua LL se può essere analizzata con un parser LL e una lingua è una lingua LR se può essere analizzato con un parser LR).

LL ha un bel po 'di fastidio che ti infastidirà quando implementerai praticamente qualsiasi linguaggio di programmazione. Vedi qui per una panoramica.

Esistono lingue non ambigue che non sono lingue LR, ma quelle sono piuttosto rare. Non si incontrano quasi mai tali linguaggi. Tuttavia, LALR ha alcuni problemi.

LALR è più o meno un trucco per i parser LR per rendere le tabelle più piccole. Le tabelle per un parser LR possono in genere crescere enormemente. I parser LALR lasciano la possibilità di analizzare tutte le lingue LR in cambio di tabelle più piccole. La maggior parte dei parser LR usa effettivamente LALR (non in modo segreto, ma di solito è possibile trovare esattamente ciò che implementa).

LALR può lamentarsi dei conflitti di riduzione del turno e riduzione-riduzione. Questo è causato dalla modifica della tabella: "ripiega" voci simili insieme, il che funziona perché la maggior parte delle voci sono vuote, ma quando non sono vuote genera un conflitto. Questi tipi di errori non sono naturali, difficili da capire e le correzioni di solito sono abbastanza strane.

Errori del compilatore e ripristino degli errori

LL vince qui. In un analisi LL, di solito è abbastanza facile emettere errori di compilazione utili, in particolare in parser scritti a mano. Sai cosa ti aspetti dopo, quindi se non si presenta, di solito sai cosa è andato storto e quale sarebbe stato l'errore più sensato.

Inoltre, nell'analisi di LL, il recupero degli errori è molto più semplice. Se un input non viene analizzato correttamente, puoi provare a saltare un po 'e capire se il resto dell'ingresso è analizzato correttamente. Se, ad esempio, alcune istruzioni di programmazione non sono corrette, puoi saltare e analizzare l'istruzione successiva, in modo da poter rilevare più di un errore.

Usando un parser LR questo è molto più difficile. Puoi provare ad aumentare la tua grammatica in modo che accetti input errati e stampi errori nelle aree in cui le cose sono andate storte, ma di solito è piuttosto difficile da fare. Anche la possibilità di finire con una grammatica non LR (o non LALR).

Velocità

La velocità non è davvero un problema con il modo in cui si analizza il proprio input (LL o LR), ma piuttosto la qualità del codice risultante e l'uso delle tabelle (è possibile utilizzare tabelle sia per LL che per LR). LL e LR sono quindi paragonabili a questo riguardo.

Link

Qui è un link a un sito che contrappone anche LL e LR. Cerca la sezione in basso.

Qui puoi trovare una conversazione sulle differenze. Non è una cattiva idea guardare criticamente le opinioni espresse lì, però, c'è un po 'di guerra santa andare lì.

Per maggiori informazioni, qui e qui sono due dei miei post sui parser, sebbene non siano strettamente relativi al contrasto tra LL e LR.