Implementazione di Linguaggi 2 Massimo Ancona Testo: A.V. Aho, R. Sethi, J.D.Ullman Compilers...

Implementazione di Implementazione di Linguaggi 2Linguaggi 2

Massimo AnconaMassimo Ancona

Testo: Testo: A.V. Aho, R. Sethi, J.D.Ullman A.V. Aho, R. Sethi, J.D.Ullman Compilers Principles,Techniques and Compilers Principles,Techniques and

Tools, Addison WesleyTools, Addison Wesley

22

Diagramma del processo di Diagramma del processo di compilazionecompilazione

33

Strumenti associati al Strumenti associati al compilatore: il Linkercompilatore: il Linker

44

Contesto/ambiente di un Contesto/ambiente di un cmpcmp

Programming EnvironmentProgramming EnvironmentUn ambiente grafico interattivo per lo sviluppo, il Un ambiente grafico interattivo per lo sviluppo, il

testing e la manutenzione dei programmi:testing e la manutenzione dei programmi: integra e integra e gestisce gli strumenti e i meccanismi seguentigestisce gli strumenti e i meccanismi seguenti

Strumenti e meccanismi correlati ai compilatoriStrumenti e meccanismi correlati ai compilatori Sistemi per le compilazioni separate Sistemi per le compilazioni separate Sistemi per il controllo delle versioniSistemi per il controllo delle versioni Meccanismi per le ricompilazioni efficientiMeccanismi per le ricompilazioni efficienti Macroprocessori e PreprocessoriMacroprocessori e Preprocessori Linker loaderLinker loader Interpreti debugger profilerInterpreti debugger profiler

55

Processo Di CompilazioneProcesso Di Compilazione Nella sua forma piu' astratta il processo di compilazione e' descritto nella figura seguente: il compiler e' una funzione che mappa un programma in linguaggio sorgente in un programma equivalente in linguaggio oggetto.

66

Fasi e Passi (Passate)Fasi e Passi (Passate) Sono due concetti ortogonali: Le fasi denotano trasformazioni sul programma eseguite da tutti i compilatori.

I passi si riferiscono al numero di processi successivi, in cui e' suddiviso un compilatore (il loro numero dipende in parte dal linguaggio).

Il compilatore in una passata, legge il codice sorgente o una sua forma intermedia equivalente, raffinando il processo di treduzione e producendo una nuova rappresentazione intermedia, fino ad arrivare al codice target, nell’ultima passata.

77

Fasi Di CompilazioneFasi Di Compilazione

