Analisi sintattica (parte prima)

(1)

Automi e Linguaggi Formali

Analisi Sintattica

(2)

Ruolo dell’analisi sintattica

Un compilatore deve produrre codice oggetto e deve anche controllare che il programma in input sia scritto secondo le regole della sua sintassi

L’analisi lessicale controlla che i token siano scritti bene, e genera una sequenza di token

L’analisi sintattica prende in input la sequenza di token Non tutte le sequenze di token rappresentano programmi validi Bisogna riconoscere sequenze di token valide, cio`e ottenibili tramite la grammatica che descrive le regole della sintassi del linguaggio

Se la sequenza di token `e valida, deve essere creato un albero di parsing

Automi e Linguaggi Formali – A.A 2014-2015

(3)

Eliminare l’ambiguit`

a

Un analizzatore sintattico deve trasformare la sequenza di token in un albero sintattico

Se la grammatica è ambigua, esistono più alberi di parsing possibili Pertanto è necessario eliminare l’ambiguità

Esempio: C → if E then C C → if E then C else C

Questa grammatica `e ambigua

Il comando if E1 then if E2 then S1 else S2ha due alberi sintattici

Di solito: ogni else va accoppiato con il then pi`u vicino Grammatica non ambigua:

C → C1 | C2

C1 → if E then C1 else C1

(4)

Parsing top-down

Costruisce un albero di parsing per una stringa, iniziando dalla radice e creando i nodi in ordine depth-first (dato un nodo, prima lui e poi i figli da sinistra a destra, ricorsivamente) Trova la derivazione da pi`u a sinistra per una stringa

Ad ogni passo, una produzione viene usata per trasformare un non-terminale

Una volta scelta la produzione, bisogna individuare i simboli terminali della parte destra della produzione nella stringa in input

(5)

Esempio

Grammatica E → TE0 E0→ +TE0| T → FT0 T0→ ∗FT0| F → (E )|id con stringa id + id ∗ id .

(6)

Esempio

(7)

Parsing ricorsivo-discendente

Una procedura per ogni non-terminale

Si inizia con la procedura per il simbolo iniziale

Terminazione con successo se si scorre tutta la stringa in input Pseudocodice non-deterministico per un non-terminale A:

1 scegli una produzione per A: A → X1X2. . . Xk 2 for (i = 1 to k)

3 se Xi `e un non-terminale chiama la procedura per Xi

4 altrimenti, se Xi = simbolo corrente, passa al prossimo simbolo

della stringa

5 altrimenti, errore

La produzione scelta potrebbe non essere quella giusta ⇒ bisogna permettere il backtracking

Errore vuol solo dire che bisogna tornare al passo 1 per scegliere un’altra produzione per A, a meno che non ce ne siano pi`u

(8)

Esempio

Grammatica: S → c A d A → a b | a con stringa cad .

All’inizio, albero con la sola radice S e puntatore all’inizio della stringa (c)

S ha solo una produzione, quindi usiamo quella Puntatore scorre anche c

Usiamo la prima produzione per A e aggiungiamo i figli a e b Puntatore scorre anche a, ma b `e diverso dal prossimo simbolo della stringa (d)

Torniamo indietro e proviamo la seconda produzione per A (puntatore torna indietro alla c e poi scorre a)

Puntatore legge d che `e uguale al possimo simbolo nella stringa

La stringa `e finita, quindi abbiamo creato un albero di parsingAutomi e Linguaggi Formali – A.A 2014-2015

(9)

(10)

Ricorsione a sinistra

Una grammatica `e “ricorsiva a sinistra” se esiste un non-terminale A tale che A⇒ Aα per qualche stringa α∗ I metodi di parsing top-down non possono gestire grammatiche ricorsive a sinistra: vanno in loop perch´e riscrivono sempre a sinistra

Ricorsivit`a sinistra diretta: produzione A → Aα|β Nuove produzioni: A → βA0 e A0 → αA0_|

Si pu`o eliminare anche la ricorsivit`a sinistra non diretta Esempio:

S → Aα|γ A → S β `

e ricorsiva a sinistra perch´e S⇒ Sβα+

(11)

Parser predittivi

Come i parser discendenti ricorsivi ma possono “predire” quale produzione usare

guardando ad alcuni prossimi token

non c’`e mai bisogno di tornare indietro (backtracking)

Funzionano con grammatiche LL(k)

La prima L significa che l’input viene letto da sinistra a destra La seconda L significa che seguono derivazioni da sinistra Il k significa che la predizione `e basata sulla lettura anticipata di k token

(12)

LL(1) vs. Parser discendenti ricorsivi

Nei parser discendenti ricorsivi

Ad ogni passo, molte produzioni tra cui scegliere Backtracking per ritrattare le scelte sbagliate

In LL(1)

Ad ogni passo, una sola produzione (o nessuna, che vuol dire errore)

Variante di parser ricorsivi discendenti senza backtracking

(13)

Come predire quale produzione usare?

Consideriamo la grammatica E → T + E |T

T → a|a ∗ T |(E ) Difficile predire perch´e

Per T: due produzioni iniziano con a Per E: non chiaro quale usare

(14)

Esempio

La grammatica E → T + E |T T → a|a ∗ T |(E )

