Swappa :: Traduttori - Lezione del 5 marzo 2009

 :: Traduttori - Lezione del 5 marzo 2009 ::

Torna alla pagina di 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 -> α ∈ 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₀
γ = 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

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

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

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

Questo significa che la stringa derivata non può mai essere più piccola della stringa iniziale, proprio perché α non è mai vuota.

Perché si parla di dipendenza dal contesto? Il contesto è rappresentato da γ e δ, le quali "circondano" A e determinano se è possibile sostituirla con α.

Grammatiche di tipo 2

Questo sono dette grammatiche libere dal contesto:

 A -> β

dove:

A è un simbolo non terminale
β ∈ (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₃, L₂, L₁ ed L₀.

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

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.

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.

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.

Torna alla pagina di Traduttori