![Page 1: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/1.jpg)
Linguaggi Liberi dal Contesto
Linguaggi Liberi dal Contesto
![Page 2: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/2.jpg)
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
![Page 3: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/3.jpg)
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
![Page 4: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/4.jpg)
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
![Page 5: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/5.jpg)
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
![Page 6: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/6.jpg)
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
![Page 7: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/7.jpg)
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
![Page 8: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/8.jpg)
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
![Page 9: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/9.jpg)
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
![Page 10: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/10.jpg)
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
![Page 11: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/11.jpg)
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
![Page 12: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/12.jpg)
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
![Page 13: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/13.jpg)
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
![Page 14: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/14.jpg)
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
![Page 15: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/15.jpg)
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
![Page 16: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/16.jpg)
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
![Page 17: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/17.jpg)
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
![Page 18: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/18.jpg)
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
![Page 19: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/19.jpg)
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
![Page 20: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/20.jpg)
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
![Page 21: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/21.jpg)
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
![Page 22: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/22.jpg)
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
![Page 23: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/23.jpg)
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
![Page 24: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/24.jpg)
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
![Page 25: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/25.jpg)
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
![Page 26: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/26.jpg)
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
![Page 27: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/27.jpg)
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
![Page 28: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/28.jpg)
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
![Page 29: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/29.jpg)
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
![Page 30: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/30.jpg)
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
![Page 31: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/31.jpg)
Albero sintattico per una sequenza di ∗
*
*
*
T
T F
T F
T
T F
F
.. .
Linguaggi Liberi dal Contesto
![Page 32: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/32.jpg)
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
![Page 33: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/33.jpg)
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
![Page 34: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/34.jpg)
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
![Page 35: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/35.jpg)
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
![Page 36: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/36.jpg)
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
![Page 37: Linguaggi Liberi dal Contesto - Dipartimento di Informaticapages.di.unipi.it/levi/publ/TDA7.pdf · Derivazione a sinistra Una derivazione di w = a ∗(a +b00) da E nella grammatica](https://reader034.vdocumenti.com/reader034/viewer/2022051604/5ffd4a0988e0e4584160ece1/html5/thumbnails/37.jpg)
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