Una fase denota il tipo di operazione effettuata. Fasi e passate sono concetti ortogonali anche se una struttura canonica del compilatore tende ad incapsulare una (o piu') fasi, in una specifica passata.La divisione piu' grossolana prevede due fasi: analisi e sintesi. Con la prima il programma sorgente viene suddiviso nelle parti costituenti ottenendone una rappresentazione intermedia. Nella seconda si costruisce il programma target nel linguaggio oggetto.

88

Analisi e SintesiAnalisi e Sintesi

Strumenti che eseguono l’analisi dell’inputStrumenti che eseguono l’analisi dell’input

Editori di testo, Formattatori e Sistemi Editori di testo, Formattatori e Sistemi Ipertestuali (HTML, XML, PDF, TEX) Ipertestuali (HTML, XML, PDF, TEX)

Silicon Compilers (sintetizzatori di circuiti e Silicon Compilers (sintetizzatori di circuiti e componenti Hardware)componenti Hardware)

Query InterpretersQuery Interpreters Motori di Ricerca e strumenti correlatiMotori di Ricerca e strumenti correlati

99

Analisi e Sintesi Analisi e Sintesi

Analisi e SintesiAnalisi e Sintesi AnalisiAnalisi

divide il pgm sorgente nelle parti divide il pgm sorgente nelle parti costituenti creando una costituenti creando una rappresentazione intermedia.rappresentazione intermedia.

Sintesi Sintesi

costruisce il programma oggettocostruisce il programma oggetto dalla dalla rappresentazione intermedia.rappresentazione intermedia.

1010

Dettaglio Dettaglio DelleDelle Fasi Fasi ELenco completo delle possibili fasi di compilazione:

1111

Rappresentazioni Rappresentazioni IntermedieIntermedie

sorgente primo := base + 53 * delta;out lessicale id[1] op= id[2] op+ ci=53 op* id[3]out sintattico op= id[1] op+ id[2] op* 53 id[3]

1212

Rappresentazioni Rappresentazioni Intermedie (e Finali) Intermedie (e Finali)

out semantica op=

id[1] op+

id[2] op* float id[3] 53

1313

Rappresentazioni Rappresentazioni Intermedie Intermedie

codice intermedio

tmp1 = float(53) tmp2 = id[3] op* tmp1 tmp3 = id[2] op+ tmp2 id[1] = tmp3

Ottimizzazione di codice (intermedio)

tmp1 = id[3] op* 53.00 id[1] = id[2] op+ tmp1

1414

Rappresentazione Finale Rappresentazione Finale

codice macchina: movf id3, rf2 mulf #53.00, rf2 movf id[2], rf1 addf rf2, rf1 movf rf1, id[1]

Supponiamo di utilizzare

solamente due registri rf1 e rf2.

1515

Tipi di CompilatoriTipi di Compilatori

Vi sono diversi tipi di compilatoriVi sono diversi tipi di compilatori Ad un sol passoAd un sol passo Multi-passoMulti-passo Load_and_goLoad_and_go DebuggingDebugging OptimizingOptimizing Compiler-InterpreterCompiler-Interpreter

1616

Introduzione alla Introduzione alla CompilazioneCompilazione

Un compilatore in due passate

1717

Le fasi di analisi del Le fasi di analisi del sorgentesorgente

Analisi Lessicale. Analisi Lessicale. I caratteri del codice I caratteri del codice sorgente vengono letti left-to-right e sorgente vengono letti left-to-right e raggruppati in Token.raggruppati in Token.

Analisi Sintattica. Analisi Sintattica. I caratteri o token sono I caratteri o token sono raggruppati in frasi grammaticali.raggruppati in frasi grammaticali.

Analisi Semantica. Analisi Semantica. Vengono effettuati Vengono effettuati controlli per trovare errori semantici e controlli per trovare errori semantici e raccogliere informazioni per la raccogliere informazioni per la generazione di codice.generazione di codice.

1818


Analisi Lessicale.Analisi Lessicale.

Source

ProgramLexical

analyzerParser

Token

Get next Token

SymbolTable

1919

Le fasi di analisi del sorgenteLe fasi di analisi del sorgenteAnalisi Lessicale.Analisi Lessicale.

Ad esempio l’istruzione:Ad esempio l’istruzione:alpha:=beta+gamma*100;alpha:=beta+gamma*100;

viene codificata nei seguenti TOKEN:viene codificata nei seguenti TOKEN:

<ID:’alpha’><OP::=><ID:’beta’><OP:<ID:’alpha’><OP::=><ID:’beta’><OP:><I><ID:’gamma’><OP:D:’gamma’><OP:><VAL:’100’>><VAL:’100’>

Gli spazi ridondanti, i fine linea ecc. che Gli spazi ridondanti, i fine linea ecc. che separano i token vengono eliminati.separano i token vengono eliminati.

Eseguita dallo

Scanner

2020


Analisi Sintattica.Analisi Sintattica. Ogni linguaggio di programmazione Ogni linguaggio di programmazione

ha delle regole che descrivono la ha delle regole che descrivono la struttura sintattica di un struttura sintattica di un programma programma ben formatoben formato..

La sintassi di un linguaggio di La sintassi di un linguaggio di programmazione può essere descritta programmazione può essere descritta da una grammatica libera da contesto da una grammatica libera da contesto

2121


Analisi Sintattica.Analisi Sintattica.

Source

ProgramLexical

analyzerParser

Token

Get next Token

SymbolTable

ParseTree

2222

Le fasi di analisi del sorgenteLe fasi di analisi del sorgenteAnalisi Sintattica.Analisi Sintattica.

Agisce dopo l’analisi lessicale. Raggruppa i token in frasi Agisce dopo l’analisi lessicale. Raggruppa i token in frasi grammaticali che si rappresentano con un grammaticali che si rappresentano con un parse treeparse tree..

Parse tree di: Parse tree di: alpha := beta + gamma * 100alpha := beta + gamma * 100

(<:=>)(<:=>)

<EXP:ID> <EXP: <EXP:ID> <EXP: >>

<ID:’alpha’> <EXP:ID> <EXP: <ID:’alpha’> <EXP:ID> <EXP: >>

<ID:’beta’> <EXP:ID> <ID:’beta’> <EXP:ID> <EXP:VAL><EXP:VAL>

<ID:’gamma’> <ID:’gamma’> <VAL:’100’><VAL:’100’>

Eseguita dal

Parser

2323

Le fasi di analisi del sorgenteLe fasi di analisi del sorgenteAnalisi Semantica.Analisi Semantica.

Controlla il codice sorgente alla ricerca di Controlla il codice sorgente alla ricerca di errori semantici e raccoglie informazioni errori semantici e raccoglie informazioni sui tipi per la fase di generazione di sui tipi per la fase di generazione di codicecodice

Type checkingType checking è la componente più è la componente più importate di questa fase:importate di questa fase: Controlla che gli operatori abbiano operandi Controlla che gli operatori abbiano operandi

permessi dalla specifica del linguaggio.permessi dalla specifica del linguaggio.

2424

Relazione tra le Fasi Relazione tra le Fasi

La suddivisione tra analisi lessicale e La suddivisione tra analisi lessicale e sintattica è piuttosto arbitraria (come per sintattica è piuttosto arbitraria (come per le altre fasi della compilazione); le altre fasi della compilazione);

Uno dei metodi usati per discriminarle si Uno dei metodi usati per discriminarle si basa sulla basa sulla ricorsionericorsione:: i costrutti descrivibili senza ricorsione si i costrutti descrivibili senza ricorsione si

assegnano all’analisi lessicale;assegnano all’analisi lessicale; quelli sostanzialmente ricorsivi a quella quelli sostanzialmente ricorsivi a quella

sintatticasintattica..

2525

Sintassi Formale dei Linguaggi Sintassi Formale dei Linguaggi di Programmazionedi Programmazione

La si specifica tramite: La si specifica tramite: diagrammi sintattici; diagrammi sintattici; equazioni BNF EBNF;equazioni BNF EBNF; grammatiche non contestuali (context grammatiche non contestuali (context

free)free)

Tutte forme sostanzialmente Tutte forme sostanzialmente equivalenti. equivalenti.

2626

Grammatiche Libere da Grammatiche Libere da Contesto (CFG)Contesto (CFG)

Le Context Free Grammar sono una notazione Le Context Free Grammar sono una notazione per specificare la sintassi di un linguaggio.per specificare la sintassi di un linguaggio.

Una CFG ha 4 componenti:Una CFG ha 4 componenti: Un insieme di token, detti Un insieme di token, detti simboli terminalisimboli terminali Un insieme di Un insieme di non-terminalinon-terminali Un insieme diUn insieme di produzioniproduzioni, dove ogni produzione , dove ogni produzione

consiste di un non-terminale (consiste di un non-terminale (left sideleft side), una freccia ), una freccia e una sequenza di token e/o non-terminali (e una sequenza di token e/o non-terminali (right right sideside))

L’indicazione di un non-terminale come L’indicazione di un non-terminale come simbolo simbolo inizialeiniziale

2727

Grammatiche Libere da Grammatiche Libere da Contesto EsempioContesto Esempio

Vediamo un esempio di produzioni che Vediamo un esempio di produzioni che definiscono semplici espressioni aritmetiche:definiscono semplici espressioni aritmetiche:

expr expr expr op expr expr op exprexpr expr ( expr ) ( expr )expr expr id id op op + + op op - - op op * * op op / / op op

Simboli terminali: id + - * / ( (( (

Simboli non-terminali: expr op

Simbolo iniziale: expr

2828

Grammatiche Libere da Grammatiche Libere da Contesto EsempioContesto Esempio

Scrivere la grammatica context free Scrivere la grammatica context free per esprimere zero o più volte il per esprimere zero o più volte il simbolo (terminale) thing.simbolo (terminale) thing.

List List List List thing thingList List List List ListList

List List List List thing thing ListListList List List List List List thingthing

2929

Grammatiche Libere da Grammatiche Libere da Contesto (CFG): Definizione Contesto (CFG): Definizione

FormaleFormale Alfabeto Alfabeto TT ( () ) ::

è un insieme finito non vuoto, eè un insieme finito non vuoto, e

gli elementi di gli elementi di TT ( () ) vengonovengono chiamati chiamati simbolisimboli o o carattericaratteri..

Useremo le lettere Useremo le lettere V, T, N, V, T, N, per indicare per indicare alfabetialfabeti

3030


FormaleFormale Parola Parola di lunghezza di lunghezza kk00, su un alfabeto, su un alfabeto

TT:: è una sequenza finita è una sequenza finita w=xw=x11xx22…x…xk k di di

elementi di elementi di T,T,

kk, denotata anche , denotata anche k=|w|k=|w| è detta lunghezza è detta lunghezza di di ww, e, e

la parola di lunghezza la parola di lunghezza zerozero, detta , detta parola parola vuotavuota, e’ indicata , e’ indicata ..

3131


FormaleFormale L’insieme L’insieme delledelle parole su T (parole su T (linguaggiolinguaggio),),

indicato conindicato con T*T* monoide:monoide: con legge di composizione con legge di composizione concatenazione di paroleconcatenazione di parole DateDate ww11,w,w22TT, ,

ww11= x= x11xx22…x…xkk,, ww22= y= y11yy22…y…yll

w= ww= w11.w.w22= x= x11xx22…x…xkkyy11yy22…y…yll,, di lunghezzadi lunghezza k+lk+l, ,

è detta concatenazione diè detta concatenazione di ww11 ee ww22. .

Il monoide Il monoide (T*,.)(T*,.) è detto è detto monoide liberomonoide libero su su TT..

3232

Parentesi Algebrica: Parentesi Algebrica: MonoideMonoide

Un Un monoidemonoide è un insieme M munito di una singola è un insieme M munito di una singola operazione binaria, chiamata prodotto, che ad ogni operazione binaria, chiamata prodotto, che ad ogni coppia di elementi a, b di M associa un elemento coppia di elementi a, b di M associa un elemento ab, rispettando i seguenti assiomi: ab, rispettando i seguenti assiomi:

per ogni a, b appartenenti a M, il loro prodotto ab per ogni a, b appartenenti a M, il loro prodotto ab appartiene ancora a M, vale a dire, appartiene ancora a M, vale a dire, M è M è chiusochiuso rispetto al rispetto al prodottoprodotto..

Il prodotto è Il prodotto è associativoassociativo: dati a, b, c appartenenti a M, : dati a, b, c appartenenti a M, vale (vale (abab))cc = = aa((bcbc). ).

Esiste in M un (unico) Esiste in M un (unico) elemento elemento neutroneutro e tale che e tale che aeae = = eaea = = aa. .

3333


FormaleFormaleUna Una CFGCFG formalmente è una quadrupla formalmente è una quadrupla

G=(N,T,P,S)G=(N,T,P,S) con con NNT=T= e e V=NV=NTT, dove:, dove: TT è un alfabeto di simboli terminali di è un alfabeto di simboli terminali di G.G. NN è un alfabeto di simboli non-terminali è un alfabeto di simboli non-terminali

di di G.G. PP è un insieme finito di produzioni di è un insieme finito di produzioni di G.G. SSNN è detto simbolo iniziale di è detto simbolo iniziale di GG..

3434


FormaleFormaleNotazione utilizzata per le produzioniNotazione utilizzata per le produzioni NNV*:V*:

a,b,c,…,+,-,…,0,1,…,(,[,{,…a,b,c,…,+,-,…,0,1,…,(,[,{,… indicano elementi di indicano elementi di T T (= (= terminali)terminali)

A,B,C,…A,B,C,… indicano elementi di indicano elementi di N N (= non-terminali)(= non-terminali)

U,V,X,Y,ZU,V,X,Y,Z indicano elementi di indicano elementi di V=TV=TN N

u,v,x,y,u,v,x,y, indicano elementi di indicano elementi di T*T*(= stringhe di terminali)(= stringhe di terminali)

,,,,,…,,…, indicano elementi di indicano elementi di V* V* (= stringhe di simboli (= stringhe di simboli grammaticali)grammaticali)

=(A,=(A,))NNV*V* è è indicata daindicata da AA

3535

Linguaggi Context Free Linguaggi Context Free

Linguaggio generato da G: Linguaggio generato da G:

L(G)=L(G)=wwT*| S T*| S * w* w

Un linguaggioUn linguaggio L L T*T* è libero da contesto è libero da contesto sese esiste esiste G=(N,T,P,S) CFGG=(N,T,P,S) CFG tale chetale che L=L(G)L=L(G)

3636

Forme SentenzialiForme Sentenziali

Data Data G=(N,T,P,S)G=(N,T,P,S) una forma sentenziale di una forma sentenziale di GG è definita ricorsivamente, come segue:è definita ricorsivamente, come segue: SS è una forma sentenziale di è una forma sentenziale di GG,, se se AA è una forma sentenziale di è una forma sentenziale di GG e e AA è è

una produzione di una produzione di GG allora allora è una forma è una forma sentenziale di sentenziale di G.G.

La relazione traLa relazione tra AA ee alal punto punto precedente viene indicata: precedente viene indicata:

AA ( (DerivazioneDerivazione))

3737

Derivazioni Dirette e NonDerivazioni Dirette e Non

AA esprime che esprime che deriva deriva direttamentedirettamente da da AA o che o che AA genera genera direttamente direttamente . .

Le notazioni Le notazioni * * ++ indicano rispettivamente la indicano rispettivamente la chiusura transitiva-riflessiva e transitiva di chiusura transitiva-riflessiva e transitiva di * * denota che denota che == oppure oppure

ii i=1..n i=1..n ==11 22 … … nn = = e e n>0.n>0. + denota che denota che =1 2 … n =

e e n>0n>0..

3838

Derivazioni - EsercizioDerivazioni - Esercizio

La stringa La stringa – ( id + id ) – ( id + id ) è una sentenza è una sentenza della grammatica G? della grammatica G?

E E - E - ( E ) - ( E + E ) - ( id + E ) - ( id + id )

G:E E + E E E * EE ( E )E - EE id

E * - ( id + id )

3939

Derivazioni canonicheDerivazioni canoniche

Una derivazione Una derivazione * e’ detta e’ detta canonica destracanonica destra e indicata e indicata rm

* , , se ad ogni passo di derivazione si se ad ogni passo di derivazione si espande il simbolo non-terminale più espande il simbolo non-terminale più a destra.a destra. rm* se se i si ha i si ha ii==iiAAiixxii, , i+1i+1==iiiixxii, , Ai i, , =1 2 … n = i=1,…,n

4040

Derivazioni canonicheDerivazioni canoniche

Una derivazione Una derivazione * e’ detta e’ detta canonica sinistracanonica sinistra e indicata e indicata lm

* , , se ad ogni passo di derivazione si se ad ogni passo di derivazione si espande il simbolo non-terminale più espande il simbolo non-terminale più a sinistra.a sinistra. lm* se se i i si ha si ha ii=x=xiiAAii ii, , i+1=xii i, Ai i, =1 2 … n = i=1,…,n

4141

Derivazioni Canoniche Derivazioni Canoniche EsempioEsempio

G=(G=({{EE,,TT,,PP}}, , {{((,,)),,aa,,bb,,cc,,**,,++,,--}}, P, E), P, E)P={P={EEE E ++T T ||E E --T T ||TT, ,

TT T T **P P ||PP, , PP ( (E E ) | a | b | c}) | a | b | c}Data Data (a-b) – c(a-b) – c la derivazione: la derivazione:E E EE --T T TT --T T PP --T T (EE )-)-T T (E E -- TT )-)-T T (T T -- TT )-)-T T (P P -- TT )-)-T T (a -a - T T )-)-T T (a -a - P P )-)-T T (a -a - b b )-)-TT (a -a - bb )-)-P P (a -a - bb ) - c) - c

È canonica sinistra.È canonica sinistra.

Non-terminaliterminali

4242

Esempio Esempio Sia G=({E,T,P}, {(,),a,b,c,*,+,-}, P, E) doveSia G=({E,T,P}, {(,),a,b,c,*,+,-}, P, E) doveP={EP={EE+T | E-T | T, T E+T | E-T | T, T T*P | P, P T*P | P, P (E) | a | b |c} (E) | a | b |c}La derivazione:La derivazione:

EE E-T E-P E-c T-c P-c (E)-c (E-T)-c (E-P)-c (E-b)-c (T-b)-T (P-b)-c (a-b)-c

è è canonica destracanonica destra, confrontandola con la , confrontandola con la canonicacanonica sinistrasinistra: : EE E-T T-T P-T (E)-T (E-T)-T (T-T)-T (P-T)-T (a-T)-T (a-P)-T (a-b)-T (a-b)-P (a-b)-c

Si vede che differiscono solo per l’ordine di applicazione Si vede che differiscono solo per l’ordine di applicazione delle produzioni. delle produzioni. Entrambe applicano le stesse Entrambe applicano le stesse produzioni alle stesse istanze di non terminaliproduzioni alle stesse istanze di non terminali

4343

Parsing Tree Parsing Tree

Tutte le derivazioni che differiscono solo Tutte le derivazioni che differiscono solo per l’ordine di applicazione delle per l’ordine di applicazione delle produzioni sono sostanzialmente produzioni sono sostanzialmente equivalenti e possono essere equivalenti e possono essere rappresentate da un’unica derivazione rappresentate da un’unica derivazione canonica destra, un’ unica derivazione canonica destra, un’ unica derivazione canonica sinistra o da un unico albero canonica sinistra o da un unico albero etichettato detto etichettato detto Parsing TreeParsing Tree..

4444

Parsing Tree - Definizione Parsing Tree - Definizione

La radice è etichettata da S Ogni foglia dell’albero è etichettato da o

da un simbolo di T (terminale) Ogni nodo interno è etichettato da un

simbolo di N (non terminale) Se A etichetta un nodo interno e X1,X2,…,

Xn sono le etichette dei figli, allora AX1X2…Xn P

4545

Parsing Tree - EsempioParsing Tree - Esempio

Derivazione: Derivazione: - (id + id)- (id + id)

EE

-- E E

(( E E ))

E E ++ E E

id idid id

G:E E + E E E * EE ( E )E - EE id

4646

Esempio di Parsing Tree Esempio di Parsing Tree

Derivazione di:Derivazione di: (a – b ) – c(a – b ) – c

Grammatica:

EEE E ++T T ||E E --T T ||TT

TT T T **P P ||PP, ,

PP ((E E )) | a | b | | a | b | cc}}

