:: Traduttori - Lezione del 18 marzo 2009 ::
Torna alla pagina di Traduttori
Ci sono altre cosucce da dire, relativamente alle grammatiche.
Una grammatica è detta ridotta quando rispetta queste proprietà:
Le regole della forma A -> ε sono dette ε-produzioni, e vedremo in seguito che la loro presenza complica un po' l'analisi di una grammatica. Vedremo quindi di trovare un modo per costruire una G senza ε-produzioni, esclusa però un'eventuale S -> ε.
Molti controlli sulle grammatiche possono essere eseguiti con degli algoritmi. Ad esempio:
Tuttavia, non ci sbilanciamo a dire niente sulla complessità eventuale di questi algoritmi.
Ora che abbiamo fatto un po' di lezioni, siamo arrivati al punto di definire in modo formale che cos'è un linguaggio. Qua e là c'erano degli indizi che ci dicevano quali sarebbero stati gli strumenti per questo lavoro. Li riassumiamo qui:
I primi che vedremo saranno le BNF e i grafi sintattici, rimandando a più tardi la descrizione degli automi.
BNF sta per Backus-Naur Form, dove Backus e Naur sono quelli che l'hanno inventata nel 1959 per descrivere il linguaggio ALGOL.
Può descrivere grammatiche libere dal contesto, e la possiamo intendere come un metalinguaggio, perché si tratta di un linguaggio che si usa per descrivere altri linguaggi.
Eccone le caratteristiche:
La EBNF, cioè la Extended BNF, introduce alcune regole aggiuntive per dare più espressività:
Ma le BNF hanno anche dei limiti. Pensiamo a questo esempio: in Pascal, ogni variabile deve essere dichiarata prima dell'uso. Questo tipo di regola non può essere espressa in nessun modo tramite una BNF, e il motivo è che la BNF non ha memoria.
I grafi sintattici sono dei grafi in cui le regole di produzione vengono rappresentate con dei grafi orientati, in cui gli NT sono rappresentati da quadri, e i T da quadri con gli angoli arrotondati.
Possono essere usati sia per generare linguaggi, che per riconoscerne altri. Non ci soffermiamo molto su questi perché non vanno molto di moda...
I linguaggi regolari sono i linguaggi definiti su Σ, cioè sottinsiemi di Σ*, generati da grammatiche regolari.
Per ripassare, le grammatiche regolari sono quelle che hanno produzioni fatte così:
Le espressioni regolari sono un modo per specificare linguaggi regolari.
La prima cosa da fare è dare la definizione di espressione regolare. La via che scegliamo è quella della definizione induttiva.
Come base dell'induzione, diciamo che:
Bisogna stare attenti ad una cosa: in L(a) = {a} la a di L(a) è una espressione regolare, mentre la a di {a} è un simbolo di Σ.
I passi induttivi sono invece i seguenti:
Facciamola breve:
La precedenza tra i vari operatori la capiamo meglio con un esempio. Prendiamo la seguente regexp:
01* + 10*
Potremmo riscriverla così:
(0(1)*) + (1(0)*)
e capiamo che le * hanno efficacia sul simbolo che le precede, la concatenazione segue subito dopo, e il + ha meno precedenza di tutti. Ricordo che il fatto di scrivere due simboli vicini è già una concatenazione.
Già che ci siamo, che stringhe vengono generate da questa regexp?
Vediamo ora un esercizio di quelli che si possono presentare all'esame.
Ho un L così definito:
L = { w appartenentia {0,1}*: 0 e 1 alternati in w}
È quindi il linguaggio composto dalle stringhe in cui lo 0 e l'1 si alternano. Esempi di stringhe buone sono 010101, 1010101.
La domanda è: qual'è la regexp che descrive questo linguaggio? Un modo semplice (anche se incompleto) è quello di prendere i due diversi tipi di stringa generati e metterli in un'alternativa. Dal momento che (10)* produce tutte le stringhe 101010... e (01)* produce invece le 0101..., posso pensare di avere una regexp così fatta:
(10)* + (01)*
Il problema è che questa regexp produce solo stringhe di lunghezza pari, ed esclude quelle del tipo 101, oppure 0101010.
Una bella soluzione è la seguente:
(ε + 1)(01)*(ε + 0)
che tiene conto di tutti i casi possibili. Infatti, da essa si possono generare tutte le seguenti stringhe:
01 010 101 101010 01010 ...
Infatti, il pattern che si ripete, nella descrizione del mio linguaggio, è 01. Può essere preceduto da un 1, e può essere seguito da uno 0.
Data una classe di linguaggi ed un'operazione definita sui suoi linguaggi, questa operazione è detta chiusa se il suo risultato appartiene ancora alla classe.
Nella classe dei linguaggi regolari, operazioni chiuse sono:
Vediamo ora un'importante conseguenza di questa faccenda. Se ci mettiamo nei panni del compilatore, allora possiamo assumere che, se le singole stringhe sono appartenenti al linguaggio, allora anche la concatenazione di queste stringhe apparterrà al linguaggio, proprio perché l'operazione di concatenazione è chiusa.