Materiale didattico

Analizzatori lessicali: esempi relativi a JFLex
Riconoscimento e parsing di linguaggi context-free (2 maggio 2006)
Parser ricorsivo-discendenti
Generazione di codice
Parser bottom-up

Analizzatori lessicali

Esempi d'uso
Un semplice esempio di riconoscitore di elementi lessicali all'interno di un testo:
(N.B. Per alcuni  esempi è necessaria la versione 5 del linguaggio Java)

• Versione 0
  Individua all'interno dello standard input semplici elementi lessicali, come stringhe alfabetiche, numeriche e alcuni simboli di punteggiatura. Il metodo yylex della classe Yylex generata dall'analizzatore si limita a visualizzare un messaggio per ogni elemento individuato e termina quando viene inserito il carattere di fine input. È definita una classe Esempio per iniziare l'esecuzione e richiamare yylex .
• Versione 1
  Qualche aggiunta alla versione precedente: può leggere anche da un file, il cui nome deve essere fornito al momento dell'esecuzione sulla linea di comando; è in grado di leggere caratteri Unicode.
  
• Versione 2
  Gli elementi lessicali sono gli stessi delle due versioni precedenti, ma l'architettura è simile a quella di un vero analizzatore lessicale. Nella classe Yytoken vengono definite, mediante un tipo enumerativo, delle costanti per rappresentare i vari elementi lessicali e viene definita la struttura dei token.
  Il metodo yylex  è un produttore di token: a ogni chiamata restituisce un'istanza di Yytoken corrispondente all'elemento lessicale appena letto.
  Separatamente sono fornite due rudimentali classi di prova, che richiamano yylex : una si occupa di elencare i token incontrati, l'altra di riscrivere l'input letto utilizzando lettere maiuscole.
  
  
• Versione 3
  Alcuni cambiamenti rispetto alla versione precedente: la classe generata si chiama AnalizzatoreLessicale, il metodo di scansione  getProssimo. Vengono inoltre utilizzate alcune direttive di JFlex. La  classe che elenca i Token riscritta per i nuovi nomi.
  
  

• Versione 1
  
  • Il file di specifica lessicale
  • Il tipo enumerativo che definisce le costanti corrispondenti ai token
    
  • La classe che definisce i Token
  • Una classe di prova per elencare i Token
  • La calcolatrice
    
    
• Versione 2
  In questa versione alle costanti del tipo enumerativo viene associato un metodo di calcolo.  Il codice della calcolatrice può essere di conseguenza semplificato (il file di specifica lessicale e la classe che definisce i Token sono gli stessi della versione 1).
  
  
  • Il tipo enumerativo che definisce le costanti corrispondenti ai token
    
  • La calcolatrice 

• Versione 0
  Individua all'interno dello standard input numeri romani scritti correttamente utilizzando i simboli I V X, e li trascrive in output.
• Versione 1
  Una volta individuato un numero scritto correttamente, lo visualizza anche in notazione decimale.
• Versione 2
  È uno scanner per i numeri romani: il metodo di scansione  (nextToken) ad ogni chiamata produce un token, di tipo Token contenente il numero letto, in notazione romana e in notazione decimale. Come esempio d'uso viene fornita separatamente la classe RiconosciRomani.java.

• I sorgenti del package lt2.calc (classi legate all'analizzatore lessicale e classe EspressioneException).
  
• Un riconoscitore di espressioni ricorsivo discendente.
  
• Un convertitore da notazione infissa a notazione postfissa.
  
• Una calcolatrice.
  
• Ancora la calcolatrice, implementata mediante la costruzione di abstract syntax trees.
  
• La calcolatrice con l'aggiunta degli identificatori.
  
• Un compilatore per le espressioni aritmetiche (il compilatore genera codice per la macchina a stack illustrata sotto).
  

Generazione di codice

Negli esempi si utilizza una macchina a stack, implementata nella classe Macchina. Viene inoltre fornita la classe Codice, utile per generare il codice e memorizzarlo in un file. Alcune note relative alle istruzioni della macchina e all'uso di queste classi sono fornite nel documento Note sulla macchina a stack.

Nota: le classi Macchina e  Codice fanno parte di un package di nome lt2.macchina. Per utilizzare correttamente le classi si consiglia di definire all'interno di una directory lt2, una sottodirectory di nome macchina, nella quale vanno posti e compilati i file Macchina.java e Codice.java. La directory lt2 dovrà essere collocata in una posizione accessibile secondo la variabile d'ambiente CLASSPATH.
I file sorgenti Macchina.java e Codice.java che NON DEVONO essere modificati.

Gli esempi presenti su questa pagina utilizzano solo un piccolo sottoinsieme delle istruzioni disponibili. Esempi d'uso di altre istruzioni, per la compilazione dei costrutti tipici dei linguaggi di programmazione, sono mostrati a lezione.

In particolare, con riferimento all'esempio del compilatore per le espressioni aritmetiche, eseguendo Espressione.java verrà chiesto all'utente di inserire un'espressione. Se l'espressione è scritta correttamente verrà generato un file di nome eseguibile contenente il codice corrispondente. L'applicazione Macchina.java permette di eseguire tale codice. Richiamando tale applicazione con l'opzione -L è possibile visualizzare il codice senza eseguirlo, mentre con l'opzione -d è possibile vedere ciascuna istruzione prima che venga eseguita.

Esempio: espressioni aritmetiche
Gli esempi presentati di seguito sono analoghi a quelli relativi ai parser top-down. È stata utilizzata la versione 11a beta di CUP e il package lt2.calc.

• Un riconoscitore di espressioni.
  
• Un convertitore da notazione infissa a notazione postfissa.
  
• Una calcolatrice.
  
• Ancora la calcolatrice, implementata mediante la costruzione di abstract syntax trees.
  
• La calcolatrice con l'aggiunta degli identificatori.
  
• Un compilatore per le espressioni aritmetiche (il compilatore genera codice per la macchina a stack).