4747

Classificazione di Chomsky È una classificazione dei linguaggi basata

sulla complessità delle produzioni delle grammatiche che li generano. I linguaggi di tipo 0 sono generati da

grammatiche a struttura di frase. I linguaggi di tipo 1 sono generati da

grammatiche dipendenti dal contesto. I linguaggi di tipo 2 sono generati da

grammatiche libere dal contesto. I linguaggi di tipo 3 sono generati da

grammatiche lineari (o regolari).

4848

Classificazione di Chomsky Grammatiche a struttura di frase.

Le produzioni sono del tipo A Grammatiche dipendenti dal contesto.

Le produzioni sono del tipo A dove , V*, AN e V* .

Grammatiche libere dal contesto. Le produzioni sono del tipo A, dove V* .

Grammatiche lineari (o regolari). Le produzioni sono del tipo AuB oppure Au, dove u * e A, B N.

4949

Classificazione di Chomsky

Ogni grammatica di tipo n è anche una grammatica di tipo n − 1.

Un linguaggio è di tipo n se è generato da una grammatica di tipo n, ma non di tipo n + 1.

Esempi:- Linguaggio di tipo 3: L = {ambn : m, n 0}.- Linguaggio di tipo 2: L = {anbn : n 0}.- Linguaggio di tipo 1: L = {anbncn : n 0}.- Linguaggio di tipo 0: L = {an : n è numero primo}.

