Linguaggi Formali Compilazione: Grammatiche

LFC

FormalismigenerativiEspressioni regolari

Grammatiche libere

Altri tipi di grammatica

Linguaggi formali e compilazioneCorso di Laurea in Informatica

A.A. 2008/2009

LFC


Grammatiche libere


Linguaggi formali e compilazione

Formalismi generativiEspressioni e linguaggi regolariGrammatiche libereAltri tipi di grammatiche

LFC


Grammatiche libere


Linguaggi regolari

I Un linguaggio L su un alfabeto Σ = {a1, . . . ,an} sidice regolare se può essere espresso mediantecomposizione finita di operazioni di concatenazione,unione e chiusura riflessiva a partire dai linguaggielementari (detti anche unitari) {a1}, . . . , {an}.

I Ogni linguaggio finito è chiaramente regolare mentreci sono abbondanti esempi di interessanti linguaggiinfiniti che non sono regolari.

I Come vedremo, i linguaggi regolari giocano un ruoloimportante nella definizione del lessico di unprogramma scritto in linguaggio ad alto livello, oltreche in svariati altri campi dell’Informatica.

LFC


Grammatiche libere


Esempi di linguaggi regolari

I Sia Σ l’alfabeto ASCII e sia X = X1X2 . . .Xn unagenerica stringa di Σ∗. Il linguaggio {X} è regolare inquanto esprimibile come concatenazione deilinguaggi unitari {X1}, {X2}, . . . , {Xn}.

I Il linguaggio {X ,Y ,Z}, dove X ,Y e Z sono stringhegeneriche sull’alfabeto ASCII è regolare perchéesprimibile come unione dei linguaggi regolari{X}, {Y}, e {Z}.

I Generalizzando l’esempio precedente si dimostracome ogni linguaggio finito sia esprimibile comeunione di concatenzazioni di linguaggi unitari.

LFC


Grammatiche libere


Altri esempi

I Il linguaggio L5 = {anbm|n,m ≥ 0} è regolare inquanto esprimibile nel modo seguenteL5 = {a}∗{b}∗.

I I seguenti linguaggi, introdotti nel gruppo di lucidiintroduttivi, sono tutti regolari:{ab,c}2, {ab,c}3, {ab,c}∗, {ab,c}+,

({ab,c}2

)R

I Il linguaggio L6 = {anbn|n ≥ 0} non è regolare.I Il linguaggio L10 = {an|n primo} non è regolare.

LFC


Grammatiche libere


Espressioni regolari

I Le espressioni regolari su un alfabeto Σ sono unformalismo che riflette (e semplifica) le costruzionidelineate sopra per la definizione di linguaggiregolari.

I Più precisamente, le espressioni regolari (e.r.)su Σsono definite ricorsivamente nel modo seguente:

Base. I Φ è un’espressione regolare chedenota l’insieme vuoto;

I per ogni a ∈ Σ, a è un’e.r. che denotal’insieme {a};

LFC


Grammatiche libere



Segue definizione di e.r.

Concatenazione Se E ed F sono e.r., la scrittura EF èun’e.r. che denota l’insieme di stringhe chepossono essere scritte concatenando unastringa dell’insieme denotato da E (piùbrevemente diremo “una stringa di E”) conuna stringa di F ;

Unione Se E ed F sono e.r., la scrittura E + F èun’e.r. che denota l’unione di E e di F .

Chiusura Se E è un’e.r., la scrittura E∗ è un’e.r. chedenota l’insieme delle stringhe ottenuteconcatenando stringhe di E un numeroarbitrario i ≥ 0 di volte.

LFC


Grammatiche libere



Un’ulteriore regolaParentesi. Se E è un’e.r., la scrittura (E) è un’e.r.

equivalente alla prima, cioè che denota lostesso insieme di stringhe

serve a forzare un ordine di composizione delleespressioni diverso da quello standard (in base al qualechiusura precede concatenazione che precede unione).

LFC


Grammatiche libere


Esempi

I L’espressione regolare 0 + 1∗10 su B (interpretabilecome 0 + ((1∗)10), in base alle regole diprecedenza) denota il linguaggioR1 = {0,10,110,1110, . . .}.

I Il linguaggio R1 è chiaramente differente dallinguaggio R2 su B definito dall’espressione regolare(0 + 1)∗10, che consiste di tutte le stringhe binarieche terminano con 10.

I Posto Σ = {a,b,c}, l’espressione regolarea(b + c)∗a denota il linguaggio R3 su Σ costituitodalle stringhe che iniziano e terminano con ilcarattere a e che non contengono altri caratteri a.

I La scrittura (1+01)∗(0+1+01) denota il linguaggiodelle stringhe su B di lunghezza maggiore di zeroche non contengono due caratteri 0 consecutivi.

LFC


Grammatiche libere


Abbreviazioni di uso pratico

I Poiché {ε} = Φ∗, si può utilizzare il simbolo ε perindicare l’insieme {ε}.

I La scrittura [E ] si può utilizzare al posto della e.r. E+εe l’operatore [ ] prende il nome di opzione.

I Se è definito un ordinamento fra i caratteri di Σ,allora si possono utilizzare convenzioni specificheper denotare intervalli di caratteri. Ad esempio, lascrittura [a− f] denota i caratteri compresi fra a ed f(opzione su un intervallo).

I Poiché L+ = LL∗, l’operatore di chiusura (nonriflessiva) è ammesso nelle e.r. dove si intende cheE+ = EE∗.

LFC


Grammatiche libere


Abbreviazioni di uso pratico

I Poiché Ln =

n︷︸︸︷LL . . . L, l’operatore di elevamento a

potenza è ammesso nelle e.r. e si intende che

En =

n︷︸︸︷EE . . . E .

I La scrittura [E ]ji si può utilizzare al posto della e.r.E i + E i+1 + . . .+ E j .

I Per alcuni insiemi di caratteri di particolareimportanza (cifre, lettere, caratteri alfanumerici,caratteri di spaziatura, ...) si possono usareespressioni specifiche, come ad esempio(prendendo a prestito la notazione dalle espressioniriconosciute dal comando grep di Linux):[: digit :], [: alpha :], [: alnum :], [: space :], . . .

