Qual è la differenza tra LR (0) e analisi SLR?

Question

Sto lavorando ai miei concetti di compilatori, ma sono un po 'confuso ... Google non mi ha portato da nessuna parte a una risposta definitiva.

SLR e LR (0) sono uno stesso? In caso contrario, qual è la differenza?

Answer 1

I parser sia LR (0) che SLR (1) sono parser dal basso verso l'alto, direzionale e predittivo. Ciò significa che

• I parser tentano di applicare le produzioni al contrario per ridurre la frase di input al simbolo di avvio (dal basso verso l'alto)
• I parser scansionano l'input da sinistra a destra (direzionale)
• I parser tentano di prevedere quali riduzioni si applicano senza necessariamente vedere tutti gli input (predittivo)

Sia LR (0) che SLR (1) sono Shift/Riducing Parser, nel senso che elaborano i token del flusso di input posizionandoli su uno stack e in ogni punto mutevole un token spingendolo sullo stack o Ridurre Alcune sequenze di terminali e non terminali in cima allo stack di nuovo su un simbolo non terminal. Si può dimostrare che qualsiasi grammatica può essere analizzata dal basso verso l'alto usando un parser a turni/riduci, ma che il parser potrebbe non essere deterministico. Cioè, il parser potrebbe dover "indovinare" se applicare un turno o una riduzione e potrebbe finire per dover tornare indietro per rendersi conto che ha fatto la scelta sbagliata. Non importa quanto potente un parser deterministico/riduce il parser, non sarà mai in grado di analizzare tutte le grammatiche.

Quando viene utilizzato un parser a spostamento/riduzione deterministico per analizzare una grammatica che non può gestire, si traduce Shift/Riduci conflitti o ridurre/ridurre i conflitti, dove il parser può entrare in uno stato in cui non può dire quale azione intraprendere. In un conflitto di turno/ridurre, non può dire se dovrebbe aggiungere un altro simbolo allo stack o eseguire un po 'di riduzione sui simboli superiori dello stack. In un conflitto di riduzione/riduzione, il parser sa che deve sostituire i simboli migliori della pila con un po 'di non terminal, ma non può dire quale riduzione usa.

Mi scuso se questa è un'esposizione lunga, ma abbiamo bisogno di questo per essere in grado di affrontare la differenza tra l'analisi LR (0) e SLR (1). Un parser LR (0) è un parser a turni/riduzione che utilizza token zero di lookahead per determinare quale azione intraprendere (da cui 0). Ciò significa che in qualsiasi configurazione del parser, il parser deve avere un'azione inequivocabile da scegliere: sposta un simbolo specifico o applica una riduzione specifica. Se ci sono mai due o più scelte da fare, il parser fallisce e diciamo che la grammatica non è LR (0).

Ricordiamo che i due possibili conflitti LR sono spostamenti/riduci e riducono/riducono. In entrambi questi casi, ci sono almeno due azioni che l'automa LR (0) potrebbe intraprendere e non può dire quale di loro utilizzare. Poiché almeno una delle azioni contrastanti è una riduzione, una linea di attacco ragionevole sarebbe quella di provare a fare più attenzione al parser quando esegue una riduzione particolare. Più specificamente, supponiamo che il parser sia autorizzato a esaminare il segno successivo dell'input per determinare se dovrebbe cambiare o ridurre. Se permettiamo al parser solo di ridurre quando "ha senso" di farlo (per una certa definizione di "ha senso"), allora potremmo essere in grado di eliminare il conflitto facendo in modo che l'automa scelga specificamente di spostarsi o ridurre in a Passaggio particolare.

Nella SLR (1) ("LR semplificato (1)"), il parser è autorizzato a guardare un token di Lookahead quando si decide se dovrebbe cambiare o ridurre. In particolare, quando il parser vuole provare a ridurre qualcosa della forma A → W (per non terminali A e String W), guarda il segno successivo dell'input. Se quel token potesse apparire legalmente dopo il non terminale A in qualche derivazione, il parser si riduce. Altrimenti, no. L'intuizione qui è che in alcuni casi non ha senso tentare una riduzione, perché dati i token che abbiamo visto finora e il segno imminente, non è possibile che la riduzione possa mai essere corretta.

L'unica differenza tra LR (0) e SLR (1) è questa ulteriore capacità di aiutare a decidere quale azione intraprendere quando ci sono conflitti. Per questo motivo, qualsiasi grammatica che può essere analizzata da un parser LR (0) può essere analizzata da un parser SLR (1). Tuttavia, i parser SLR (1) possono analizzare un numero maggiore di grammatiche rispetto a LR (0).

In pratica, tuttavia, la SLR (1) è ancora un metodo di analisi abbastanza debole. Più comunemente, vedrai i parser Lalr (1) ("Lookahead LR (1)"). Anche loro lavorano cercando di risolvere i conflitti in un parser LR (0), ma le regole che usano per risolvere i conflitti sono molto più precise di quelle utilizzate nella SLR (1) e di conseguenza un numero molto maggiore di grammatiche sono LALR (1) di quanto sono SLR (1). Per essere un po 'più specifici, i parser SLR (1) cercano di risolvere i conflitti osservando la struttura della grammatica per conoscere ulteriori informazioni su quando spostarsi e quando ridurre. I parser LALR (1) guardano sia il parser grammaticale che LR (0) per ottenere informazioni ancora più specifiche su quando spostarsi e quando ridurre. Poiché LALR (1) può guardare alla struttura del parser LR (0), può identificare più precisamente quando alcuni conflitti sono spuri. Le utility Linux yacc e bison, per impostazione predefinita, produrre parser LALR (1).

Storicamente, i parser LALR (1) sono stati in genere costruiti attraverso un metodo diverso che si basava sul parser LR (1) molto più potente, quindi vedrai spesso Lalr (1) descritto in quel modo. Per capirlo, dobbiamo parlare di parser LR (1). In un parser LR (0), il parser funziona tenendo traccia di dove potrebbe essere nel mezzo di una produzione. Una volta scoperto che ha raggiunto la fine di una produzione, sa provare a ridurre. Tuttavia, il parser potrebbe non essere in grado di dire se si trova alla fine di una produzione e al centro di un'altra, il che porta a un conflitto di turno/ridurre o di quale di due diverse produzioni ha raggiunto la fine (una riduzione/ ridurre il conflitto). In LR (0), questo porta immediatamente a un conflitto e il parser fallisce. Nella SLR (1) o LALR (1), il parser prende quindi la decisione di spostare o ridurre in base al segno successivo di Lookahead.

In un parser LR (1), il parser tiene traccia di ulteriori informazioni mentre opera. Oltre a tenere traccia di ciò che la produzione ritiene che il parser sia utilizzato, tiene traccia di ciò che i token possibili potrebbero apparire dopo che la produzione è stata completata. Poiché il parser tiene traccia di queste informazioni ad ogni passaggio, e non solo quando deve prendere la decisione, il parser LR (1) è sostanzialmente più potente e preciso di qualsiasi LR (0), SLR (1) o Lalr (1) Parser di cui abbiamo parlato finora. LR (1) è una tecnica di analisi estremamente potente e può essere mostrata usando un po 'di matematica difficile che qualsiasi lingua che potrebbe essere analizzata determinante qualunque Il parser a turni/riduce ha un po 'di grammatica che potrebbe essere analizzato con un automa LR (1). (Si noti che ciò non significa tutto ciò grammatiche che possono essere analizzati determinalmente sono LR (1); Questo dice solo che una lingua che potrebbe essere analizzata ha determinato la grammatica LR (1)). Tuttavia, questo potere ha un prezzo e un parser LR (1) generato può richiedere così tante informazioni per operare che non può essere utilizzato nella pratica. Un parser LR (1) per un linguaggio di programmazione reale, ad esempio, potrebbe richiedere decine a centinaia di megabyte di ulteriori informazioni per operare correttamente. Per questo motivo, LR (1) non è in genere utilizzato in pratica e vengono invece usati parser più deboli come LALR (1) o SLR (1).

Più recentemente, un nuovo algoritmo di analisi chiamato GLR (0) ("LR generalizzato (0)") ha guadagnato popolarità. Invece di provare a risolvere i conflitti che appaiono in un parser LR (0), il parser GLR (0) funziona invece provando tutte le possibili opzioni in parallelo. Usando alcuni trucchi intelligenti, questo può essere fatto per funzionare in modo molto efficiente per molte grammatiche. Inoltre, Glr (0) può analizzare Qualsiasi grammatica senza contesto, anche grammatiche che non possono essere analizzate da un parser LR (k) per qualsiasi k. Anche altri parser sono in grado di farlo (ad esempio, il parser Earley o un parser Cyk), sebbene GLR (0) tende a essere più veloce in pratica.

Se sei interessato a saperne di più, questa estate ho insegnato un corso di compilatori introduttivi e ho trascorso poco meno di due settimane a parlare di tecniche di analisi. Se desideri ottenere un'introduzione più rigorosa a LR (0), SLR (1) e una serie di altre potenti tecniche di analisi, potresti goderti le mie diapositive per lezioni e i compiti a casa sull'analisi. Tutti i materiali del corso sono disponibili Qui sul mio sito personale.

Spero che sia di aiuto!

Answer 2

Questo è quello che ho imparato. Di solito il parser LR (0) può avere ambiguità, ovvero una scatola della tabella (si deriva per la creazione del parser) può avere più valori (o) per dirlo meglio: il parser porta a due stati finali con lo stesso input. Quindi il parser SLR viene creato per rimuovere questa ambiguità. In ordine per costruirlo trova tutte le produzioni che portano a stati di Goto, trova il seguito per il simbolo di produzione sul lato sinistro e includono solo quegli stati di Goto che sono presenti nel seguito. Questa intumazione significa che non si include una produzione che non è possibile usando il grammatore originale (perché lo stato non è nel set di follow)