Parsing Bottom-up

Automi e Linguaggi Formali

Parsing Bottom-up

Idea del parsing bottom-up

Costruisce l’albero sintattico iniziando dalle foglie e salendo verso la radice

Esempio

E ! T + E |T

T _{! int ⇤ T |int|(E )}

Idea del parsing bottom-up

Esempio

Il parsing bottom-up riduce una stringa al simbolo iniziale invertendo le produzioni:

stringa produzione

int _{⇤ int + int} T _{! int}

int ⇤ T + int T ! int ⇤ T

T + int T _{! int}

T + T E _{! T}

T + E E ! T + E

Osservazione

Leggiamo le produzioni in ordine inverso (dal basso verso l’alto rispetto all’albero di parsing) E’ una derivazione da destra (letta in ordine inverso, da destra a sinistra)

Esempio

Esempio

int _{⇤ int + int} int _{⇤ T + int} T + int T + T T + E E E T int _{⇤ T} int + E T int

Costruzione dell’albero

Costruzione dell’albero

int _{⇤ int + int}

int ⇤ T + int _{int ⇤}

T

Costruzione dell’albero

int _{⇤ int + int} int _{⇤ T + int} T + int

T

int _{⇤ T}

Costruzione dell’albero

int ⇤ int + int int ⇤ T + int T + int T + T T int ⇤ T int + T int

Costruzione dell’albero

int ⇤ int + int int _{⇤ T + int} T + int T + T T + E T int ⇤ T int + E T int

Costruzione dell’albero

int _{⇤ int + int} int _{⇤ T + int} T + int T + T T + E E E T int _{⇤ T} int + E T int

Un algoritmo per il parsing bottom-up

Sia I la stringa in input repeat

seleziona una sottostringa non vuota di I dove X _! `e una produzione

se non c’`e alcun , torna indietro rimpiazza con X in I

until I = S (simbolo iniziale) o tutte le possibilit`a sono state provate

Maniglie

Decisioni da prendere durante il parsing bottom-up:

quale sottostringa ridurre che produzione usare

Maniglia (handle): sottostringa tale che X _! `e una produzione che corrisponde ad un passo in una derivazione da destra della stringa in input

Nota: la sottostringa pi`u a sinistra che coincide con la parte destra di una produzione non `e sempre una maniglia

Dove riduciamo ?

Sia ↵ ! la stringa corrente durante un parsing bottom-up

Assumiamo che la prossima riduzione sia fatta usando la produzione X !

Allora ! `e una stringa di terminali, perch´e ↵X ! <sub>! ↵ ! `e un passo di una derivazione da</sub> destra

Notazione

Idea: Dividere la stringa in due sottostringhe la sottostringa di destra deve essere ancora esaminata (una stringa di terminali)

