Compilatore Z : XML tra Source e Target

2 CAPITOLO 1. INTRODUZIONE
duzione”, cioe` “universalmente” usato come lo e` invece Java. Il nostro scopo
e` quello di mostrare che queste tecniche sono efficaci anche se sviluppate in un
linguaggio meno specialistico, da un programmatore “non accademico”.
I risultati che andiamo a presentare ci danno speranza per voler, in linea
di principio, procedere con queste tecniche, dato che le conoscenze generali
sui linguaggi e i compilatori che abbiamo dovuto acquisire si sono dimostrate
relativamente di base (ad esempio, la grammatica che definisce il traduttore
da λ-calcolo a XML non e` particolarmente complicata), inoltre Java offre una
buona serie di strumenti per la creazione di analizzatori lessicali e parser, in
generale, e per la manipolazione di dati semistrutturati come quelli in formato
XML, in particolare.
L’applicazione sviluppata consta non soltanto del compilatore, ma anche di
un interfaccia web client-server, che consente di introdurre il “programma” da
compilare, e di scegliere il target desiderato tra quelli disponibili.
La tesi si divide in sei capitoli principali e un’appendice contenente il codice
sviluppato. Il Capitolo 2 e` un’introduzione al λ-calcolo e alla corrispondente
sintassi utilizzata nel seguito. Il Capitolo 4 descrive tutti i possibili output del
nostro compilatore. Il Capitolo 3 e` una breve rassegna su XML, il linguaggio da
noi utilizzato come linguaggio intermedio. Il Capitolo 5 descrive, con un certo
dettaglio, l’utilizzo delle librerie Java che riguardano JLex e Java CUP (per la
creazione di analizzatori lessicali e parser). Il Capitolo 6 illustra brevemente le
librerie Java per la manipolazione dei dati in formato XML. Il Capitolo 7 de-
scrive il compilatore, presentandone i moduli principali, che sono l’analizzatore
lessicale, il parser e gli algoritmi di manipolazione dei dati XML. Concludiamo
poi con un diagramma riassuntivo e alcuni commenti sul lavoro svolto.
Ringraziamenti
Un particolare ringraziamento va alle persone che in questi ultimi anni mi
sono state vicino e mi hanno dato la forza per superare tutte le situazioni difficili.
Un grazie sincero a: mio padre e mia madre, Franca, Sara, Daniela, Angelo,
Marco, Roberto, Alessia, Fabrizio, Andrea e a tutti i miei colleghi di lavoro.
Capitolo 2
Linguaggio Source: il
Lambda Calcolo
In questo capitolo descriviamo in breve il linguaggio source del nostro compila-
tore: il λ-calcolo (o lambda calcolo).
Il λ-calcolo e` una teoria delle funzioni viste come regole anziche` come grafi.
Una funzione vista come grafo e` un insieme di coppie “argomento, valore”, in-
vece una funzione vista come regola e` il processo di passare dall’argomento al
valore, processo codificato da una definizione. In questo contesto, in cui l’aspetto
computazionale ha parte preponderante, le funzioni sono come programmi che
possono avere come input ed output altri programmi, per cui ci troviamo di
fronte a una struttura senza gerarchia (ovvero senza tipi, almeno a priori), da
qui la definizione di “λ-calcolo puro” o “λ-calcolo non tipato”, il cui oggetto di
studio sono sia le funzioni quanto i loro argomenti. In particolare, una funzione
nel λ-calcolo puo` essere esplicitamente applicata a se stessa (autoapplicazione),
cosa non possibile secondo la nozione classica di funzione. Il λ-calcolo studia
quindi le funzioni e il loro comportamento rispetto all’applicazione di una fun-
zione al suo argomento (e non rispetto alla composizione di funzioni, come invece
avviene, ad esempio, nella teoria delle categorie), e cio` implica che l’applicazione
e` un’operazione primitiva del λ-calcolo: una funzione f applicata ad un ar-
gomento a e` denotata con fa. L’operazione complementare all’applicazione e`
l’astrazione: sia t(x) un’espressione contenente la variabile x, allora λx.t(x) e`
una funzione f che, applicata al valore a, con un passo di computazione (detto
β-regola) diventa f(a) = (λx.t(x))a = t(a), ovvero la funzione f computera` un
valore avendo ricevuto in input il valore a per il suo parametro x. E` importante
osservare che le funzioni con piu` argomenti possono essere ricondotte al caso di
funzioni che considerano un solo argomento per volta. Ad esempio, considerando
il λ-calcolo esteso con l’usuale operatore aritmetico di ’+’ e con i numeri interi
positivi (sia l’operatore che i numeri sono, naturalmente, definibili direttamente
nel λ-calcolo, ma in questo contesto viene comodo aggiungerli direttamente,
ovvero considerarli come “zucchero sintattico”), la funzione “somma di due nu-
3
4 CAPITOLO 2. LINGUAGGIO SOURCE: IL LAMBDA CALCOLO
meri interi” potrebbe essere espressa in tale calcolo come λx.λy.(x+y), per cui
se scriviamo ((λx.λy.(x+y))4)5, con due passi di β-regola otteniamo 4+5, che e`
uguale a 9 se diamo a ’+’ la sua usuale semantica. Il λ-calcolo venne introdotto
da Church nei primi anni ’30, parallelamente alla teoria dei combinatori di
Schnfinkel e Curry, come proposta di formalismo per una teoria generale delle
funzioni e per la fondazione (di parte) della logica e della matematica. A causa
della presenza di paradossi logici nel calcolo, questo scopo non venne raggiunto,
ma una parte consistente della teoria del λ-calcolo diede comunque un grosso im-
pulso allo sviluppo della teoria della ricorsivita`, e in, generale, alla teoria delle
funzioni computabili, che sono alla base della computazione automatica. Us-
ando il λ-calcolo come teoria, Church propose una formalizzazione della nozione
di “effettivamente computabile” (ovvero di “meccanicamente calcolabile” via
una sequenza di passi) attraverso il concetto di funzione λ-definibile. Tale for-
malizzazione e` equivalente alla teoria della ricorsivita` (che secondo la Tesi di
Church e` la formalizzazione per antonomasia della nozione di “effettivamente
computabile”) e alla teoria della macchine di Turing. Il λ-calcolo possiede al-
cune importanti caratteristiche dei linguaggi di programmazione e delle loro
implementazioni. Per esempio, le variabili legate dall’operazione di astrazione
corrispondono ai parametri di un sottoprogramma (procedura) e il fatto che il λ-
calcolo sia non tipato corrisponde al fatto che per una macchina un programma
e i suoi dati sono la stessa cosa (ovvero non sono nient’altro che sequenze di
bit, il cui significato e` dato solamente dall’uso che se ne fa). Nonostante la sua
semplice sintassi, il λ-calcolo e` abbastanza potente da descrivere tutte le fun-
zioni calcolabili meccanicamente (dalla Tesi di Church succitata), per cui puo`
essere visto come un linguaggio di programmazione paradigmatico, intendendo
che in esso alcuni problemi della programmazione, in modo specifico quelli rel-
ativi alla chiamata di procedure, possono essere studiati in una forma pura e
questo puo` essere fonte di ispirazione per il progetto e l’analisi di linguaggi di
programmazione “reali”.
2.1 Definizione del Calcolo
DEFINIZIONE 1. L’alfabeto del λ-calcolo e` costituito da:
• un insieme V numerabile di simboli per variabili;
• le parentesi tonde “(” e “)”;
• due simboli speciali: l’operatore di astrazione λ, e il punto “.” (opzionale).
L’insieme Λ delle espressioni del λ-calcolo (dette λ-termini, o λ-espressioni,
o semplicemente termini od espressioni) e` definito dalla seguente grammatica:
Λ ::= V | (ΛΛ) | (λV Λ)
2.1. DEFINIZIONE DEL CALCOLO 5
Seguendo la tradizione consolidata del linguaggio matematico, le variabili
sono normalmente indicate con le ultime lettere dell’alfabeto latino arricchite
eventualmente da pedici:
u, x, y, z, ..., x1, x2, ...
I λ-termini generici sono indicati con t, t′, t′′, t1, t2, ... o piu` liberamente con
altre lettere dell’alfabeto latino (minuscole o maiuscole) se la scrittura dovesse
diventare di difficile lettura.
Il linguaggio del λ-calcolo puo` essere descritto anche in forma diversa, cioe`
per mezzo di un numero finito di regole di deduzione. Riportiamo qui di seguito
anche questa presentazione.
DEINIZIONE 2. L’insieme Λ dei λ-termini e` induttivamente definito dalle
regole che seguono:
(atomica) x ∈ V
x ∈ Λ
(astrazione)
x ∈ V t ∈ Λ
(λxt) ∈ Λ
(applicazione)
t, t
′ ∈ Λ
(tt′) ∈ Λ
Se si scrivono termini un po’ complessi ci si rende conto che le espressioni
possono diventare incomprensibili per la grande quantita` di parentesi. Si adot-
tano allora alcune convenzioni per migliorare la leggibilita`. La prima conven-
zione riguarda l’astrazione e si rifa` alla notazione che era abbastanza comune nei
primi decenni del secolo XX: invece di usare (λxt) si puo` usare λx.t eliminando
cos`ı un paio di parentesi per ogni astrazione. Ma anche in questo modo le par-
entesi rimangono troppo numerose: si introducono allora due regole associative.
Ecco l’elenco completo:
λx.t sta per (λxt)
e1e2 ... en−1en sta per ((...(e1e2)...en−1)en)
λx1x2...xn.e sta per (λx1(λx2...(λxne)...))
Si noti che l’applicazione “associa a sinistra”, mentre l’astrazione “associa a
destra”.
Vorremo ora tornare sul significato intuitivo dell’astrazione nel λ-calcolo. Se
ad esempio volessimo scrivere:
6 CAPITOLO 2. LINGUAGGIO SOURCE: IL LAMBDA CALCOLO
fn(x) = xn
si potrebbe pensare che stiamo scrivendo una funzione a due argomenti oppure
che fn e` semplicemente un nome che incorpora una lettera che compare anche
nel definiens.
Per questo motivo si introduce l’operatore di astrazione che indica esplici-
tamente quali entita` linguistiche debbano essere intese come argomenti della
funzione e quali no. Rifacendosi all’esempio, la funzione e` adeguatamente de-
scritta da λx.xn e dal momento che solo x e` legata dall’operatore di astrazione
si deduce che x e` argomento dell’espressione funzionale, mentre n e` da inten-
dersi come variabile libera. Se invece si vuole considerare tale espressione come
funzione di due argomenti si dovra` scrivere λnλx.xn oppure λxλn.xn (non e` la
stessa cosa!). In generale si dice che ogni occorrenza della variabile x compare
legata (bound) in λx.e ∈ Λ; ogni occorrenza di variabile che non sia legata e`
detta libera (free).
Siccome il nostro scopo e` quello di utilizzare il λ-calcolo come linguaggio
source del nostro traduttore, non e` necessario, in questo contesto, ne` introdurre
formalmente la regola di computazione β, brevemente descritta nell’introduzione
di questo capitolo, ne` dare esempi di codifica di alcune funzioni calcolabili (come
ad esempio la somma). Per entrambe le questioni ci riferiamo a [1].
2.2 La Nostra Sintassi
Uno dei primi problemi da risolvere per poter far creare agli utenti file di testo
contenenti funzioni espresse nel λ-calcolo, e` quella di dover definire un sintassi
molto simile a quella propria del λ-calcolo, ma facilmente digitabile allo stesso
tempo.
La convenzione da noi utilizzata e` la seguente:
Variabili : Le variabili sono indicate con tutte le lettere dell’alfabeto (a-z)
Lambda : Il λ e` rappresentato dalla lettera maiuscola “L”
Punto : Il punto si rappresenta esattamente nella stessa maniera “.”
Applicazione : L’applicazione e` rappresentata dal carattere speciale “@”
Parentesi : Le parentesi sono esattamente le stesse parentesi tonde “(” e “)”
Con questa sintassi e` quindi possibile esprimere tutte le λ-funzioni. Vor-
remmo sottolineare che la nostra enfasi e` sull’albero sintattico corrispondente
a ogni funzione, che si puo` facilmente ricavare dalle regole di deduzione della
DEFINIZIONE 2. Ecco un esempio di λ-termine nelle tre forme:
2.2. LA NOSTRA SINTASSI 7
λ-Calcolo: λx.y(λz.z)xy
⇓ ⇓
Nostra Sintassi: Lx.y@(Lz.z)@x@y
⇓ ⇓
Albero Sintattico Corrispondente:
Lx
|
@
/ \
@ y
/ \
@ x
/ \
y Lz
|
z
Il λ-calcolo puro puo` essere dotato di un algoritmo di inferenza di tipo. Di
questo si parlera` nella Sezione 4.4.
Capitolo 3
Linguaggio Intermedio:
XML
In questo capitolo introduciamo brevemente le caratteristiche del linguaggio
intermedio del nostro compilatore: l’XML.
3.1 Cos’e` XML
XML, Extensible Markup Language (ovvero “linguaggio di marcatura esten-
sibile”) offre un formato completamente estensibile, di facile apprendimento e
molto ricco, per la strutturazione di dati e documenti che possano essere scam-
biati in modo efficiente via Web.
Anche se la “M” in XML sta per “Markup”, XML non e`, a rigor di termini, un
linguaggio di marcatura, bens`ı un raffinato “meta”-linguaggio, uno strumento
standardizzato, ma estremamente flessibile, per creare altri linguaggi. Per es-
sere ancora piu` precisi, XML permette la creazione di dialetti di linguaggi che
seguono regole precise e rigorose per la struttura, la sintassi e la semantica,
come stabilito dal W3C (World Wide Web Consortium) l’organizzazione uffi-
ciale che ha il compito di promuovere lo sviluppo di tecnologie interoperabili
(cioe` specifiche, direttive, software, strumenti).
3.2 Cosa Offre
XML permette la memorizzazione dei dati in forma di testo semplice: qualsiasi
applicazione che possa leggere un file di testo puo` leggere un documento XML.
Non e` necessario avere il programma di origine per accedere ai dati, come invece
accade ad esempio per file memorizzati in formato binario proprietario. In
questo modo, risolvere un problema nell’ambiente di un sistema informativo e`
semplice: basta lanciare un editor di testo qualsiasi per rivedere e modificare il
9
10 CAPITOLO 3. LINGUAGGIO INTERMEDIO: XML
documento. XML e` quindi un insieme di regole per creare formati di testo facili
da generare e facilmente elaborabili da un computer. I file di testo risultanti
sono strutturati, in modo tale da essere:
• privi di ambiguita`;
• estendibili;
• indipendenti dalla piattaforma.
3.3 Somiglianze
Ci sono molte somiglianze fra XML e HTML. Alcune delle regole sintattiche
di HTML sono presenti anche in XML. Infatti i due linguaggi hanno marcatori
racchiusi fra i simboli < e > chiamati tag. Uno dei grossi vantaggi di XML e`
che non esiste un insieme di marcatori predefinito, si possono definire marcatori
con nomi a piacimento. Come per HTML, XML puo` avere anche attributi che
servono per modificare o specificare gli elementi. Vediamo adesso un esempio
semplice di documento XML con elementi e attributi.
Esempio Un documento XML con elementi figli annidati e attributi.
<conto tipo=”risparmio” valuta=”Euro” >
<nome>Mario Rossi< /nome>
<saldo>2.784,50< /saldo>
< /conto>
Nell’esempio si nota che esiste un elemento principale conto che ha due at-
tributi, il tipo e la valuta con rispettivamente i valori risparmio e Euro. I val-
ori degli attributi vengono sempre collocati fra apici singoli o doppi. L’elemento
conto non contiene dati carattere o testo, bens`ı elementi figli, cioe` nome e
saldo. Ciascun elemento(nome, saldo e conto) ha un marcatore di inizio e
un corrispondente marcatore di fine con una barra (/, slash ) nel marcatore di
fine. Tutti gli elementi XML debbono essere terminati. Il vantaggio piu` grosso
che salta subito all’occhio dall’esempio e` che XML ha elementi e attributi au-
todescrittivi che offrono una marcatura piu` ricca rispetto a quella di HTML. In
XML si puo` scegliere l’elemento radice che deve contenere tutti gli altri elementi
del documento. XML si basa sul presupposto che contenuto e aspetto (o stile)
debbano essere tenuti separati dalla codifica di marcatura dei dati.
3.4 La Suite Completa
La suite XML comprende parecchie tecnologie importanti, si veda la seguente
tabella.
3.5. XML E` PROLISSO 11
Tecnologia Descrizione
XML Version 1.0 Raccomandazione tecnica per XML
DTD Document Type Definition (uno schema)
XDR XML Data Reduced (schema Micrososft)
XSD XML Schema Definition (schema W3C)
Namespaces Un metodo per qualificare i nomi di elementi e attributi
XPath XML Path Language
XLink XML Link Language
XPointer XML Pointer Language
DOM Document Object Model API
SAX Simple API for XML
XSL eXstensible Style Sheet Language
XSL-FO XSL Formatting Objects
XSLT XSL Transformation Language
XInclude Sintassi XML Include
XBase Sintassi XML Base URI
3.5 XML e` Prolisso
I file XML sono documenti di testo con delimitatori per la marcatura, percio`
sono quasi sempre di dimensioni maggiori rispetto a file binari analoghi. Questa
caratteristica e` stata presa seriamente in considerazione nella fase di proget-
tazione del linguaggio: i membri del W3C che avevano ricevuto l’incarico di
creare lo standard hanno scelto di costruire un linguaggio prolisso, lasciando
ampio spazio per la possibilita` di estensioni e per l’autodescrittivita` di elementi
e attributi. I progettisti di XML si sono resi conto che lo spazio di memoria e` una
risorsa che tende a diventare sempre meno costosa, percio` non hanno ritenuto
che le dimensioni dei file fossero un problema; inoltre sono ormai ampiamente
disponibili programmi di compressione a basso costo, veloci, efficienti e gratuiti
per molte piattaforme. Infine XML e` ottimizzato per il trasporto su Internet
con il protocollo http/1.1, che comprime “al volo” le stringhe di dati testuali,
per una minore occupazione di banda.
3.6 Dalle Origini a Oggi
La prima idea dell’XML risale al 1996; lo standard W3C e` del 10 febbraio
1998. XML e` basato sullo Standard Generalized Markup Language (SGML),
creato una decina d’anni prima, che e` a sua volta un metalinguaggio per la
creazione di altri linguaggi: una delle applicazioni di SGML e` HTML, mentre
ricordiamo che XML e` un sottoinsieme di SGML. L’HTML e` stato riformulato
come applicazione XML, l’XHTML (eXtensible Hypertext Markup Language),
con l’obiettivo di dare ad HTML un certo grado di estensibilita`.
XML non richiede licenza, e` indipendente dalla piattaforma, ed e` ben sup-
portato. Nessuno ha un’esclusiva su XML: non ci sono problemi di licenza,
12 CAPITOLO 3. LINGUAGGIO INTERMEDIO: XML
il linguaggio e` disponibile per tutte le implementazioni, e anche le tecnologie
componenti sono di pubblico dominio. L’indipendenza dalla piattaforma rende
XML ideale per l’uso sul Web. Nuovi modelli di e-business richiedono sistemi
trasparenti di scambio di dati basati sulle transazioni via Internet. La maggior
parte delle societa` di sviluppo ha contribuito con la creazione di strumenti, la
promozione di standard e la preparazione di soluzioni esemplificative, e in genere
offre ampio sostegno agli sviluppatori.
3.7 Bibliografia
Per approfondire XML si consigliano i seguenti testi:
XML Guida Completa [12] Questo e` un corso introduttivo sull’XML che si
spinge a trattare anche caratteristiche piu` avanzate. E` composto da 21
lezioni al termine delle quali sono proposti gli esercizi correlati e le risposte
alle domande piu` frequenti sull’argomento. Nei capitoli del libro troviamo
ad esempio la descrizione delle tecniche per strutturare dati con XML,
creare schemi XML e DTD, manipolare i DOM e trasformare documenti
con XSLT.
XSLT [13] Tutto cio` che serve per poter convertire documenti da XML a
HTML, o da un vocabolario XML ad un altro lo si trova ben descritto
in questo libro. Vengono dettagliatamente descritte tutte le tecniche per
analizzare documenti XML tramite XPATH e per generare target di tipo
HTML, SVG, JPEG, codice sorgente Java, e XSLT.
XSLT Cookbook [9] In questo libro troviamo una serie di “ricette” pronte per
poter risolvere tutta una serie di problematiche relative alle trasformazioni
di documenti XML.