Parser Bottom UP

Giuseppe Morelli

Parser Bottom UP

• Un parser Bottom Up lavora costruendo il corrispondente albero di parsing per una data stringa di input partendo dalle foglie (bottom) e risalendo via visa verso la radice (top).

• Nel seguito verranno trattati parser bottom up noti come Shift-Reduce parser.

• Sono in grado di costruire grammatiche chiamate LR.

• La costruzione di parser LR è alquanto complessa;

• Esistono tuttavia generatori automatici di parser in grado di costruire parser LR efficienti

Riduzioni

• Il parsing Bottom Up può essere pensato come il processo di “riduzione” di un data stringa w al simbolo iniziale della grammatica.

• Ad ogni passo della riduzione uno specifica sottostringa che coincide con il corpo di una produzione è sostituita da il simbolo non terminale della testa della produzione stessa.

• Durante il parsing è fattore chiave riuscire a determinare quando effetturare una riduzione e quale produzione applicare affinchè il parsing possa proseguire

• Ritornando all’esempio:

• La sequenza di riduzioni applicate può essere codificata attraverso:

NOTA: Dopo le prime due riduzioni (F->id; T->F) si potrebbe Ridurre T

attraverso E->T oppure id (di destra) attraverso F -> id

• Per definizione una riduzione è il passo inverso della procedura di derivazione (attraverso la quale un non terminale era sostituito dal corpo di una produzione, durante la generazione di una stringa).

• Lo scopo del parsing bottom-up è costruire un darivazione al contrario (in senso inverso).

• Derivazione

• Riduzione

Esempio

• Si consideri la grammaticaS -> aABeA -> Abc |bB -> d

E l’input: abbcde• Riduzione: abbcde (A->b A->Abc B->d S->aABe) abbcde, aAbcde, aAde, aABe, S• Derivazione

S => aABe => aAde => aAbcde => abbcde

• Per ottenere una riduzione al simbolo iniziale attraverso l’inversa di una derivazione è necessario essere in grado di riconoscere gli handles(maniglie) delle varie forme proposizionali.

• Un handle è una sottostringa che coincide con il corpo di una produzione e la cui riduzione rappresenta un passo lungo il processo di derivazione destra inverso

• Esempio precedente i simboli sottolineati sono handles

…

• Data una forma proposizionale destra γ un handle per γ è una produzione A -> β ed una posizione in γ corrispondente ad una occorrenza di β tale che rimpiazzando β con A si ottiene ancora una forma sentenziale destra che precede immediatamente γ in una derivazione destra per γ.

o equivalentemente• Se S => αAw => αβw allora la produzione A-

>β nella posizione seguente ad α è un handle di αβw.

NOTE• Alla destra dell’handle la stringa w è fatta solo

di simboli terminali• Se una grammatica è non ambigua ogni forma

sentenziale destra avrà solo un handle (ovvero le derivazioni destre sono univocamente determinte)

• Sebbene formalmente un handle è una produzione spesso ci si riferirà solo al suo body

Esempi

• .

• Si consideri la stringa id+id*id e la grammatica:E -> E+E | E*E | (E) | id

– id+id*id => E + id * id => E+E*id => E+E*E => E+E => E

– id+id*id =>E+id*id =>E+E *id => E*id => E*E => E

• L’inversa di una derivazione destra può essere ottenuta attraverso un procediemento di “potatura” degli handle (handle pruning).

• Si parte dalla stringa di terminali w da ridurre; se w è una frase della grammatica(sentence: derivazione ovvero forma sentenziale con soli terminali) allora sia w =γn dove γn è n-esima forma sentenziale destra di una derivazione destra

• Per ricostruire la derivazione nell’ordine inverso: localizzare l’handle βn in γn e rimpiazzare βn con la testa della produzione An -> βn per ottenere la forma sentenziale γn-1. Si continua trovando βn-1 in γn-1 …. fino ad arrivare al simbolo iniziale.

• La sequenza delle produzioni utilizzate (in ordine inverso) rappresenta la derivazione destra per la stringa di input

Shift- Reduce parser

• Per una corretta potatura dell’albero si devono affrontare e risolvere due problemi:1. Bisogna essere in grado di localizzare la

sottostringa da ridurre2. Bisogna determinare quale produzione

utilizzare nella riduzione• Tali problemi possono essere affrontati

utilizzando:– Uno stack per contenere i simboli della grammatica

ovvero un prefisso della forma sentenziale destra fino ad un handle

– Un buffer di input per contenere la porzione di input di cui ancora si deve fare il parsing.

• Convenzionalmente il $ indica sia il top dello stack sia la destra della stringa di input

• Inizialmente stack vuoto e stringa w si indicherà con:

• Durante il processo di analisi della stringa di input da sinistra a destra, il parser muoverà 0 o più simboli nello stack fino a quando non sarà in grado di ridurre una stringa della grammatica (corpo della produzione) con il top dello stack (sostituisce top con non terminale testa della produzione). La fine senza errori è determinata dalla presenza del simbolo iniziale nello stack, con buffer di input vuoto.

Operazioni di un parser Shift Reduce.

• Shift: sposta il successivo simbolo di input nello stack

• Reduce: riduzione dell’handle sullo stack (top) mediante una opportuna produzione. Sostituzione dell’handle con un non terminale

• Accept: Segnalazione che il parsing si è concluso con successo

• Error: Segnalare errore di sintatti e richiamare una opportuna procedure di recovery.

EsempioE -> E + EE -> E * E E -> (E) E -> id

STACK INPUT AZIONE$$ id$ E$ E + id$ E + E$ E + E

id$ E + E E$ E + E $ E

id + id id $+ id id $+ id id $ id $ id $$$$$

SHIFTREDUCE E idSHIFT, SHIFTREDUCE E id SHIFT, SHIFT (perché NON REDUCE E E + E)REDUCE E id “ E E E“ E E + EACCEPT

Conflitti

• Un parser shift-reduce può raggiungere una configurazione in cui, pur conoscendo lo stack nella sua interezza ed i simboli di input da trattare , non sa decidere se:– Effettaure una operazione di SHIFT o di

REDUCE (conflitto Shift/Reduce)– Scegliere fra più riduzioni possibili quale

effettuare (conflitto Reduce/Reduce)

Esempio

• Quando il parser è nella seguente configurazione:

• Non è possibile determinare se nello stack c’è un handle oppure no quindi se fare un o shift o una riduzione

Esempio

• Quando il parser è nella seguente configurazione:

• Non sappiamo decidere quale riduzione fare tra (5) e (7)

• Se invece di id per array e procedure il lexer restituisce risp. id e procid per i costrutti