•Scopi •Tecniche •Strumenti – ANTLR-Yacc sintattica.pdf · context free - complessità...

L3 - Introduzione ai compilatori -UNINA

1

Analisi sintattica

•Scopi •Tecniche•Strumenti – ANTLR-Yacc


2

L’analizzatore sintattico (parser) nel compilatore

Analizzatore lessicale

Analizzatore sintattico

Symbol table

Parse tree

Next token

Linguaggio sorgente

Fasi successive

token


3

Tipi di parser

• Parser Universali: analizzano qualsiasi grammatica context free - complessità esponenziale

Usati nella pratica (complessità lineare):• Parser Top Down: visita dell’albero di derivazione

dall’alto (radice) verso il basso (foglie) - LL • Parser Bottom Up: visita dell’albero di derivazione

dal basso (foglie) verso l’alto (radice) - LR

Punto di partenza per la costruzione di un parser: la grammatica del linguaggio


4

Parser top down- analisi discendenteCostruzione dell’albero di analisi a partire dalla radice creando i nodi in “preordine”- Es.

S→ aSA1| b2

A→ bA3 |aA4 | a5 | cA6

abbaca

S

a S A

b b A

c

A

aOrdine applicazione delle produzioni: 1,2,3,4,6,5

S � aSA � abA � abbA � abbaA � abbacA � abbaca

derivazione canonica sinistra

al posto della 4, anche si potrebbe applicare anche la 5

a

A


5

Analisi discendente - parser predittivo• L’analisi discendente può richiedere il backtrack: per un

simbolo input a è possibile applicare più produzioni:

A → α1 |…|αn se esistono più alternative (α1…αn) che iniziano con a. Rimedio: fattorizzazione sinistra

• L’analisi discendente non è applicabile se la grammatica èricorsiva sinistra (left recursive), cioè se A � Aα (A non terminale). Rimedio: eliminazione ricorsione sinistra

• Può essere possibile adattare una grammatica in modo che si applicabile un parser predittivo che operi senza backtrack.


6

Fattorizzazione sinistra

Idea: quando non è chiaro quale produzione usare per per espandere un non terminale A, si possono riscrivere le produzioni in moda da “postecipare” la scelta, introducendo un non terminale supplementare.

ES.:

A → α β1 | α β2

fattorizzazione sinistra:A → α A’

A’ → β1 | β2

<stmt> → if <expr> then <stmt>| if <expr> then <stmt> else <stmt>

fattorizzazione sinistra:<stmt> → if <expr> then <stmt><S><S> → ε | else <stmt>


8

Eliminazione ricorsione sinistra - 1Metodo: date le produzioni “ricorsive sinistre” e non di un non

terminale A:A → A α1| …|Aαn| β1 |…| βn

si sostituiscono con (eliminazione ricorsione sinistra immediata)A → β1A’ |…| βnA’A’ → α1 A’| …| αn A’| ε

Es. espressioni aritmetiche

E → E+T | TT → T*F | FF → (E) |id

E → TE’E’ → +TE’|εT → FT’T’ → *FT’|εF → (E) |id


9

Eliminazione ricorsione sinistra - 2

Per eliminare le ricorsioni sinistre non immediate (A �+ Aα )si usa l’algoritmo: A1, … , An non terminalifor (i=1 to n) do

for (j=1 to i-1) {1) sostituisci Ai → Aj γ con Ai → δ1 γ | … | δnγ(Aj → δ1 | … | δ n sono le produzioni di Aj)

2) elimina le ricorsioni sinistre immediate per Ai }

Es.: S → Aa|bA → Ac|Sd| ε

S → Aa|bA → Ac|Aad|bd|ε

S → Aa|bA → bdA’|A’A’ → cA’|adA’| ε


10

Automi a pila (push down)Nastro di ingresso

Unità di controllo

Z1

...

Zkpila

push

Z1

...

Zk

Z1

...

Zk

Zk

popZk


11

Automi a pila non deterministici(Q, Σ, Γ,δ, q0, Z0, F)

• Q è l’insieme di stati• Σ è un insieme di simboli (alfabeto di input)• Γ è un insieme di simboli (alfabeto della pila)• δ è la funzione d transizione o di stato dell’automa ed associa alle

triple stato, simbolo input, simbolo in cima alla pila sotto insieme di stati (anche vuoto) e una nuova stringa di pila– δ: (Q × Γ ×(Σ U ε)) � 2Q xΓ*

• q0 è uno stato particolare detto lo stato iniziale dell’automa• Z0è il carattere iniziale della pila• F è un insieme di stati detti stati finali (o di accettazione) dell’automa.


12

Mosse dell’automaδ (q, a, Z) = {(p1,γ1),…,(pn, γ n)}

• l’automa con Z in cima allo stack e a in lettura può scegliere di passare ad uno degli stati p1, pn sostituendo a Z γ1... γ n in cima allo stack e passa al prossimo carattere.

δ (q, ε, Z) = {(p1,γ1),…,(pn, γ n)}• l’automa con Z in cima allo stack e senza leggere alcun

carattere in ingresso può scegliere di passare ad uno degli stati p1, pn sostituendo a Z γ1... γ n in cima allo stack

• Due tipi di indeterminismo: | δ (q, a, Z)|>1 (più transizioni possibili per coppia a,Z) e quando δ ( q, a, Z) e δ (q ε, Z) sonn entrambe definiti (l’automa può scegliere se legger o meno il carattere)

Riconoscimento per svuotamanto della pila (qo,x,Z0) → (q, ε, ε) oppureper raggiungimento stato finale: (qo,x,Z0) → (q, ε, γ) (q∈ F)• le diverse modalità di riconoscimento sono equivalenti


13

Algoritmo-Data la grammatica G=(V, Σ, P,S ), l’automa a pila che riconosce il linguaggio generato dalla grammatica è dato da

