ANALISI SINTATTICA

LUCIDI DI F. D'AMORE E

A. MARCHETTI SPACCAMELA

AUTOMI PUSHDOWN

controllo

tabella

input

pila

$ u t w

vxy

…z$

Nov

201

2 FI

2 - #

fi2sa

pien

za

2

ARGOMENTI Il compito dell'analisi sintattica

Generazione automatica

Trattamento degli errori

Grammatiche libere dal contesto

Grammatiche ambigue

Analisi Top-Down vs. Analisi Bottom-Up

Una semplice analisi Top-Down

Nov

201

2 FI

2 - #

fi2sa

pien

za

3

FASI DI COMPILAZIONE Programma sorgente (stringa di caratteri)

Fin. Assembly

Analisi lessicale

Analisi sintattica (parsing)

Analisi semantica e traduzione

Tokens

Albero derivazione

Front-End

Ottimizzazione codice

Nov

201

2 FI

2 - #

fi2sa

pien

za

4

TOKEN Un token è una porzione di input, categorizzata input = stringa su alfabeto Unicode alfabeto Java ≠ Unicode

scanning = riconoscimento (tramite ASFD) di un token tokenization = suddivisione dell'input in token

Nov

201

2 FI

2 - #

fi2sa

pien

za

5

esempio Wikipedia

ESEMPIO DI GRAMMATICA TIPO 2

Nov

201

2 FI

2 - #

fi2sa

pien

za

6

1 S → S ; S 2 S → id := E 3 S → print (L) 4 E → id 5 E → num 6 E → E + E 7 E → (S, E) 8 L → E 9 L → L, E

ESEMPIO DI DERIVAZIONE

Nov

201

2 FI

2 - #

fi2sa

pien

za

7

1 S → S ; S 2 S → id := E 3 S → print (L) 4 E → id 5 E → num 6 E → E + E 7 E → (S, E) 8 L → E 9 L → L, E

S S ; S

S ; id := E

id := E ; id := E

id := num ; id := E

id := num ; id := E + E

id := num ; id := E + num

id := num ; id :=num + num

a 56 b 77 16

ESEMPIO ALBERO DERIVAZIONE

S

S ; S

S ; id := E

id := E ; id := E

id := num ; id := E

id := num ; id := E + E

id := num ; id := E + num

id := num ; id :=num + num

; s s

s

id := E id := E

num E + E

num num

Nov

201

2 FI

2 - #

fi2sa

pien

za

8

GRAMMATICHE AMBIGUE Una grammatica è ambigua quando per due stringhe che appartengono al linguaggio definito abbiamo due diversi alberi di derivazione Le grammatiche ambigue non sono adatte per i linguaggi di programmazione •  Semantica non chiara

•  Complessità analisi (due alberi derivazione)

Nov

201

2 FI

2 - #

fi2sa

pien

za

9

GRAMMATICHE NON AMBIGUE PER ESPRESSIONI ARITMETICHE

Grammatica ambigua e possibile disambiguazione

1  E → E + T 2  E → T 3  T → T * F 4  T → F 5 F → id 6 F → (E)

1 E → E + E 2 E → E * E 3 E → id 4 E → (E)

1  E → E * T 2  E → T 3  T → F + T 4  T → F 5 F → id 6 F → (E)

Nov

201

2 FI

2 - #

fi2sa

pien

za

10

PERCHÉ GRAMMATICHE TIPO 2 PER DESCRIVERE I LINGUAGGI DI PROGRAMMAZIONE ?

•  Le grammatiche di tipo 2 permettono di rappresentare la struttura gerarchica dei programmi

•  Sono più semplici delle grammatiche di tipo 1 e questo permette di avere parser efficienti

•  Vedremo in realtà che a tale scopo useremo ulteriori restrizioni

Nov

201

2 FI

2 - #

fi2sa

pien

za

11

ANALISI SINTATTICA (PARSING) INPUT

Sequenza di tokens OUTPUT

Albero di derivazione

Riporta errori di sintassi Crea tabella dei simboli, che contiene i diversi identificatori usati nel programma

Nov

201

2 FI

2 - #

fi2sa

pien

za

12

PROPRIETÀ DEI PREFISSI Per ogni sequenza di token iniziale (prefisso) t1, t2, …, tk che l’analisi individua legale

•  devono esistere tokens tk+1, tk+2, …, tn tali che t1, t2, …, tnè un programma sintatticamente corretto

Se consideriamo un token come un singolo carattere, per ogni parola prefisso x che l’analisi considera legale

•  esiste parola suffisso w tale che x⋅w è un programma valido

Nov

201

2 FI

2 - #

fi2sa

pien

za

13

ANALISI SINTATTICA (1) Bottom-up (dal basso all’alto)

•  Costrusci l’alberto dalle foglie •  Avanza nell’input (shift) o deriva un non terminale (reduce) •  Accetta quando input è finito e hai ottenuto assioma

remaining input

Nov

201

2 FI

2 - #

fi2sa

pien

za

14

ANALISI SINTATTICA (2) Top-Down (dall’alto al basso)

•  Inizia con l’assioma •  Ripetutamente scegli un simbolo non terminale A

dell’albero finora ottenuto e applica una produzione ad A •  Successo quando le foglie dell’albero rappresentano la

stringa di input

A

Nov

201

2 FI

2 - #

fi2sa

pien

za

15

ANALISI TOP-DOWN Supponi di aver completato parte di una derivazione S ⇒* wAα e che wxy sia input Passo ripetuto

Scegli una produzione su A A ::= β1 β2 … βn

che è congruente con input (la parte x non ancora ottenuta)

Il passo deve essere deterministico

Nov

201

2 FI

2 - #

fi2sa

pien

za

16

A