LFC


Grammatiche libere


Esempi di interesse nel contesto deilinguaggi di programmazione

I Osserviamo dapprima che nel contesto delladefinizione della sintassi dei linguaggi diprogrammazione il simbolo + è spesso rimpiazzatoda |.

I L’espressione regolare [1− 9][: digit :]∗ denotal’insieme delle stringhe che rappresentano (nellaconsueta rappresentazione in base 10) i numeriinteri positivi.

I L’espressione regolare[: alpha :]([: alpha :]|[: digit :])∗ denota l’insieme degliidentificatori legali in alcuni linguaggi diprogrammazione (soprattutto fra i più vecchi).

LFC


Grammatiche libere


Esercizi proposti

I Scrivere un’e.r. per il seguente linguaggiosull’alfabeto {a,b,c}:

E1 = {anbmck |m = 0⇒ k = 3}

I Scrivere un’e.r. per il linguaggio E2, sull’alfabeto{a,b}, delle stringhe contenenti al più due a.

I Scrivere un’e.r. per il linguaggio E3, sull’alfabeto{a,b}, delle stringhe contenenti un numero dispari dib.

I Scrivere un’e.r. per il linguaggio E4, sull’alfabeto{a,b}, definito ricorsivamente nel modo seguente:

1. ε ∈ E4;2. Se x ∈ E4 allora anche abax ∈ E4 e xaa ∈ E4.

Inoltre, solo le stringhe ottenibili in questo modoappartengono a E4.

LFC


Grammatiche libere


Esercizi proposti

I Scrivere un’e.r. per il linguaggio E5, sull’alfabeto{a,b,c}, costituito dalle stringhe in cui ognioccorrenza di b è seguita da almeno un’occorrenzadi c.

I Descrivere nel modo più semplice possibile, inItaliano, il linguaggio corrispondente alla seguenteespressione regolare: ((a|b)3)∗(a|b).

I Si dica qual è la stringa più corta che non appartieneal linguaggio descritto dall’espressione regolarea∗(ab)∗b∗.

LFC


Grammatiche libere




LFC


Grammatiche libere


Grammatiche formali

I Come le espressioni regolari, anche le grammaticheformali sono uno strumento per la descrizione dilinguaggi.

I Sono un formalismo generativo perché il linguaggio èdefinito come l’insieme delle stringhe che possonoessere “generate” usando le regole dellagrammatica.

I Le grammatiche libere (Context-Free Grammar osemplicemente CFG) sono un particolare tipo digrammatica formale che trova ampio uso nelladefinizione dei linguaggi di programmazione.

I Solo per fare un esempio, la struttura a blocchi deiprogrammi scritti in Pascal (C, C++, Java, ...) vienedescritta mediante grammatiche libere.

LFC


Grammatiche libere


Definizione formale di grammaticaI Una grammatica G è una quadrupla di elementi:

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

doveI N è un insieme di simboli, detti non terminali;I T è un insieme di simboli terminali, N ∩ T = Φ;I P è l’insieme delle produzioni;I S ∈ N è il simbolo iniziale (o assioma).

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

I La forma delle produzioni è ciò che caratterizza il“tipo” di grammatica.

I In una grammatica libera le produzioni hanno laseguente forma

A→ α

dove A ∈ N e α ∈ V∗

LFC


Grammatiche libere


Un primo esempio di grammatica libera

N = {E}T = {(, ),+, ∗,id}S = EP = {E → E+E ,

E → E∗E ,E → (E),E → id}

I Si noti la presenza, nella definizione di unagrammatica, dei cosiddetti metasimboli, simboli cioèche non sono terminali ne’ non terminali.

I Esempi di metasimboli sono le parentesi graffe (chehanno il solito significato di descrizione di insieme) ela freccia orientata a destra (→).

LFC


Grammatiche libere


Derivazioni

I Le grammatiche sono formalismi generativi perchèconsentono di “generare” stringhe di caratteri tramiteil meccanismo delle derivazioni.

I Una derivazione è il processo mediante il quale, apartire dall’assioma ed applicando una sequenza diproduzioni, si arriva a scrivere una stringa di T ∗.

I Al riguardo le produzioni sono anche dette regole diriscrittura.

I Una produzione del tipo

E → E+E

si legge infatti nel seguente modo: Il simbolo E puòessere “riscritto” come E+E .

LFC


Grammatiche libere


Derivazioni (continua)

I Sia α = βAγ, dove A ∈ N e β, γ ∈ V∗ e sia A→ δuna produzione di G.

I Applicare la produzione A→ δ alla stringa αconsente di sostituire (“riscrivere”) il non terminale Acon il lato destro δ della produzione, ottenendo lastringa βδγ.

I Si dice che α deriva direttamente la stringa βδγ e siscrive

α⇒G βδγ

I Se α1 ⇒G α2 ⇒G . . .⇒G αk , k ≥ 1, allora si diceche α1 deriva αk e si scrive α1 ⇒∗G αk .

I Qualora non possano sorgere ambiguità eviteremo diindicare la grammatica nella notazione⇒G.

LFC


Grammatiche libere


Esempi

Chiamiamo G1 la grammatica precedentementeintrodotta. Allora:

I E+E ⇒G1 id+E tramite l’applicazione dellaproduzione E → id alla prima occorrenza di E .

I E+E ⇒∗G1id + id tramite l’applicazione della

produzione E → id ad entrambe le occorrenze di E .I E ⇒∗G1

id + (E) in quantoE ⇒G1 E+E ⇒G1 E+(E)⇒G1 id + (E).

I E ⇒∗G1id + (id), in quanto E ⇒G1 E+E ⇒G1

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

E+E ⇒G1 id+E ⇒G1 id + (E)⇒G1 id + (id).

LFC


Grammatiche libere


Frasi e linguaggio generato da unagrammatica

Sia G = (N , T ,P,S) una grammatica.I Si chiama forma di frase di G una qualunque stringaα di V∗ tale che S ⇒∗G α.

I Se α ∈ T ∗ allora si dice che α è una frase di G.I Il linguaggio generato da G (che indicheremo spesso

con la notazione L(G)) è l’insieme delle frasi di G.I Dagli esempi precedenti possiamo conlcudere che le

