Modelli e Complessità

PARSER PREDITTIVO PER ESPRESSIONI ARITMETICHE

CALCOLO DEI FIRST-SET

• LL(1): si prende decisione sulla base di singolo non terminale e prossimo token da leggere
• LR(1): la decisione è basata sull'intero contesto sinistro (in pila) e sul prossimo token in input
• LR(1) è più "potente" di LL(1), poiché permette di analizzare un insieme più grande di grammatiche (tutte le CF deterministiche)
• Sono disponibili tool per generare automaticamente parser basati su tabelle di parsing, sia per LL che per LR
• Ottimo tool per LR: bison
• Celebri tool per LL: ANTLR e JavaCC
• Riporta e localizza l'errore
• Diagnosi dell'errore
• Correzione dell'errore
• Recupero del processo di analisi dall'errore per proseguire correttamente (e scoprire nuovi errori)
• Difficile: si possono individuare nuovi errori strani e non effettivi
• a := a * ( b + c * d ; dove il simbolo ";" funziona da

delimitatore e permette di continuare l'analisi

• Grammatiche CF adatte a definire i linguaggi di programmazione
• Le ambiguità di una grammatica si possono spesso eliminare
• Parser predittivi top-down sono scelta naturale e più semplice
• Funzionano con grammatiche in cui introduciamo altri vincoli
• Sono efficienti
• Permettono il trattamento degli errori

obiettivo: fissata una grammatica non-contestuale G, data una stringa x in input, costruire un albero di derivazione (destro) di x a partire dalle foglie, usando le produzioni di G con G fissata

obiettivo: fissata una grammatica non-contestuale G, data una stringa x in input, costruire un albero di derivazione (sinistro) di x a partire dalla radice, usando le produzioni di G con G fissata

metodo: analisi shift-reduce

metodi

• Lineare
• analisi a discesa ricorsiva (esponenziale)
• analisi predittiva (basata su grammatiche LR(k))
• analisi predittiva (lineare)

basata su grammatiche LL(k))

• esistono altri metodi
• ricostruisce una derivazione destra della stringa in input, o restituisce messaggio di errore in caso la derivazione non esista
• durante l'esecuzione effettua "sostituzioni inverse" (riduzioni) su sottostringhe dell'input, percorrendo al contrario il processo di derivazione
• basato su una pila (inizialmente vuota), legge l'input un token alla volta, eseguendo ad ogni lettura uno shift oppure una o più operazioni di reduce
• se non è possibile operare uno shift o una reduce allora si produce un messaggio di errore
• durante il parsing l'input è diviso in due parti
• ancora da leggere (undigested)
• letto, inserito in pila e parzialmente processato (semi-digested)
• operazione shift
• sposta in pila (shift) prossimo token in input
• operazione reduce
• ∈individua stringa α V* affiorante nella pila, tale che esiste X➝α, esegui pop

Di tutti i caratteri di α ed esegui push di X (reduce); α è detta handle○ dopo una reduce potrebbe essere possibile eseguire un'altra reduce○ se dopo una reduce la pila contiene solo l'assioma e l'input è stato letto interamente allora il parsing termina con successo

Modelli Pagina 51

Ad ogni passo del parsing potrebbero nascere conflitti

• reduce-reduce, ovvero potremmo eseguire il reduce con due produzioni differenti
• shift-reduce, ovvero potremmo indifferentemente eseguire shift o reduce○ N.B. In realtà non è indifferente: lo è solo apparentemente○ esempio del dangling else

Per risolvere i conflitti occorre stabilire come

• riconoscere un handle
• decidere la produzione da usare in una riduzione
• utilizzare strumenti (come il lookahead) per dirimere un conflitto shift/reduce

Studieremo parser LR

• L: left-to-right scan dell'input
• R: costruzione di una derivazione rightmost

(destra)• le grammatiche che ammettono parsing LR sono più numerose di quelle che ammettono parsing predittivo LL○ in pratica includono tutte quelle dei linguaggi di programmazione

• per il parsing LR c'è un minor bisogno di "aggiustare" le produzioni, rispetto al caso LL○ c'è un lungo lavoro di preparazione di tabelle che permettono di riconoscere casi e definire azioni – per fortuna automatizzabile, poiché non richiede creatività

• nel parsing shift-reduce la pila contiene le forme di frase che vengono via via elaborate per applicare in senso inverso le produzioni, fino ad arrivare all'assioma

• in molti casi la produzione da applicare non dipende solo da quale è lo handle individuato ma anche dagli altri simboli in pila, e quindi da un contesto

• per meglio catturare il contesto si mettono in pila non semplici token, ma veri e propri stati, che rappresentano il contesto sinistro

corrente• lo stato che affiora dalla pila, eventualmente aiutato da un lookahead, consente di prendere la decisione corretta (shift o reduce, e con quale produzione)

per ora ci si limita alla nozione intuitiva stato = produzione di cui abbiamo già verificato una parte➝αβ,

es.: X ove α è la parte già verificata e β quella ancora da verificare

I parser LR fanno uso di due tavole