5050

Grammatiche e Linguaggi Grammatiche e Linguaggi AmbiguiAmbigui

Una grammatica Una grammatica GG è è ambiguaambigua se: se: wwL(G) con due parsing tree diversi L(G) con due parsing tree diversi

Un linguaggio è inerentemente Un linguaggio è inerentemente ambiguo se per ogni G tale che ambiguo se per ogni G tale che L=L(G) si ha che G e’ ambigua. L=L(G) si ha che G e’ ambigua.

5151

Tecniche per Tecniche per DisambiguareDisambiguare

Inserire regole di precedenza per gli Inserire regole di precedenza per gli operatori.operatori.

Utilizzare associatività a sinistra o a Utilizzare associatività a sinistra o a destra.destra.

Manipolare la grammatica.Manipolare la grammatica.

5252

Grammatica Ambigua Grammatica Ambigua EsempioEsempio

G=({S}, {G=({S}, {ifif,, then then,, else else,, s, b s, b},}, P={S P={S if if bb then S then S || if if bb then then S S else else SS || s s}, S)}, S)

SSrmrm ifif bb then then SS rmrm ifif bb then if b then then if b then SS else else SS rmrm ifif bb thenthen ifif bb thenthen SS else s else s rmrm ifif bb thenthen ifif bb then s elsethen s else s s