stringhe id + (E) e id + (id) sono forme di frase diG1; id + (id) è anche una frase e dunque è nellinguaggio L(G).

I Se la grammatica è libera da contesto allora anche illinguaggio viene detto libero (da contesto).

LFC


Grammatiche libere


Esempi

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

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

I Il linguaggio {ab,c}∗ è libero perché generato da

S → SS,S → ab,S → c,S → ε

I 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 → ε

LFC


Grammatiche libere


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

I La grammatica G2 così definita

N = {E ,T ,F ,A}T = {0,1, (, ),+, ∗,Φ, ε}S = EP = {E → T , E → T+E ,

T → F , T → FT ,F → (E), F → (E)*,F → A, F → A*,A→ 0, A→ 1}

genera tutte le stringhe sull’alfabeto0,1, (, ),+, ∗,Φ, ε che sono espressioni regolari benformate.

LFC


Grammatiche libere


EsempioI La stringa (epressione regolare) 0(0+1)∗

appartiene a L(G2) causa la derivazione:

E ⇒G2 T⇒G2 FT Usando T → FT⇒G2 FF Usando T → F⇒G2 AF Usando F → A⇒G2 A(E)∗ Usando F → (E)∗

⇒G2 0(E)∗ Usando A→ 0⇒G2 0(T + E)∗ Usando E → T + E⇒G2 0(T + T )∗ Usando E → T⇒G2 0(F + T )∗ Usando T → F⇒G2 0(F + F )∗ Usando T → F⇒G2 0(A + F )∗ Usando F → A⇒G2 0(A + A)∗ Usando F → A⇒G2 0(0 + A)∗ Usando A→ 0⇒G2 0(0 + 1)∗ Usando A→ 1

LFC


Grammatiche libere


Linguaggio generato da una grammatica(continua)

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

I Dapprima si formula una congettura sulla forma dellefrasi di L(G), di solito provando alcune sempliciderivazioni.

I Dopodiché si dimostra separatamente (perinduzione) che:

I se X è generata dal linguaggio, allora X ha quellaparticolare forma;

I se X è una stringa con quella particolare forma,allora è generabile dal linguaggio.

LFC


Grammatiche libere


Esempio

I Si consideri laseguente grammatica:

N = {A,B}T = {a,b}S = AP = {A→ aA,

A→ B,B → bB,B → ε}

I Vogliamo dimostrare cheL(G) = L5 = {anbm|n,m ≥ 0}.

I Dimostriamo che, se X ∈ L(G), allora X = anbm, peropportuni valori di n ed m. La dimostrazione procedeper induzione sulla lunghezza k delle derivazioni.

LFC


Grammatiche libere


Esempio (continua)I Preliminarmente, osserviamo che una derivazione

lunga k (k ≥ 1) genera, a partire da B, la stringabk−1 (anche questa è una semplice induzione).

I Per tornare a L(G), la base dell’induzione è costituitadall’unica derivazione lunga 2 (la più corta):A⇒ B ⇒ ε, che genera una stringa della formavoluta (con n = m = 0).

I Dimostriamo ora che la tesi è vera per derivazionilunghe k > 2.

I Per una tale derivazione possiamo scrivere

A⇒ aA⇒∗ X ,

oppureA⇒ B ⇒∗ X ,

I L’applicazione ad X dell’ipotesi induttiva (nel primocaso) o del risultato preliminare (secondo caso)porta agevolmente alla tesi.

LFC


Grammatiche libere


Esempio (continua)

I Dimostrare che ogni stringa della forma anbm

appartiene al linguaggio è ancora più semplice.I anbm è infatti generabile dalla seguente derivazione

di lunghezza n + m + 2

A⇒∗ anA⇒ anB ⇒∗ anbmB ⇒ anbm

costituita daI n applicazioni della regola A→ aA;I una applicazione di A→ B;I m applicazioni di B → bB;I una applicazione di B → ε.

LFC


Grammatiche libere


Equivalenza

I Due grammatiche G e G′ si dicono equivalenti segenerano lo stesso linguaggio.

I In alcuni testi, la sola coincidenza dei linguaggigenerati viene detta equivalenza debole.

I In seguito vedremo diverse trasformazioni dellegrammatiche che conservano il linguaggio.

I Un primo semplice esempio è costituito dallagrammatica G1 e dalla seguente grammatica:

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

che risultano essere (debolmente) equivalenti.

LFC


Grammatiche libere


Convenzioni notazionaliI I simboli non terminali, detti anche variabili

sintattiche, verranno spesso espressi (come nel casodella grammatica appena introdotta) usando letteremaiuscole in corsivo.

I La scrittura

E → E+E | E∗E | (E) | id

verrà utilizzata come abbreviazione per

E → E+E ,E → E∗E ,E → (E),

E → id

I Il metasimbolo | (barra verticale) indica dunquealternativa.

LFC


Grammatiche libere


Descrizione succinta di una grammatica

I Se si conviene di elencare per prime le produzionirelative al simbolo iniziale, una grammatica puòessere espressa semplicemente tramite leproduzioni (in realtà abbiamo già usato questaconvenzione).

I Ad esempio, la grammatica G2 che descrive leespressioni regolari su {a,b} può esseresemplicemente descritta come

E → T | T + ET → F | FTF → (E) | (E)∗ | A | A∗

A → 0 | 1

LFC


Grammatiche libere


Backus-Naur Form (BNF)

I Nella descrizione della sintassi dei linguaggi diprogrammazione le variabili sintattiche vengonorappresentate mediante un identificatore descrittivoracchiuso fra parentesi angolate.

I Esempio

〈comando if〉 → if 〈espressione booleana〉 then

〈lista di comandi〉endif |if 〈espressione booleana〉 then

〈lista di comandi〉else

〈lista di comandi〉endif

LFC


Grammatiche libere


Altri esempi

I Nella BNF, la grammatica G1 viene descritta dalleseguenti produzioni

〈espressione〉 → 〈espressione〉+ 〈espressione〉 |〈espressione〉 → 〈espressione〉 ∗ 〈espressione〉 |〈espressione〉 → (〈espressione〉) | id

I 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


Grammatiche libere


Altre convenzioni

