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 grammatica
S -> aABe
A -> Abc |b
B -> 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 ridurre
2. 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.
Esempio
E
E
E
E
STACK
INPUT
$
$ id
$E
$ E + id
$E+E
$ E + E  id
$E+EE
$E+E
$E
id + id  id $
+ id  id $
+ id  id $
id $
id $
$
$
$
$
->
->
->
->
E+E
E*E
(E)
id
AZIONE
SHIFT
REDUCE E  id
SHIFT, SHIFT
REDUCE E  id
SHIFT, SHIFT (perché NON REDUCE E  E + E)
REDUCE E  id
“ E E  E
“ E E + E
ACCEPT
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