ANTLR (ANother Tool for Language Recognition) è un potente generatore di parser per leggere, processare, eseguire o tradurre strutture di testo o file binari. E’ ampiamente usato per la realizzazione di linguaggi, tools e frameworks. Partendo da una grammatica, ANTLR genera un parser che può produrre e navigare alberi sintattici.

Dopo aver visto come installarlo sul nostro sistema Windows, facciamo uno step avanti e poniamoci l’obiettivo di sviluppare il nostro parser per un linguaggio di programmazione esistente.

Approfittando della vena creativa che ci spinge in questi articoli, faremo uso di Jack, un linguaggio di programmazione Java-like presentanto nel libro The Elements of Computing Systems: Building a Modern Computer from First Principles.

Iniziamo il nostro viaggio discutendo la generazione della grammatica che descrive il linguaggio, passeremo poi alla generazione del parser e del lexer in Python così da porre le basi per lo sviluppo di un vero e proprio compilatore.

Il Compilatore

Prima di partire, facciamo due parole su come dovrà essere composto il nostro compilatore. In genere possiamo dividere l’analisi effettuata da uno strumento di questo tipo in 2 macro aree:

• Analisi sintattica: identifica le strutture fondamentali di un testo;
• Generazione del codice: converte le varie parti identificate in codice macchina.

Per non complicare troppo le cose, in questo articolo ci focalizziamo sull’analizzare e sviluppare la prima area. Questa si divide a sua volta in:

• Tokenizer: suddivide l’input in parole base del linguaggio;
• Parser: cerca di effettuare il match tra le parole riconosciute nello step precedente e le regole sintattiche del linguaggio.

Il primo step dell’analisi sintattica è quindi la divisione in token del testo da analizzare, si parla quindi di un’analisi lessicale che ha l’obiettivo di verificare che tutte le parole presenti nel testo siano legali.

ANTLR permette di effettuare questa analisi tramite la produzione di un oggetto chiamato lexer.

Una volta fatto ciò, si passa al vero e proprio parsing. In questa fase si cerca di determinare l’esatta corrispondenza tra il testo e le regole sintattiche espresse in quella che prende il nome di grammatica.

E’ proprio grazie alla grammatica che saremo in grado di istruire ANTLR a riguardo di quali sono le regole che governano il nostro linguaggio.

E’ la grammatica che permette di determinare in maniera precisa qual è il lessico del linguaggio e quali le strutture portanti, così da permettere ad ANTLR di generare sia il lexer che il parser.

La Grammatica di Jack

Secondo quelle che sono le specifiche del linguaggio presentate dagli autori, una possibile implementazione della grammatica di Jack è la seguente:

ANTLR necessita che il file contenente la grammatica sia salvato con estensione .g4. Altra regola fondamentale è che le regole lessicali (Lexel rules) devono essere messe alla fine del file.

Sebbene per ragioni di spazio e tempo non andremo nel dettaglio di come creare una grammatica da zero, spieghiamo velocemente una regola presente per dare un’idea della potenza espressiva di questo strumento.

Prendiamo per riferimento l’espressione:

3 + 1;

la parte della grammatica chiamata in causa è:

Quando incontrerà l’espressione 3 + 1, ANTLR la catalogherà come di tipo expression. Questo componente è descritto come un oggetto term seguito da zero o più occorrenze (l’asterisco è utilizzato come nelle espressioni regolari) di un oggetto composto da op e term.

All’interno dell’elemento expression dunque, saranno contenuti 3 elementi: term, op, term. Il primo term conterrà un INTEGERCONSTANT che a sua volta è composto da una o più occorrenze (il segno di somma è anche in questo caso utilizzato come nelle espressioni regolari) di numeri da 0 a 9.

Il secondo elemento, op, conterrà il segno +, il terzo elemento term conterrà infine un altro INTEGERCONSTANT.

Appare chiaro come già da queste 5 semplici regole, sia possibile mappare e riconoscere la struttura di una qualsiasi espressione complessa a piacere.

ANTLR per Python

Una volta preparata la grammatica, passiamo ad installare il runtime di ANTLR per Python. Tieni di conto che esistono implementazioni di questo strumento per molti linguaggi di programmazione.

L’installazione è molto semplice e fa uso del gestore di pacchetti di Python. Apri dunque una prompt dei comandi e digita:

Dopo aver terminato l’installazione possiamo poi generare il lexer ed il parser per la grammatica presentata. Per far ciò, apriamo un altro prompt dei comandi e, dopo aver raggiunto al cartella dove è salvato il nostro file .g4, digitiamo:

Così facendo, ANTRL produrrà i vari file Python necessari per analizzare del testo sulla base della grammatica che abbiamo definito.

Estendiamo il Parser

Di tutti i file generati, quello che ci interessa di più è il listener. La classe prodotta da ANTLR rappresenta un’interfaccia da implementare con un metodo per ogni regola espressa nella nostra grammatica.

Il sorgente si presenta in questo modo:

Una volta passato un file da analizzare, ANTLR provvederà a richiamare i metodi di questa classe ogniqualvolta una particolare regola grammaticale viene riconosciuta.

Nell’implementazione che ti presento, scaricabile da questo link, troverai la classe JackAnalyzer che estendendo jackListener ne reimplementa i metodi così da generare un file XML contenente la struttura sintattica del file .jack passato in input.

Conclusioni

Il progetto presentato in questo articolo è un semplice analizzatore sintattico che mostra le possibilità che un tool come ANTLR rende disponibili.

Per eseguire correttamente il programma, parti da un file .jack valido e copiane il path nella variabile dir presente nel metodo main di JackAnalyzer.

Una volta terminata l’esecuzione, troverai nella stessa cartella del file .jack un file onomino con estensione .xml che presenterà la struttura sintattica del programma analizzato.