S S rmrm if b then if b then SS else else S S rmrm if b then if b then SS else else s s rmrm if b thenif b then if b thenif b then SS else s else s rmrm if b then if b then if b then s else sif b then s else sif b then if b then s else sif b then if b then s else s

5353

Grammatica Ambigua Grammatica Ambigua EsempioEsempio

Grammaticha ambigua:Grammaticha ambigua:G=({S}, {G=({S}, {ifif,, then then,, else else,, s, b s, b},}, P={S P={S if if bb then S then S || if if bb then then S S else else SS || s s}, }, S)S)

Grammatica disambiguata:Grammatica disambiguata:G=({S, SG=({S, S11, S, S22}, {}, {ifif,, then then,, else else,, s, b s, b},}, P={S P={S S S11, S, S11 if if bb then then SS11 || if if bb then then S S22 else else SS11 || s s,, SS22 if b then S if b then S22 else S else S11 | s}, | s}, S)S)

5454

Grammatica non ambigua con Grammatica non ambigua con proprietà opportune proprietà opportune

Nota: la gramamtica è context free, e mostriamo Nota: la gramamtica è context free, e mostriamo solo le produzioni.solo le produzioni.

Grammatica di espressioniGrammatica di espressioni non ambiguanon ambigua con con priorità di operatori e associativitàpriorità di operatori e associatività cablatecablate