1. Action table Action[s, a]
2. Goto table Goto[s, X] • indica quale nuovo stato piazzare in cima alla pila (push) dopo la riduzione del non-terminale X, mentre• descrive quale azione eseguire quando lo stato affiorante in pila è s e il prossimo lo stato affiorante è s, e serve per completare una riduzione

token in input è il terminale a• Azioni: riduzione del non-terminale X significa che è stato individuato uno handle α ed usata la produzione X➝α•

○ shift uno stato sulla pila (push) • dopo i

pop affiora in pila lo stato s○ reduce uno handle associato a uno o più stati in cima alla pila (attenzione: • l'indicazione della tavola Goto è il nuovo stato di cui fare il push (dopo i pop già eseguiti)solo pop)○ accept, termina con successo○ report error, se non è possibile procedere→ pila inizializzata con stato iniziale s→ token in input: a→ stato corrente: s• Action[s , a] == shift(s ) : esegue push(su) e legge il prossimo tokenAction[s , a] == reduce(A➝B … B ) :• ○ esegue k pop (estrazione di k stati), dopodiché, se sv è lo stato affiorante, esegue push(Goto(s , A));○ il token in input non cambia• Action[s , a] == accept : il paser conclude le operazioni con successo• Action[s , a] == error :○ errore sintattico (con la pila corrente e il token in input non è possibile raggiungere una forma di frase con uno handle da ridurre)○ in questo caso è in genere

possibile stampare messaggio diagnostico sull'errore

N.B. per ciascuna reduce si fornisce in output la produzione ridotta⋅• si introduce un punto per separare la parte destra di una produzione in due sottosequenze:

• ⋅a sinistra del punto elementi già letti e impilati (shifted),
• a destra elementi ancora da analizzare

→E⋅+Tes.: E•

◦ sono già stati impilati elementi derivati da E e occorre ora accettare in input il simbolo +•

ciascuna di queste produzioni con il punto si chiama LR(0) item, o semplicemente item, e descrive lo stato del parser

si aggiunge la produzione E'→E dove E' è il nuovo assioma (non compare in parti destre)•

◦ l'obiettivo è avere l'assioma originale come parte destra di una produzione, così da poter effettuare una reduce finale

𝕊per ogni produzione A→𝕋 si considerano gli item ottenuti introducendo in tutte le posizioni possibili di il puntino• →⋅E+T,

1. E⋅+T
2. E+⋅T
3. E+T⋅

es. E E E EModelli Pagina 52venerdì 29 aprile 2022 13:00 ⋅X• solitamente non è possibile descrivere lo stato di un parser con un singolo item perché in presenza di possono esistere vari elementi in First(X)○ o elementi in Follow(X) qualora si annulli• lo stato viene caratterizzato collezionando più item, attraverso una procedura detta di chiusura (closure)• ad ogni collezione corrisponde uno statoChiusura di un set di itemse il set contiene un item A➝α⋅Bβ, con B V , allora aggiungere al set B➝⋅γ, per ciascuna produzione B➝γ, con γ V*•• continuare su tutte le produzioni nel set finché possibile, aggiungendo produzioni aventi come parte sinistra non -terminali che appaiono in partidestre preceduti dal punto○ la parte destra di una produzione aggiunta inizierà con il punto• si definisce stato l'insieme risultante

dall'operazione di chiusura di un set di item Consideriamo questa grammatica aumentata G' che genera il linguaggio L' = Determinazione dei set of item ➝Sinizio: assioma S' chiusura:➝S○ S'○ aTc ○ ac ○ bc (+) S➝aSc | | | - questa collezione di produzioni definisce uno stato (s ) - il simbolo (+) indica che la riga di produzioni è aggiunta durante la chiusura - per definire gli altri item sets si procede ricorsivamente - per ogni produzione A➝αBβ, con B V , si crea un nuovo stato (se non già creato) contenente la produzione A➝αBβ, e se ne fa la chiusura - il simbolo "scavalcato" dal punto determina la transizione fra stati Determinazione altri stati Modelli Pagina 53 - Definizione: - Una grammatica è detta LR(0) se, per ciascuno degli stati: - è presente al più una sola produzione con il punto finale (assenza diconflitti reduce-reduce)○ non sono contemporaneamente presenti una produzione con il punto finale e un'altra con il punto non finale (assenza di conflitti shift-reduce)• in una grammatica LR(0) la decisione shift/reduce viene presa senza guardare l'input (lookahead nullo)• il parsing LR(0), che usa lookahead nullo, si applica a poche grammatiche○ in particolare: non funziona per le grammatiche ambigue≥• in generale, guardando k 1 caratteri in input possibile effettuare LR parsing su molte più grammatiche○ ma una grammatica ambigua non può naturalmente ammettere alcun tipo di parser, proprio a causa dell'ambiguità1. un linguaggio può essere generato da una grammatica LR(k) se e solo se è context free deterministico (riconosciuto da un automa a pila deterministico) ≥2. un linguaggio ammette una grammatica LR(1) se e solo se ammette una grammatica LR(k), k 1tutti i linguaggi context free deterministici ammettono