Analisi sintattica Linguaggi formali e compilazione libere ... · Java Input per P Programma P in...

LFC

CompilatoriFunzioni e struttura

Analisi lessicale: token,pattern e lessemi

Analisi sintatticaParsing e grammatichelibereLinguaggi formali e compilazione

Corso di Laurea in Informatica

A.A. 2014/2015

LFC



Analisi sintatticaParsing e grammatichelibere

Linguaggi formali e compilazione

CompilatoriFunzioni e strutturaAnalisi lessicale: token, pattern e lessemi

Analisi sintatticaParsing e grammatiche libere

LFC




Che cosa è un compilatore

◮ Un compilatore è un traduttore.◮ Questo vuol dire un programma che:

◮ riceve in input la descrizione di un “oggetto” X scrittoin un certo linguaggio L;

◮ produce in output la descrizione di X in un altrolinguaggio L′.

◮ La traduzione deve essere corretta nel senso che ilsignificato (o semantica) dell’input deve esserepreservato.

LFC




Traduttori in generale

◮ Alcuni semplici esempi:◮ un algoritmo che trasforma numeri dal sistema

romano a quello posizionale decimale;◮ il programma ps2pdf disponibile in Linux;◮ un software che trasforma programmi scritti in C in

programmi scritti in binario per l’architettura x86.

◮ Solo nell’ultimo caso si parla propriamente dicompilazione.

◮ Che cosa significa, negli esempi sopra citati, che “ilsignificato deve essere preservato” (e dunque che latraduzione è corretta)?

LFC




Compilazione ed esecuzione di programmi inlinguaggio ad altro livello

◮ La compilazione è il più importante caso ditraduzione in ambito informatico.

◮ Un compilatore per un linguaggio L e una macchinaM è un traduttore che, data una stringa(programma) in linguaggio L, produce un programma“equivalente” nel linguaggio macchina di M.

◮ Compilazione e successiva esecuzione di unprogramma

Programma

P in linguaggio L

Compilatore

di L per il

computer M

Input per P

Programma P in

codice eseguibile

sul computer M

CPU di M Risultati

LFC




Uno schema alternativo: l’interpretazionepura

◮ Un’alternativa alla compilazione è l’interpretazione

diretta dei programmi.◮ Nel caso dell’interpretazione di L su M, un

programma in esecuzione su M prende direttamentein input frasi in linguaggio L e le “esegue”,producendo in output il risultato dell’esecuzione.

◮ Lo schema per l’interpretazione pura

Programma

P in linguaggio L

Input per P

Risultati

Interprete del

l inguaggio L

LFC




Esistono anche soluzioni “miste”

◮ Compilazione ed intepretazione in Java

Programma

P in JavaCompilatore

Java

Input per P

Programma P in

codice intermedio

(bytecode)

JRE per

computer MRisultati

◮ In tutti i casi (anche nell’interpretazione “pura”), letecniche di compilazione giocano un ruolofondamentale.

LFC




Inciso: linguaggi compilati e linguaggiinterpretati

◮ In linea di principio, di uno stesso linguaggio L

potrebbero esistere implementazioni compilate edimplementazioni interpretate.

◮ Nella pratica, i linguaggi “si specializzano” in unasola delle due alternative, anche (o forse soprattutto)perché compilazione ed interpretazione offronovantaggi e svantaggi complementari, che sono poiriflessi nei linguaggi stessi.

◮ C, C++, Fortran e Pascal sono linguaggi compilati.◮ I linguaggi dinamici (Perl, Python, PHP, ...) sono

linguaggi interpretati.◮ Il caso di Java.

LFC




Schema generale di un compilatore

Compilatore

Programma

sorgente

Programma

oggetto

◮ Cominciamo a guardare “dentro la scatola” ...

Programma

sorgente

Programma

oggetto

Compilatore

F r o n t - e n d B a c k - e n d

Codice

intermedio

LFC




Due componenti principali

