Ambiguità
S
S
S
D11 = SS ( S S S ( S (S ) S ( S ((S )) S (
S
+
S (( )) S (S (( )) (S) (S (( )) ( ) ( (( )) ( )
(
S
!
Una Grammatica si dice ambigua se medesime stringhe
sono generate da alberi sintattici di differente struttura
ovvero
con due distinte derivazioni left most
(
S
(
S
S
)
!
)
)
!
albero alternativo
ovvero
con due distinte derivazioni right most
Per cui si può concludere che la grammatica G11 è
una grammatica ambigua
S
S
S
(
S
)
(
S
)
!
(
S
!
)
Esempio di Grammatica Ambigua
La Grammatica G12 con produzioni
!!
!!
E ' E+E | E- E | E *E | E/E | id
id ' a | b | c!
è una grammatica ambigua
E
E
E
+
E
E
E
*
E
E
+
I
I
a
*
E
I
I
b
c
E
I
I
a
b
c
Alberi semantici e notazioni polacche
un Albero semantico è un albero in cui i nodi interni rappresentano operazioni da effettuarsi sui suoi
sottoalberi, mentre i nodi foglia rappresentano operandi
Esempio di costruzione
E
E
E
+
E
E
E
a
*
+
E
+
b *
*
c
a
I
a
I
I
b
c
Primo passo - togliere tutti i simboli intermedi aventi un unico discendente
Secondo passo - Sostituire ad ogni simbolo non terminale l’operatore corrispondente
b
c
Alberi semantici e notazioni polacche
Esempio di costruzione
E
E
E
E
*
E
+
I
E
*
+
E
c
a + b *
I
a
b
c
I
b
a
c
Questo albero è stato costruito a partire dalla seconda versione dell’albero
sintattico visto in precedenza. Il procedimento è corretto, ma il risultato è,
come deve essere diverso in virtù dell’ambiguità della grammatica.
Data un’espressione costruita a partire da una grammatica non ambigua è possibile costruire l’albero
semantico direttamente tramite opportuni algoritmi. Un tale albero è ovviamente unico.
sqrt
!
a*b
c+d
/
+
*
a
b
c
d
Alberi semantici e notazioni polacche
Attraversando in modo opportuno un albero semantico si può avere una sequenzializzazione delle operazioni
scandendo la stringa da sinistra verso destra e collocando gli elementi dentro uno stack.
+
*
a
b
notazione polacca postfissa o inversa - RPN (Reverse Polish Notation)
(visita dell’albero in ordine posticipato, o postordine)
+ a *b c
notazione polacca prefissa
(visita dell’albero in ordine anticipato, o preordine)
c
*
ab+* c
+
a
abc*+
*+abc
[Se si è a conoscenza dell’arietà delle operazioni coinvolte la
notazione polacca ha la caratteristica di rappresentare
un’espressione in forma linearizzata senza parentesi.]
c
b
sqrt
a b*c d + / sqrt
/
*
a
sqrt / * a b + c d
+
b
c
d
Si leggono i simboli della stringa memorizzando gli operandi nello stack, appena si trova un simbolo di
operazione la si effettua e si pone nello stack il risultato.
Togliere l’ambiguità
Le fonti di ambiguità della Grammatica G12 dipendono dai seguenti motivi:
1. Non viene rispettata la precedenza degli operatori
2. Una sequenza di operatori identici si può raggruppare sia da sinistra che da destra
Una versione non ambigua della grammatica G12 è la seguente grammatica G13
E ! E+T | E- T | T
T ! T *F | T/F | F
F ! (E) | id
id ! a | b | c |.....
• Un fattore F, rappresenta un’espressione che non si può scomporre rispetto ad un operatore
adiacente. Un identificatore o un’espressione parentesizzata è un fattore.
• Un termine T, rappresenta un’espressione che non si può scomporre rispetto ad un operatore
additivo (+, -) adiacente. In sostanza un termine è un prodotto (divisione) di più fattori
• Un’ espressione è una qualsiasi composizione di termini tramite operatori additivi (+,-).
Ancora sull’ambiguità
• Una grammatica ambigua si può trasformarla in una non ambigua equivalente? Non sempre…
• Ci sono linguaggi context-free con la proprietà che ogni grammatica che li genera è ambigua, tali
linguaggi sono detti inerentemente ambigui
Esempi di linguaggi inerentemente ambigui
{an bn cm dm : n ! 1, m !1} ! {an bm cm dn : n ! 1, m !1 }
{ai bi c*
: i ! 0} ! {a* bi ci : i !0 }
• Per molti linguaggi di utilizzo pratico è sempre possibile trovare la grammatica non ambigua
equivalente
Ancora sull’ambiguità
•
Consideriamo il seguente frammento della grammatica del Pascal, scritta secondo la
Backus-Naur Form (BNF)
<statement> ::= … | <if-statement> | …
<if-statement> ::= if <exp> then <statement> [else <statement>]
La frase if a then if b then c else d viene derivata mediante due alberi sintattici
E
S
S
IS
IS
E
S
S
IS
IS
S
S
if a then if b then c else d
E
E
S
S
if a then if b then c else d
Questo sottolinguaggio del Pascal è inerentemente ambiguo. I due alberi sintattici
inducono scelte semantiche diverse riguardo l’associazioe dell’else con gli if. In Pascal
si stabilisce, con una regola esterna alla gramamtica, che l’else si associa all’if più a destra.
Data la grammatica
E
Sostituzioni in Alberi di derivazione
E
1. E ! E + T | E - T | T
2. T ! T * F | T / F | F
3. F ! ( E ) | i
T
T
abbiamo visto in che modo sia possibile costruire l’albero
di derivazione per la stringa a + b*c
T
F
F
F
a
Si osservi come all’interno di un percorso possiamo trovarci in presenza
dello stesso simbolo di variabile, radice di un sottoalbero.
E’ sempre possibile sostituire il sottoalbero di una variabile con un’altro
sottoalbero sempre riferito alla stessa variabile. Quello che si produce è ancora un
albero di derivazione di una stringa legale del linguaggio.
E
E
T
T
F
F
a
F
T
T
+ b
F
* c *
c
+
b
Questa proprietà è tipica per le derivazioni dei linguaggi Contex
Free. Infatti ogni simbolo non terminale si può sviluppare in
modo indipendente dal contesto in cui si trova
*
c
Sostituzioni in Alberi di derivazione
Esempio
La grammatica
S ! 0B | 1A
A ! 0 | 0S | 1AA
B ! 1 | 1S | 0BB
Genera tutte e sole le stringhe che hanno un ugual numero di 0 e di 1
Una possibile derivazione per la stringa 0011 è:
S # 0B #00BB # 001B # 0011
Un’altra possibile derivazione è:
S # 0B #00BB # 00B1 # 0011
0
0
B
0
S
S
S
B
B
1
1
0
B
0
(Si sta parlando di una grammatica ambigua?)
B
B
1
1
Possiamo ripetere il procedimento indefinitamente
ottenendo parole del linguaggio via via crescente
B
0
0
B
B
B
1
B
B
E’ una caratteristica dei linguaggi Contex-free, che
discende dalla proprietà di sostituzione il fatto che
la crescita avvenga in maniera costante.
Ad esempio se una grammatica genera parole la
cui lunghezza cresce in modo esponenziale allora
il linguaggio non è libero dal contesto.
1 1
Quindi:
S # 0B #00BB # 00B1 # 000BB1 # 000B11 # 000111