Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf ·...
Transcript of Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf ·...
Linguaggi Liberi dal Contesto
Linguaggi Liberi dal Contesto
Grammatiche e Linguaggi Liberi da Contesto
Data una stringa w ∈ L(G ), dove G e’ un CGF, possonoesistere diverse derivazioni di w (che tipicamente differisconoper l’ordine di applicazione delle produzioni)
Esistono vari modi per risolvere il problema1 fissare un ordine nell’applicazione delle produzioni2 astrarre dall’ordine di applicazione delle produzioni, tramite un
parse tree (o albero sintattico)
Linguaggi Liberi dal Contesto
Derivazioni a sinistra o a destra
Derivazione a sinistra ⇒lm
: rimpiazza sempre la variabile piu’
a sinistra con il corpo di una delle sue regole.
Derivazione a destra ⇒rm
: rimpiazza sempre la variabile piu’
a destra con il corpo di una delle sue regole.
Linguaggi Liberi dal Contesto
Esempio: espressioni
Espressioni (semplici) in un tipico linguaggio di programmazione.Gli operatori sono + e *, e gli operandi sono identificatori, cioe’stringhe in L((a + b)(a + b + 0 + 1)∗)Le espressioni sono definite dalla grammatica
G = ({E , I},T ,P,E )
dove T = {+, ∗, (, ), a, b, 0, 1} e P e’ il seguente insieme diproduzioni:
E → I E → E + EE → E ∗ E E → (E )
I → a I → bI → Ia I → IbI → I0 I → I1
Linguaggi Liberi dal Contesto
Derivazione a sinistra
Una derivazione di w = a ∗ (a + b00) da E nella grammatica delleespressioni:
E ⇒ E ∗ E ⇒ I ∗ E ⇒ a ∗ E ⇒ a ∗ (E ) ⇒
a ∗ (E + E ) ⇒ a ∗ (I + E ) ⇒ a ∗ (a + E ) ⇒ a ∗ (a + I ) ⇒
a ∗ (a + I0) ⇒ a ∗ (a + I00) ⇒ a ∗ (a + b00)
Linguaggi Liberi dal Contesto
Derivazione a destra
A destra:E ⇒
rmE ∗ E ⇒
rm
E ∗ (E ) ⇒rm
E ∗ (E + E ) ⇒rm
E ∗ (E + I ) ⇒rm
E ∗ (E + I0)
⇒rm
E ∗ (E + I00) ⇒rm
E ∗ (E + b00) ⇒rm
E ∗ (I + b00)
⇒rm
E ∗ (a + b00) ⇒rm
I ∗ (a + b00) ⇒rm
a ∗ (a + b00)
Linguaggi Liberi dal Contesto
Forme Sentenziali
Sia G = (V ,T ,P,S) una CFG, e α ∈ (V ∪ T )∗.
Se S∗⇒ α diciamo che α e’ una forma sentenziale.
Se S ⇒lm
α diciamo che α e’ una forma sentenziale sinistra,
Se S ⇒rm
α diciamo che α e’ una forma sentenziale destra
Nota: L(G ) contiene le forme sentenziali che sono in T ∗.
Linguaggi Liberi dal Contesto
Esempio
Nella grammatica delle espressioni
E ∗ (I + E ) e’ una forma sentenziale perche’
E ⇒ E ∗ E ⇒ E ∗ (E ) ⇒ E ∗ (E + E ) ⇒ E ∗ (I + E )
Questa derivazione non e’ ne’ a sinistra ne’ a destra
a ∗ E e’ una forma sentenziale sinistra, perche’
E ⇒lm
E ∗ E ⇒lm
I ∗ E ⇒lm
a ∗ E
E ∗ (E + E ) e’ una forma sentenziale destra, perche’
E ⇒rm
E ∗ E ⇒rm
E ∗ (E ) ⇒rm
E ∗ (E + E )
Linguaggi Liberi dal Contesto
Alberi sintattici
astraendo dall’ordine di applicazione delle produzioni si ottieneuna struttura ad albero, l’albero sintattico (o parse tree)
gli alberi sintattici sono una rappresentazione alternativa allederivazioni
il parse tree rappresenta la struttura sintattica della stringa ede’ usato nelle applicazioni delle grammatiche CGF di cuiabbiamo parlato
w potrebbe essere un programma, una query SQL, undocumento XML, ...
Linguaggi Liberi dal Contesto
Ambiguita’
Idealmente dovrebbe esistere un solo albero sintattico (la”vera” struttura) che rappresenta tutte le derivazioni di unastringa
Tuttavia, una grammatica puo’ essere ambigua, ovveropossono esistere diversi alberi sintattici per la stessa stringa
Sfortunatamente, non sempre possiamo rimuoverel’ambiguita’.
Linguaggi Liberi dal Contesto
Definizione di Albero Sintattico
Sia G = (V ,T ,P,S) una CFG. Un albero e’ un albero sintatticoper G se:
1 Ogni nodo interno e’ etichettato con una variabile in V .
2 Ogni foglia e’ etichettata con un simbolo in V ∪ T ∪ {ε}.Ogni foglia etichettata con ε e’ l’unico figlio del suo genitore.
3 Se un nodo interno e’ etichettato A, e i suoi figli (da sinistra adestra) sono etichettati
X1,X2, . . . ,Xk ,
allora A → X1X2 . . .Xk ∈ P.
Linguaggi Liberi dal Contesto
Esempio
E → I E → E + EE → E ∗ E E → (E )
il seguente e’ un albero sintattico:
E
E + E
I
La radice e’ E , le etichette delle foglie (non terminali), lette dasinistra a destra formano la stringa I + E .L’albero sintattico rappresenta le derivazioni E
∗⇒ I + E
Linguaggi Liberi dal Contesto
Esempio
Nella grammatica
P → ε P → 0 P → 1P → 0P0 P → 1P1
il seguente e’ un albero sintattico:
P
P
P
0 0
1 1
ε
La radice e’ P, le etichette delle foglie (terminali), lette da sinistraa destra formano la stringa 0110.L’albero sintattico rappresenta la derivazione P
∗⇒ 0110
Linguaggi Liberi dal Contesto
Prodotto
Il prodotto di un albero sintattico e’ la stringa di foglie da sinistraa destra.Importanti sono quegli alberi sintattici dove:
1 Il prodotto e’ una stringa terminale.
2 La radice e’ etichettata dal simbolo iniziale.
L’insieme dei prodotti di questi alberi sintattici e’ il linguaggio dellagrammatica.
Linguaggi Liberi dal Contesto
Esempio: nella grammatica delle espressioni
E
E E*
I
a
E
E E
I
a
I
I
I
b
( )
+
0
0
Il prodotto e’ a ∗ (a + b00).
Linguaggi Liberi dal Contesto
Teorema: equivalenza
Sia G = (V ,T ,P,S) una CFG. Per ogni stringa α ∈ (T ∪ V )∗ eper ogni variabile A ∈ V , le seguenti affermazioni sono equivalenti:
A∗⇒ α
C’e’ un albero sintattico di G con radice A e’ prodotto α.
Nota: il teorema vale in particolare per le stringhe di terminaliw ∈ T∗ e per le derivazioni dal simbolo iniziale S . Quindiw ∈ L(G ) sse c’e’ un albero sintattico di G con radice S e’prodotto w .
Linguaggi Liberi dal Contesto
Schema della Prova
dagli alberi alle derivazioni: facciamo vedere che si puo’costruire una derivazione sinistra o simmetricamente unaderivazione destra
dalle derivazioni facciamo vedere in modio induttivo come sipuo’ costruire un albero.
Linguaggi Liberi dal Contesto
Corrispondenza tra derivazioni ed alberi sintattici
per ogni albero sintattico esiste una ed una solo derivazionesinistra corrispondente
per ogni albero sintattico esiste una ed una solo derivazionedestra corrispondente
Linguaggi Liberi dal Contesto
Corrispondenza tra derivazioni
Sia G = (V ,T ,P,S) una CFG. Per ogni stringa α ∈ (T ∪ V )∗ eper ogni variabile A ∈ V , le seguenti affermazioni sono equivalenti:
A∗⇒ α
A⇒lm
∗α
A ⇒rm
∗α
Prova Se A⇒lm
∗α allora banalmente A∗⇒ α (analogo per il caso
simmetrico)
Se A∗⇒ α allora esiste un albero sintattico con radice A e prodotto
α. Prendiamo come A⇒lm
∗α la derivazione sinistra corrispondente
(analogo per il caso simmetrico).
Linguaggi Liberi dal Contesto
Ambiguita’
Definizione: Sia G = (V ,T ,P,S) una CFG. Diciamo che G e’ambigua se esiste una stringa in T ∗ che ha piu’ di un alberosintattico.Se ogni stringa in L(G ) ha al piu’ un albero sintattico, G e’ dettanon-ambigua.
Linguaggi Liberi dal Contesto
Esempio
Consideriamo la grammatica delle espressioni
1. E → I
2. E → E + E
3. E → E ∗ E
4. E → (E )· · ·
la grammatica e’ ambigua
Linguaggi Liberi dal Contesto
Esempio
La forma sentenziale E + E ∗ E ha due derivazioni:
E ⇒ E + E ⇒ E + E ∗ E
e E ⇒ E ∗ E ⇒ E + E ∗ E
Questo ci da’ due alberi sintattici:
+
*
*
+
E
E E
E E
E
E E
EE
(a) (b)
Linguaggi Liberi dal Contesto
Esempio
Di conseguenza la stringa di terminali a + a ∗ a ha due alberisintattici:
I
a I
a
I
a
I
a
I
a
I
a
+
*
*
+
E
E E
E E
E
E E
EE
(a) (b)
Linguaggi Liberi dal Contesto
Ambiguita’
l’esistenza di vari alberi sintattici rovina la grammatica
esempio: i due alberi sintattici della stringa a + a ∗ acorrispondono a due semantiche differenti, (a + a) ∗ a oa + (a ∗ a)?
bisogna rimuovere l’ambiguita’ dalle grammatiche
va fatto a mano, non esiste nessun algoritmo per farlo inmodo sistematico
Ancora cattive notizie: alcuni CFL hanno solo CFG ambigue
Linguaggi Liberi dal Contesto
Esempio
Studiamo la grammatica
E → I | E + E | E ∗ E | (E )
I → a | b | Ia | Ib | I0 | I1
Ci sono due problemi:
1 Non c’e’ precedenza tra * e +
2 Non c’e’ raggruppamento di sequenze di operatori: E + E + Ee’ inteso come E + (E + E ) o come (E + E ) + E?
Linguaggi Liberi dal Contesto
Soluzione
Introduciamo piu’ variabili, ognuna che rappresenta espressioni conlo stesso grado di ”forza di legamento”
1 Un fattore e’1 Identificatori2 Un’espressione racchiusa tra parentesi.
Non puo essere spezzata da un + o per ∗ adiacente.
2 Un termine e’ un’espressione che non puo’ essere spezzata daun +. Ad esempio, a ∗ b puo’ essere spezzata da a1∗ o ∗a1.Non puo’ essere spezzata da +, perche’ ad esempio a1 + a ∗ be’ (secondo le regole di precedenza) lo stesso di a1 + (a ∗ b), ea ∗ b + a1 e’ lo stesso di (a ∗ b) + a1.
3 Il resto sono espressioni, cioe’ possono essere spezzate con * o+.
Linguaggi Liberi dal Contesto
La grammatica modificata
Usiamo F per i fattori, T per i termini, e E per le espressioni.Consideriamo la seguente grammatica:
1. I → a | b | Ia | Ib | I0 | I12. F → I | (E )
3. T → F | T ∗ F
4. E → T | E + T
Linguaggi Liberi dal Contesto
Esempio
Ora l’unico albero sintattico per la stringa a + a ∗ a e’:
F
I
a
F
I
a
T
F
I
a
T
+
*
E
E T
Dalla radice E applichiamo la produzione E −− > E + T , lasemantica dell’espressione e’ a + (a ∗ a)
Linguaggi Liberi dal Contesto
Esempio
Se alla radice applicassimo la produzione E −− > T ,dovremmo derivare a + a ∗ a da T . Ma a + a ∗ a non e’ unfattore (non e’ derivabile da F ), e non e’ derivabile da T ∗ F .Infatti, a + a non e’ derivabile da T .
La stringa (a + a) ∗ a che rappresenta l’altra interpretazionesemantica e’ invece derivabile da T ∗ F perche’ (a + a) e’ unfattore.
Linguaggi Liberi dal Contesto
Perche’ la nuova grammatica non e’ ambigua?
Spiegazione intuitiva:
Un fattore e’ o un identificatore o (E ), per qualcheespressione E .
L’unico albero sintattico per una sequenza
f1 ∗ f2 ∗ · · · ∗ fn−1 ∗ fn
di fattori e’ quello che da’ f1 ∗ f2 ∗ · · · ∗ fn−1 come termine e fncome fattore, come nell’albero del prossimo lucido.
Un’espressione e’ una sequenza
t1 + t2 + · · ·+ tn−1 + tn
di termini ti . Puo’ essere solo raggruppata cont1 + t2 + · · ·+ tn−1 come un’espressione e tn come untermine.
Linguaggi Liberi dal Contesto
Albero sintattico per una sequenza di ∗
*
*
*
T
T F
T F
T
T F
F
.. .
Linguaggi Liberi dal Contesto
Ambiguita’ inerente
Un CFL L e’ inerentemente ambiguo se tutte le grammatiche per Lsono ambigue.Esempio: Consideriamo un linguauggio unione di due linguaggiL = L1 ∪ L2
L1 = {anbncmdm : n ≥ 1,m ≥ 1}
L2 = {anbmcmdn : n ≥ 1,m ≥ 1}.
Linguaggi Liberi dal Contesto
Il linguaggio L
Il linguaggio L contiene tutte le stringhe del tipo a+b+c+d+ chesoddisfano una delle seguenti condizioni
ci sono tante a che b e ci sono tante c che d
ci sono tante a che d e ci sono tante b che c
Esempio abccdd ∈ L1 ma abccdd 6∈ L2; viceversa aabcdd ∈ L2 maaabcdd 6∈ L1.
Linguaggi Liberi dal Contesto
Una Grammatica per L
Una grammatica CGF per L1 e’
S → ABA → aAb | abB → cBd | cd
Una grammatica CGF per L2 e’
S → CC → aCd | aDdD → bDc | bc
Mettendole insieme troviamo una grammatica CGF per L.
Linguaggi Liberi dal Contesto
La grammatica e’ ambigua
Il problema sono le stringhe che appartengono a tutti e due ilinguaggi
L1 ∩ L2 = {anbncndn : n ≥ 1}
queste stringhe hanno due alberi sintattici (o derivazionisinistre): una ottenuta da S applicando le regole dellagrammatica di L1, l’altra ottenuta da S applicando le regoledella grammatica di L2
Linguaggi Liberi dal Contesto
Esempio
I due alberi sintattici per la stringa aabbccdd
S
A B
a A b
a b
c B d
c d
(a)
S
C
a C d
a D d
b D c
b c
(b)
Linguaggi Liberi dal Contesto
In conclusione
puo’ essere provato che ogni grammatica per L si comportacome questa. Il linguaggio L e’ quindi inerentemente ambiguo
intuitivamente, le derivazioni di L1 ed L2 devono esserederivate da simboli non terminali differenti, produzionidifferenti
i due linguaggi devono infatti accoppiare i simboli in mododiverso
Linguaggi Liberi dal Contesto