◮ Il front-end rappresenta la fase di analisi dell’input.◮ Il back-end è la fase di sintesi dell’output.◮ Il codice intermedio è indipendente dall’architettura

hardware (i386, powerpc, sparc, ...).◮ Vantaggi di questa organizzazione:

◮ modularità;◮ portabilità;◮ economicità.

◮ Noi ci occuperemo “esclusivamente” del front-end

LFC




Uno schema ancora più dettagliatoProgramma sorgente

Analisi lessicale

Analisi sintattica (parsing)

Generazione del codice intermedio

Ottimizzazione del codice

Generazione del codice

Codice oggetto

Schema trat to dal "Dragon book" (1977)

Gestione degli erroriGestione della

Symbol table

LFC




Il front-end più in dettaglio

◮ Il front-end di un compilatore (cioè la parte chetermina con la creazione di una rappresentazioneintermedia del programma) è costituita dai seguentimoduli:

◮ analizzatore lessicale (scanner);◮ analizzatore sintattico (parser);◮ symbol table (e routine di gestione);◮ generatore di codice intermedio.

◮ Per ragioni di tempo non ci potremo occupare, inquesto corso, della gestione degli errori.

LFC




Il modello di front-end

◮ La seguente figura illustra un tipico schema diorganizzazione del front-end di un compilatore (trattoda Aho, Lam, Sethi, Ullman (2007)).

Analizzatore

lessicaleParser

Gestore della

symbol table

Generatore di

codice intermedioToken

Programma

sorgenteAlbero

sintatt ico

three-addreess

code

Richiesta

token

LFC




Analizzatore lessicale

◮ L’analizzatore lessicale, detto anche scanner, èl’unico modulo che legge il file di testo checostituisce l’input per il compilatore.

◮ Il suo ruolo è di raggruppare i caratteri in input intoken, ovvero “oggetti” significativi per la successivaanalisi sintattica.

◮ Esempi di token sono i numeri, gli identificatori e leparole chiave di un linguaggio di programmazione.

◮ Ad esempio, la sequenza di caratteri:

X = 3.14;

potrebbe venire trasformata nella sequenza di token:

id assign number sep

LFC




Analizzatore lessicale (continua)

◮ Ci sono però altri compiti che deve svolgerel’analizzatore lessicale:

◮ riconoscere e “filtrare” commenti, spazi e altricaratteri di separazione;

◮ associare gli eventuali errori trovati da altri moduli delcompilatore (in particolare dal parser) alle posizioni(righe di codice) dove tali errori si sono verificati alloscopo di emettere appropriati messaggi diagnostici;

◮ procedere all’eventuale espansione delle macro (se ilcompilatore le prevede).

LFC




Parser

◮ Il parsing opera esclusivamente al livello di sintassi

(cioè della corretta formazione delle frasi).◮ Un parser (detto appunto anche analizzatore

sintattico) è uno strumento che, in termini generali,consente di dare struttura ad una descrizione lineare.

◮ Per questa ragione il parsing è un processo moltocomune, anche in altre ambiti dell’Informatica.

◮ Alcuni esempi:◮ passare dalla descrizione testuale di un grafo ad una

sua rappresentazione in liste di adiacenze;◮ dato un insieme di pagine web, creare un grafo che

ne descriva la struttura dei collegamenti;◮ dato un documento XML, creare una

rappresentazione dell’informazione in essocontenuta (detta information set) da renderedisponibile all’applicazione client.

LFC




Parser (continua)

◮ La struttura viene conferita alla descrizione lineare ininput in accordo a regole formali.

◮ Nel caso dei linguaggi di programmazione taliformalismi sono generalmente grammatiche.

◮ L’output viene a sua volta specificato mediante unformalismo in grado di esprimere le proprietà di

struttura.◮ Generalmente tale formalismo è un albero (con varie

proprietà).◮ In tutti i casi, il parsing include un’analisi della

correttezza formale (well-formedness) delle stringheda analizzare.

LFC




Generazione del codice intermedio

