Grammatiche libere dal contesto

Grammatiche libere dal contesto
G = < VN,VT,P,S >
VN - Insieme finito di simboli detti Non terminali
VT - Insieme finito di simboli detti Terminali
!
!!
V = VN ! VT, VN "#, VT "#,
VN $ VT =#
S-. Simbolo distinto o Assioma del Linguaggio
!!
S % VN
P - Insieme di Produzioni o Regole di Riscrittura
!
!!
P & VN x V*
Processo di generazione
La Grammatica G con produzioni
E
10
1. E ! E + T | E - T | T
2. T ! T * F | T / F | F
3. F ! ( E ) | i
E
Genera stringhe aritmetiche
!
Esempio: la stringa a + b * c è derivata da E
T
T
T
F
nel seguente modo:
E "E + T !!
"T +T ! !
" T + T * F!
"F+T*F!
" i +T * F!
" i + T * i!
" i +F * i!
" i +i * i!
pertanto:
E "* a + b*c
(regola 1)
(regola 1)
(regola 2)
(regola 2)
(regola 3)
(regola 3)
(regola 2)
(regola 3)
F
F
a
+
b
*
c
- E’ conveniente avere un ordine di applicazione delle regole?
- L’albero di generazione può essere costruito in modi diversi?
- E’ possibile costruire per la medesima stringa alberi di
!derivazione diversi?
Alberi di derivazione
E
E
1. E # E + T | E - T | T
2. T # T * F | T / F | F
3. F # ( E ) | i
T
T
T
F
F
F
a
+
Data una grammatica non contestuale G tutte le stringhe s da essa
generabili possono essere rappresentate tramite un albero aventi le seguenti proprietà:
b
*
c
1. La radice è etichettata con il simbolo iniziale S
2. Ogni nodo interno è etichettato con un simbolo non terminale ! VN
3. Ogni foglia è etichettata da un simbolo terminale o dalla stringa vuota "
4. Se il nodo K è etichettato con un simbolo non terminale A ed ha k figli etichettati con i simboli
!1 ,......., !k allora esiste una produzione della forma A # !1 ,......., !k
5. Se S $* w e w è una stringa di caratteri terminali allora w è rappresentata dalle foglie dell’albero.
Parentesi bilanciate
La Grammatica G11 genera stringhe di parentesi bilanciate
S ! " | SS | (S)
due possibili derivazioni sono:
S # SS # S (S) # (S) (S) # (S) ( ) # ( ) ( )
S # SS # ( S ) S # ( ) S # ( ) ( S ) # ( ) ( )
S
S
(
S
!
S
)
(
S
!
)
La Derivazione come classe di equivalenza
Data una grammatica G è possibile pervenire alla generazione di una stringa con processi di
generazione diverse. Date due generazioni D e D’:
D = x1 ! x2 ! ...... ! xn
D’ = x’ ! x’ ! ...... ! x’
1
2
n
se si verifica che :
1. " i ! k xi = x’i
2. xk-1 = x’ k-1 = u A v B w con u,v,w # V* e A, B # VN
3. xk = u y v B w, con A $ y # P
4. x’ k = u Av z w, con B$ z # P
5. xk+1 = x’ k+1= u y v z w
"
si dirà che D precede D’ e si scriverà
""
D prec D’
u y v B w !u y v z w . . . .
xk-1 = x’ k-1 = u A v B w
"
"
"
uAvzw!uyvzw....
Esempio
D1 = S ! SS ! (S) S ! ((S)) S ! (( )) S ! (( ))( S) ! (( )) ( )
D2 = S ! SS ! (S) S ! ((S)) S ! ((S )) (S) ! (( ))( S) ! (( )) ( )
!
Pertanto D1 prec D2
D2 = S ! SS ! (S) S ! ((S)) S ! ((S )) (S) ! (( ))( S) ! (( )) ( )
D3 = S ! SS ! (S) S ! ((S)) S! ((S )) (S)! (( S))( ) ! (( )) ( )
pertanto D2 prec D3
Esempio cont.
D
4
D
5
D
6
D
7
D
8
= S ! SS ! (S) S ! (S) S ! (S )( ) ! (( S))( ) ! (( )) ( )
= S ! SS ! S (S) ! (S) (S) ! ((S)) (S) ! (( ))( S) ! (( )) ( )
= S ! SS ! S (S) ! (S) (S) ! ((S)) (S) ! (( S))( ) ! (( )) ( )
= S ! SS ! S (S) ! (S) (S) ! (S )( ) ! ((S))( ) ! (( )) ( )
= S ! SS ! S (S) ! S ( ) ! (S )( ) ! ((S))( ) ! (( )) ( )
prec
D
1
prec D2
prec
D
3
prec
D
5
prec D6
leftmost derivation
prec
prec
D
4
D
prec
prec
D
8
7
rightmost derivation
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à
Nel caso di grammatica ambigua, se si generano due alberi sintattici diversi, si hanno due
alberi semantici diversi, che quindi inducono una semantica diversa per la parola
riconosciuta (nel nostro caso un’espressione)
Le fonti di ambiguità della Grammatica G dipendono dai seguenti motivi:
12
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 G è la seguente grammatica G
12
E !
T!
F !
id !
13
E+T | E- T | T
T *F | T/F | F
(E) | 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à
•
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 è ambiguo. I due alberi sintattici
inducono scelte semantiche diverse riguardo l’associazione dell’else con gli if. In Pascal
si stabilisce, con una regola esterna alla grammatica, che l’else si associa all’if più a destra.
Ancora sull’ambiguità
•
Grammatica non ambigua per lo stesso sottolinguaggio.
<statement> ::= <open-statement> | <closed-statement> | <simple-statement>
<open-statement> ::= if <exp> then <statement>
<open-statement> ::= if <exp> then <closed-statement> else <open-statement>
<closed-statement> ::= <simple-statement>
<closed-statement> ::= if <exp> then <closed-statement> else <closed-statement>
S
S
OS
CS
S
CS
?
CS
E
E
CS
CS
CS
SS
SS
E
E
S
SS
if a then if b then c else d
if a then if b then c else d
Ancora sull’ambiguità
• Si può trasformare una grammatica ambigua 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
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
Forme Normali
A partire da una grammatica Context-free G è sempre possibile costruire una grammatica
equivalente G’ ovvero L(G) = L(G’) che abbiano le produzioni in forme particolari, dette forme
normali.
Le forme normali vengono usate per dimostrare proprietà particolari dei linguaggi piuttosto che
per scopi applicativi.
Forma normale di Chomsky
E’ caratterizzata da regole di due tipi
A ! BC dove A, B, C " VN
A ! a con a " VT
Forma normale di Greibach
E’ caratterizzata da regole di un solo tipo
A ! a # con a " VT e # " VN*
Nel seguito faremo riferimento solo alla forma normale di Chomsky
Forma Normale di Chomsky
Prima di illustrare la trasformazione occorre effettuare una serie di passaggi preliminari per rendere
la grammatica adatta alla trasformazione stessa (forma ridotta). I passaggi effettuati saranno tutti
rivolti alla determinazione di grammatiche equivalenti rispetto a quella di partenza, con l’eventuale
esclusione del simbolo {!}.
1. A partire da G viene costruita una grammatica G1 di tipo 2 senza !-produzioni che genera L(G) -{!}
2. A partire dalla grammatica G1 si costruisce una grammatica G2 di tipo 2 senza !-produzioni e senza
produzioni unitarie.
3. A partire dalla grammatica G2 si costruisce una grammatica G3 di tipo 2 senza !-produzioni, senza
produzioni unitarie e senza simboli inutili.
4. La grammatica G4 equivalente alla grammatica di partenza G coincide con G3 se ! " L(G),
altrimenti G4 è ricavata da G3 introducendo un nuovo assioma ed un opportuno insieme di produzioni
su tale simbolo.
Forma Normale di Chomsky
1. Eliminazione delle !-produzioni
L’eliminazione delle !-produzioni viene fatta in due step. Nel primo step vengono individuate le variabili
(simboli non terminali) annullabili, nel secondo step si effettua l’eliminazione delle !-produzioni.
Una variabile (simbolo non terminale) si dice annullabile se questo può generare la stringa vuota.
Primo step
Es1.
S " ACA
A " aAa | B | C
B " bB | b
C " cC | !
Es2
S " AB
A " aAA | !
B " bBB | !
Si verifica immediatamente come il simbolo C sia un simbolo annullabile in
quanto genera direttamente !.
A partire da C si verifica come anche il simbolo A sia annullabile così come il
simbolo S. Pertanto i simboli annullabili sono S A C.
A partire da A e da B, che sono immediatamente annullabili si ricava l’annullabilità
di S. Pertanto i simboli annullabili sono S A B.
Forma Normale di Chomsky
Eliminazione delle !-produzioni (cont.)
A questo punto siamo in grado di effettuare l’eliminazione delle !-produzioni con un procedimento
algoritmico che ha l’obiettivo di definire la grammatica equivalente aggiungendo opportune produzioni
alla grammatica di partenza.
Per ogni produzione della grammatica G del tipo A " X1, X2, ...., Xk, supponiamo che m dei k simboli
siano annullabili, allora la grammatica risultante G1 avrà 2m versioni della produzione (con la sola
eccezione di quando m=k). Inoltre non verranno riportate le produzioni della forma A " !.
Es1. (simboli annullabili S A C)
S " ACA
A " aAa | B | C
B " bB | b
C " cC | !
S"
A"
B"
C"
ACA |AC | CA | AA |A |C | !
aAa | aa | B | C
bB | b
cC | c
Es2 (simboli annullabili S A B )
S " AB
A " aAA | !
B " bBB | !
S " AB | A | B
A " aAA | aA | a
B " bBB | bB | b
L’ !-produzione può comparire
direttamente sull’assioma a
condizione che questo con compaia
alla destra di qualche produzione
Forma Normale di Chomsky
Osservazioni sull’eliminazione delle !-produzioni
Oss. 1- La !-produzione presente in
S"
A"
B"
C"
ACA |AC | CA | AA |A |C | !
aAa | aa | B | C
bB | b
cC | c
non è significativa se non per la possibilità da parte della grammatica di generare anche la stringa vuota.
Infatti il linguaggio L(G) generato dalla grammatica G senza una tale !-produzione è perfettamente
equivalente a una grammatica G’ con tale !-produzione. Cioé L(G’) = L(G) # {!}.
Oss. 2 - E’ possibile aggiungere direttamente la !-produzione all’assioma del linguaggio come
nell’esempio prima visto. Ciò è possibile a condizione che l’assioma non compaia in una parte destra di
qualche produzione. Se questa eventualità si verifica è comunque possibile aggiungere la !-produzione
al costo dell’inserimento di un simbolo non terminale aggiuntivo, secondo il seguente criterio.
Criterio seguito
VN’ = VN # { S’}
P’ = P # { S’ " !} # { S’ " $ | S " $ % P}
Esempio
S " aSbA | ab
A " cAd | cd
S’ " aSbA | ab | !
S " aSbA | ab
A " cAd | cd