({q0}, Σ,, Γ =(V ∪ Σ, ∪ {Z0}), δ, q0, Z0, F=∅ )Funzione di transizione δ (mosse dell’automa)• l’automa inizia caricando l’assioma e la marca finale sulla pila (q0,S)

∈ δ(q0, ε , Z0)

• X è il simbolo al top dello stack, a è il carattere letto:– se X∈ V ed esiste una produzione X→α, l’automa sostituisce X con αR in cima

allo stack senza passare al carattere successivo ((q0, αR) ∈ δ(q0, ε , X)), altrimenti emette un messaggio di errore - applicazione di una produzione

Dalla grammatica all’analizzatore top-down

S

X

Y…

a

X

a

X→b1…bkParsing table

bk

Y

ab1

…

…


14

•l’automa termina con successo con lo svuotamento della pila

(qo, ε,) → δ (q, ,)

•X è il simbolo al top dello stack, a è il carattere letto:

-se X ∈ Σ e X=a pop X e passa al prossimo carattere ((q0, βR) ∈δ(q0, a , X) ed esiste X→a β; inoltre (q0, ε) ∈δ(q0, a , a)) - shift

a

Y…

a b

Y…

a b


15

Parsing TableL’automa può essere realizzato con una tabella di transizione (parsing table):

M [non terminale in cima, terminale letto]=(una o più produzioni da applicare). Esempio “if then else”:

S → if E then SS’|a

S’ → ε | else SE → b

Simbolo inputV

a b else if then Z0

S S→a S → if Ethen SS’

S’ S’ → εS’→ E S

S’ → ε

E E → b

L’automa è in generale non deterministico: più entry nella parsing table


16

Costruzione dell’analizzatore top downLa costruzione dell’automa top-down (riempimento della parsing table) a partire dalla grammatica (V, Σ , P, S) può avvenire tramite due funzioni FIRST e FOLLOW

FIRST(α): insieme di tutti i terminali che iniziano le stringhe derivate da αFIRST(α) ={a∈ Σ : α � aβ , β ∈ (Σ ∪V)*}, α ∈ (Σ ∪V)*; se α �* ε, ε ∈FIRST(α)

FOLLOW(A): insieme di tutti i terminali che seguono il non terminale A in qualche forma sentenziale, ovvero: FOLLOW(A) ={a∈ Σ : S �* αAaβ , α ,β ∈ (Σ ∪V)*}

L’automa si costruisce analizzando ogni produzione della grammatica A → α ed ogni terminale a (M-tabella di transizione)

• se a ∈ FIRST(α) si pone A → α ∈ M[A,a]

• se ε ∈ FIRST(α) si pone A → α ∈ M[A,b] per tutti i terminali b ∈ FOLLOW(A); se FOLLOW(A)=$, A → α ∈ M[A,$] ($ marcatura fine lettura).


17

Costruzione di FIRST e FOLLOWFIRST(α)

1) per i terminali a si pone FIRST(a)={a}.

2) per i non terminali A:

2.1) se A→X1 X2 …Xn∈P si pone tutto ciò che è in FIRST(X1) in FIRST(A) (FIRST(A) ⊇ FIRST(X1)); se X1 �* ε, si pone FIRST(A)⊇ FIRST(X2)…

2.2) se A→ ε si pone FIRST(A) ⊆ {ε }

FOLLOW(A)

1) si pone FOLLOW(S) ⊇ {$}

2) data A→αBβ ∈P

2.1 se β ≠ ε si pone FOLLOW(B) ⊇ FIRST(β); (tutto cio che è in FIRST(β) è in FOLLOW(B))

2.2 se β = ε oppure β �* ε FOLLOW(B) ⊇ FOLLOW(A) es.


18

E → TE’E’ → +TE’|εT → FT’T’ → *FT’|εF → (E) |id

FIRST(E) =FIRST(T)=FIRST(F) ={‘(‘, id }FIRST(E’)={‘+’, ε }FIRST(T’)={‘*’, ε }FOLLOW(E)={‘)’,$} 1-2.1

FOLLOW(E’)=FOLLOW(E)={‘)’,$} 2.2

FOLLOW(T)={‘+’}∪ FOLLOW(E’)={‘+’,‘)’,$} 2.1-2.2

FOLLOW(T’)=FOLLOW(T)={‘+’,‘)’,$} 2.2

FOLLOW(F)={‘*’} ∪ FOLLOW(T’)={‘*’, ‘+’,‘)’,$} 2.2

Esempio calcolo FIRST - FOLLOW

Simbolo input V

( ) + * Id $ E E→TE’ E→TE’ E’ E’ → ε E’→+TE’ E’ → ε

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

F F → (E) F → (id)

PARSE TABLE


19

Grammatiche LL(1)•Una grammatica è detta LL(1) se la sua parsing table non ha più di una produzione per coppia (simbolo input, simbolo statck), ovvero se l’analizzatore discendente è deterministico.

L (left to right) L (leftmost derivation) 1 (1 simbolo di lookhaed di prospezione: l’automa può effettuare transazioni guardando 1 carattere in lettura senza passare al prossimo)

•Esistono grammatiche LL(2)…LL(k)

Proprietà grammatiche LL(1):

•non possono essere ne ambigue ne ricorsive sinistre

•se esistono più produzioni per non terminale (A→ α | β)queste devono derivare stringhe che iniziano con terminali differenti, e solo una può derivare la stringa vuota: in questo caso si ha: β �* ε, α non può derivare stringhe che iniziano con FOLLOW(A).


20

Limiti analisi LL(1)•L’eliminazione della ricorsione sinistra e la fattorizzazione sinistra non garantiscono che la grammatica risultante sia ancora LL(1), anche se è possibile eliminare residue ambiguità (es.: if then else)

•Non esistono tecniche sistematiche per ottenere grammatiche LL(1).

•Esistono linguaggi deterministici non ottenibili da grammatiche LL(1)