◮ A partire dalla struttura prodotta dal parser e (comevedremo) dalle informazioni raccolte nella symboltable, questa fase produce un programma scritto inun linguaggio intermedio

◮ Il codice intermedio è indipendente dalla macchina equindi è teoricamente portabile.

◮ Esistono diverse soluzioni per rappresentare talecodice e, fra queste, il cosiddetto three-address code

(codice a tre indirizzi).

LFC




Breve descrizione delle altre fasiOttimizzazione del codice In questa fase operano

algoritmi che manipolano il programmascritto in codice intermedio in modo daottenere un programma equivalente che (ingenere) utilizza una minore quantità dispazio e/o che “gira” più velocemente.

Generazione del codice In questa fase il programma incodice intermedio (eventualmenteottimizzato) viene trasformato in codicemacchina. Qui vengono prese le decisionisull’allocazione dei dati in memoria, il codicedi accesso e l’utilizzo dei registri.

Gestione della tabella dei simboli È un’attività cheaccompagna tutte le fasi della compilazione.La tabella dei simboli è essenzialmente undizionario che registra tutti i nomi usati nelprogramma e le informazioni ad essoassociate (esempio, un identificatore e il suotipo).

LFC




Breve descrizione delle fasi

Gestione degli errori Durante una qualunque delle fasi sipossono verificare degli errori, che devonoessere individuati e segnalati con opportunimessaggi diagnostici. Gli esempi piùfacilmente comprensibili di errore riguardanole fasi di analisi lessicale (ad esempio, unidentificatore che contiene un carattere nonammesso) e di analisi sintattica (ad esempioun’espressione aritmetica mal formata). Ingenerale se vengono rilevati errori non vieneprodotto il codice oggetto.

LFC




Le fasi attraverso un semplice esempio

LFC




Interazione parser-lexical analyzer◮ Lo scanner opera come “routine” del parser.

Analizzatore

lessicaleParser

Gestore della

symbol table

TokenProgramma

sorgente

Albero

sintatt ico

Richiesta

token

◮ Quando il parser deve leggere il prossimo simbolo diinput esegue una chiamata allo scanner.

◮ Lo scanner legge la “prossima” porzione di input finoa quando non riconosce un token, che vienerestituito al parser.

◮ Ciò che viene propriamente restituito è un token

name, una delle due componenti che costituiscono iltoken vero e proprio.

LFC




Token

◮ Un token è un oggetto astratto caratterizzato da dueattributi, un token name (obbligatorio) e un valore

opzionale.◮ Ecco alcuni esempi di sequenze di caratteri

riconosciuti come token da un compilatore C++:◮ “0.314E+1”, cui corrisponde la coppia (token) in cui

il nome è number e il valore è il numero razionale3.14, opportunamente rappresentato;

◮ “x1”, cui corrisponde un token in cui il nome è id e ilcui valore è, a sua volta, un insieme di informazionielementari (la stringa di caratteri che formal’identificatore, il suo tipo, il punto del programmadove è stato definito);

◮ “else”, cui corrisponde il solo token name else.

LFC




Token name

◮ Il nome del token serve principalmente al parser, perstabilire correttezza sintattica delle frasi (e costruirel’albero sintattico).

◮ Il valore dei token è invece, da questo punto di vista,non rilevante (almeno in prima istanza).

◮ Ad esempio, le frasi “x<10” e “pippo!=35” sono deltutto equivalenti e riconducibili alla frase generica incui il valore di un identificatore è confrontato con unnumero.

◮ Una tale frase può quindi essere astrattamentedescritta come “id comparison number”, doveabbiamo utilizzato il nome comparison per il tokenche descrive gli operatori relazionali.

LFC




Token value

◮ Il valore di un token gioca il suo ruolo principale nellatraduzione del codice.

◮ Con riferimento agli esempi del lucido precedente:◮ di un identificatore è importante sapere (tra gli altri) il

tipo, perché da questo dipende (in particolare) laquantità di memoria allocare;

