:: Traduttori - Lezione del 5 marzo 2009 ::
Torna alla pagina di Traduttori
Il simbolo
Il simbolo è un'entità atomica non ulteriormente indivisibile. Non vuol dire che sia composto da un singolo carattere, ma che dal pdv della sintassi, sotto al simbolo non si scende.
L'analizzatore lessicale prende i vari caratteri del testo, e li raggruppa in simboli, i quali poi saranno l'unità di base del passo succesivo.
L'alfabeto
L'alfabeto è un insieme finito di simboli, e soprattutto non vuoto (mmm). Si indica con la lettera Σ (sigma).
La stringa
Una stringa è invece una sequenza finita o nulla di simboli presi da Σ.
La stringa vuota si indica con ε (epsilon).
Per fare un esempio, supponiamo di avere un alfabeto così:
Σ = {+, -, *, /, (, ), n}
in cui n è un intero generico.
Stringhe valide potrebbero essere
n + (n / n)
(n + n)
n + + -
Stringhe non valide invece
n * [a + c]
perché le parentesi quadre, a e c non fanno parte di Σ.
Il linguaggio
Un linguaggio L, definito su di un alfabeto Σ, è un sottinsieme di tutte le stringhe finite ottenibili dall'alfabeto Σ.
Da notare che può anche essere un sottinsieme infinito, anche se i suoi elementi sono stringhe finite. In effetti, basta pensare a tutti i possibili programmi che si possono scrivere in C: le stringhe sono di lunghezza finita, ma tutti i possibili programmi sono in numero infinito.
Specificare un linguaggio
Come già dicevamo nella lezione del 3 marzo, ci sono diversi approcci nei confronti di un linguaggio. Per specificare un linguaggio, ovvero stabilire che cosa fa parte di un linguaggio e che cosa no, ci sono diversi metodi:
- enumerazione: semplicemente faccio la lista di che cosa è ammesso e di che cosa no. Ovviamente non è una cosa molto furba...
- teoria degli insiemi: definisco un linguaggio mediante un'espressione della teoria degli insiemi, ad esempio: L = {xy | x = 0n, y = 1n, n>= 0}, che definisce tutte le stringhe composte da un certo numero di 0 seguiti dallo stesso numero di 1. Il problema è che questa definizione è difficilmente implementabile come algoritmo.
- mediante una grammatica: la grammatica definisce in modo intelligente un linguaggio.
La cardinalità di un linguaggio è il numero di elementi che lo costituisce. Si indica così: |L|, ed è quindi il numero di stringhe che contiene. Come abbiamo visto sopra, può anche essere infinita.
Se invece la cardinalità è 0, allora si indica con la lettera phi: Φ, che indica il linguaggio vuoto. OCIO: se è vuoto vuol dire che non contiene NEANCHE la stringa vuota: sarebbe già contenere qualcosa.
Operazioni su stringhe
Vediamo un po' di operazioni che si possono fare sulle stringhe.
La concatenazione consiste nel mettere il contenuto di una stringa dopo un'altra (uuuh). Si segna così: xy.
Se x = soma e y = rone, allora xy = "somarone".
Il neutro dell'operazione di concatenazione è ε, perché è la stringa vuota:
xε = εx = x
La potenza n-esima di una stringa consiste nella concatenazione di x con n volte se stessa. Ad esempio, x3 = xxx.
Invece, x0 = ε.
Una stringa è detta prefisso di un'altra stringa quando... è un prefisso:) Idem per il suffisso.
Per esempio, w = xyz ha come prefisso x, e come suffisso z. Inoltre, sia x che y che z sono sottostringhe di w.
La stringa vuota ε è prefisso, suffisso e sottostringa di ogni stringa.
Una stringa x è prefisso, suffisso e sottostringa di se stessa.
Due stringhe sono dette uguali se contengono gli stessi simboli, in egual numero, ordinati allo stesso modo. Vabeh non mi dilungo troppo...
Operazioni su linguaggi
Allo stesso modo con cui si eseguono operazioni su stringhe, si possono anche eseguire operazioni su linguaggi. Dato che si tratta di insiemi, le loro operazioni sono di tipo insiemistico.
L'unione di due linguaggi si segna L1 U L2. Il risultante è un insieme contenente tutte le stringhe di L1 e le stringhe di L2. Ocio che le stringhe in comune vengono contate una volta sola, perché un insieme non ammette ripetizioni.
Il linguaggio vuoto è l'unità rispetto all'unione:
L U Φ = Φ U L = L
L'intersezione è l'intersezione tra insiemi.
La differenza consiste nel prendere tutte le stringhe che appartengono ad un insieme ma non all'altro.
L'uguaglianza è l'uguaglianza.
Concatenare due linguaggi vuol dire ottenere un linguaggio che contiene tutte le stringhe ottenute concatenando ogni stringa del primo linguaggio con ogni stringa del secondo linguaggio.
Ecco un esempio:
L1 = {a,b,c}
L2 = {1,2,3}
L1L2 = {a1, a2, a3, b1, b2, b3, c1, c2, c3}
Ocio che L1L2 non è uguale a L2L1.
Il linguaggio vuoto Φ è l'elemento 0 rispetto alla concatenazione:
ΦL = LΦ = Φ
Elemento 0 vuol dire che annulla tutto: infatti, come dicevamo sopra, Φ non contiene nulla, nemmeno la stringa vuota, la quale sarebbe già qualcosa. È come lo 0 nella moltiplicazine.
Invece, la stringa vuota ε è l'elemento unità, cioè si comporta come l'1 nella moltiplicazione:
L{ε} = {ε}L = L
Metto la ε tra parentesi graffe per indicare che sto descrivendo un linguaggio in modo enumerativo.
La potenza n-esima di un linguaggio consiste, come per le stringhe, nella concatenazione con se stesso n volte. Inoltre, L0 = {ε}.
La chiusura di Kleene si indica con L*, ed è definita come l'unione di tutte le potenze i-esime di L, con i >= 0. Si tratta quindi di L0 U L1 U L2 U ... U Li.
La chiusura positiva è la chiusura di Kleene, ma senza L0, ovvero senza la stringa vuota.
Osservazioni sui linguaggi
L* si chiama chiusura, anche se sembra una cosa così open, perché ogni linguaggio che si può ottenere da L, unendo o concatenando le sue stringhe, è contenuto in L*, che quindi racchiude tutto.
Possiamo anche vedere l'alfabeto come un linguaggio, trattandosi infatti di un insieme di simboli: in questo caso, le stringhe sono di lunghezza 1, perché composte da un solo simbolo. Ricordo ancora che della lunghezza del simbolo in caratteri non diciamo niente: può essere lungo 1 o 10 caratteri, ma sempre atomico è. Pertanto, se dico "stringhe di lunghezza 1", mi riferisco alla loro lunghezza in simboli, non a quella effettiva in caratteri.
Σ* è il linguaggio universale su Σ: essendo l'insieme di tutte le concatenazioni possibili di simboli di Σ, allora conterrà anche tutte le stringhe generate con elementi di Σ. Posso anche dire che tutti i linguaggi costruiti su Σ sono sottinsiemi di Σ*.
E allo stesso modo definisco Σk come l'insieme di tutte le stringhe di lunghezza k (lunghezza sempre intesa come lunghezza in simboli).
Rappresentazione dei linguaggi
- rappresentazione generativa sintetica: L è l'insieme delle stringhe ottenute da una struttura finita detta grammatica
- rappresentazione riconoscitivo-analitica: L è l'insieme delle stringhe che vengono riconosciute (o accettate) da un automa
- rappresentazione algebrica: L è la soluzione di un sistema di relazioni algebriche.
Anche qui salta fuori ancora la grammatica. Il primo punto usa esplicitamente una grammatica, perché la usa per produrre un linguaggio. Ma anche al secondo punto si usa una grammatica: viene usata per riconoscere un linguaggio.
La grammatica
La grammatica è la descrizione dei modi di comporre frasi senza alcun riferimento all'informazione che portano. Vuol dire che definisco delle categorie sintattiche, e le relazioni tra di esse.
A livello lessicale sono interessato a stabilire relazioni tra i simboli per ottenere lessemi.
A livello sintattico invece mi interessa stabilire relazioni tra lessemi per ottenere frasi "buone". Prendo i lessemi, e li faccio appartenere ad una categoria.
La definizione formale di grammatica dice che una grammatica G è una quadrupla (NT, T, S, P) dove:
- NT = insieme di simboli non terminali, indicati con lettere maiuscole A, B, ...
- T = insieme di simboli terminali, indicati con lettere minuscole: a, b, ...
- S = simbolo iniziale della grammatica
- P = regole di produzione
T deve essere un sottinsieme dell'alfabeto V, mentre S deve essere appartenente all'insieme NT dei simboli non terminali.
L'idea di fondo è che ho dei simboli non terminali, e in particolare uno da cui parto. Applicando le regole di produzione P, sono in grado di sostituirli man mano e di arrivare fino ad avere una frase composta da soli simboli terminali.
Le regole di produzione P sono della forma:
P : <α1, β1>, ..., <αn, βn>
in cui:
- α e β sono stringhe miste, cioè sono composte un po' da simboli terminali e simboli non terminali
- α1 contiene almeno un simbolo non terminale
- si scrivono come α -> β
Alla fine di tutto, ho T, che è l'insieme delle stringhe finali accettate dalla mia grammatica (e il verbo accettare ci fa ricordare gli automi di cui sopra).
Esempio
Supponiamo di voler scrivere una grammatica che mi permetta di definire le stringhe palindrome, ovvero quelle che si possono leggere allo stesso modo a partire ad entrambe le estremità, ad esempio abba, aca, a, bb e così via.
- l'alfabeto è composto da {a, b, c}.
- NT = {S}
- T = {a, b, c}
- P = {S -> aSa, S-> bSb, S -> cSc, S -> a, S -> b, S -> c, S -> ε}
Il simbolo iniziale è sempre S, e non lo scriviamo per semplicità. Inoltre, diciamo subito che possiamo scrivere le regole di produzione anche in questo modo:
S -> a|b|c
in cui le barre verticali | indicano che si è in presenza di un'alternativa.
La soluzione è quella di sopra, ma perché è corretta? Innanzitutto, si parte sempre da una stringa contenente il simbolo non terminale di partenza, cioè la S.
Poi, si eseguono le derivazioni: si prende un simbolo non terminale e lo si sostituisce con la sua "definizione" data nella lista delle regole di produzione.
In questo caso, posso ad esempio decidere di sostituire S con aSa, perché così sta scritto nelle regole di produzione. Poi vado avanti: sostituisco i simboli non terminali con le loro regole di produzione e così via finché non finisco:
1) S
2) S -> aSa: aSa
3) S -> bSa: abSba
4) S -> c: abcba
Come si può vedere, la derivazione si applica alla stringa prodotta al passo precedente, così che la stringa finale man mano si crea. Al passo 3), per esempio, ho sostituito S con bSb Siccome S nella stringa precedente si trovava in mezzo alle due a, ho semplicemente messo bSb al posto della S: abSba.
La derivazione
Abbiamo già visto che cos'è la derivazione nell'esempio pratico: è la ripetuta applicazione di regole della grammatica.
Una stringa di simboli che è coinvolta nella derivazione viene detta forma di frase, oppure anche forma sentenziale.
Se invece una forma di frase contiene solo simboli terminali, la chiamo solamente frase.
Nell'esempio di sopra, i passi 1, 2 e 3 contenevano forme sentenziali, mentre l'ultimo passo mi ha dato una frase. Il passaggio dalle forme sentenziali alla frase è appunto la derivazione.
La derivazione non è il singolo passaggio, ma è tutta l'applicazione dal passo 1 al passo finale. Quindi, avremmo potuto anche scrivere così:
S ->* abcba
il che vuol dire che siamo in grado, in uno o più passi, di andare da S alla mia frase abcba. La scrittura ->* si chiama chiusura transitiva di ->.
Supponiamo che in una frase ci siano più simboli non terminali:
aBcdAfgC
(ricordo che le minuscole sono simboli terminali, mentre le maiuscole sono non terminali).
La derivazione viene eseguita un passo alla volta. Quale scelgo tra A, B e C?
- se scelgo il NT più a sinistra, uso una regola LEFTMOST
- se scelgo il NT più a destra, uso una regola RIGHTMOST
- ma posso anche scegliere altri NT:)
La Leftmost e la Rightmost sono dette derivazioni canoniche.
Torna alla pagina di Traduttori