•ES.:

S → R | (S)

R → E = E

E → a | (E + E)

(((a+a)))

(((a+a)+a)+a)=a l’analisi LL(k) è insufficiente per qualsiasi k


21

Superamento limiti LL(1)

•Si possono usare tecniche ibride (parser ascendenti per i costrutti tipo espressioni, parser discendenti per i costrutti tipo istruzioni.

•Le grammatiche LL(1) sono una classe di quelle LR: si può sempre utilizzare l’analisi LR con analizzatori ottenuti con strumenti per la generazione automatica di parser


22

Parser top-down a discesa ricorsiva

• Lo stack di un parser top-down può essere implicitamente realizzato attraverso delle funzioni ricorsive

• Per ogni produzione si costruisce una procedura (ev.: ricorsiva) in cui è codificata la parte destra della produzione secondo alcune regole


23

Costruzione parser a discesa ricorsivaA→→→→X1…Xn|Y1…Yn|εεεεA( )

{

if (M[cc,A]=A→X1…Xn){...//codice X1...//codice X2

if(cc==Xi)//caso terminalecc=nextok();

else errore();

Xi(); //== caso non terminale

}

else if (M[cc,A]=A→Y1…Yn)

{ …

}

}

main ()

{

S();

if (cc!=$)errore();

}


24

Grammatica per espressioniE → TE’E’ → +TE’|εT → FT’T’ → *FT’|εF → (E) |id

void E( ) {

T( ) ;

Ep ( );

}

void Ep() {

if(cc=‘+’) {

cc=nextok();

T();

Ep();

} else error();

}

void F () {

if(cc=‘(’) {

cc = nextok();

E();

if (cc!=‘)’ error(); }

else if ( cc != id ) error();

}

...

main ( )

{

E ( );

if (cc!=‘$’) error();

}


25

Trattamento degli errori

•Un parser deve essere in grado di scoprire, diagnosticare e correggere gli errori in maniera efficiente, per riprenderel’analisi e scoprire nuovi errori.

•I parser LL e LR hanno la proprietà “viable prefix”: sono in grado di rilevare un errore non appena si presenta perchésono in grado di riconoscere i prefissi validi del linguaggio


26

Strategie di riparazione•“panic mode”:scoperto l’errore il parser riprende l’analisi in corrispondenza di alcuni token selezionati (es.: delimitatori begin end) scartando alcuni caratteri. Svantaggi: può essere scartato molto input

•“phrase level” correzioni locali ottenute inserendo/modificando/cancellando alcuni terminali per poter riprendere l’analisi (es.: ‘,’scambio’;’) Svantaggi: possibili loop, difficoltà quando la distanza dall’errore è notevole

•“error productions” Uso di produzioni che estendono la grammatica per generare gli errori più comuni. Metodo efficiente per la diagnostica.

•“global correction” Si cerca di “calcolare” la migliore correzione possibile alla derivazione errata (minimo costo di interventi per inserzioni/cancellazioni/). Metodo globale poco usato in pratica, ma tecnica usata per ottimizzare strategia “phrase level”


27

Trattamento degli errori nei parser predittiviUn parser predittivo non ricorsivo conserva nello stack l’informazione dei terminali e dei non terminali che si aspetta nel seguito dell’analisi.Tecniche simili esistono per gli analizzatori ricorsivi.

Tipi di errore:

1) Il terminale sullo stack non corrisponde a quello letto

2) Per A in cima allo stack e a carattere letto, M[A,a] non èdefinita.


28

Scelta dei token di sincronizzazione

Tecniche “panic mode” per la scelta dei token di sincronizzazione:

• Per i non terminali A: FOLLOW(A) - si scartano tutti i terminali fino a trovarne uno in FOLLOW(A), quindi si fa pop(A)

• E’ possibile considerare altri simboli, che terminano il costrutto corrente (es.: ‘;’ dopo assegnamento). Altri esempi: per le espressioni le keyworddelle istruzioni (if <expr> then …), per le istruzioni i blocchi, ecc.

• Durante la ricerca dei token di sincronizzazione, l’analisi può riprendere in corrispondenza di un simbolo in FIRST(A) con l’analisi di A, e dopo continuare la scansione

• Se un non terminale A deriva ε, la produzione può essere usata come default per ridurre i terminal da analizzare in caso di errore

• se un terminale in cima allo stack non corrisponde a quello letto può essere scartato e prodotto un messaggio “simbolo non atteso …”


29

Errori nell’analisi discendenteLa tavola di parsing può essere completata con i token di

sincronizzazione M[A,a]=sync se FOLLOW(A)=a. • Se M[A,a]=‘ ‘skip a; errore• se M[A,a]=sync pop(A) - ripresa da errore• se il terminale a in cima allo stack non corrisponde a quello

letto, skip a - errore

Tecnica Phrase level :le caselle vuote della tavola di parsingvengono riempite con procedure di ricovero


30

ANTLR

Analisi LL(k) per ciascuna fase

Genera e fa interagire analizzatori lessicali, sintattici e semantici (analizzatori AST) scritti in linguaggio Java o C++

LEXERPARSER

TREE-PARSER

Gli analizzatori possono lavorare autonomamente o in collaborazione tra loro.

http://www.antlr.org/ Terence Parr


31

Ciascun analizzatore realizza una classe che estende le classi basi lexer, parser e treeparser.

In tutte le fasi le grammatiche sono scritte in notazione EBNF (anche per il lexer si scrive una grammatica). Le grammatiche EBNF introducono dei simboli aggiuntivi per semplificare la scritta delle grammatiche:

P: a1 | a2 | … | an produzioni alternative per PP: …( a )?... Stringa opzionaleP: …( a )*… Stringhe ripetute 0 o piu’ volteP: …( a )+… Stringhe ripetute 1 o piu’ volte