I Elementi opzionali possono essere inclusi fra i metasimboli [ e ].

I Ad esempio, potremo usare la scrittura

〈comando if〉 → if 〈espressione booleana〉 then

〈lista di comandi〉[ else

〈lista di comandi〉 ]

endif

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

I Ad esempio

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

LFC


Grammatiche libere


Altre convenzioni (continua)

I Più recentemente, nella BNF i simboli terminali (dettianche token name) vengono scritti in grassetto.

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

I Ad esempio, potremo scrivere

comando if → if espressione booleana thenlista di comandi

[ elselista di comandi ]

endif

LFC


Grammatiche libere


Altre convenzioni (continua)

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

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

I Esempio (tratto dalla sintassi del C):

comando composto → ′′{′′ {dichiarazione } { comando } ′′}′′

LFC


Grammatiche libere


Esercizi proposti

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

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

I 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 stringaif b then if b then a else a

LFC


Grammatiche libere


Alberi di derivazione (parse tree)

I Un parse tree illustra graficamente il processo diderivazione di una stringa a partire dal simboloiniziale (o, più genericamente, da un non terminale).

I Formalmente, un parse tree per una grammaticalibera G = N , T ,P,S è un albero radicato edetichettato che soddisfa le seguenti proprietà:

I i nodi interni sono etichettati con simboli di N e, inparticolare, la radice è etichettata con l’assioma;

I le foglie sono etichettate con simboli di T o con ilsimbolo ε;

I se A ∈ N etichetta un nodo interno e X1, . . . ,Xk sonole etichette dei figli di (il nodo con etichetta) A, conXi ∈ V, allora deve esistere in P la produzioneA→ X1X2 . . .Xk ;

I Se A ∈ N etichetta un nodo interno il cui unico figlioè un nodo con etichetta ε, allora deve esistere in P laproduzione A→ ε.

LFC


Grammatiche libere


Esempi

I Parse tree per la stringa id ∗ (id + id) nellagrammatica G1

E

E E*

( )E

id id+

id

LFC


Grammatiche libere


Esempi

I Parse tree per la stringaif b then if b then a else a

nella grammatica GI

S

I

S

a

elseS

I

S

a

thenB

b

if

thenB

b

if

LFC


Grammatiche libere


Alberi di derivazione (parse tree)I Un parse tree impone una struttura sintattica alle

frasi e questo è generalmente il primo passo perattribuire ad esse un significato.

I La struttura sintattica può essere vista in manieraricorsiva come composizione della struttura di(sotto)frasi corrispondenti a sottoalberi del parsetree.

I In particolare, il sottoalbero radicato in un nodo conetichetta A ∈ N fornisce la struttura della frasederivata a partire da A.

I Nel caso del parse tree relativo alla fraseid ∗ (id + id), il sottoalbero radicato nel nodo indicatodalla freccia fornisce la struttura sintatticadell’espressione fra parentesi e l’albero nella suainterezza mostra la struttura della frase comecomposizione di espressioni.

LFC


Grammatiche libere


Parse tree e derivazioni

I Un risultato fondamentale afferma che α è una frasedi una grammatica G (cioè può essere derivata in Ga partire dal simbolo iniziale) se e solo se esiste in Gun parse tree per α.

I In generale, una frase di una grammatica può essereottenuta mediante più di una derivazione (sirammenti l’esempio di id + (id) nella grammatica G1).

I In particolare, ad un dato parse tree per α possonocorrispondere più derivazioni.

I Per definire con precisione il comportamento di unparser (come vedremo) è conveniente eliminarequesta “ridondanza” limitandoci a considerare soloparticolari derivazioni.

LFC


Grammatiche libere


Derivazioni canoniche

I Si dice che S ⇒∗G α è una derivazione canonicasinistra della frase α in G, se in essa ad ogni passoviene riscritto il simbolo non terminale più a sinistra.

I Analoga definizione vale per la derivazione canonicadestra.

I Delle due derivazioni viste per id + (id) in G1, laseconda è una derivazione canonica sinistra, mentrela prima non è una derivazione canonica.

I Se α ∈ V∗ (cioè se α è una forma di frase) e S ⇒∗G αmediante una derivazione canonica sinistra (destra),si dice che α è una forma di frase sinistra (destra); iltermine inglese utilizzato è left/right sentential form.

I Considerare derivazioni canoniche può non esseresufficiente ad eliminare ambiguità.

LFC


Grammatiche libere


EsempioI La frase id + id + id di G1 può essere ottenuta

mediante due differenti derivazioni canoniche destre,e precisamente

E ⇒G1 E+E⇒G1 E+E+E⇒G1 E+E+id⇒G1 E+id+id⇒G1 id + id + id

eE ⇒G1 E+E⇒G1 E+id⇒G1 E+E+id⇒G1 E+id+id⇒G1 id + id + id

(dove i simboli non terminali sottolineati sono quelliche verranno espansi al passo successivo).

LFC


Grammatiche libere


Ambiguità

I Abbiamo visto che ad una frase può corrisponderepiù di una derivazione cononica.

I Tuttavia, per un dato un parse tree esiste una soladerivazione canonica sinistra e una sola derivazionecanonica destra. (NB. D’ora in avanti, ci riferiremoalle derivazioni canoniche destre semplicementecome alle derivazioni canoniche.)

I Diciamo quindi che una grammatica è ambigua seesistono frasi per le quali esistono differenti parsetree (equivalentemente, differenti derivazionicanoniche sinistre o destre).

I L’ambiguità è un ostacolo alla realizzazione di unparser e di norma o viene eliminata alla radice(utilizzando grammatiche non ambigue) oppureutilizzando opportune regole per la disambiguazione.

LFC


Grammatiche libere


Esempio

I La grammatica GI è ambigua in quanto alla fraseif b then if b then a else a

corrisponde un altro parse tree, e precisamenteS

I

S

I

S

a

elseS

a

thenB

b

if

thenB

b

if

LFC


Grammatiche libere


Aspetti problematici per il parsingCi sono alcune caratteristiche delle grammatiche libereche possono ostacolare il processo di parsing, o anchesolo un “certo tipo” di parsing (come vedremo). Neelenchiamo brevemente alcune:

