|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.Trad120309 History
Hide minor edits - Show changes to output
Changed line 80 from:
* β appartiene a (NT U T)'^*^' to:
* β ∈ (NT U T)'^*^'
Changed line 11 from:
* A -> α ∈ a P to:
Changed line 11 from:
* A -> α appartenente a P to:
* A -> α ∈ a P
Changed line 73 from:
Perché si parla di '''libertà dal contesto'''? Il contesto è rappresentato da γ e δ, le quali "circondano" A e determinano se è possibile sostituirla con α. to:
Perché si parla di '''dipendenza dal contesto'''? Il contesto è rappresentato da γ e δ, le quali "circondano" A e determinano se è possibile sostituirla con α.
Changed line 32 from:
to:
Changed lines 147-155 from:
S
/ | \
/ | \
/ | \
<nome> <verbo> <oggetto>
| | |
Dario mangia Patrizia
to:
[@
S
/ | \
/ | \
/ | \
/ | \
<nome> <verbo> <oggetto>
| | |
Dario mangia Patrizia
@]
Changed lines 136-137 from:
Ma facciamo un esempio, tanto per scurirci: to:
Ma facciamo un esempio, tanto per scurirci.
Prendiamo una bella grammatica, in cui i non terminali sono messi tra parentesi angolari (come è costume nelle grammatiche BNF che affronteremo in seguito). Scrivo qui le regole di produzione, e il resto lo inferite da soli:
S = <nome> <verbo> <oggetto>
<nome> = Dario | Patty | Denisoglu
<verbo> = mangia | sacrifica | assale
<oggetto> Patty | Patrizia | Patrizioglu
Una frase generata da questa grammatica può essere: "Dario mangia Patrizia", oppure "Patty assale Patty", oppure "Denisoglu sacrifica Patty". Comunque vada, Patrizia ne fa le spese.
La derivazione che porta a "Dario mangia Patrizia" può essere inalberata in questo modo:
S
/ | \
/ | \
/ | \
<nome> <verbo> <oggetto>
| | |
Dario mangia Patrizia
La frontiera è composta da Dario, mangia e Patrizia, e quindi la frase finita è "Dario mangia Patrizia". La si legge da sinistra verso destra, e non al contrario, e quindi leggere "Patrizia mangia Dario" è sbagliato, oltre che concettualmente oltraggioso.
Un compilatore (lo scopo della mia vita è scrivere un compilatore di linguaggi pruprurrosi e denisoglui!) prenderà una stringa, ne genererà il parse tree e, secondo oscure tecniche ancora ignote, stabilirà se i frutti di questo albero saranno buoni o no.
Come dicevamo sopra, se c'è più di un parse tree per stringa, allora siamo in presenza di ambiguità. Ci sono però delle regole per disambiguare in modo automatico, oppure semplicemente il compilatore prende l'iniziativa e stabilisce lui come risolvere l'ambiguità. Immaginate poi la dannazione di chi scrive programmi e non sa che cosa sta succedendo.
Added lines 107-136:
!!!Ricorsione
La ricorsione è un particolare tipo di derivazione. Se è ''ricorsione a sinistra'', ha questa forma:
A ->'^+^' Aβ
Se è ''ricorsione a destra'', sarà invece
A ->'^+^' βA
C'è anche la ''ricorsione interna'', oppure ''autoinclusiva'':
A ->'^+^' αAβ
Ricordo che la scrittura ->'^+^' significa che derivo in almeno un passaggio.
Le derivazioni ricorsive portano a linguaggi infiniti.
!!!Grammatica ambigua
Una grammatica è '''ambigua''' se esiste nel linguaggio da essa generato una stringa generabile con due derivazioni canoniche dello stesso tipo ma distinte, ovvero, generabile con due diverse derivazioni canoniche sinistre oppure due diverse derivazioni canoniche destre.\\
Ecco a che cosa serviva la definizione di derivazione canonica:)
Un linguaggio è detto '''non ambiguo''' se esiste '''almeno''' una grammatica non ambigua che lo genera.\\
Presupposto di questa frase è che un L possa essere generato da G diverse: è infatti vero.\\
Se invece tutte le G che generano questo L sono ambigue, allora L è purtroppo intrinsecamente ambiguo.
!!!Parse tree
Il '''parse tree''' è una rappresentazione grafica e gerarchica della derivazione. Ocio: della ''derivazione'', e non di una grammatica! Ogni singola derivazione ha il suo parse tree, e se questo è uguale a quello di un'altra derivazione della stessa canonicità, allora la grammatica è ambigua.
Il parse tree è un albero. La sua radice (in cima) è S, ovvero l'assioma della grammatica (la prima regola da cui si parte sempre per produrre). Tutti i nodi che non sono foglie sono simboli non terminali. Le foglie invece sono o simboli terminali, o la stringa vuota ε. Un singolo sottoalbero descrive una '''produzione'''.
L'insieme delle foglie è detto '''frontiera''' del parse tree. La frontiera viene letta da sinistra a destra, e quello che esce sarebbe la stringa derivata.
Ma facciamo un esempio, tanto per scurirci:
Changed line 54 from:
to:
Changed line 57 from:
to:
Changed lines 75-107 from:
to:
!!!Grammatiche di tipo 2
Questo sono dette '''grammatiche libere dal contesto''':
A -> β
dove:
* A è un simbolo non terminale
* β appartiene a (NT U T)'^*^'
Ciò che circonda A non ha nessuna importanza per la sua trasformazione in β.
!!!Grammatiche di tipo 3
Sono le '''grammatiche regolari''', e i linguaggi che generano sono detti '''linguaggi regolari'''.
Le possiamo distinguere in due tipi, a seconda che il simbolo terminale sia a destra o a sinistra di B:
1) A -> aB
A -> a
2) A -> Ba
A -> a
''a'' appartiene a (NT U T)'^*^', quindi può essere un non terminale oppure un terminale, o anche il nulla. B invece deve essere un non terminale.\\
Le prime sono ''lineari a sinistra'', le seconde ''lineari a destra''.
Attenzione però: una grammatica regolare o è lineare destra, oppure è lineare sinistra. Non può essere entrambe le cose, se no diventa una grammatica di tipo 2, cioè libera dal contesto.
!!!Proprietà delle grammatiche
A seconda di quale grammatica lo genera, un linguaggio si classifica come L'_3_', L'_2_', L'_1_' ed L'_0_'.
Le grammatiche di tipo 2 e 3 sono quelle utilizzate per definire i linguaggi di programmazione, perché si prestano alla loro implementazione algoritmica.
Le grammatiche sono in relazione tra di loro: quelle di tipo 3 sono incluse in quelle di tipo 2, a loro volta incluse in quelle di tipo 1, a loro volta incluse in quelle di tipo 0.
Ci sono però dei linguaggi che '''non''' sono generabili da una grammatica: esiste quindi un "soprainsieme" che comprende G'^0^'.
Inoltre, ci sono linguaggi di una classe L'_i_' che non possono essere generati da una grammtica G'_i+1_'. Questo è anche abbastanza logico, visto che nelle definizioni qui sopra si è visto che man mano che il tipo "aumenta", aumentano anche le restrizioni poste alle regole di produzione.
Added lines 71-75:
Questo significa che la stringa derivata non può mai essere più piccola della stringa iniziale, proprio perché α non è mai vuota.
Perché si parla di '''libertà dal contesto'''? Il contesto è rappresentato da γ e δ, le quali "circondano" A e determinano se è possibile sostituirla con α.
''...continua...''
Added lines 1-73:
(:title Traduttori - Lezione del 5 marzo 2009:)
%titolo%''':: Traduttori - Lezione del 5 marzo 2009 ::'''
[[Torna alla pagina di Traduttori -> Traduttori]]
!!!Definizione formale di derivazione
Una derivazione si scrive così, in termini formali: ν -> γ, dove la prima lettera ν è la ''ni'' dell'alfabeto greco.\\
Quindi, da ν si deriva γ per la grammatica G sse:
* ν = σAτ
* γ = σατ
* A -> α appartenente a P
Spieghiamo bene queste cose:
* Le prime due regole mi dicono come sono fatte le stringhe ν e γ
* σ e τ possono essere simboli terminali o no, e possono anche essere eventualmente vuote
* A è un simbolo non terminale
* α può essere un simbolo terminale o no
In pratica, queste regole mi stanno dicendo che posso andare da ν a γ se esiste una regola che trasforma una qualche parte di ν in modo tale che la renda uguale a γ. Dal punto di vista teorico, niente di nuovo, però è così che si scrive formalmente.
Una derivazione si dice '''diretta''' se basta una sola produzione per andare da ν a γ.\\
Una derivazione è invece '''indiretta''' se c'è bisogno di una serie di stringhe intermedie, e delle condizioni così fatte:
* ν = w'_0_'
* γ = w'_n_'
* per ogni i da 0 a n, w'_i_' -> w'_i+1_'
Questo vuol dire che da ν si deriva γ se esiste una sequenza di stringhe frutto di successive derivazioni consecutive, che partono proprio da ν e arrivano a γ.\\
La derivazione indiretta si scrive '''ν ->* γ''' (l'asterisco dovrebbe essere sopra il ->).
!!!Derivazioni canoniche
Supponiamo di avere una stringa che voglio derivare:
aAbcBaA
Le lettere maiuscole A e B sono simboli non terminali, che quindi andranno sostituiti. In generale si sottolinea il simbolo non terminale che vado a derivare. In questo caso, se scelgo di derivare la prima A, scriverei
a(+A+)bcBaA -> adbcBaA
(notate che mi sono anche inventato la produzione A -> db)
La '''derivazione canonica sinistra''' è una derivazione in cui scelgo di sviluppare sempre il non terminale più a sinistra nella mia stringa.
Nella '''derivazione canonica sinistra''' invece sviluppo sempre per primo il non terminale più a destra.
Fra un po' vedremo a che cosa serve questa distinzione apparentemente inutile.
!!!Definizione formale di linguaggio
Data una grammatica G = (NT, T, S, P), il linguaggio generato da G lo si può segnare così: '''L'_g_'''', oppure così: '''L(G)'''.
La sua definizione formale è questa:
L(G) = {w appartenente a T'^*^' | S ->* w}
che vuol dire: è composto da tutte e sole le stringhe '''w''' appartenenti all''''alfabeto terminale''' della grammatica (ovvero tutte le stringhe producibili con i simboli terminali T della grammatica G), tali che esista una derivazione, anche indiretta, che parta dall''''assioma''' della grammatica, cioè '''S''', e porti alla stringa '''w'''.
Intuitivamente questo concetto era già chiaro, e questa è solo la sua formalizzazione.
!!Classificazione delle grammatiche
[[Chomsky -> http://it.wikipedia.org/wiki/Gerarchia_di_Chomsky]] ha classificato, tempo addietro, le grammatiche, a seconda dei vincoli che vengono posti sulle regole di produzione.\\
Questa distinzione è importante perché permette di riassumere certe proprietà delle grammatiche e dei linguaggi da esse generate, e ci permette di stabilire che tipo di ''macchina'' sarà poi in grado di riconoscere e/o generare quella particolare grammatica.
!!!Grammatica di tipo 0
La grammatica di tipo 0 non ha nessun vincolo sulle produzioni. Viene anche detta '''grammatica a struttura di frase'''. I linguaggi generati da questa grammatica sono anche detti '''ricorsivamente enumerabili'''.
!!!Grammatica di tipo 1
E' detta '''grammatica dipendente dal contesto'''.
Le regole di questa grammatica hanno la seguente forma:
γAδ -> γαδ
con i seguenti vincoli:
* A appartiene all'insieme dei NT
* γ e δ appartengono a (NT U T)'^*^'
* α appartiene a (NT U T)'^+^'
L'appartenenza di γ e δ a (NT U T)'^*^' vuol dire che possono essere una qualsiasi combinazione, eventualmente composta dalla stringa nulla, di tutti i simboli terminali o non terminali.
Invece, dire che α appartiene a (NT U T)'^+^' vuol dire che la stringa nulla è esclusa: α deve essere qualcosa.
----
[[Torna alla pagina di Traduttori -> Traduttori]]
|
|