Per generare i parser scrivere la grammatica in un file “g”: a ciascuna regola corrisponde un metodo della classe che viene eseguito quando viene attivata, dal parser LL(k) la parte destra della regola

a ciascuna regola può corrispondere una “regola semantica”

Le regole semantiche vengono codificate nei metodi corrispondenti della classe parser


32

ANTLR:struttura progettoCiascuna parte (lexer,parser,treegenerator) di un

progetto ANTLR ha una struttura simile:

1. { optional class code }2. class YourParserClass extends Parser

(Lexer o Tree parser) ;

3. options4. tokens5. { optional action for instance vars/methods }6. parser (lexer o tree parser) rules


33

Parte opzioni e tokens

class SqlLexer extends Lexer;

options {k = 2; //== profondità lookhead (prospezione)caseSensitive = false;caseSensitiveLiterals = false;charVocabulary = '\3' .. '\177';

}

tokens { KEYWORD_VOID="void"; EXPR; DECL; INT="int";

}

I token possono essere definiti (TERMINALI) o non definiti. In questo caso sono usati per riferire sotto-alberi creati nel corso dell’analisi.


34

Parte regolerulename : alternative_1| alternative_2 ...

| alternative_n ;

rulename[formal parameters] : ... ; rulename returns [type id] : ... ;

Le regole possono restituire valori o utilizzare parametri.In corrispondenza di ciascuna regola ANTLR genera un metodo della classe

Lexera: …void a(){

}


35

Lexer: analizzatori lessicali con ANTLR• ID : ( 'a'..'z' )+ ; Le regole dell’analizzatore lessicale diventano metodi del

Lexerpublic final void mID(...) throws RecognitionException,

CharStreamException, TokenStreamException

{ ... _loop3:

do { if (((LA(1) >= 'a' && LA(1) <= 'z'))) { matchRange('a','z'); } } while (...); ...

}

• Eliminazione spazi (Token.SKIP)WS : ( ' ' | '\t' | '\n' { newline(); } | '\r' )+

{ $setType(Token.SKIP); } ;


36

Il metodo NextToken

public Token nextToken() throwsTokenStreamException