I ambiguità;I presenza di simboli non terminali che generano

linguaggi vuoti;I simboli non terminali che non compaiono in nessuna

forma di frase;I presenza di cicli (derivazioni del tipo A⇒+ A) o

comunque di left recursion (derivazioni del tipoA⇒+ Aα, con α 6= ε);

I presenza di produzioni A→ ε, dove A 6= S;I presenza di prefissi comuni a due o più produzioni

relative allo stesso non terminale, ad esempioA→ αβ1 e A→ αβ2.

LFC


Grammatiche libere


Esempi

I La grammatica

S → Sa | b

presenta una ricorsione immediata a sinistra inquanto S → Sa.

I La grammatica

S → A | bA → Aa | Sa

presenta una ricorsione a sinistra in quantoS ⇒+ Sa.

I La grammatica GI (oltre ad essere ambigua)presenta un prefisso comune alla due produzioni cheriscrivono il simbolo I.

LFC


Grammatiche libere


EsempiI Nella grammatica

S → SAA → a | ε

c’è una produzione A→ ε e questa provoca il cicloS ⇒+ S.

I Nella grammatica

S → aSA → a

il non terminale A è irraggiungibile da S.I Nella grammatica

S → aS | a | AA → Aa

il non terminale A genera il linguaggio vuoto.

LFC


Grammatiche libere


Scrittura di una grammatica per il parsingI Terminiamo questa parte del corso sulle CFG

presentando una serie di algoritmi per la “rimozione”degli aspetti problematici cui abbiamo fatto cenno.

I Ci serve qualche definizione.Raggiungibilità Un non terminale è raggiungibile se

può comparire in una forma di frase.Buona definizione Un non terminale è ben definito

se non genera il linguaggio vuoto.Pulizia Si dice che una grammatica è pulita se

non contiene cicli e ogni non terminaleè raggiungibile e ben definito.

Annullabilità Un non terminale A è annullabile seA⇒+ ε.

Prefissi comuni Presenza di coppie di produzioni deltipo A→ αβ1 e A→ αβ2.

Ricorsione sinistra Presenza di derivazioni del tipoA⇒+ Aα.

LFC


Grammatiche libere


Rimozione dei non terminali non ben definiti

I Per eliminare i simboli non terminali che generano unlinguaggio vuoto si calcola dapprima l’insiemecomplemento, costituito dai non terminali ben definiti,mediante un algoritmo di chiusura.

I Chiameremo D tale insieme.I La base dell’algoritmo pone in D tutti quei terminali A

per i quali esiste una produzione A→ α, con α ∈ T ∗.I Il passo ricorsivo consiste nell’aggiungere a D quei

simboli non terminali A per i quali esiste unaproduzione A→ α in cui α contiene simboli terminalio simboli già in D.

I Quando il passo ricorsivo non aggiunge nulla a D,l’algoritmo termina e l’insieme dei non terminali nonben definiti è N\D.

LFC


Grammatiche libere


EsempioI Si consideri la grammatica G così definita:

S → aAb | bDEaA → ε | aA | DB → b | bCC → cED → dAE → eCF → fD

I L’insieme D viene calcolato inserendo dapprima isimboli A e B (passo base), quindi S e D, infine F .Ne consegue che C ed E sono non ben definiti.

I Come “effetto collaterale” è possibile eliminare quelleproduzioni inutili che, come S → bDEa, contengonoa destra simboli non ben definiti.

LFC


Grammatiche libere


Esempio (continua)

I Dopo l’eliminazione dei non terminali non ben definitie delle produzioni inutili si ottiene la grammatica G′,equivalente a G:

S → aAb

A → ε | aA | DB → b

D → dAF → fD

LFC


Grammatiche libere


Rimozione dei non terminali non raggiungibili

I Il problema dell’eliminazione dei simboli nonraggiungibili può essere visto come una sempliceistanza del problema della raggiungibilità in un grafoorientato.

I Data una CFG G si costruisce un grafo orientatoG = (V ,E) nel seguente modo: l’insieme V deivertici contiene un elemento corrispondente ad ogninon terminale di G; l’insieme E contiene una coppia(arco orientato) 〈A,B〉 se e solo se esiste unaproduzione A→ αBβ, α, β ∈ V∗.

I L’esecuzione dell’algoritmo BFS consente di stabilirei nodi raggiungibili dal nodo (corrispondente ad) S.

I Si può quindi procedere all’eliminazione dei nonterminali corrispondenti ai vertici non raggiunti.

LFC


Grammatiche libere


Esempio (continua)I Eseguendo la BFS sul grafo corrispondente a G′

S

A

B

D

F

si scopre che B ed F non sono raggiungibili da S.I La loro eliminazione porta alla grammatica

equivalente G′′:

S → aAb

A → ε | aA | DD → dA

I È ora facile vedere che il linguaggio generato da G′′

è a(a|d)∗b.

LFC


Grammatiche libere


Eliminazione dei non terminali annullabili

I L’algoritmo calcola l’insieme E dei simboli nonterminali a partire dai quali è possibile derivare ε.

1: E ← {A ∈ N|A→ ε ∈ P}2: while ∃A→ A1 . . .Ak t.c. Ai ∈ E & A 6∈ E do3: E ← E ∪ {A}4: end while5: Elimina da P le produzioni del tipo A→ ε6: Elimina i non terminali di E dalle restanti

produzioni in tutti i modi (combinatorialmente)possibili

LFC


Grammatiche libere


Esempio

I Si consideri la grammatica:

S → A | εA → aAC | SBB → bB | b | εC → c

I Inizialmente si pone E = {S,B}, poiché S e B sonoimmediatamente annullabili.

I Poiché esiste la produzione A→ SB, al secondopasso il non terminale A viene inserito in E .

I Nessun altro non terminale può essere aggiunto a E .I Risulta quindi E = {S,A,B}.

LFC


Grammatiche libere


Esempio (continua)I Dopo l’eliminazione delle produzioni del tipo: A→ ε

S → AA → aAC | SBB → bB | bC → c

dopo la cancellazione dei non terminali in E in tutti imodi combinatorialmente possibili:

S → AA → aAC | aC | SB | S | BB → b | bBC → c