EEE+T | E-T | TE+T | E-T | TTTT*F | T/F | F T*F | T/F | F FFP^F | PP^F | PP P (E) | I | N(E) | I | NI I a|b|c|d a|b|c|dN N 0 | 1 | 2 0 | 1 | 2

G G per espressioni, per espressioni, semplice masemplice ma ambiguaambiguaEEEOE|(E)|a|b|c|dEOE|(E)|a|b|c|dOO+|-|*|^ +|-|*|^

5555

Altri esempi di grammaticheAltri esempi di grammatiche

GG00 di espressioni non ambigua con priorità di di espressioni non ambigua con priorità di operatori e associativitàoperatori e associatività cablatecablate

EEE+T | E-T | T E+T | E-T | T |-T|+T|-T|+TTTT*F | T/F | F T*F | T/F | F F F (E) | I | N(E) | I | NI I a|b|c|d a|b|c|dN N 0 | 1 | 2 0 | 1 | 2

GG11 per espressioni, semplice, non ambigua ma per espressioni, semplice, non ambigua ma flatflatEEEOT|TEOT|T|-T|+T|-T|+TT T (E)|a|b|c|d|0|1|2(E)|a|b|c|d|0|1|2OO+|-|*|/ +|-|*|/

5656

Derivazione canonica di GDerivazione canonica di G00

DataData a-b*c a-b*c ee G G00 abbiamo:abbiamo:

EErmrmEE--TT rmrmEE--TT**FF rmrmEE--TT**II rmrmEE--TT*c *c rmrmEE--FF*c*c rmrmEE--II*c*c rmrmEE-b*c -b*c rmrmTT-b*c-b*c rmrmFF-b*c -b*c rmrmII-b*c-b*c rmrma-b*ca-b*c

