cerca
Traduttori - Lezione del 18 marzo 2009
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.Trad180309 History

Hide minor edits - Show changes to output

Added lines 96-131:

!!!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.
Added lines 83-95:
!!!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:)
Changed lines 22-23 from:
Tuttavia, non ci sbilanciamo a dire niente sulla '''complessità''' eventuale di questi algoritmo.
to:
Tuttavia, non ci sbilanciamo a dire niente sulla '''complessità''' eventuale di questi algoritmi.
Changed lines 30-31 from:
Ora li vedremo tutti.
to:
I primi che vedremo saranno le BNF e i grafi sintattici, rimandando a più tardi la descrizione degli automi.
Added lines 48-81:

!!!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
Added lines 1-51:
(:title Traduttori - Lezione del 18 marzo 2009:)
%titolo%''':: Traduttori - Lezione del 18 marzo 2009 ::'''

[[Torna alla pagina di Traduttori -> 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 algoritmo.

!!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

Ora li vedremo tutti.

!!!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.


----
[[Torna alla pagina di Traduttori -> Traduttori]]