ANALISI TOP-DOWN: PARSER A DISCESA RICORSIVA Un vantaggio dei parser top-down è che sono più semplici da implementare Idea fondamentale: scrivere una funzione (procedura, metodo o sottoprogramma) in corrispondenza ad ogni simbolo non terminale

Ognuna di queste funzioni è responsabile di accoppiare il non-terminale con il resto dell’input

Nov

201

2 FI

2 - #

fi2sa

pien

za

17

ANALISI TOP-DOWN: PARSER A DISCESA RICORSIVA Se ci sono due produzioni del tipo

A → α1 α2 … αn | β1 β2 … βm

bisogna provare entrambi le possibilità Algoritmo ricorsivo contiene funzione A che tenta dapprima di usare la produzione A → α1 α2 … αn. Se ottiene successo, allora A termina con successo, altrimenti tenta di usare la produzione A → β1 β2 … βm. Se ottiene successo, allora A termina con successo, altrimenti termina con fallimento. Tentare di usare una produzione significa consumare porzioni di input (terminali nella parte destra) e chiamare funzioni associate a non terminali. Esempio: A → aBcD successo sse il prossimo carattere in input è 'a', la chiamata B restituisce successo, il carattere successivo da leggere è 'c' e la chiamata D restituisce successo N.B. Produzioni del tipo A → Aα sono un problema

Nov

201

2 FI

2 - #

fi2sa

pien

za

18

int A(...) { /* par.: porzione di input da leggere */! /* prova la prima possibilità A → α1 α2 … αn */! if (α1(...)) {! if (! α2()) Error(“Missing a2”);! if (! α3()) Error(“Missing a3”);! …! if (! αn()) Error(Missing an”);! return SUCCESSO;! }! /* prova la seconda alternativa A → β1 β2 … βm*/! if (β1(...)) {! if (! β2()) Error(“Missing β2”);! if (! β3()) Error(“Missing β3”);! …! if (! βm()) Error(Missing βm”);! return SUCCESSO ;! }! return ERRORE;!}!

Nov

201

2 FI

2 - #

fi2sa

pien

za

19

PARSER PREDITTIVI Provare tutte le possibili produzioni porta a programmi lenti Supponi di dover espandere il non terminale A e di avere due produzioni del tipo

A → α

A → β

Dobbiamo saper scegliere la produzione giusta sulla base dell’input ancora da esaminare Se siamo in grado di fare questo otteniamo un parser predittivo che non ha bisogno di simulare il non determinismo

Nov

201

2 FI

2 - #

fi2sa

pien

za

20

ESEMPIO I linguaggi di programmazione sono spesso adatti al parsing predittivo Esempio stmt ::= id = exp ; | !

return exp ; | !

if ( exp ) stmt | !

while ( exp ) stmt !

Se la prima parte dell’input da esaminare inizia con IF PARENTESI-SIN ID …

allora dovremmo espandere stmt come un if-statement (terza produzione)

Nov

201

2 FI

2 - #

fi2sa

pien

za

21

LL(K) PARSING •  parsing predittivo top-down, spesso a discesa ricorsiva •  analizza l'input da sinistra (Left) a destra e costruisce una

derivazione sinistra (Leftmost) della frase •  usa il lookahead per scegliere la produzione

•  lookahead k significa che l'osservazione dei prossimi k token da leggere permette di decidere quale regola usare

•  LL parsing con lookahead k viene denotato LL(k)

•  in pratica: è rarissimo usare k > 1

•  i linguaggi CF per i quali è possibile effettuare parsing LL(1) sono un sottoinsieme proprio dei CF deterministici

Nov

201

2 FI

2 - #

fi2sa

pien

za

22

GRAMMATICHE LL(1)

Nov

201

2 FI

2 - #

fi2sa

pien

za

23

Data una produzione A ::= α, definiamo FIRST(α) come l'insieme dei simboli terminali che possono essere all'inizio di α Una grammatica è LL(1) se, per ogni simbolo non terminale A, se esistono le produzioni A ::= α e A ::= β, allora

FIRST(α) ∩ FIRST(β) = Ø

Se una grammatica è LL(1) allora possiamo costruire un parser predittivo esaminando un unico simbolo!

N.B. In alternativa al termine FIRST è anche usato come sinonimo il termine STARTERS

PARSING PER GRAMMATICHE LL(1) L’analisi di grammatiche LL(1)

•  Spesso si realizza il parser iterativamente, usando una pila inizializzata con l'assioma

•  Esamina l’input da sinistra a destra •  Quando in cima alla pila abbiamo un simbolo non

terminale A •  Decide la produzione da applicare esaminando 1 simbolo

dell’input La possibilità di esaminare solo un simbolo è sufficiente nella maggioranza dei linguaggi di programmazione

Nov

201

2 FI

2 - #

fi2sa

pien

za

24

ESEMPIO: GRAMMATICA LL(1) PER ESPRESSIONI ARITMETICHE espressione → digit | ‘(‘espressione operatore espressione ‘)’ operatore → ‘+’ | ‘*’

digit → ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’

Nov

201

2 FI

2 - #

fi2sa

pien

za

25

ESEMPIO: GRAMMATICA NON LL(1)

S → A c | B d A → a B → a

α First(α) a {a} c {c} d {d} A {a} B {a} S {a} Ac {a} Bd {a}

Nov

201

2 FI

2 - #

fi2sa

pien

za

26

PARSER TOP-DOWN EFFICIENTI •  Basati su automi

pushdown •  Deterministici •  Riportano un errore

appena l’input non è un prefisso di un programma valido

•  Non applicabili a tutte le grammatiche di tipo 2

generatore del parser

parser

Nov

201

2 FI

2 - #

fi2sa

pien

za

27

grammatica CF

grammatica ambigua

tokens albero di derivazione