Shift-ridurre: quando smettere riducendo?

Question

sto cercando di conoscere shift-riducono parsing. Supponiamo di avere la seguente grammatica, utilizzando le regole ricorsive che ordine delle operazioni fanno rispettare, ispirate al ANSI C Yacc grammatica :

S: A;

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

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

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

E noi vogliamo analizzare 1 + 2 usando shift-ridurre l'analisi. In primo luogo, il 1 viene spostato come un numero. La mia domanda è, è poi ridotto a P, allora M, allora A, poi finalmente S? Come fa a sapere dove fermarsi?

Supponiamo che fa ridurre fino a S, poi si sposta '+'. Ci piacerebbe Ora abbiamo uno stack contenente:

S '+'

Se spostiamo '2', le riduzioni potrebbero essere:

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 il numero, sarebbe comunque valida nel senso che qualsiasi combinazione sarebbe una corretta rappresentazione del testo. Come funziona il parser "conoscere" per renderlo

A '+' M

In modo che possa ridurre l'intera espressione ad A, allora S? In altre parole, come fa a sapere di smettere di ridurre prima di spostare il token successivo? Si tratta di una delle principali difficoltà in LR generazione parser?

---

Modifica:. Un'aggiunta alla domanda segue

Ora supponiamo che 1+2*3 parse. Alcuni spostamento / ridurre le operazioni sono i 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, non lookahead da 1 simbolo anche dirci di non ridurre A+M a A, in quanto ciò comporterebbe un errore di sintassi inevitabile dopo aver letto *3?

Answer 1

Il problema che stai descrivendo è un problema con la creazione di parser LR(0) - che è, parser bottom-up che non fanno alcun lookahead simboli al di là di quello attuale sono l'analisi. La grammatica che hai descritto non sembra essere una grammatica LR(0), che è il motivo per cui si esegue in problemi quando si cerca di analizzarlo w / o lookahead. E ' non sembrano essere LR(1), tuttavia, così, cercando 1 simbolo avanti in ingresso si potrebbe facilmente determinare se spostamento o ridurre. In questo caso, un parser LR(1) sarebbe guardare avanti quando si aveva il 1 in pila, vedere che il simbolo successivo è un +, e rendersi conto che non dovrebbe ridurre A passato (dal momento che è l'unica cosa che potrebbe ridurre a quella sarebbe ancora abbinare una regola con + in seconda posizione).

Un interessante proprietà delle grammatiche LR è che per qualsiasi grammatica che è LR(k) per k>1, è possibile costruire una grammatica LR(1) che è equivalente. Tuttavia, lo stesso non si estende tutta la strada fino a LR(0) -. Ci sono molte grammatiche che non possono essere convertiti in LR(0)

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

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

Answer 2

Non sono esattamente sicuro della Yacc / Bison parsing algoritmo e quando si preferisce spostare oltre la riduzione, tuttavia so che Bison supporta LR (1) analisi che significa che ha un lookahead token. Ciò significa che i token non vengono passati alla pila immediatamente. Piuttosto, essi attendere che altre riduzioni possono accadere. Quindi, se si sposta entro marchi di token percepiscono applica tale operazione.

Prima di tutto, nel tuo caso, se si sta valutando 1 + 2, si sposterà 1. Esso contribuirà a ridurre quella pedina ad una A in quanto il '+' lookahead gettone indica che il suo corso valida solo. Poiché non ci sono più riduzioni, sposterà il '+' gettone sulla pila premuto 2 come lookahead. Sposterà il 2 e ridurre al M poiché A + M produce una A e l'espressione è completa.