Grammatiche libere da contesto

Grammatiche
Regole per specificare frasi corrette in italiano
Una frase e’ un soggetto, seguito da un
verbo, seguito da un complemento oggetto
Un soggetto e’ un nome, o un articolo
seguito da un nome
Corso di Automi e Linguaggi
Formali
Parte 4 – Linguaggi liberi dal contesto
Uso delle regole: per generare frasi corrette
Esempio: F
S V CO
A N V CO
(A=
un) (N=cane) (V=mangia) (CO= un osso)
un cane mangia un osso
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.3/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.1/31
Posso usare le espressioni regolari per
generare tutte le stringhe del linguaggio
Molti linguaggi non sono regolari
Esempio:
E il linguaggio naturale? E i linguaggi di
programmazione? Puo’ un automa a stati
finiti riconoscere programmi validi da
programmi non validi? NO!
Regole corrispondenti:
genera e poi una stringa di
Esempio:
Limitazioni dei linguaggi regolari
Da espressioni regolari a grammatiche
:
Per la stringa
Pero’ e’ quello che fa un compilatore
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.4/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.2/31
Derivazioni
) se
(
Insieme di regole: grammatica
Grammatica libera da contesto: per applicare
una regola
non devo guardare cosa
c’e’ intorno ad
la posso applicare sia alla
che a
la posso applicare solo
La regola
alla prima stringa:
Esempio:
stringa
) se esistono
posso derivare (
tale che:
e
Da
posso derivare in un passo
e
e
in
Da
Grammatiche libere da contesto
Solo un simbolo a sinistra della freccia
Derivazione: sequenza di passi
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.7/31
Non-determinismo
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.5/31
Grammatiche libere da contesto
e
)
, con
(scriveremo
Regola: coppia
stringa su
:
Linguaggio generato da una grammatica
derivazione: processo non deterministico
Quadrupla
alfabeto (terminali)
insieme (non-terminali)
insieme di regole:
simbolo iniziale
Piu’ nonterminali in una forma sentenziale:
Piu’ regole con la stessa parte sinistra:
e
Parte sinistra: sempre un non-terminale
Linguaggio libero da contesto se
da contesto
Parte destra: terminali e/o non-terminali
(forma sentenziale)
Tutte le stringhe di terminali derivabili da
e’ libera
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.8/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.6/31
Esempio
Esempio
Esempio di derivazione:
Esempio di derivazione:
Libero da contesto e non regolare
Libero da contesto e non regolare
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.11/31
Tutti i linguaggi regolari sono anche liberi da
contesto
Libero da contesto e regolare
,
,
,
,
qualsiasi numero
:
,
,
,
Esempio di derivazione:
,
Molti linguaggi di programmazione le
contengono; il compilatore deve controllare
che siano corrette
Esempio
Esempio: espressioni algebriche
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.9/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.12/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.10/31
Anche comandi
Aggiungo le regole
Dare una derivazione per la stringa
Posso derivare il comando
Esercizio
do
while
Aggiungo
Qual e’ il linguaggio generato?
Posso derivare il comando
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.15/31
Esercizio
Dare una derivazione per la stringa
Qual e’ il linguaggio generato?
Dare una derivazione per la stringa
Esercizio
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.13/31
Qual e’ il linguaggio generato?
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.16/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.14/31
,
Dare una derivazione per la stringa
,
Esempio:
Ogni stringa puo’ essere generata da piu’
derivazioni
Esercizio
Parsing
Qual e’ il linguaggio generato?
S
A
a
B
A
e
e
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.19/31
Esercizio
Un albero rappresenta un insieme di
derivazioni: uguali tranne l’ordine di
espansione di un nonterminale
Il linguaggio degli identificatori
rappresentati dalla espressione regolare
Stringa derivata: concatenazione delle foglie
: regola
- figli
Relazione padre
Costruire grammatiche libere da contesto per
i seguenti linguaggi:
Radice = simbolo iniziale, nodo interno =
nonterminale, foglia = terminale
Albero di parsing
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.17/31
Albero di parsing:
Per ogni nonterminale, si dice quale regola
usare, ma non quando
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.20/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.18/31
Ambiguita’ e parsing
Derivazioni canoniche
Un compilatore cerca di costruire un albero di
parsing per ogni pezzo (es.: comando) di un
programma
Se la grammatica e’ ambigua, piu’ alberi di
parsing, cioe’ piu’ significati per il comando
Derivazione piu’ a destra: rimpiazzo sempre il
nonterminale piu’ a destra
Tutte le derivazioni rappresentate dallo stesso
albero di parsing sono equilaventi
Es. (dangling else): if x=y then if z>v then C1
else C2
Derivazione piu’ a sinistra: rimpiazzo sempre
il nonterminale piu’ a sinistra
else
then
Il ramo else puo’ essere associato al primo if
(uso la seconda regola per prima) o al
secondo if (uso la prima regola per prima)
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.23/31
Ambiguita’
Grammatiche ambigue
Altra sorgente di nondeterminismo: quale
regola usare per rimpiazzare un certo
nonterminale
S
A
A
a
A
a
a
A
e
B
A
a
e
,
e
,
Derivazioni:
S
Esempio:
Diversi alberi di parsing per la stessa stringa
,
,
E’ volte e’ possibile rimuovere l’ambiguita’:
ottengo una grammatica equivalente non
ambigua
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.21/31
if
then
if
Grammatica ambigua: se per una stringa del
linguaggio ci sono diverse derivazioni piu’ a
sinistra
A
e
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.24/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.22/31
puo’ essere visto come
Da automi a stati finiti a grammatiche libere
da contesto
Ma esistono linguaggi non regolari
nessun
automa a stati finiti ma grammatiche libere da
contesto
Automi:
una regola
L’automa non puo’ usare la pila per ricordare
e poi confrontarla con
, perche’ non sa
dov’e’ la meta’ della stringa di input
deve
fare vari tentativi
Automi e grammatiche
Nondeterminismo
Esistono automi piu’ potenti di quelli a stati
finiti, che possono accettare linguaggi liberi
da contesto?
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.27/31
Sestupla
insieme finito di stati
alfabeto di input
insieme di simboli per la pila
simbolo iniziale
relazione di transizione:
Esempio
Automi a pila
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.25/31
Un automa che possa accettare le stringhe di
ha bisogno di una pila, dove mettere tutte le
e poi toglierle quando legge le
Se alla fine la pila e’ vuota, la stringa e’
accettata
Combinazione di pila a automa a stati finiti
insieme di stati finali
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.28/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.26/31
Nastro read-only contenente la stringa in
input
Nastro piu’ pila
Pila e testina che leegge il top della pila
Transizione
: dallo stato ,
se legge il simbolo sul nastro e la parola
sulla pila, passa allo stato , rimpiazzando
con sulla pila (pop di e push di ), e
spostandosi di un posto verso destra sul
nastro
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.31/31
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.29/31
Configurazioni
Piu’ transizioni con la tripla
: non legge niente sul nastro
Anche
,
se
arrivo a
a
tale che
Accetta se da
stato finale
Dalla configurazione
transizione
e
per
e top della pila =
: legge
Configurazione: stato + stringa gia’ letta + pila
Se non e’ in , si arriva allo stato finale ma
), oppure si arriva
la pila non e’ vuota (
con la pila vuota ma non si riesce a leggere
o
)
tutta la stringa (
Testina che si sposta da sinistra a destra e
legge un simbolo alla volta
con
,
,
,
,
Automa per
Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.30/31