Shift-reduce: quando smettere di ridurre?

Question

Sto cercando di imparare a ridurre l'analisi. Supponiamo di avere la seguente grammatica, utilizzando le regole ricorsive che ordine delle operazioni fanno rispettare, ispirate al ANSI C Yacc grammar:

S: A; 

P 
    : NUMBER 
    | '(' S ')' 
    ; 

M 
    : P 
    | M '*' P 
    | M '/' P 
    ; 

A 
    : M 
    | A '+' M 
    | A '-' M 
    ; 

e vogliamo analizzare 1 + 2 usando shift-ridurre l'analisi. Innanzitutto, il 1 viene spostato come NUMERO. La mia domanda è, è ridotta a P, quindi a M, quindi A, infine a S? Come sa dove fermarsi?

Supponiamo che riduca fino a S, quindi cambia "+". ora avremmo una pila contenente:

S '+' 

Se Shift '2', potrebbero essere le riduzioni:

S '+' NUMBER 
S '+' P 
S '+' M 
S '+' A 
S '+' S 

Ora, su entrambi i lati l'ultima riga, S potrebbe essere P, M, A o NUMBER, e sarebbe comunque valido nel senso che qualsiasi combinazione sarebbe una rappresentazione corretta del testo. Come funziona il parser "conoscere" per renderlo

A '+' M 

Così che può ridurre l'intera espressione ad A, allora S? In altre parole, come fa a smettere di ridurre prima di spostare il prossimo token? È questa una difficoltà chiave nella generazione del parser LR?

---

Edit: Un'aggiunta alla domanda segue.

Supponiamo ora di analizzare 1+2*3. Alcune operazioni di spostamento/riduzione sono le seguenti:

Stack | Input | Operation 
---------+-------+---------------------------------------------- 
     | 1+2*3 | 
NUMBER | +2*3 | Shift 
A  | +2*3 | Reduce (looking ahead, we know to stop at A) 
A+  | 2*3 | Shift 
A+NUMBER | *3 | Shift (looking ahead, we know to stop at M) 
A+M  | *3 | Reduce (looking ahead, we know to stop at M) 

È corretto (concesso, non è ancora completamente analizzato)? Inoltre, guarda avanti di 1 simbolo ci dice anche di non ridurre A+M a A, in quanto ciò provocherebbe un inevitabile errore di sintassi dopo aver letto *3?

Answer 1

Il problema che stai descrivendo è un problema con la creazione di parser LR(0), ovvero parser dal basso verso l'alto che non hanno alcun aspetto rispetto ai simboli oltre a quello corrente che stanno analizzando. La grammatica che hai descritto non sembra essere una grammatica LR(0), motivo per cui ti imbatti in problemi quando cerchi di analizzarlo senza guardare avanti. sembra essere LR(1), tuttavia, osservando 1 simbolo avanti nell'input, è possibile determinare facilmente se spostarsi o ridurlo. In questo caso, un parser LR(1) guarderebbe al futuro quando aveva lo 1 nello stack, vedere che il simbolo successivo è un + e rendersi conto che non dovrebbe ridurre il precedente A (poiché è l'unica cosa che potrebbe ridurre a quello sarebbe ancora abbinare una regola con + nella seconda posizione).

Un'interessante proprietà di LR grammatiche è che per ogni grammatica che è LR(k) per k>1, è possibile costruire un LR(1) grammatica equivalente. Tuttavia, lo stesso non si estende fino a LR(0) - ci sono molte grammatiche che non possono essere convertite in LR(0).

Vedi qui per maggiori dettagli sul LR(k) -ness:

http://en.wikipedia.org/wiki/LR_parser

Answer 2

io non sono esattamente sicuro di algoritmo di analisi Yacc/Bison e quando preferisce spostando sopra la riduzione, tuttavia so che supporti Bison LR (1) parsing che significa che ha un token lookahead. Ciò significa che i token non vengono passati immediatamente allo stack. Piuttosto, attendono fino a quando non possono verificarsi ulteriori riduzioni. Quindi, se lo spostamento del token successivo ha senso, applica tale operazione.

Prima di tutto, nel tuo caso, se stai valutando 1 + 2, cambierà 1. Ridurrà quel token ad un A perché il token lookahead '+' indica che è l'unica rotta valida. Dal momento che non ci sono più riduzioni, sposta il gettone "+" sullo stack e tiene premuto 2 come lookahead. Sposterà il 2 e ridurrà a M poiché A + M produce un A e l'espressione è completa.