◮ di un operatore di confronto è necessario sapereesattamente di quale confronto si tratta, per poterpredisporre il test e l’istruzione (macchina) di saltoopportuna;

◮ di una costante numerica è necessario sapere ilvalore per effettuare l’inizializzazione corretta.

LFC




Token (continua)

◮ È naturalmente il progettista del linguaggio chestabilisce quali debbano essere considerati token.

◮ Ad un token name possono corrispondere (ingenerale) molte stringhe alfanumeriche nel codicesorgente (si pensi ai token che descrivono numeri oidentificatori).

◮ Il progettista deve quindi stabilire esattamente anchela mappatura fra stringhe e token name (cioè, qualistringhe corrispondono a quali token).

◮ Tale mappatura viene descritta utilizzando opportuniformalismi, il più importante dei quali è costituitodalle espressioni regolari.

LFC




Un minimo di terminologia

◮ Le sequenze di simboli che possono legalmentecomparire in un programma e che corrispondono aitoken sono dette lessemi.

◮ Un pattern è invece una descrizione (formale oinformale) delle stringhe (lessemi) che devonoessere riconosciute (dall’analizzatore lessicale)come istanze di un determinato token name.

◮ Le espressioni regolari sono un formalismo perspecificare tali pattern.

LFC




Pattern, lessemi e token name (continua)

◮ La seguente tabella illustra, mediante alcuni esempi,i concetti che stiamo analizzando.

Token name Pattern Esempio di lessemaid letter(letter | digit)∗ pippo1

number [+ | -]nzd digit∗[.]digit∗ -3.14

comparison < | > | <= | >= | = | != <

literal [:alpha:] “Pi greco”if if if

while while while

Si noti che, per ragioni di spazio, il pattern che descrive iltoken number non prevede la notazione scientifica.

LFC




Scopo del parsing◮ L’obiettivo della fase di parsing è innanzitutto di

stabilire se una sequenza di token rappresenta una“frase” corretta del linguaggio e, nel caso,descriverne la struttura.

◮ Sulla base di che cosa possiamo stabilire, adesempio, chewhile (a>0) {a=a-1}

è una frase corretta in C/C++, mentrewhile (a>0) a=a-1}

è una frase sintatticamente errata?◮ La risposta (anche se solo parziale) è che una frase

è corretta se e solo se è conforme alla sintassi dellinguaggio.

◮ Il formalismo che si è imposto per la descrizionedella sintassi dei linguaggi di programmazione èquello delle grammatiche libere (da contesto), ininglese context-free grammar.

LFC




Un pezzo di grammatica del C

iteration_statement

: while '(' expression ')' statement

| do statement while '(' expression ')' ';'

| for '(' expression_statement expression_statement ')' statement

| for '(' expression_statement expression_statement expression ')' statement

;

statement

: labeled_statement

| compound_statement

| expression_statement

| selection_statement

| iteration_statement

| jump_statement

;

compound_statement

: '{' '}'

| '{' statement_list '}'

| '{' declaration_list '}'

| '{' declaration_list statement_list '}'

;

LFC




Grammatiche formali

◮ Come le espressioni regolari, anche le grammatiche

formali (da qui in avanti semplicementegrammatiche), sono uno strumento per ladescrizione di linguaggi.

◮ Una grammatica è un formalismo generativo perchéil linguaggio da essa definito coincide con l’insiemedelle stringhe che possono essere “generate”usando determinate regole che fanno parte dellagrammatica stessa.

◮ Le grammatiche possono avere diversi gradi di

espressività, e dunque definire linguaggi più o menoricchi.

◮ Esiste però un forte compromesso fra espressività epossibilità di riconoscimento automatico, chevedremo ben rappresentato nel caso caso deilinguaggi di programmazione.

LFC




Definizione formale di grammatica

◮ Diamo ora la definizione generale di grammatica(formale).

◮ Una grammatica G è una quadrupla di elementi:

G = (N ,T ,P,S),