EEEE++T | ET | E--T | TT | T |-T|+T|-T|+TTTTT**F | TF | T//F | F F | F F F ((EE) ) | I | N| I | NI I a a || b b || c c | | ddN N 0 0 || 1 1 || 2 2

5757

Parse tree (GParse tree (G00) )

Derivazione Canonica:Derivazione Canonica:

EErmrmEE--TT rmrmEE--TT**FF rmrmEE--TT**II rmrmEE--TT*c *c rmrmEE--FF*c*c rmrmEE--II*c*c rmrmEE-b*c -b*c rmrmTT-b*c-b*c rmrmFF-b*c -b*c rmrmII-b*c-b*c rmrma-b*ca-b*c

EE

EE -- TT

TT T * F T * F

FF F I F I

II I c I c

aa b b

5858

Derivazione canonica di Derivazione canonica di GG11

DataData a-b*c a-b*c ee G G11 abbiamo:abbiamo:

EErmrmEOEOTT rmrmEEOOc c rmrmEE*c *c rmrmEOEOTT*c*c rmrmEEOObb**c c rmrm

rmrmEE-b*c -b*c rmrm

rmrmTT-b*c -b*c rmrm a-b*c a-b*c

EEEOT|T|-T|+TEOT|T|-T|+TT T (E)|(E)|aa||bb||cc||dd||00||11||22OO++||--||**||/ /

5959

Parse tree (GParse tree (G11))

Derivazione Derivazione Canonica:Canonica:

EErmrmEOEOTT rmrmEEOOc c rmrmEE*c *c rmrmEOEOTT*c*c rmrmEEOObb**c c rmrm

rmrmEE-b*c -b*c rmrm

rmrmTT-b*c -b*c rmrm a-b*c a-b*c

EE

E E O O T T

E O TE O T * * c c

T - bT - b

a a

6060

EsercizioEsercizio

Studiare GStudiare G22::

EEFOT | T FOT | T FFFOT | T | FOT | T | TT((EE)| a )| a || b b || c c || d d || 0 0 || 1 | 2 1 | 2 OO+ + || - - || * * || ^ ^

6161

EsempioEsempioDocumenti HTML XML:Documenti HTML XML:

DDPs B PdPs B PdPsPs<html><html>PdPd<\html><\html>B B <body>L <\body> <body>L <\body>LLE L | E E L | E | | EE<div>R<\div> <div>R<\div> RRrestrest

6262



6363



6464


DDPs L PdPs L Pd

PsPs<html><html>

PdPd<\html><\html>

LLE L | E E L | E | | EE<div>R<\div> <div>R<\div>

RRrestrest

6565

Operazioni sui LinguaggiOperazioni sui Linguaggi

Dati due linguaggi L, M Dati due linguaggi L, M * definiamo * definiamo prodotto di L e Mprodotto di L e M, indicato LM o L, indicato LM o L..M, M, l’insieme:l’insieme:

LLM ={uv | u M ={uv | u L & v L & v M} M}

6666

Operazioni sui LinguaggiOperazioni sui Linguaggi

Definiamo Definiamo chiusura di Kleene di Lchiusura di Kleene di L, , indicata con L*, l’operazione:indicata con L*, l’operazione: LL00={={}} LL11=L=L LLii=L=LLLi-1i-1 i>0 i>0 L*=L*=ii00 L Lii

LL++==i>0i>0 L Lii

6767

Operazioni sui Linguaggi - Operazioni sui Linguaggi - EsempiEsempi

Proprieta’: supponiamo T terminale e Proprieta’: supponiamo T terminale e vediamo le produzioni di Evediamo le produzioni di E

GG00=({E},{t,+,-},P=({E},{t,+,-},P00,E),E)PP00={E={EE+t | E-t | tE+t | E-t | t|-t|+t}|-t|+t}L(GL(G00)={-t,+t,t}({+,-}t)*)={-t,+t,t}({+,-}t)*eeGG11=({E,O},{t,+,-},P1,E)=({E,O},{t,+,-},P1,E)PP11={E={EEOt|tEOt|t|-t|+t,|-t|+t,OO+|-}+|-}OO+|- +|- L(GL(G11)=L(G)=L(G00))

6868

Linguaggi - EsempiLinguaggi - Esempi

Esempio di linguaggio inerentemente Esempio di linguaggio inerentemente ambiguoambiguo L={aL={aiibbjjcckk| i=j OR j=k; i,j,k| i=j OR j=k; i,j,k0}0} SSSS11SS22 | S | S33SS44

SS11aSaS11b |b | S S22 S S22 c| c| SS44bSbS44c |c | S S33 S S33 a| a|

Esempio di linguaggio non context Esempio di linguaggio non context free.free. L={aL={annbbnnccnn| n>(| n>() 0} non e’ un CFL ) 0} non e’ un CFL

6969

Syntax Tree (albero Syntax Tree (albero sintattico) e Parsing Tree sintattico) e Parsing Tree

