Corso di Automi e Linguaggi Formali
Linguaggi liberi dal contesto
Limitazioni dei linguaggi regolari
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!
Pero’ e’ quello che fa un compilatore
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
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
Da espressioni regolari a grammatiche
Posso usare le espressioni regolari per generare tutte le stringhe del linguaggio
Esempio: genera e poi una stringa di
Regole corrispondenti:
Per la stringa :
Grammatiche libere da contesto
Insieme di regole: grammatica
Grammatica libera da contesto: per applicare una regola non devo guardare cosa
c’e’ intorno ad
Esempio: la posso applicare sia alla stringa che a
La regola la posso applicare solo alla prima stringa:
Solo un simbolo a sinistra della freccia
Grammatiche libere da contesto
Quadrupla
alfabeto (terminali)
insieme (non-terminali)
insieme di regole:
simbolo iniziale Regola: coppia
, con e stringa su (scriveremo ) Parte sinistra: sempre un non-terminale Parte destra: terminali e/o non-terminali (forma sentenziale)
Derivazioni
Da posso derivare in un passo ( ) se
e
e
in
Da posso derivare ( ) se esistono
tale che:
e
Derivazione: sequenza di passi
Non-determinismo
Piu’ regole con la stessa parte sinistra:
e
Piu’ nonterminali in una forma sentenziale:
derivazione: processo non deterministico Linguaggio generato da una grammatica :
Tutte le stringhe di terminali derivabili da Linguaggio libero da contesto se e’ libera da contesto
Esempio
Esempio di derivazione:
Libero da contesto e non regolare
Esempio
Esempio di derivazione:
Libero da contesto e regolare
Tutti i linguaggi regolari sono anche liberi da contesto
Esempio
Esempio di derivazione:
Libero da contesto e non regolare
Esempio: espressioni algebriche
Molti linguaggi di programmazione le
contengono; il compilatore deve controllare che siano corrette
, qualsiasi numero
, :
,
,
,
,
,
,
Anche comandi
Aggiungo le regole
Posso derivare il comando
Aggiungo
while do
Posso derivare il comando
Esercizio
Dare una derivazione per la stringa Qual e’ il linguaggio generato?
Esercizio
Dare una derivazione per la stringa Qual e’ il linguaggio generato?
Esercizio
Dare una derivazione per la stringa Qual e’ il linguaggio generato?
Esercizio
Dare una derivazione per la stringa Qual e’ il linguaggio generato?
Esercizio
Costruire grammatiche libere da contesto per i seguenti linguaggi:
Il linguaggio degli identificatori
rappresentati dalla espressione regolare
Parsing
Ogni stringa puo’ essere generata da piu’
derivazioni
Esempio: ,
,
Albero di parsing:
S B
a e
A A
Albero di parsing
Radice = simbolo iniziale, nodo interno = nonterminale, foglia = terminale
Relazione padre - figli : regola
Stringa derivata: concatenazione delle foglie Un albero rappresenta un insieme di
derivazioni: uguali tranne l’ordine di espansione di un nonterminale
Per ogni nonterminale, si dice quale regola usare, ma non quando
Derivazioni canoniche
Derivazione piu’ a sinistra: rimpiazzo sempre il nonterminale piu’ a sinistra
Derivazione piu’ a destra: rimpiazzo sempre il nonterminale piu’ a destra
Tutte le derivazioni rappresentate dallo stesso albero di parsing sono equilaventi