la sottostringa di sinistra ha terminali e non-terminali (`e inserita in una pila)

Il punto di divisione `e marcato dal simbolo <sub>|</sub> il simbolo <sub>| non `e parte della stringa</sub> Inizialmente, tutto l’input `e non esaminato:

Operazioni di Shift e Reduce

Il parsing bottom-up usa solo due tipi di azioni (non banali):

Shift (scorri) Reduce (riduci)

Shift

Muove | di un posto verso destra

Sposta un terminale nella stringa di sinistra legge un terminale e lo inserisce sulla pila

Reduce

Applica una produzione inversa nella parte finale della stringa di sinistra

Rimpiazza una stringa di terminali in cima alla pila con la parte sinistra di una

produzione

Se A _{! xy `e una produzione, allora:} Cbxy|ijk ) CbA|ijk

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift

int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift T +|int shift

T + int| reduce T ! int T + T| reduce E ! T T + E| reduce E ! T + E

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift

int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift T +|int shift

T + int| reduce T ! int T + T| reduce E ! T T + E| reduce E ! T + E

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift T +|int shift

T + int| reduce T ! int T + T| reduce E ! T T + E| reduce E ! T + E

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int

int⇤ T | + int reduce T ! int ⇤ T T| + int shift

T +|int shift

T + int| reduce T ! int T + T| reduce E ! T T + E| reduce E ! T + E

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift T +|int shift

T + int| reduce T ! int T + T| reduce E ! T T + E| reduce E ! T + E

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift

T +|int shift

T + int| reduce T ! int T + T| reduce E ! T T + E| reduce E ! T + E

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift T +|int shift

T + int| reduce T ! int T + T| reduce E ! T T + E| reduce E ! T + E

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift T +|int shift

T + int| reduce T ! int

T + T| reduce E ! T T + E| reduce E ! T + E

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift T +|int shift

T + int| reduce T ! int T + T| reduce E ! T

T + E| reduce E ! T + E E|

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift T +|int shift

T + int| reduce T ! int T + T| reduce E ! T T + E| reduce E ! T + E

L’esempio con le due operazioni Shift-Reduce

|int ⇤ int + int shift int| ⇤ int + int shift int⇤ |int + int shift

int⇤ int| + int reduce T ! int int⇤ T | + int reduce T ! int ⇤ T

T| + int shift T +|int shift

T + int| reduce T ! int T + T| reduce E ! T T + E| reduce E ! T + E

La pila

La stringa di sinistra pu`o essere implementata con una pila

La cima della pila `e il simbolo _|

Un’operazione di Shift inserisce un terminale in cima alla pila

Un’operazione di Reduce toglie 0 o pi`u simboli dalla pila (parti destre di produzioni) e aggiunge un non-terminale sulla pila (parti sinistre di produzioni)

Conflitti

Il parsing shift-reduce non funziona con tutte le grammatiche libere da contesto

Per alcune grammatiche, qualunque parser shift-reduce arriva a dei conflitti

Anche conoscendo tutta la pila e i prossimi k simboli in input

Conflitto shift-reduce: il parser non sa decidere se fare uno shift o una reduce

Conflitto reduce-reduce: il parser non sa quale riduzione fare

Grammatiche non LR(k) (o non LR) Una grammatica ambigua non `e LR

Parsing Shift-Reduce

Due azioni:

Shift

ABC_{|xyz ) ABCx|yz} Reduce (con A _{! xy)} Cbxy|ijk ) CbA|ijk

Come decidere se applicare shift o reduce

Esempio

E ! T + E |T

T _{! int ⇤ T |int|(E )}

Consideriamo int_{| ⇤ int + int}

Potremmo ridurre tramite T _{! int} arrivando a T_{| ⇤ int + int}

Errore: non potremo arrivare al simbolo iniziale E

Maniglie

Intuizione: vogliamo ridurre solo se il risultato pu`o ancora essere ridotto fino al simbolo iniziale Prendiamo una derivazione da destra:

S ₎⇤

rm ↵X ! rm) ↵ ! Allora ↵ `e una maniglia di ↵ !

In un parsing shift-reduce, le maniglie appaiono solo in cima alla pila, mai nel mezzo

Maniglie

Intuizione: vogliamo ridurre solo se il risultato pu`o ancora essere ridotto fino al simbolo iniziale Prendiamo una derivazione da destra:

S ₎⇤

rm ↵X ! rm) ↵ ! Allora ↵ `e una maniglia di ↵ !

In un parsing shift-reduce, le maniglie appaiono solo in cima alla pila, mai nel mezzo

Maniglie

Intuizione: vogliamo ridurre solo se il risultato pu`o ancora essere ridotto fino al simbolo iniziale Prendiamo una derivazione da destra:

S ₎⇤

rm ↵X ! rm) ↵ ! Allora ↵ `e una maniglia di ↵ !

In un parsing shift-reduce, le maniglie appaiono solo in cima alla pila, mai nel mezzo

Maniglie solo in cima alla pila

Induzione informale sul numero di passi di riduzione: All’inizio `e vero, e la pila `e vuota

Dopo aver ridotto una maniglia

Il nonterminale pi`u a destra `e in cima alla pila

La prossima maniglia deve essere alla destra del nonterminale pi`u a destra, perch´e `e una derivazione da destra

La sequenza di mosse shift raggiunge la prossima maniglia

Sommario sulle maniglie

In un parsing shift-reduce, le maniglie appaiono sempre in cima alla pila

Le maniglie non sono mai alla sinistra del nonterminale pi`u a destra

Quindi non dobbiamo mai muovere verso sinistra il simbolo |

Gli algoritmi di parsing bottom-up si basano sul riconoscimento delle maniglie

Riconoscere le maniglie

Non esistono algoritmi efficienti per riconoscere le maniglie

Soluzione: usare delle euristiche che cercano di indovinare quali pile sono delle maniglie

Per alcune grammatiche, le euristiche indovinano sempre correttamente

Per le euristiche che useremo, si tratta delle grammatiche SRL

Grammatiche e conflitti