{ ... for (;;) { Token _token = null;

int _ttype = Token.INVALID_TYPE; resetText(); ... switch (LA(1))

{ case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': mINT(); break;

case '\t': case '\n': case '\r': case ' ': mWS(); break; default: // error } ...

}

}

ANTLR crea un metodo NextToken che chiama a sua volta i metodi delle varie regole lessicali


37

Azioni semanticheLe azioni semantiche sono blocchi di codice “target” che

possono precedere o seguire stringhe riconosciute (es. generare output, modificare symbol table, modifiicarel’albero sintattico). E’ possibile specificare una porzione di codice iniziale comune a più sottoregole.

( {init-action}:

{action of 1st production} production_1

| {action of 2nd production} production_2

)?

“Rule reference” possibilità di passare parametri ai blocchi semantici

funcdef : type ID "(" args ")" block[1] ; block[int scope] : "begin" ... {/*use arg

scope/*} "end" ;


38

Superamento limiti analisi LL• ANTLR consente di usare un valore “indefinito” di lookhaed per

superare i limiti dell’analisi LL(k) (k finito) – prediction block:

( prediction block ) => production

Esempio,distinzione tra set (liste di elementi separati tra virgole), e assegnazione di liste interestat: ( list "=" )=> list "=" list | list ;

• Ci sono casi in cui l’estensione arbitraria della prospezione non elimina l’ambiguità di una grammatica:

stat: "if" expr "then" stat ( "else" stat )? | ... ;

In questi casi ANTRL applica le produzioni in ordine di definizione


39

Analisi ascendente bottom up

• Idea • Analisi LR(0)• Analisi SLR(1)• Analisi LALR(1)• Parser generator: YACC


40

Analisi ascendente bottom upidea

•Costruzione dell’albero di analisi dalle foglie risalendo (riducendolo) alla radice

•Tecnica shift-reduce: si scorre la stringa da sinistra a destra, ed ogni volta che una parte della stringa input coincide con con la parte destra di una produzione B→β, viene sostituita col non terminale a sinistra.

αβγ

B→β

αBγ

S →aABe

A →Abc | b

B → d

abbcde

aAbcde

aAde

aABe

S

Derivazione “rightmost”all’incontrario


41

Analisi ascendente con stack (automa)– Inizialmente lo stack è vuoto e sull’input c’è la stringa da analizzare– Shift L’automa scandisce l’input da sinistra a destra mettendoli sullo stack. – Reduce Quando trova nello stack una parte “riducibile” (handle) la

sostituisce col non terminale associatoS→β0 →β1 … →βn βi=α Aγ ; βi+1=α δγ δ è un handle per βi+1che viene

ridotto da A (produzione A→ δ)

– L’automa si arresta quando non può più sciftare ne ridurre.• Riconoscimento: tutta la stringa analizzata e sullo stack c’è l’assioma• Errore: tutti gli altri casi

• L’automa è deterministico se non c’è mai più di una parte riducibile sullo stack.

42

Schema parser LRNastro di ingresso

Parser LR

sm-1

Xm

smpila

a1 ai... ... am $

Xm-1

Goto table

Actiontable

Tipi di azioni

- shift action[sm,ai]=“ shift s ” il parser esegue una mossa di shift con s=goto(sm,ai), pone s,ai in cima allo stack e passa al prossimo carattere

...

X0

sm

ai

s

Xm

...

...a1 ai... amai+1

ai carattere in lettura

sm simbolo al top dello stack

action [ s, a]

Stato al top dello stack

Simbolo input corrente


43

- reduce action[sm,ai]=“reduce A → β ” il parser esegue una mossa di riduzione, pop r=2|β| simboli dallo stack, con goto(sm-r,A)=s pone s,A in cima allo stack senza passare passa al prossimo carattere

Sm-r

A

s

Xm-r

...

...a1 ai... amai+1

- accept action[sm,ai]=“accept” il parser accetta la stringa input

- error action[sm,ai]=“error” il parser ha scoperto un errore


44

Analisi LR - alcune caratteristiche

• Usata nei linguaggi di programmazione

• Esistono Tool automatici per generare parser.

• La classe delle grammatiche LR include quelle LL (i parser LR(k) “cercano” la parte destra di una produzione “guardando”quello che si è derivato dalla parte destra con k simboli di lookhaed; i parser LL(k) devono scoprire l’uso di una produzione guardando i primi k simboli di quello che deriva dalla parte destra)

• Riconoscimento immediato degli errori


45

Tipi di parser LR

•LR(0) Lift to right, Rightmost

• SLR(1) Simple LR

• LALR(1) Look-haed LR

• LR(k)

si differenziano per le tecniche usate per riempire la action e la goto table, ovvero per come viene scelto di fare le riduzioni

SLR(1) e LALR(1) usate nei parser generator


46

Costruzione LR(0)•Idea base Si devono poter riconoscere i prefissi ascendenti (viable prefix) della grammatica per poter fare poi le riduzioni.

•Realizzazione Si può costruire una automa finito in grado di riconoscere i prefissi ascendenti

•G=(V ,Σ ,P, S)

Un item (o candidata) è una produzione con un punto nella parte destra A→ β1.β2

Se S�*αβ1β2ϒ è una derivazione destra della grammatica A→ β1.β2 èuna candidata per il prefisso ascendente αβ1

Il punto rappresenta il prefisso correntemente analizzato


47

Automa che riconosce i prefissi ascendentiData la grammatica G=(V ,Σ ,P, S), l’automa finito NFA che riconosce i prefissi ascendenti è dato da:

Q={A→α1.α2, A→α1α2∈P} ∪{q0} i prefissi ascendenti che vengono analizzati

q0={S’→. S} stato iniziale - S’∉ S

δ(A→α1.Bα2, ε)={B→.β, B→β ∈P} stati di riduzione

δ(A→α1.Xα2, X)={A→α1X.α2,} stati di shift - goto

F=Q

E’ possibile ottenere il DFA corrispondente applicando l’eliminazione delle

ε-transizioni e la subset construction


48

Esempio NFA che riconosce i prefissi ascendenti -1

S’ →S$ S →SAS → AA →( S ) A → ( )

S’ → .S$ S’ → S.$S

S →. SA

S → . A

ε transizioni


49


S’ →S$ S →SAS → AA →( S ) A → ( )

S’ → .S$ S’ → S.$S

S →. SAS

S →S .A

S → . A

A → .(S)

A → . ( )

S → A.

S’ → S$.$

A


50


S’ →S$ S →SAS → AA →( S ) A → ( )

S’ → .S$ S’ → S.$S

S →. SAS

S →S .A

S → . A

A → .(S)

A → . ( )

AS →S A.

S → A.A

A → (.S)( A → (S.)S

A → (. ) A → ( ).)(

S’ → S$.$

A → (S).

)


51

Costruzione diretta dell’automa DFA riconoscitore dei prefissi ascendenti

Funzioni CHIUSURA e GOTO su set di items

CHIUSURA(I)= {I ∪ {tutti gli item B→. β}}: (A→α1.Bα2 ∈ I, B→ β ∈ P)

coincide con la ε chiusura dell’automa

GOTO(I,X)=CHIUSURA ({A→α1B.α2 : A→α1.Bα2 ∈ I})

_____________________________________________________________

Algoritmo costruzione degli stati Q dell’automa LR(0)

Data G=(V ,Σ ,P, S) si introduce si un simbolo supplementare: S’, S’→S

1)Q=CHIUSURA({S’→ . S})

2) continua fino a che è possibile:

per ogni q ∈ Q per cui esiste p= GOTO(q, X) e p∉ Q,, poni Q, ⊇ p


52

Analisi LR(0)

•Stati di riduzione: contengono item A→ α.

•Stati di spostamento: contengono item A→α1.α2

•Una grammatica è LR(0) se il riconoscitore dei prefissi ascendenti non contiene stati che sono sia di spostamento che di riduzione, e con gli stati di riduzione con una unica candidata

•ES. Grammatica LR(0)

•S’ →S, S →SA|A, A →( S )|( )

grammatica delle parentesi bilanciate


53

Esempio DFA che riconosce i prefissi ascendenti

S’ →S$ S →SAS → AA →( S ) A → ( )

S’ → .S$S →.SAS → . AA → .( S ) A → .( )

S S’ → S.$S →S.AA → .( S ) A → .( )

S → A.

A

S →S$.$

A → ( . S ) A → (.)S →. SAS → . AA → .( S ) A → .( )

(S →S.AA → .( S ) A → .( )

S

S→ SA.(A

(

A

(

A → ( ).)


54

Parser LR(0)

Costruzione della tabella di parsing

I Gli stati s1…sn sono gli stati del riconoscitore dei prefissi ascendenti;lo stato iniziale contiene S→.S’

II Se A→α1.aα2 ∈ si e GOTO[si ,a ]= sj, � action[si ,a] = “shift sj”

s1 è uno stato di spostamento - a è un terminale

III Se A→ α. ∈ si � action[si ,a] = “reduce by A→ α ”, A≠ S’

s1 è uno stato di riduzione- non viene analizzato a

IV Se S’→ S . ∈ si � action[si ,a] = “accept ”

V In tutti gli altri casi action[si ,a] = “error ”

VI La tabella goto viene completata con la funzione GOTO del DFA: GOTO(si, , A) = sj, � goto(si, , A) = sj


55

Analisi SLR(1)

L’analisi LR(0) non è applicabile in molti casi pratici, come ad esempio le espressioni

E’ → E E → E+T | TT → T*F | F F → (E) | id

Il riconoscitore dei prefissi ascendenti ha più di uno stato sia di riduzione che di spostamento:

E → T.T → T .*F


56

Esempio DFA per grammatica non LR(0)

E’ → E E → E+TE → TT → T*F T → F F → (E) F → id

E

(

E’ → .E E → .E+TE → .TT → .T*F T → .F F → .(E) F → .id

1 E’ → E. E → E.+T

2

E → T. T → T.*F

3T

T→ F. 4

F

5

id

6F → id. F → (.E)

E → .E+TE → .TT → .T*F T → .F F → .(E) F → .id

E → E+.TT → .T*F T → .F F → .(E) F → .id

7+

T

E → E+T. T →T.*F

8

T →T*.FF → .(E) F → .id

*9

(

id

T→T* F. 10

F

*

E’ →(E.)E → E.+T

11E

TF

id

T

+

E→ (E). 12)

(Nello stato 3 la riduzione non èpossibile con * in lettura

(

id

F


57

Parser SLR(1)

Costruzione della tabella di parsing -

I Gli stati s1…sn sono gli stati del riconoscitore dei prefissi ascendenti-lo stato iniziale contiene S→.S’

II Se A→α1.aα2 ∈ si e GOTO[si ,a ]= sj, � action[si ,a] = “shift sj”

III Se A→ α. ∈ si � action[si ,a] = “reduce by A→ α ” per tutti gli a che sono in FOLLOW(A), A≠ S’

IV Se S’→ S . ∈ si � action[si ,a] = “accept ”


VI La tabella goto viene completata con la funzione GOTO del DFA: GOTO(si, , A) = sj, � goto(si , A) = sj


58

Tabella di parsing SLR(1) - esempio

1) E’ → E 2) E → E+T3)E → T4)T → T*F 5)T → F 6)F → (E) 7)F → id

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

Id + * ( ) $ E F T1 R6 S5 2 3 42 S7 Acc3 R3 S9 R34 R55 S6 S5 11 3 46 R77 S6 S5 8 48 R2 S9 R29 S6 S5 1010 R511 S7 S1212 R6 R6

ACTION GOTO

E → T.

T → T.*F

Rimozione conflitto shift-reduce stato 3 LR(0) con ‘*’ in lettura.

Dato che ‘*’ non appartiene a FOLLOW(E) is esegue “scift”


59

Limiti analisi SLR(1)I parser SLR(1) sono usati in pratica, ma possiedono alcune importanti limitazioni.

ES.:

S →L=R

S → R

L →*R

L → idR →Lgrammatica assegnamento

linguaggio C

S’ →. SS →. L=R

S →. R

L →. *R

L →. idR →. L

Stato iniziale DFA LR(0)

L S →L .=R

R →L .

Il parser SLR(1) con ‘=‘ in -1 -può

Ridurre: R →L,

‘=‘∈FOLLOW(R) - S�L=R �*R=R

shiftare: S →L .=R

Se in input c’è ‘=‘ la mossa da fare è “shift” perché si sta facendo la derivazione S �L=R � *R=R

01


60

Superamento limiti analisi SLR(1)• L’idea è quella di effettuare le riduzioni A → α in corrispondenza dei simboli che effettivamente seguono il non terminale A nel contesto della derivazione (prospezione), e non scegliendo tutti quelli che sono in FOLLOW(A).

• L’uso esplicito della prospezione aumenta la classe delle grammatiche analizzabili.

Item LR(1) = [A→α1. α2 , a] A → α1α2 è una produzione, a un terminale o la marcatura $

Data una derivazione destra della grammatica S�*αβ1β2ϒ, un item LR(1)

[A→ β1.β2 , a] è un candidato per il prefisso ascendente αβ1 se a è il primo simbolo di ϒ, oppure se ϒ= ε, allora a = $.

• E’ possibili usare più simboli di prospezione (analisi LR(k))

• L’analisi LR(k) è poco usata in realtà, ci si limita la caso LR(1)


61

Analisi LR(1)L’automa che riconoscere i prefissi ascendenti esegue:

εεεε - transizioni

[A→α1. Bα2 , a] [B→. γ , b] se:1) α2 �* bβ da α2 è derivabile una stringa che inizia con b;2) α2 �* ε, b = a altrimenti.

Deve essere b ∈ FIRST(α2a))Le riduzione [B→ γ ., b] sono attuabili solo se b è il simbolo di input (non per tutti a ∈ FOLLOW(B))

goto X- transizione

[A→α1. Xα2, a] [A→α1X .α2, a]


62

Parser LR(1)

Costruzione della tabella di parsing -

I Gli stati s1…sn sono gli stati del riconoscitore dei prefissi ascendenti LR(1)-lo stato iniziale contiene S→.S’

II Se [A→α1.aα2, b] ∈ s1 e GOTO[si ,a ]= sj, � action[s1 ,a] = “shift sj”

III Se [A→ α., a] ∈ si � action[si , a] = “reduce by A→ α ” A≠ S’

IV Se [S’→ S .,a] ∈ si � action[si ,a] = “accept ”


VI La tabella goto viene completata con la funzione GOTO del DFA: GOTO(si, , A) = sj, � goto(si, , A) = sj


63

Esempio NFA che riconosce i prefissi ascendenti LR(1) - 1

S’ → S

S →L=R

S → R

L →*R

L → idR →L

S’ → .S, $ S’ → S.,$S

S →. L=R,$

S → . R,$

ε transizioni


64

Esempio NFA che riconosce i prefissi ascendenti LR(1) - 2

S’ → S

S →L=R

S → R

L →*R

L → idR →L

S’ → .S, $ S’ → S.,$S

S →. L=R,$

S → . R,$

L →. id,=

L →.* R,=

S → L .=R,$

L

S → R.,$

R

R → . L,$


65

Esempio NFA che riconosce i prefissi ascendenti LR(1) - 3 ...

S’ → S

S →L=R

S → R

L →*R

L → idR →L

S’ → .S, $ S’ → S.,$S

S →. L=R,$

S → . R,$

L →. id,=

L →.* R,=

S → L .=R,$

L

S → R.,$

R

R → . L,$

R → L.,$

L

S → L =.R,$=


66

Esempio DFA che riconosce i prefissi ascendenti LR(1)

S’ → S

S →L=R

S → R

L →*R

L → idR →L

S →L .=R, $

R →L ., $

In corrispondenza dell’input ‘=‘ non è più è possibile effettuare la riduzione


67

Svantaggi del metodo LR(1)

• Il metodo LR(1) supera i limiti del metodo SLR(1), ma produce un numero di stati 10 volte superiore (migliaia per i linguaggi di programmazione)

• Il compromesso usato nei parser generator èil metodo LALR(1) (Look haed LR(1)), che hanno lo stesso numero di stati SLR(1), ma conservano parte dell’informazione dei look haed LR(1)


68

Metodo LALR(1)• idea LALR(1) - raggruppare gli item LR(1)

che hanno la stessa prima parte (item LR(0))

Es. 1 Dati gli stati LR(1)

A→α1. α2 , a

A→α1. α2, b

si ottiene lo stato LALR(1):

A→α1. α2 , a/b

Es. 2 Dati gli stati LR(1)

si ottiene l’unico stato LALR(1):

A→α. , a

B→β., b

A→α. , b

B→β., a

A→α. , a/b

B→β., a/bSi un conflitto tipo reduce/reduce: entrambe le produzioni A→α, B→β possono essere usate per una riduzione su a e b


69

Un gerarchia di classe di grammatiche

LR(0)

SLR(1)

LALR(1)

LR(1)

LR(k)

Grammatiche non ambigue

LL(1)

LL(k)

La classe LL(k) ècontenuta propriamente in LR(k)


70

Conflitti nell’analisi LR - shift reduce 1I conflitti nell’analisi LR sono tipicamente dovute a grammatiche non ambigue, non LR, ma comunque usate per loro espressività e perché portano a parsermeno complessi

Es.: “dangling-else”

S → if E then S else E

| if E then S

| other

Esiste uno stato del riconoscitoredei prefissi che non è LR(0)

S → if E then S . else E

S → if E then S .

• Il conflitto si ha quando in input c’è else verifica anche per l’analizzatore SLR(1) (in quanto else ∈FOLLOW(S) che per quello LALR(1) (set di lookhaed {else, $}).

• Il conflitto nella pratica e nei parser generator si risolve preferendo l’azione di shift a quella di riduzione.

• Nel caso del dangling else corrisponde ad associare l’else all’if che immediatamente lo precede


71

Conflitti nell’analisi LR - shift reduce 2Es. grammatica delle espressioni Si ottengono stati LR (1):

E → E +E | E*E | num ...

E → E *E ., +

E → E.+E , +

•Caso a. Il conflitto può essere risolto stabilendo che ‘+’ è associativo sinistro, e sceglie la riduzione.

•Caso b. Il conflitto può essere risolto dando precedenza ‘*’ rispetto a ‘+’ e scegliendo la riduzione.

• Nei parser generator è possibile specificare la precedenza e l’associatività Anche il dangling-else può essere risolto dando precedenza all’else

...

E → E +E ., +

E → E.+E , +

E → . E+E, $E → . E *E, $E → . num , $E → . E+E, +E → . E *E, *

0

a b

Sia in a che b c’è conflitto shift/reduce con ‘+’ in input, anche per i parser LALR(1) e SLR(1)


72

Conflitti nell’analisi LR - reduce reduceEs. sequenza di identificatoriS → ε | id S | id

•Soluzione: riscrivere la grammatica: S → ε | id S

S → id . S, $S → id . , $S → . , $S → . id S, $S → . id , $

S’ → .S, $S → . , $S → . id S, $S → . id , $

0

1 In 1 si ha un conflitto reduce/reduce con ‘$’ in input.

id

S → id . S, $S → . , $S → . id S, $

S’ → .S, $S → . , $S → . id S, $

id 1


73

Analisi LR -Trattamento degli errori -panic mode

Tecnica “panic mode” isolare la frase che contiene l’errore e riprendere l’analisi non appena possibile.

Quando scopre un errore l’automa percorre lo stack verso il basso fino e un non terminale sullo stack per cui goto[A,a]=s; pone s sullo stack e continua l’analisi.

Se si scorre tutta la pila, si passa al prossimo carattere di input, e così via

-

sm

am

sm

Xm

...

...a1 ai... amai+1

sn

am

Xn

...

...a1 ak... ama s

La scelta dei simboli può essere fatta in modo da isolare il tipo di frase

(es.: ‘;’ per le espressioni)


74

Analisi LR -Trattamento degli errori -phrase level

•Tecnica “phrase level” cercare di ripristinare l’analisi apportando correzioni “locali” alla frase errata.

•Quando scopre un errore su un carattere a l’automa cerca di inserire un carattere b per cui è definita la “goto”: la riparazione è accettata se l’analisi può riprendere da b, altrimenti si ripristina la pila iniziale.

•La tabella di parse “action[A,a]” può contenere esplicitamente il riferimento ad una funzione di gestione errore adatta al contesto, negli spazi che non sono ne spostamento ne di riduzione.


75

Esempio error recovery- SLR(1)

1) E’ → E 2) E → E+T3)E → T4)T → T*F 5)T → F 6)F → (E) 7)F → id

Id + * ( ) $ E F T1 R6 E1 S5 2 3 42 S7 Acc3 R3 S9 R34 R55 S6 S5 11 3 46 R77 S6 S5 8 48 R2 S9 R29 S6 S5 1010 R511 S7 S1212 R6 R6

ACTION GOTO

E1) messaggio “missingoperand” ; azione

inserimento id fittizio


76

Analisi LR -Trattamento degli errori -error production in YACC

•Produzioni extra della grammatica per gestire gli errori - A→ errorα

• YACC gestisce le produzioni di errore in maniera speciale

• Il simbolo error è una parola riservata, ed è considerata un terminale. Quando scopre un errore, YACC fa pop di tutti i simboli e gli stati dallo stack, fino a che non trova uno stato che contiene l’item

[A→ . error α ], fa shift su error passando a [A→ error . α ].

• Se α= ε viene eseguita la riduzione, e YACC scarta tutto l’input fino a che non riesce a riprendere l’analisi (erroe potrebbe essere una funzione di gestione errori)

• Se α non è vuota, vengono messi sullo stack tutti i terminali fino ad ottenere α, effettuare la riduzione e proseguire l’analisi.

•Es.: <istruzione> → error ; quando c’è un errore in una istruzione passa al prossimo ‘;’. L’errore può essere gestito tramite una funzione


77

Yacc - struttura progetto

dichiarazioni%%regole%%procedure ausiliarie

Grammatica LALR(1)

YACC Analizzatore sintattico


78

YACC- Parte dichiarazioni• Definizione dei token del linguaggio%token DIGIT

• Informazioni di precedenza e di associatività%left ‘+’ ‘-’%left ‘*’ ‘/’%rigth UMINUS%nonassoc ‘<‘

• Simbolo di start (solo uno)%start <S>• Il codice ‘c’ va racchiuso tra “%{ … }%”

Ordine di precedenza dal basso verso l’altro. ‘+’,’-’ sono associativi a sinistra, ed hanno lo stesso livello di precedenza. L’ordine di precedenza èUMINUS �� * / �� + -. Gli operatori non associativi non possono essere combinati a due a due.


79

YACC- Parte regole• Struttura:

<non_terminale> : produzione 1 {azione semantica 1} | produzione 2 {azione semantica 2} |

…produzione n {azione semantica n};

• azione semantica = blocco istruzioni “c”; $$ valore associato al non terminale a sinistra; $i si riferisce al valore termine i-mo della produzione (terminale o non terminale). Nella azione semantica generalmente si calcola il valore di $$ in funzione dei $i.

• I terminali vanno racchiusi tra apici, se non specificati come TOKEN. L’analizzatore lessicale si fa carico di riconoscere i TOKEN.


80

YACC- Parte procedure ausiliarie• La parte procedure ausiliarie contiene generalmente contiene

l’analizzatore sintattico, la funzione main, altre routine di support(eventualmente una personalizzazione della funzione yerror()). Il parser è racchiuso nella funzione yyparse(), che restituisce 0 in assenza di errori, 1 altrimenti.

• L’analizzatore sintattico yylex restituisce il token (numero intero), mentre il valore del token è conservato in yylval (es.: per ‘>’TOKEN=GT, *yylval=‘>’)

• L’analizzatore lessicale può essere creato con LEX:– incluso nel file nella parte procedure:#include “lex.yy.c”

– effettuando il link a partelex lexical.l

yacc syntax.y

cc y.tab.c -ly -ll


81

%{#include <ctype.h>%}%token DIGIT

%%line : expr '\n' { printf("%g\n", $1); }

;

expr : expr '+' term { $$ = $1 + $3; }| term;

term : term '*' factor { $$ = $1 * $3; }| factor;

factor : '(' expr ') { $$ = $2; }| DIGIT;

%%int yylex(void){

int c;while ((c = getchar()) == ' ');if (isdigit(c)) {

yyval=c-’0’;return DIGIT;

}return c;

}

ESEMPIOYACC 1

E→E+T

T →T*F

F →(E) | DIGIT


82

%{#include <ctype.h>#include <stdio.h>#define YYSTPYE double%}%token NUMBER%left '+' '-'%left '*' '/'%right UMINUS%%lines : lines expr '\n' {printf("%g\n", $2);}

| lines '\n'| /* epsilon */;

expr : expr '+' expr { $$ = $1 + $3; }| expr '-' expr { $$ = $1 - $3; }| expr '*' expr { $$ = $1 * $3; }| expr '/' expr { $$ = $1 / $3; }| '(' expr ')' { $$ = $2; }| '-' expr %prec UMINUS { $$ = -$2;}| NUMBER;

%%int yylex(void){

int c;while ((c = getchar()) == ' ');if (c == '.' || isdigit(c)) {

ungetc(c, stdin);scanf("%lf", &yylval);return NUMBER;

}return c;

}

ESEMPIO YACC 2E→E+E | E*E | E/E | -E|(E) | NUMBERgrammatica ambigua e precedenza operatori

Piu espressioni su una linea

%prec da alla produzione la stessa precedenza di UMINUS,

più alta di tutti gli altri operatori: non ci sono conflitti

shift reduce con * /


83

lines : lines expr '\n' { printf("%g\n", $2); }| lines '\n'| /* e */| error '\n' { yyerror("reenter last line:");

yyerrok(); };

ESEMPIO YACC - gestione errori

factor : '(' expr ')' { $$ = $2; }| '(' expr error { $$ = $2; yyerror("missing ')'");

yyerrok(); }| '-' factor { $$ = -$2; }| NUMBER;

La produzione “error” induce YACC a scandire l’input fino a ‘\n’, quindi emette il messaggio di errore e ripristina lo stato normale con la routineyyerrok().

In questo caso viene riconosciuto un caso di parentesi non bilanciata.

Le produzioni di errore vanno a fare parte della grammatica, e possono produrre a loro volta conflitti

•Scopi •Tecniche •Strumenti – ANTLR-Yacc sintattica.pdf · context free - complessità...

Documents

Transcript of •Scopi •Tecniche •Strumenti – ANTLR-Yacc sintattica.pdf · context free - complessità...