I La grammatica modificata è equivalente allagrammatica di partenza, salvo che non può generarela stringa vuota.

LFC


Grammatiche libere


Esempio (continua)

I Per rendere del tutto equivalenti le grammatichepossiamo aggiungere un nuovo assioma S′ con leproduzioni S′ → S | ε.

I La grammatica “completa” diviene quindi:

S′ → S | εS → AA → aAC | aC | SB | S | BB → b | bBC → c

LFC


Grammatiche libere


Eliminazione dei cicliI I cicli, cioè derivazioni del tipo A⇒+ A, sono non

solo inutili ma anche dannosi, in quanto dannoorigine ad ambiguità.

I Un algoritmo per eliminare i cicli elimina più ingenerale le produzioni che danno origine aderivazioni del tipo A⇒+ B.

I Si suppone che non ci siano non terminali annullabili.I In una tale grammatica, la possibilità che risulti

A⇒+ B può essere solo conseguenza di una catenadi cosiddette produzioni singole:

A → A1

→ A2

. . .

→ Ak

→ B

che sono facili da individuare.

LFC


Grammatiche libere


Eliminazione dei cicli (continua)

I Si consideri ora una generica coppia A,B tale cheA⇒+ B; se

B → α1 | . . . | αr

sono le produzioni (non singole) di B, allora siaggiungono alla grammatica le produzioni

A → α1 | . . . | αr

I Al termine, si eliminano tutte le produzioni singole.

LFC


Grammatiche libere


Esempio

I Si consideri ancora la grammatica:

S′ → S | εS → AA → aAC | aC | SB | S | BB → b | bBC → c

I È facile vedere che risulta: S′ ⇒+ S, S′ ⇒+ A,S′ ⇒+ B, S ⇒+ A, S ⇒+ B, S ⇒+ S, A⇒+ B.

I Le produzioni che vanno aggiunte sono quindi

S′ → aAC | aC | SB | b | bBS → aAC | aC | SB | b | bBA → b | bB

LFC


Grammatiche libere


Esempio (continua)

I La grammatica risultante (priva di cicli) è:

S′ → aAC | aC | SB | b | bB | εS → aAC | aC | SB | b | bBA → aAC | aC | SB | b | bBB → b | bBC → c

I Una grammatica equivalente ma più semplice (esempre senza cicli) è:

S′ → S | εS → aSC | aC | SB | b | bBB → b | bBC → c

LFC


Grammatiche libere


Eliminazione delle ricorsioni sinistre

I Si può assumere che la grammatica in input noncontenga non terminali annullabili ne’ cicli.

I Sia A1, . . . ,An un ordinamento (arbitrario) dei simbolinon terminali.

I L’idea dell’algoritmo è di far sì che ogni produzionedel tipo Ai → Ajα abbia sempre i < j .

I L’algoritmo consta di due cicli annidati:1. Nel ciclo esterno (con iteratore i) vengono eliminate

le ricorsioni immediate Ai → Aiα;2. Nel ciclo interno (con iteratore j) vengono modificate

quelle produzioni del tipo Ai → Ajα in cui j < i .

LFC


Grammatiche libere


Eliminazione delle ricorsioni sinistre(continua)

I Per eliminare tutte le produzioni del tipo A→ Aαr ,r = 1,2, . . . , t (per qualche t ≥ 1), si considerano lealtre produzioni relative al non terminale A

A→ β1 | β2 | . . . | βm

in cui nessuna stringa βs inizia per A.I Le produzioni per A vengono quindi sostituite nel

modo seguente

A → β1A′ | β2A′ | . . . | βmA′

A′ → α1A′ | α2A′ | . . . | αtA′ | ε

LFC


Grammatiche libere



I Per eliminare una produzione del tipo Ai → Ajα siconsiderano le altre produzioni relative al nonterminale Aj

Aj → β1 | β2 | . . . | βp

in cui nessuna stringa inizia per Aq, q ≤ j .I La produzione Ai → Ajα viene quindi sostituita nel

modo seguente

Ai → β1α | β2α | . . . | βmα

LFC


Grammatiche libere



L’algoritmo completo è il seguente1: Disponi i non terminali in ordine A1, . . . ,An2: for i = 1 to n do3: for j = 1 to i − 1 do4: Sostituisci le produzioni del tipo Ai → Ajα5: end for6: Sostituisci le produzioni del tipo Ai → Aiα7: end for

LFC


Grammatiche libere


Esempio

I Consideriamo ancora la grammatica G1 per leespressioni

E → E + E | E ∗ E | (E) | id

che contiene solo ricorsioni immediate (ancheperché contiene un solo non terminale).

I Le produzioni vengono sostituite nel modo seguente,con l’introduzione di un non terminale E ′

E → (E) E ′ | id E ′

E ′ → + E E ′ | ∗ E E ′ | ε

LFC


Grammatiche libere


EsempioI Consideriamo la grammatica così definita:

A → Bb | aB → Bb | Ac

che consente la derivazione A⇒+ Acb.I Se nell’ordinamento dei non terminali A si fa

precedere a B diviene necessario eliminare laproduzione B → Ac.

I Questo comporta l’introduzione delle due produzioniB → Bbc | ac.

I La successiva eliminazione delle ricorsioniimmediate (B → Bb | Bbc) porta alla seguentegrammatica modificata

A → Bb | aB → acB′

B′ → bB′ | bcB′ | ε

LFC


Grammatiche libere


Eliminazione delle ambiguità

I Da un punto di vista algoritmico il problema ènotevolmente più complicato.

I Addirittura, se non si fanno restrizioni di altro tiposulla grammatica libera G in input, il problema distabilire se G è ambigua non ammette algoritmo(problema indecidibile).

I Gli algoritmi esistono per sottoclassi dellegrammatiche libere.

I Nella pratica la soluzione consiste nel “progettare” lagrammatica in modo che essa sia non ambigua(piuttosto che verificarlo a posteriori) evitando unaserie di errori che possono generare ambiguità.

I Esamineremo alcuni degli accorgimenti da utilizzare

LFC


Grammatiche libere


Ambiguità delle frasi condizionali

I Nel contesto dei linguaggi di programmazione èconsuetudine interpretare la frase ambigua dellagrammatca GI