dove◮ N è un insieme di simboli, detti non terminali;◮ T è un insieme di simboli terminali, N ∩ T = Φ;◮ P è l’insieme delle produzioni, cioè scritture della

forma X → Y , dove X ,Y ∈ (N ∪ T )∗;◮ S ∈ N è il simbolo iniziale (o assioma).

◮ Conviene anche definire l’insieme V = N ∪ T come ilvocabolario della grammatica.

LFC




Le produzioni

◮ La forma delle produzioni è ciò che caratterizzapropriamente il “tipo” di grammatica, cioè la suacapacità espressiva.

◮ Se le produzioni sono del tipo: A → xB oppureA → x , dove x ∈ T e A,B ∈ N , la grammatica èdetta lineare destra.

◮ Se invece le produzioni sono del tipo: A → Bx

oppure A → x , dove x ∈ T e A,B ∈ N , lagrammatica è detta lineare sinistra.

◮ Una grammatica regolare è una grammatica lineare(destra o sinistra).

◮ Il nome non è casuale. Infatti grammatiche regolaridescrivono proprio i linguaggi regolari che giàconosciamo.

LFC




Le produzioni

◮ Per la definizione della sintassi dei linguaggi diprogrammazione, hanno invece particolareimportanza i cosiddetti linguaggi liberi da contesto (opiù semplicemente linguaggi liberi).

◮ I linguaggi liberi sono generabili da grammatiche(dette anch’esse libere) in cui le produzioni hanno laseguente forma generale

A → X

dove A ∈ N e X ∈ V∗, cioè in cui la parte sinistra èun qualunque simbolo non terminale mentre la partedestra è una qualunque stringa di terminali o nonterminali.

LFC




Derivazioni

◮ Il meccanismo in base al quale le grammatiche“generano” linguaggi è quello delle derivazioni.

◮ Una derivazione è il processo mediante il quale, apartire dall’assioma ed applicando una sequenza diproduzioni, si ottiene una stringa di T ∗, cioè unastringa composta da soli terminali.

◮ Le produzioni rappresentano infatti vere e proprieregole di riscrittura.

◮ Ad esempio, una produzione del tipo

E → E+E

si può leggere nel seguente modo: il simbolo E puòessere “riscritto” come E+E .

LFC




Derivazioni (continua)

◮ L’idea è che una grammatica descriva (generi) illinguaggio costituito proprio dalle sequenze disimboli terminali derivabili a partire dall’assioma S.

◮ Consideriamo, ad esempio, la grammaticaG5 = (N ,T ,P,S) così definita:

◮ N = {S,A,B};◮ T = {a,b};◮ S = S;◮ P contiene le seguenti produzioni:

S → ǫ, S → A

A → a, A → aA, A → B

B → bB, B → b

◮ Nel linguaggio generato da G5 è inclusa la stringa ab

perché:

S ⇒ A ⇒ aA ⇒ aB ⇒ ab.

LFC




Nota sulla notazione...

◮ La scrittura α ⇒ β (dove α, β ∈ V∗) indica che β puòessere ottenuta direttamente da α mediantel’applicazione di una produzione della grammatica.

◮ Ad esempio, con riferimento alla derivazione dellucido precedente, aA ⇒ aB perché nellagrammatica G5 è presente la produzione A → B.

◮ Non sarebbe stato corretto scrivere aA → aB

(perché non esiste una tale produzione).◮ Se α deriva β mediante l’applicazione di 0 o più

produzioni si scrive α∗⇒G β.

◮ Ad esempio, in G5, aA∗⇒G ab.

LFC




Descrizione succinta di una grammatica

◮ Una grammatica può essere espressa in modo piùsuccinto elencando le sole produzioni, qualora siconvenga che le prime produzioni in elenco sianoquelle relative all’assioma.

◮ Ad esempio, scrivendo

E → E+E

E → E∗E

E → (E)

E → id