Albero SintatticoAlbero Sintattico Una delle rappresentazioni intermedie più usate. Più astratto del parsing Una delle rappresentazioni intermedie più usate. Più astratto del parsing

tree,tree,

dipende solo dal linguaggio (non dalla grammatica)dipende solo dal linguaggio (non dalla grammatica)

7070

EBNFEBNFUsa i simboli metalinguistici “=“ “|” “[“ “]” “{“. “}” “.” “”” Usa i simboli metalinguistici “=“ “|” “[“ “]” “{“. “}” “.” “”” […] significa opzionalita’[…] significa opzionalita’{…} significa ripetizione: 0 o piu’ volte{…} significa ripetizione: 0 o piu’ volte““(…)” significa raggruppamento(…)” significa raggruppamento““|” indica alternativa “.” termina una produzione|” indica alternativa “.” termina una produzioneI simboli terminali vengono racchiusi tra “ “I simboli terminali vengono racchiusi tra “ “EsempioEsempioExpression = SimpleExpression [ Relation SimpleExpression ].Expression = SimpleExpression [ Relation SimpleExpression ].Relation = "=" | "<>" | "<" | "<=" | ">" | ">=" | "IN".Relation = "=" | "<>" | "<" | "<=" | ">" | ">=" | "IN".SimpleExpression = [ "+" | "-" ] Term { AddOperator Term }.SimpleExpression = [ "+" | "-" ] Term { AddOperator Term }.AddOperator = "+" | "-" | "OR".AddOperator = "+" | "-" | "OR".Term = Factor { MulOperator Factor }.Term = Factor { MulOperator Factor }.MulOperator = "*" | "/" | "DIV"| "MOD" | "AND"MulOperator = "*" | "/" | "DIV"| "MOD" | "AND"

7171

EBNF Esempio (Espressioni) EBNF Esempio (Espressioni)

Expression = SimpleExpression [ Relation Expression = SimpleExpression [ Relation SimpleExpression ].SimpleExpression ].

Relation = "=" | "<>" | "<" | "<=" | ">" | ">=" | "IN".Relation = "=" | "<>" | "<" | "<=" | ">" | ">=" | "IN".

SimpleExpression = [ "+" | "-" ] Term { AddOperator SimpleExpression = [ "+" | "-" ] Term { AddOperator Term }.Term }.

AddOperator = "+" | "-" | "OR".AddOperator = "+" | "-" | "OR".

Term = Factor { MulOperator Factor }.Term = Factor { MulOperator Factor }.

MulOperator = "*" | "/" | "DIV" | "MOD" | "AND"MulOperator = "*" | "/" | "DIV" | "MOD" | "AND"

7272

EBNF Espressioni (cont.) EBNF Espressioni (cont.) Designator [ ActualParameters ] | "(" Expression ")" | NOT Factor.Designator [ ActualParameters ] | "(" Expression ")" | NOT Factor.

Set = "[" [ Element { "," Element } ] "]".Set = "[" [ Element { "," Element } ] "]".

Element = OrdinalConstant [ ".." OrdinalConstant].Element = OrdinalConstant [ ".." OrdinalConstant].

OrdinalConstant= Char | Integer.OrdinalConstant= Char | Integer.

ActualParameters = ["(" [ ExpressionList ] ")"].ActualParameters = ["(" [ ExpressionList ] ")"].

Ident = IdChar { IdChar | Digit }.Ident = IdChar { IdChar | Digit }.

IdChar = Letter | "_".IdChar = Letter | "_".

Number = Integer | Real.Number = Integer | Real.

7373

EBNF Espressioni (cont. 2) EBNF Espressioni (cont. 2) Integer = Digit { Digit } | Digit { HexDigit } "H".Integer = Digit { Digit } | Digit { HexDigit } "H".

Real = Digit { Digit } "." { Digit } [ ScaleFactor ].Real = Digit { Digit } "." { Digit } [ ScaleFactor ].

ScaleFactor = "E" [ "+" | "-" ] Digit { Digit }.ScaleFactor = "E" [ "+" | "-" ] Digit { Digit }.

HexDigit = Digit | "A" | "B" | "C" | "D" | "E" | "F".HexDigit = Digit | "A" | "B" | "C" | "D" | "E" | "F".

Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".

CharConstant = "'" Char "'" | Digit { HexDigit } "X".CharConstant = "'" Char "'" | Digit { HexDigit } "X".

String = ' { CharN | "''" } '.String = ' { CharN | "''" } '.

Char = CharN | "'".Char = CharN | "'".

Implementazione di Linguaggi 2 Massimo Ancona Testo: A.V. Aho, R. Sethi, J.D.Ullman Compilers...

Documents

Transcript of Implementazione di Linguaggi 2 Massimo Ancona Testo: A.V. Aho, R. Sethi, J.D.Ullman Compilers...