if cond then if cond then stmt else stmtnel seguente modo:if cond then

beginif cond then stmt else stmt

endassociando cioè ogni else con il più vicino then nonancora associato.

I Questa regola di solito viene implementata daiparser ma non viene forzata dalle produzioni.

LFC


Grammatiche libere


Ambiguità delle frasi condizionali (continua)I Volendo modificare la grammatica, si introducono

due tipologie di istruzione condizionale, chechiameremo chiusa e aperta

S → O | CC → if B then C else C | AO → if B then S |

if B then C else O

dove A indica un generico altro comando.I Se ora riconsideriamo la frase

if b then if b then a else adove b ed a indicano, rispettivamente, condizionilogiche e comandi generici (non condizionali)vediamo che all’interpretazione

if b then begin if b then a end else anon corrisponde nessuna derivazione.

LFC


Grammatiche libere


Esempio

I Consideriamo il seguente frammento di grammatica,nella quale, rispetto al caso precedente, abbiamoinserito anche un’istruzione iterativa

S → O | CC → if B then C else C | I | AO → if B then S |

if B then C else OI → while B do S

I Con questa grammatica la stringaif b then while b do if b then a else a

è ambigua, come dimostrano i due possibili alberi diderivazioni mostrati nelle successive trasparenze (lasoluzione è lasciata come esercizio)

LFC


Grammatiche libere


Esempio (continua)S

C

C

A

a

elseC

I

S

O

S

C

A

a

thenB

b

if

doB

b

while

thenB

b

if

LFC


Grammatiche libere


Esempio (continua)S

O

S

C

I

S

C

C

A

a

elseC

A

a

thenB

b

if

doB

b

while

thenB

b

if

LFC


Grammatiche libere


Ambiguità legata alla ricorsioneI Se una grammatica ammette (per almeno un simbolo

non terminale raggiungibile) risorsioni bilaterali, cioèsia ricorsioni a sinistra che a destra, allora lagrammatica è ambigua.

I In generale, supponiamo che una data grammaticaconsente una derivazione del tipo A⇒+ AαA, conα ∈ V∗.

I Sono quindi possibili le seguenti due derivazionidella stringa α1α2α3α4α5, dove αi ∈ T è derivabileda A, i = 1, . . . ,5.

A

A

α5

α4A

A

α3

α2A

α1

A

A

A

α5

α4A

α3

α2A

α1

LFC


Grammatiche libere


Ambiguità legate all’unione di linguaggi

I Se G′ e G′′ generano i linguaggi L′ e L′′, allora unmodo immediato per generare il linguaggioL = L′ ∪ L′′ è di usare una grammatica siffatta

S → S′|S′′

S′ → . . . Produzioni di G′

S′′ → . . . Produzioni di G′′

assumendo che S′ ed S′′ siano gli assiomirispettivamente di G′ e G′′ e che le due grammatichenon abbiano simboli non terminali comuni.

I Tuttavia se L′ ∩ L′′ 6= Φ allora la grammatica risultaambigua.

LFC


Grammatiche libere


EsempioI Sia G′ la grammatica (già vista) che genera il

linguaggio L11, delle palindrome sull’alfabeto {a,b}:

P → aPa | bPb | a | b | εI Sia G′′ la grammatica (anch’essa già vista) che

genera il linguaggio L5, delle stringhe anbm:

A→ aA | B, B → bB | εI Poiché l’intersezione dei due linguaggi non è vuota

(contiene stringhe del tipo an e bm), la grammatica

S → P | AP → aPa | bPb | a | b | εA → aA | B, B → bB | ε

è ambigua.I Ad esempio, la frase aa ammette le due seguenti

derivazioni canoniche: S ⇒ aPa⇒ aa eS ⇒ A⇒ aA⇒ aaA⇒ aaB ⇒ aa.

LFC


Grammatiche libere


Ambiguità legate al concatenamento dilinguaggi

I Se G′ e G′′ generano i linguaggi L′ e L′′, allora unmodo immediato per generare il linguaggio L = L′L′′

è di usare una grammatica siffatta

S → S′S′′

S′ → . . . Produzioni di G′

S′′ → . . . Produzioni di G′′

assumendo che S′ ed S′′ siano gli assiomirispettivamente di G′ e G′′ e che le due grammatichenon abbiano simboli non terminali comuni.

I Se G′ può generare le stringhe α1α2 e α1 e G′′ puògenerare le stringhe α2α3 e α3, allora la stringaα1α2α3 ammette due derivazioni canoniche.

LFC


Grammatiche libere


Esempio

I Il linguaggio L8 (delle stringhe del tipo anbmck ) puòessere ottenuto come concatenazione dei linguaggi{anbm} e {bncm}, e dunque dalla grammatica:

S → ACA → aA | B, B → bB | εC → bC | D, D → cD | ε

che però risulta ambigua, a causa della capacità dientrambe le grammatiche “componenti” di generarele stringhe bn.

I Ad esempio, per la stringa abc si possono dare leseguenti due derivazioni canoniche: S ⇒ AC ⇒AD ⇒ AcD ⇒ Ac⇒ aAc⇒ aBc⇒ abBc⇒ abc eS ⇒ AC ⇒ AbC ⇒ AbD ⇒ AbcD ⇒ Abc⇒aAbc⇒ aBbc⇒ abc.

LFC


Grammatiche libere


Precedenza degli operatori

I La grammatica G1 fornisce un esempio di ambiguitàlegata alla presenza di produzioni bilaterali

E → E+E | E∗E

I In questo caso è facile eliminare la ricorsionebilaterale immediata, introducendo un nuovo simbolonon terminale E ′

E → E+E ′ | E∗E ′ | E ′

E ′ → id | (E)

I La nuova grammatica non è più ambigua ma, comeG1, presenta un problema legato alla precedenzadegli operatori.

LFC


Grammatiche libere


Precedenza degli operatori (continua)I Si osservi l’albero di derivazione della stringa

id + id ∗ idE

E’

id

*E

E’

id

+E

E’

idI Esso suggerisce che l’interpretazione debba essere

(id + id) ∗ id, che non coincide con l’interpretazioneche universalmente si dà alla stringa in Matematica.

LFC


