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

Token: S id E num .= print ( ) , +

S : statement (istruzione) id: identificatore E: espressione num: numero

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

Nov

201

2 FI

2 - #

fi2sa

pien

za

8

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

GRAMMATICHE AMBIGUE Una grammatica è ambigua quando per una stessa stringa che appartiene al linguaggio definito esistono 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 5  T ! T * F 6  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 5  T ! F + T 6  T ! F 5 F ! id 6 F ! (E)

Nov

201

2 FI

2 - #

fi2sa

pien

za

10

PERCHÉ GRAMMATICHE CF PER 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 come legale (cioè che potrebbe fornire una stringa del linguaggio)

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

Equivalentemente

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’albero dalle foglie •  Avanza nell’input (shift) o deriva un non terminale

(reduce) •  Accetta quando input è finito e hai ottenuto assioma •  Ricostruisce in effetti l'albero attraverso una sua visita in

post-order

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 • Albero ricostruito in pre-ordine

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)

Per motivi di efficienza 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.

Nov

201

2 FI

2 - #

fi2sa

pien

za

18

ANALISI TOP-DOWN: PARSER A DISCESA RICORSIVA Tentare di usare una produzione significa consumare porzioni di input (terminali nella parte destra) e chiamare funzioni associate a non terminali.

Esempio: A ! aBcD

Abbiamo successo se e solo se •  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

19