pu`o essere trasformata in

E → TX X → +E | T → aY |(E ) Y → ∗T |

(15)

FIRST and FOLLOW

Due funzioni che ci permettono di capire quale produzione scegliere, leggendo il prossimo simbolo in input

FIRST(α) = insieme di terminali che iniziano stringhe derivabili da α, dove α `e una qualunque stringa di simboli terminali o non Se α⇒ , allora ∈ FIRST (α)∗

Esempio di uso: se abbiamo le produzioni A → α|β, e FIRST(α) `e disgiunto da FIRST(β), allora basta guardare il prossimo simbolo in input. Se `e in FIRST(α), va scelta la produzione A → α.

FOLLOW(A), per un non-terminale A, `e l’insieme del terminali a che possono apparire alla destra di A in una forma sentenziale Esiste una derivazione S ⇒ αAaβ∗

Se A `e il simbolo pi`u a destra in qualche forma sentenziale, allora $ `

(16)

Come calcolare FIRST di un simbolo

Calcoliamo FIRST(X) per ogni simbolo X, terminale o no Se X `e terminale, FIRST(X) = {X}

Se X `e non terminale e X → Y1Y2. . . Yk,

Se esiste i tale che a ∈ FIRST (Yi) e

∈ FIRST (Y1) ∩ . . . ∩ FIRST (Yi −1), allora a ∈ FIRST (X ).

Se ∈ FIRST (Yj) per tutti i j = 1, . . . , k, allora ∈ FIRST (X )

Nota: tutto quello che `e in FIRST(Y1) `e anche in FIRST(X).

Se Y1non deriva , allora FIRST(X) = FIRST(Y1), altrimenti

aggiungiamo FIRST(Y2), e cos`ı via. Se X → , allora ∈ FIRST (X )

(17)

Come calcolare FIRST di una stringa

Per calcolare FIRST(X1. . . Xn):

Mettiamo in FIRST(X1, . . . , Xn) tutti i simboli di FIRST(X1)

tranne

Se ∈ FIRST (X1), mettiamo anche i simboli di FIRST(X2)

tranne

Se ∈ FIRST (X1) ∩ FIRST (X2), mettiamo anche i simboli di

FIRST(X3) tranne

E cos`ı via

Se in tutti i FIRST(Xi) per tutti gli i, mettiamo in

(18)

Come calcolare FOLLOW

Mettiamo $ in FOLLOW(S), dove S `e il simbolo iniziale Se produzione A → αBβ, mettiamo in FOLLOW(B) tutto FIRST(β) meno

Se produzione A → αB, o produzione A → αBβ, dove ∈ FIRST (β), mettiamo in FOLLOW(B) tutto FOLLOW(A)

(19)

Esempio

Grammatica: E → TE0 E0 → +TE0| T → FT0 T0 → ∗FT0| F → (E )|id

FIRST(F) = FIRST(T) = FIRST(E) = {(, id } FIRST(E’) = {+, }

FIRST(T’) = {∗, }

FOLLOW(E) = FOLLOW(E’) = { ), $} FOLLOW(T) = FOLLOW(T’) = {+, ), $} FOLLOW(F) = {+, ∗, ), $}

(20)

Grammatiche LL(1)

Se G ha le due produzioni A → α e A → β:

FIRST(α) e FIRST(β) sono due insiemi disgiunti

Da α e β non si possono derivare stringhe che iniziano con lo stesso terminale

Al pi`u uno tra α e β pu`o derivare la stringa vuota

Se in FIRST(β), allora FIRST(α) e FOLLOW(A) sono disgiunti, e simile se in FIRST(α).

Se β⇒ , α non deriva nessuna stringa che inizia con un∗ terminale in FOLLOW(A)

Se α⇒ , β non deriva nessuna stringa che inizia con un∗ terminale in FOLLOW(A)

(21)

Tavola per il parser predittivo

Matrice bidimensionale M[A,a], dove A `e un non-terminale, e a `e un terminale o $

Idea: la produzione A → α è scelta se il prossimo simbolo di input a è in FIRST(α). Se α⇒ , allora va scelta se a è in∗ FOLLOW(A).

Per ogni produzione A → α:

Per ogni terminale a in FIRST(α), mettiamo A → α in M[A,a] Se ∈ FIRST (α), mettiamo A → α in M[A,b] per ogni b ∈ FOLLOW(A)

Se ∈ FIRST (α) e $ ∈ FOLLOW(A), mettiamo A → α anche in M[A,$]

(22)

Esempio

non simbolo d’ingresso

terminale id + * ( ) $

E E → TE’ E → TE’

E’ E’ → +TE’ E’ → E’ →

T T → FT’ T → FT’

T’ T’ → T’ → *FT’ T’ → T’ →

F F → id F → (E)

(23)

Funziona solo per grammatiche LL(1)

Ad esempio, se la grammatica è ricorsiva a sinistra o ambigua, la tavola avrà una o più celle con più produzioni

Esempio: S → iEtSS’ | a S’ → eS | E → b

(24)

Esempio

S → iEtSS’ | a S’ → eS | E → b

non simbolo d’ingresso

terminale a b e i t $

S S → a S → iEtSS’

S’ S’ → , S’ → eS S’ →

E E → b