intendiamo la grammatica G1 = (N ,T ,P,S) in cui:◮ N = {E};◮ T = {id,+, ∗, (, )};◮ S = E ;

e le produzioni sono ovviamente quelle indicate.

LFC




Altri esempi di derivazione

Consideriamo la grammatica G1 appena introdotta.Allora:

◮ E+E ⇒G1id+E tramite l’applicazione della

produzione E → id alla prima occorrenza di E .◮ E+E

∗⇒G1

id+ id tramite l’applicazione dellaproduzione E → id ad entrambe le occorrenze di E .

◮ E∗⇒G1

id+ (E) in quantoE ⇒G1

E+E ⇒G1E+(E) ⇒G1

id+ (E).

◮ E∗⇒G1

id+ (id), in quanto E ⇒G1E+E ⇒G1

E+(E) ⇒G1id+ (E) ⇒G1

id+ (id).◮ Una derivazione alternativa per id+ (id) è E ⇒G1

E+E ⇒G1id+E ⇒G1

id+ (E) ⇒G1id+ (id).

LFC




Descrizione succinta e metasimboli◮ Possiamo economizzare ancora sulla descrizione di

una grammatica “fondendo” produzioni che hanno lastessa parte sinistra.

◮ È consuetudine, infatti, usare la scrittura X → Y |Z alposto di X → Y e X → Z .

◮ Usando anche questa convenzione, la grammaticaG5 può essere descritta nel seguente modocompatto:

S → ǫ | A

A → a | aA | B

B → bB | b

◮ Si noti come nella descrizione di una grammatica siutilizzino simboli che non sono terminali ne’ nonterminali, come ad esempio → e | .

◮ Tali simboli prendono il nome di metasimboli.

LFC




Frasi e linguaggio generato

Sia G = (N ,T ,P,S) una grammatica.◮ Si chiama forma di frase di G una qualunque stringa

α di V∗ tale che S∗⇒G α.

◮ Se α ∈ T ∗ allora si dice che α è anche una frase diG.

◮ Dagli esempi precedenti possiamo conlcudere (adesempio) che:

◮ le stringhe id+ (E) e id+ (id) sono forme di frasedi G1;

◮ le stringhe abB, abbB e ab sono forme di frase di G5;◮ id+ (id) e ab sono anche frasi;◮ baA non è una forma di frase di G5.

◮ Il linguaggio generato da G, spesso indicato conL(G), è l’insieme delle frasi di G.

LFC




Esempi

◮ La grammatica G5 genera il linguaggioL5 = {anbm|n,m ≥ 0}.

◮ La grammatica G1 genera il linguaggio delleespressioni aritmetiche composte da +, *, (, ) e id.

◮ Le stringhe più corte in L(G1) sonoid,id+ id,id ∗ id, (id).

LFC




Linguaggio generato da una grammatica

◮ Per dimostrare formalmente che una datagrammatica G genera un dato linguaggio L (cioè perprovare che L = L(G)) si procede solitamente perinduzione.

◮ Dapprima si formula una congettura sulla forma dellefrasi di L(G), provando alcune semplici derivazioni.

◮ Dopodiché si dimostra separatamente che:◮ se X è generata dal linguaggio, allora X ha la

particolare forma congetturata;◮ se X è una stringa con quella particolare forma,

allora esiste una derivazione in grado di generarla.

◮ Il procedimento può essere (relativamente)complesso anche per grammatiche molto semplici.

LFC




Un esempio

◮ Dimostriamo formalmente che la grammatica G5

genera il linguaggio L5 = a∗b∗.◮ Ricordiamo che G5 è:

S → ǫ | A

A → a | aA | B

B → bB | b

◮ G5 genera “solo” stringhe del tipo anbm.◮ S ⇒ ǫ◮ S ⇒ A

k⇒ ak A ⇒ ak+1, k ≥ 0

◮ S ⇒ Ak⇒ ak A ⇒ ak B

h⇒ akbhB ⇒ akbh+1,

h, k ≥ 0◮ G5 genera “tutte” le stringhe del tipo anbm.