Grammatiche libere


Precedenza degli operatori (continua)

I La “usuali” precedenze di operatore possono essereforzate introducendo differenti simboli non terminaliper i diversi livelli di precedenza.

I Ad esempio, nel caso di somma e prodotto possiamointrodurre due livelli di precedenza, rappresentati dainon terminali E e T , oltre ad un simbolo (useremo F )per la catogoria delle espressioni di base (nel nostrocaso identificatori ed espressioni tra parentesi):

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

LFC


Grammatiche libere



I La grammatica precedente (con le ovvie estensioni)“gestisce” senza ambiguità anche il caso deglioperatori di divisione e sottrazione, inseriti nellegiuste categorie sintattiche:

E → E+T | E−T | TT → T∗F | T/F | FF → id | (E)

LFC


Grammatiche libere



I Volendo inserire anche l’operatore diesponenziazione (che ha precedenza maggiore), ènecessario prevedere un’ulteriore variabile sintatticae ricordarsi che l’operatore di esponenziazione (quiuseremo il simboloˆ) è associativo a destra:

E → E+T | E−T | TT → T∗P | T/P | PP → FˆP | FF → id | (E)

LFC


Grammatiche libere


Esercizi

I Si consideri il linguaggio La>b delle stringhe su{a,b} che contengono più a che b. Si dica,giustificando la risposta, se la seguente grammaticalibera genera La>b

S → a | aS | Sa | abS | aSb | Sab |baS | bSa | Sba

I Si formisca una grammatica libera per il linguaggiosu B contenente tutte e sole le stringhe con undiverso numero di 0 e 1.

LFC


Grammatiche libere


EserciziI Si considerino le seguenti grammatiche per i

linguaggi L8 ed L9:

S′ → DCD → aDb | εC → cC | ε

e

S′′ → AEE → bEc | εA → aA | ε

Si dica quale linguaggio genera la grammaticaottenuta “unendo” le due grammatiche per L8 ed L9,con la produzione iniziale S → S′ | S′′, e se lagrammatica stessa è ambigua.

LFC


Grammatiche libere




LFC


Grammatiche libere


Grammatiche lineariI Se le produzioni di una grammatica G sono tutte del

tipo A→ XB o A→ X , dove X ∈ T ∗ e B ∈ N , allorala grammatica è detta lineare destra.

I Allo stesso modo, se le produzioni sono del tipoA→ BX o A→ X , G è detta lineare sinistra.

I Grammatiche lineari (destre o sinistre) sono detteregolari.

I Si può dimostrare che le espressioni regolari e legrammatiche regolari sono formalismi equivalenti; inaltri termini, un linguaggio è regolare se e solo se ègenerabile da una grammatica regolare.

I Inoltre, poichè le grammatiche regolari sono anchelibere, ogni linguaggio regolare è anche libero.

I Il viceversa non è vero; infatti il linguaggioL6 = {anbn|n ≥ 0} non è regolare ma generabiledalla grammatica libera S → aSb | ε.

LFC


Grammatiche libere


Esempi

I Il linguaggio 0(0 + 1)∗ è regolare in quantogenerabile dalla seguente grammatica lineare destra

A→ 0B | 0, B → 0 | 1 | 0B | 1B

I Il linguaggio L5 è regolare in quanto generabile dallaseguente grammatica lineare destra (come abbiamogià visto):

S → aS | B, B → bB | ε

I Il linguaggio {ab,c}∗ è generabile dalla seguentegrammatica

S → abS | cS | ε

LFC


Grammatiche libere


Grammatiche dipendenti dal contestoI Se la forma generale delle produzioni è del tipo:

α→ β

dove α, β ∈ V∗ e |α| ≤ |β|, allora la grammatica èdetta dipendente dal contesto (in inglese,context-dependent o context-sensitive o, ancora piùbrevemente, CSG).

I Alternativamente, le produzioni possono essere deltipo

αAγ → αβγ

dove α, β, γ ∈ V∗, β 6= ε e A ∈ N .I Si può dimostrare che le due forme sono equivalenti

(cioè generano gli stessi linguaggi).I Tuttavia, la seconda forma “spiega” meglio il nome di

queste grammatiche: il simbolo A può essere riscrittocome β solo se appare nel contesto α− γ.

LFC


Grammatiche libere


Linguaggi dipendenti dal contesto

I Sono così detti i linguaggi generabili da grammatichedipendenti dal contesto.

I Poiché la forma generale delle produzioni di unaCSG sono più generali di quelle di una CFG,l’insieme dei linguaggi dipendenti dal contesto“contiene” l’insieme dei linguaggi liberi.(Si noti che la stringa vuota può essere sempreaggiunta prevedendo la produzione S → ε, dovel’assioma S non compare nella parte destra dialcuna produzione.)

I Viceversa, ci sono linguaggi dipendenti dal contestoche non sono liberi.

I Un esempio è il linguaggio

L13 = {anbncn|n ≥ 0}

LFC


Grammatiche libere


Classificazione di Chomsky

I Le grammatiche (e i corrispondenti linguaggi) sonostati raggruppati in 4 classi, in dipendenza della“potenza” delle produzioni.

I Al livello più basso abbiamo le grammatiche regolari(o di tipo 3), quindi le grammatiche libere (tipo 2) equelle dipendenti dal contesto (tipo 1).

I Le grammatiche più generali, di tipo 0, sono dettegrammatiche a struttura di frase, in cui le produzionisono come quelle delle grammatiche di tipo 1 senzala restrizione |α| ≤ |β|.

LFC


Grammatiche libere


Costrutti non liberi nei linguaggi diprogrammazione

I Alcuni aspetti della sintassi dei linguaggi diprogrammazione non sono catturabili da produzionidi grammatiche libere.

I Ad esempio, il fatto che il numero di argomenti in unachiamata di procedura debbe coincidere con ilnumero di parametri formali nella corrispondentedefinizione non è esprimibile con una CFG.

I Tale caratteristica è catturata dal cosiddettolinguaggio delle repliche (che non è libero):

LR = {αα|α ∈ T ∗}.

Linguaggi Formali Compilazione: Grammatiche

Technology

Transcript of Linguaggi Formali Compilazione: Grammatiche