:: Traduttori - Lezione del 18 marzo 2009 ::
Torna alla pagina di Traduttori
Qualità delle grammatiche
Ci sono altre cosucce da dire, relativamente alle grammatiche.
Una grammatica è detta ridotta quando rispetta queste proprietà:
- non esistono regole di produzione della forma A ->+A, cioè che portano da un NT ad un altro NT in uno o più passaggi (in zero passaggi è ovvio invece che A rimanga A)
- ogni NT deve produrre un linguaggio non vuoto
- ogni NT deve poter essere raggiunto da S
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:
- controllare se un NT conduce ad un linguaggio vuoto
- elminiare le ε-produzioni
- controllare se un NT è presente in una frase
- eliminare le circolarità
- controllare se un NT genera ε
Tuttavia, non ci sbilanciamo a dire niente sulla complessità eventuale di questi algoritmi.
Descrizione formale di un L
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:
- BNF
- grafi sintattici
- automi e riconoscitori
I primi che vedremo saranno le BNF e i grafi sintattici, rimandando a più tardi la descrizione degli automi.
BNF
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:
- gli NT sono racchiusi tra parentesi angolari: <..>
- i T sono spesso sottolineati, quando si scrivono le produzioni
- le produzioni sono scritte così: A ::= a
- nella parte sinistra delle produzioni può comparire solo un NT (perché si tratta di grammatiche libere dal contesto)
- le alternative nella stessa produzione vengono divise dalla pipe: A ::= a | b | c
La EBNF, cioè la Extended BNF, introduce alcune regole aggiuntive per dare più espressività:
- le parti opzionali vengono racchiuse tra parentesi quadre: A ::= a[<altro>] significa che A può produrre a ed eventualmente anche <altro>
- le parti alternative vengono segnate anche in questo modo: C ::= <A> (+ | -) <B>
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.
Grafi sintattici
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...
Linguaggi regolari
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ì:
- A -> aB oppure A -> Ba
- A -> a
Le espressioni regolari sono un modo per specificare linguaggi regolari.
Espressioni 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:
- ε e l'insieme vuoto sono espressioni regolari: L(ε) = {ε}, L(0) = 0 (uso 0 per indicare l'insieme vuoto)
- se a appartiene a Σ, allora a è una regexp: L(a) = {a}
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:
- se r è una regexp, allora (r) è una regexp: L((r)) = L(r). Chiamiamola pure regola di eliminazione delle parentesi:)
- se r e t sono regexp, allora r + t è una regexp così definita: L(r + t) = L(r) U L(t). Il simbolo + rappresenta quindi l'alternativa.
- se r e t sono regexp, allora r•t è una regexp: L(r•t) = L(rt) = L(r) • L(t). Il simbolo • è quindi la concatenazione.
- se r è una regexp, allora r* è una regexp: L(r*) = (L(r))*.
Facciamola breve:
- la * è la solita *: zero o più occorrenze
- + è l'alternativa
- • è la concatenazione, e può anche essere omesso
Precedenza degli operatori
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?
- 0 sì
- 0111 sì
- 100 sì
- 00 no. Perché? Eh beh leggetela bene e capirete, più facile che nemmeno spiegarlo:)
Esercizio
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.
Proprietà di chiusura dei linguaggi regolari
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:
- unione
- concatenazione
- *-chiusura
- intersezione
- complemento
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.
Torna alla pagina di Traduttori