int A(...) { /* par.: porzione di input da leggere */! /* prova la prima possibilità A ! "1 "2 … "n */! if ("1(...)) {! if (! "2()) Error(“Missing "2”);! if (! "3()) Error(“Missing "3”);! …! if (! "n()) Error(Missing "n”);! return SUCCESSO;! }! /* prova la seconda alternativa A ! #1 #2 … #mm*/! 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

20

Se ci sono due produzioni del tipo A ! "1 "2 … "n | #1 #2 … #m

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

21

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

22

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

23

GRAMMATICHE LL(1) N

ov 2

012

FI2

- #fi2

sapi

enza

24

•  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, e per ogni produzioni A ::= " e A ::= #, allora

FIRST(") " FIRST(#) = Ø

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

•  Infatti in questo caso dato A ! " | # possiamo decidere se applicare la prima o la seconda produzione esaminando se il simbolo di input in esame appartiene a FIRST(") o a FIRST(#)

•  In alternativa al termine FIRST è anche usato come sinonimo il termine STARTERS

NOTA: nel caso " ⇒* # sono necessarie delle precisazioni e la def. va completata; v. discussione su FOLLOW

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 decide la produzione da applicare esaminando un 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

25

ESEMPIO: GRAMM. LL(1) PER ESPRESSIONI ARITMETICHE CON PARENTESI Consideriamo il caso (banale) di espressioni aritmetiche completamente parentetizzate:

espressione ! digit | ‘(‘espressione operatore espressione ‘)’

operatore ! ‘+’ | ‘*’ digit ! ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’

Esempio: ((3+5)*2) appartiene al linguaggio

3+5*2 o (3+5)*2 NON appartengono al linguaggio

Questa grammatica è LL(1)

Nov

201

2 FI

2 - #

fi2sa

pien

za

26

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

27

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

28

grammatica CF

grammatica ambigua

tokens albero di derivazione

APPROCCIO IMPERATIVO •  Si può basare il parser su una tabella di parsing avente

|VN| linee e |VT| colonne

•  Ciascuna linea è associata a un non terminale, ciascuna colonna a un token

•  Nella casella (A, t) si inserisce la produzione A $ " se t $ SELECT (A $ ")

•  Caselle vuote corrispondono a errori sintattici

Nov

201

2 FI

2 - #

fi2sa

pien

za

29

UN SEMPLICE ESEMPIO

E $ ( E ) | id

( ) ID $ E E $ (E) E $ id

Nov

201

2 FI

2 - #

fi2sa

pien

za

30

PARSER TOP-DOWN EFFICIENTI

•  Data una grammatica per stabilire se è LL(1) dobbiamo calcolare gli insiemi First()

•  Questa operazione è complicata nel caso di produzioni del tipo

A $ % (produzioni vuote) &

expr ::= term + expr ¦ term

(produzioni con ricorsione)

•  ll calcolo degli insiemi First nel caso generale è discusso nel seguito

generatore del parser

parser

Nov

201

2 FI

2 - #

fi2sa

pien

za

31

grammatica CF

grammatica ambigua

albero di derivazione

FIRST-SET Definizione

Data una grammatica CF G = (VT, VN, S, P) e una stringa (forma di frase) " ∈ V*, definiamo

FIRST(") = { t | (t ∈ VT " ⇒* t%) (t = # " ⇒* #) }

ove % ∈ V*

Calcolo di FIRST("), dapprima per terminali ed #

•  FIRST(a) = { a }, per ciascun terminale a

•  FIRST(#) = { # }

Nov

201

2 FI

2 - #

fi2sa

pien

za

32

FIRST-SET PER NON TERMINALI Per ciascun non terminale A, calcoliamo FIRST(A) inizializzandolo all'insieme vuoto e poi considerando le produzioni su A Per ciascuna produzione A ! B1B2…Bk, ove Bi ∈ V, FIRST(A) = FIRST(A) ∪ (FIRST(B1) \ { # }) if(# ∈ FIRST(B1)) then FIRST(A) = FIRST(A) ∪ (FIRST(B2) \ { # }) if(# ∈ FIRST(B2)) then FIRST(A) = FIRST(A) ∪ (FIRST(B3) \ { # }) … if(# ∈ FIRST(Bk-1)) then FIRST(A) = FIRST(A) ∪ (FIRST(Bk) \ { # }) if(# ∈ FIRST(Bk)) then FIRST(A) = FIRST(A) ∪ { # } (stop al primo test che fallisce)

Nov

201

2 FI

2 - #

fi2sa

pien

za

33

ESEMPIO calcolare i FIRST-SET per i non terminali della seguente grammatica

<exp> $ <term> <exp'>

<exp&> $ ' <term> <exp&> | #

<term> $ <factor> <term&> <term&> $ / <factor> <term&> | #

<factor> $ INTLITERAL | ( <exp> )

Nov

201

2 FI

2 - #

fi2sa

pien

za

34

FIRST-SET PER PARTI DESTRE DELLE PRODUZIONI

Calcolo di FIRST(") simile al calcolo di FIRST(A)

supp. " = B1B2…Bk, ove Bi ∈ V; FIRST(") = Ø

FIRST(") = FIRST(") ∪ (FIRST(B1) \ { # })

if(# ∈ FIRST(B1)) then FIRST(") = FIRST(") ∪ (FIRST(B2) \ { # }) if(# ∈ FIRST(B2)) then FIRST(") = FIRST(") ∪ (FIRST(B3) \ { # })

…

if(# ∈ FIRST(Bk-1)) then FIRST(") = FIRST(") ∪ (FIRST(Bk) \ { # })

if(# ∈ FIRST(Bk)) then FIRST(") = FIRST(") ∪ { # }

(stop al primo test che fallisce)

Nov

201

2 FI

2 - #

fi2sa

pien

za

35

LL(1) PARSER: PRIMO TENTATIVO 1.  Costruisci i FIRST-SET

2.  Se grammatica non LL(1) errore

3.  Procedi costruendo un parser predittivo a discesa ricorsiva

•  un metodo per ciascun non terminale A •  per ogni token t $ FIRST(") usa la regola A $ "

Problema: se # ∈ FIRST(") si possono "perdere" predizioni.

In pratica: il parser dovrebbe poter usare la produzione A $ " se # ∈ FIRST(") e il prossimo carattere in input appartiene all'insieme dei simboli che potrebbero seguire A

Nov

201

2 FI

2 - #

fi2sa

pien

za

36

FOLLOW-SET Definizione Data una grammatica CF G = (VT, VN, S, P) e un non terminale A ∈ VN, definiamo FOLLOW(A) = { t | (t ∈ VT S ⇒+ "At%) (t = $ S ⇒+ (A) } ove (, % ∈ V* e $ denota la fine dell'input (talvolta si usa EOF in luogo di $)

Nov

201

2 FI

2 - #

fi2sa

pien

za

37

CALCOLO DI FOLLOW-SET

inizializzazione: FOLLOW(S) = { $ }, FOLLOW(A) = Ø per A ! S

per calcolare FOLLOW(B), B ∈ VN, individua le produzioni ove B compare nella parte destra

•  per ciascuna produzione X $ (B% FOLLOW(B) = FOLLOW(B) ∪ (FIRST(%) \ { # } )

•  se # ∈ FIRST(%) FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(X)

•  per ciascuna produzione X $ (B FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(X)

N.B. I FOLLOW-SET si calcolano solo per i non terminali

Nov

201

2 FI

2 - #

fi2sa

pien

za

38

DEF. GR CF LL(1) Per ogni produzione A $ (, definiamo SELECT(A $ () come

•  FIRST(() U FOLLOW(A), se # ∈ FIRST(() [( si può annullare]

•  FIRST((), se # FIRST(() [( non si può annullare]

Definizione di grammatica CF LL(1)

Una grammatica CF è LL(1) se, per ogni coppia di produzioni sullo stesso non terminale A $ ( e A $ #,

SELECT(A $ ( ) " SELECT(A $ #) = Ø

Nov

201

2 FI

2 - #

fi2sa

pien

za

39

ESEMPIO "STATEMENTS"

GR LL(1)

stmt ::= id = exp ; | return exp ; | if ( exp ) stmt | while ( exp ) stmt

METODO

// parse stmt ::= id=exp; | …

void stmt( ) {

switch(nextToken) {

RETURN: returnStmt(); break;

IF: ifStmt(); break;

WHILE: whileStmt(); break;

ID: assignStmt(); break;

}

}

Nov

201

2 FI

2 - #

fi2sa

pien

za

40

ESEMPIO (CONT)

WHILE // parse while (exp) stmt void whileStmt() {

// skip “while (” getNextToken();

getNextToken(); // parse condition

exp(); // skip “)”

getNextToken(); // parse stmt stmt();

}

RETURN

// parse return exp ; void returnStmt() {

// skip “return”

getNextToken();

// parse expression

exp();

// skip “;”

getNextToken();

}

Nov

201

2 FI

2 - #

fi2sa

pien

za

41

POSSIBILI PROBLEMI • Ricorsioni sinistre

•  es., E ! T| E + T | …

• Parti destre di produzioni sullo stesso non terminale aventi un prefisso comune

•  es., A ! aBC | aCD | …

Rendono le grammatiche non LL(1)!

Nov

201

2 FI

2 - #

fi2sa

pien

za

42

RICORSIONE SINISTRA

PRODUZIONI

expr ::= expr + term

¦ term

CODICE (ERRATO!)

// parse expr ::= …

void expr() {

expr();

if (current token is PLUS) {

getNextToken();

term();

}

}

Nov

201

2 FI

2 - #

fi2sa

pien

za

43

TENTATIVO DI SOLUZIONE sostituire la ricorsione sinistra con una destra

expr ::= term + expr ¦ term

prefisso comune! (non LL(1))

Nov

201

2 FI

2 - #

fi2sa

pien

za

44

RISOLUZIONE DI RICORSIONI SINISTRE Uso di ricorsione destra + nuovo non terminale

da expr ::= expr + term | term

a

expr ::= term exprtail exprtail ::= + term exprtail | )

codificabile direttamente!

Nov

201

2 FI

2 - #

fi2sa

pien

za

45

RISOLUZIONE DI RICORSIONI SINISTRE Produzioni del tipo A $ A" | %, ove % non inizia con A, costruiscono stringhe del tipo %""…" Sono generabili da A $ %A' A' $ "A' | #

Più in generale A $ A"1 | A"2 | … | A"r | %1 | %2 | … | %s

si risolvono con A $ %1A' | %2A' | … | %sA' A' $ "1A' | "2A' | … | "rA'| #

Nov

201

2 FI

2 - #

fi2sa

pien

za

46

CODICE PER LE ESPRESSIONI (1)

// parse

// expr ::= term { + term }*

void expr() {

term();

while (next symbol is PLUS)

{

getNextToken();

term()

}

}

// parse

// term ::= factor { * factor }*

void term() {

factor();

while (next symbol is TIMES)

{

getNextToken();

factor()

}

}

Nov

201

2 FI

2 - #

fi2sa

pien

za

47

CODICE PER LE ESPRESSIONI (2)

// parse

// factor ::= int | id | ( expr )

void factor() {

switch(nextToken) {

case INT:

process int constant;

getNextToken();

break;

…

case ID: process identifier; getNextToken(); break; case LPAREN: getNextToken(); expr(); getNextToken(); } }

Nov

201

2 FI

2 - #

fi2sa

pien

za

48

PREFISSI COMUNI Se esistono due produzioni sullo stesso non terminale con un prefisso comune

A $ " % | " *

si può usare la fattorizzazione

A $ " A'

A' $ % | *

Nov

201

2 FI

2 - #

fi2sa

pien

za

49

ESEMPIO ISTRUZIONE IF grammatica originale

ifStmt ::= if ( expr ) stmt | if ( expr ) stmt else stmt

grammatica fattorizzata

ifStmt ::= if ( expr ) stmt ifTail ifTail ::= else stmt | )

Nov

201

2 FI

2 - #

fi2sa

pien

za

50

PARSING DI ISTRUZIONI IF

può essere più semplice codificare direttamente la regola "else assegnato all'ultimo if aperto"

// parse

// if (expr) stmt [ else stmt ]

void ifStmt() {

getNextToken();

getNextToken();

expr();

getNextToken();

stmt();

if (next symbol is ELSE) {

getNextToken();

stmt();

}

}

Nov

201

2 FI

2 - #

fi2sa

pien

za

51

LL(1) PARSING DEMO

appl

et h

ttp://

ag-k

aste

ns.u

ni-

pade

rbor

n.de

/lehr

e/m

ater

ial/u

ebi/

pars

dem

o/ll1

fram

e.ht

ml

Nov

201

2 FI

2 - #

fi2sa

pien

za

52

PARSER PREDITTIVO PER ESPRESSIONI ARITMETICHE

1  E ! E + T 2  E ! T 5  T ! T * F 6  T ! F 5 F ! id 6 F ! (E)

Nov

201

2 FI

2 - #

fi2sa

pien

za

53

CALCOLO DEI FIRST-SET PER GRAMMATICA ESPRESSIONI

1  E ! E + T 2  E ! T 5  T ! T * F 6  T ! F 5 F ! id 6 F ! (E)

Modified First Sets First(F) = { id } First(F) = { id, ( } First(T) = { id, ( } First(E) = { id, ( } First(E+T) = { id, ( } First(T*F) = { id, ( }

Rule Select 1 { id, ( } 2 { id, ( } 3 { id, ( } 4 { id, ( } 5 { id } 6 { ( }

Nov

201

2 FI

2 - #

fi2sa

pien

za

54

SELECT-SET PER GRAMMATICA ESPRESSIONI MODIFICATA

1  E ! T E’ 2  E’ ! % 3  E’ !+ T E’ 4  T ! F T’ 5  T’ ! % 6  T’ ! * F T’ 7  F ! id 8  F ! (E)

First-Sets First(F) = {id, (}

First(T) = {id, (}

First(E)={id, (}

First(E’) = {+}

First(T’) = {*}

First(T E’)= {id, (}

First(%) = {}

First(+ T E’) = {+}

First(F T) = {id, ( }

First(* F T’) = {*}

First(id) = {id}

First(( E )) = {(}

Rule Select 1 {id, (} 2 {$, )} 3 {+} 4 {id, (} 5 { +, ), $} 6 {*} 7 {id} 8 {(}

Follow-Sets Follow(E) = {$, )}

Follow(E’) = {$, )}

Follow(T) = {+, ), $}

Follow(T’)={+, ), $}

Follow(F) = {*, +, ), $}

Nov

201

2 FI

2 - #

fi2sa

pien

za

55

LL VS LR •  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

Nov

201

2 FI

2 - #

fi2sa

pien

za

56

TRATTAMENTO ERRORI SINTATTICI •  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

Nov

201

2 FI

2 - #

fi2sa

pien

za

57

ESEMPIO N

ov 2

012

FI2

- #fi2

sapi

enza

58

a := a * ( b + c * d ;

Il simbolo “;” funziona da delimitatore e permette di continuare l’analisi

CONCLUSIONI •  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

Nov

201

2 FI

2 - #

fi2sa

pien

za

59