◮ Segue dall’arbitrarietà di k e h sopra.

LFC




Gerarchia di Chomsky

◮ La seguente tabella descrive la gerarchia digrammatiche, ad ognuna delle quali viene associatol’automa riconoscitore e la classe di linguaggicorrispondente.

◮ La progressione è dalla grammatica menoespressiva (tipo 3) a quella più espressiva (tipo 0).

Tipo Grammatica Automa Linguaggio

3 Regolare Automa finito Regolare2 Libera Automa a pila Libero1 Dipendente Automa limitato Dipendente

dal contesto linearmente dal contesto0 Ricorsiva Macchina di Ricorsivamente

Turing enumerabile

LFC




Tipi dei linguaggi

◮ Si può dimostrare che se un linguaggio è generabileda una grammatica lineare (tipo 3) allora è regolare.

◮ Se invece un linguaggio L è generato da unagrammatica G di tipo i (i = 0, ..,2), allora L è “al più”di tipo i .

◮ Infatti L potrebbe essere generabile anche da unagrammatica più semplice (di tipo i + 1).

◮ Il linguaggio L5 è regolare perché generato da unagrammatica lineare, come abbiamo appenadimostrato.

◮ Il linguaggio L(G1) è invece al più libero perchégenerabile da una grammatica libera.

LFC




Tipi dei linguaggi

◮ Posto Σ = {a,b,c}, ll linguaggio su Σ∗ costituitodalle stringhe in cui ogni a è seguita una b è al piùlibero perché generato da

S → ǫ | R

R → b | c | ab | RR

◮ In realtà L è regolare, in quanto definibile anchemediante l’espressione regolare (b+ c+ ab)∗.

◮ Il linguaggio L11 su {a,b} costituito da tutte lestringhe α palindrome (cioè tali che αR = α) è liberoin quanto generabile dalla grammatica

S → aSa,S → bSb,S → a,S → b,S → ǫ

Si può poi dimostrare che L11 non è regolare.

LFC




Un esempio più complesso: le e.r. comelinguaggio libero

◮ Come sappiamo, le espressioni regolari sono unformalismo per definire linguaggi.

◮ Ad esempio, l’espressione regolare 0(0+ 1)∗,sull’alfabeto B, definisce il linguaggio delle stringhebinarie che iniziano con 0.

◮ Per essere “manipolabili” automaticamente (adesempio, per passare da un’espressione regolare alcorrispondente automa nondeterministico), leespressioni regolari devono essere riconosciutecome ben formate.

◮ Ad esempio, l’espressione 0(0+∗1 è ben formata?

Potremmo procedere alla costruzione dell’automa?

LFC




Un esempio più complesso: le e.r. comelinguaggio libero

◮ La grammatica G2 così definita

E → T | T+E

T → F | FT

F → (E) | (E)* | A | A*,

A → 0 | 1

genera tutte le stringhe sull’alfabeto 0,1, (, ),+, ∗, ǫche sono espressioni regolari ben formatesull’alfabeto B.

LFC




Esempio (continua)◮ La stringa (epressione regolare) 0(0+1)∗

appartiene a L(G2) in quanto esiste la derivazione:

E ⇒G2T

⇒G2FT Usando T → FT

⇒G2FF Usando T → F

⇒G2AF Usando F → A

⇒G2A(E)∗ Usando F → (E)∗

⇒G20(E)∗ Usando A → 0

⇒G20(T + E)∗ Usando E → T + E

⇒G20(T + T )∗ Usando E → T

⇒G20(F + T )∗ Usando T → F

⇒G20(F + F )∗ Usando T → F

⇒G20(A + F )∗ Usando F → A

⇒G20(A + A)∗ Usando F → A

⇒G20(0+ A)∗ Usando A → 0

⇒G20(0+ 1)∗ Usando A → 1

LFC




Backus-Naur Form (BNF)◮ Nella descrizione della sintassi dei linguaggi di

programmazione, i simboli non terminali, detti anchevariabili sintattiche, vengono spesso rappresentatimediante un identificatore descrittivo racchiuso fraparentesi angolate.

◮ Esempio

〈comando if〉 → if 〈espressione booleana〉 then

〈lista di comandi〉

endif |

if 〈espressione booleana〉 then


else


endif

LFC




Altri esempi

◮ Usando la BNF la grammatica G1 verrebbe descrittadalle seguenti produzioni

〈espressione〉 → 〈espressione〉+ 〈espressione〉 |

〈espressione〉 → 〈espressione〉 ∗ 〈espressione〉 |

〈espressione〉 → (〈espressione〉) | id

◮ Una grammatica per le chiamate di procedura in Java

〈chiamata〉 → id(〈parametri-opzionali〉)

〈parametri-opzionali〉 → 〈lista-di-parametri〉 | ǫ

〈lista-di-parametri〉 → 〈lista-di-parametri〉, 〈parametro〉 |

〈parametro〉

LFC




Altre convenzioni◮ Elementi opzionali possono essere inclusi fra i meta

simboli [ e ].◮ Ad esempio, potremo usare la scrittura

〈comando if〉 → if 〈espressione booleana〉 then


[ else

〈lista di comandi〉 ]

endif

◮ Elementi ripetitivi possono essere inclusi fra imetasimboli { e }.

◮ Ad esempio

〈list di comandi〉 → 〈comando〉 { ; 〈comando〉 }

LFC




Altre convenzioni (continua)

◮ Più recentemente, nella BNF i simboli terminalivengono scritti in grassetto.

◮ In questo modo diventa possibile sopprimere l’usodelle parentesi angolate intorno alle variabilisintattiche, migliorando la leggibilità complessiva. Levariabili sintattiche continuano ad essere scritte incorsivo.

◮ Ad esempio, potremo scrivere

comando if → if espressione booleana then

lista di comandi

[else

lista di comandi ]

endif

LFC




Altre convenzioni (continua)

◮ Nel caso in cui possano sorgere ambiguità, i simboliterminali vengono racchiusi fra doppi apici.

◮ Un esempio è costituita dal caso di simboli terminalicoincidenti con qualche metasimbolo.

◮ Esempio (tratto dalla sintassi del C):

comando composto → ”{” {dichiarazione } { comando } ”}”

LFC




Qualche esercizio

◮ Fornire una grammatica libera per l’insieme dellestringhe costituite da parentesi correttamentebilanciate (ad esempio, ()(()) e (()) devono far partedel linguaggio, mentre ())( non deve farne parte).

◮ Fornire una grammatica libera per il linguaggioL12 = {anb2n|n ≥ 0} sull’alfabeto {a,b}.

◮ Si consideri la seguente grammatica GI

S → I | A

I → if B then S | if B then S else S

A → a

B → b

e si fornisca una derivazione per la stringa

if b then if b then a else a

LFC




Qualche esercizio◮ Si scriva una grammatica libera o lineare per

generare il linguaggio L composto da tutte lestringhe sull’alfabeto {a,b,c} che non contengonodue caratteri consecutivi uguali.

◮ Si consideri la seguente grammatica libera G

A → bB a | a | b

B → bA | Aa

Si verifichi dapprima che in essa le derivazioni hannolunghezza 2ℓ+ 1, ℓ ≥ 0. Si dimostri quindi, perinduzione su ℓ, che il linguaggio generato da G è:

L(G) ={

bha

k : h + k = 3ℓ+ 1,h ≥ ℓ, k ≥ ℓ}

◮ Si scriva una grammatica libera per generare illinguaggio L definito dalla seguente espressioneregolare sull’alfabeto {a,b,c}: ba∗(b+ c)a∗c

Analisi sintattica Linguaggi formali e compilazione libere ... · Java Input per P Programma P in...

Documents

Transcript of Analisi sintattica Linguaggi formali e compilazione libere ... · Java Input per P Programma P in...