Materiale didattico

Analizzatori lessicali: esempi relativi a JFLex
Riconoscimento e parsing di linguaggi context-free (26-28 aprile 2005)
Parser ricorsivo-discendenti
Parser bottom-up
Generazione di codice

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.0 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 eneumerativo 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.

• L'analizzatore lessicale:
  
  
  • 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
    
    
  Nota: le classi TipoToken, Token e la classe Scanner (generata mediante JFLex a partire dal file di specifica lessicale) fanno parte di un package di nome lt2.calc. Per compilare e utilizzare correttamente le classi si consiglia di definire all'interno di una directory lt2, una sottodirectory di nome calc. La directory lt2 dovrà essere collocata in una posizione accessibile secondo la variabile d'ambiente CLASSPATH. I sorgenti delle tre classi possono essere collocati in calc e compilati. La classe di prova ElencaToken, come le classi indicate di seguito, possono essere collocate altrove.

• ParserEspressioni.java
  Riconosce le espressioni aritmetiche sintatticamente corrette.
• Calcolatrice.java
  Calcola il risultato di un'espressione aritmetica. Il codice dei metodi è ottenuto inserendo nei metodi di ParserEspressioni le azioni semantiche utili per calcolare il risultato.
  
  
• Calcolatrice.java (seconda versione)
  Calcola il risultato di un'espressione aritmetica. Stampa inoltre l'espressione in notazione postifissa. In questo esempio il parser costruisce un albero (abstract sintax tree). La valutazione avviene successivamente al processo di riconoscimento, attraversando opportunamente tale albero. Le classi che implementano l'albero sono definite nel file Expr.java

Parser bottom-up

Esempi d'uso
Un parser per le espressioni aritmetiche:

• expr.cup
  File di specifica sintattica per le espressioni aritmetiche. Contiene la descrizione della grammatica per le espressioni e le regole di precedenza e associatività per la risoluzione dei conflitti.
• expr.lex
  File di specifica lessicale per i terminali utilizzati nelle espressioni aritmetiche. Permette di generare mediante JFlex un analizzatore lessicale utilizzabile dal parser generato a partire dal file expr.cup.
• ParserEspressioni.java
  Applicazione Java per il riconoscimento delle espressioni sintatticamente corrette, che utilizza il parser generato a partire dal file expr.cup precedente.

• expr.cup
  File di specifica sintattica per le espressioni aritmetiche. Le regole grammaticali della versione precedente sono state estese introducendo attributi utili al calcolo del risultato dell'espressione.
• expr.lex
  Il file di specifica lessicale è lo stesso della versione precedente.
• Calcolatrice.java
  Applicazione Java per il calcolo delle espressioni, che utilizza il parser generato a partire dal file expr.cup precedente.

• expr.cup
  File di specifica sintattica per le espressioni aritmetiche. Gli attributi sono utilizzati per la costruzione dell'albero sintattico.
• Expr.java
  Classe astratta per la definizione dell'albero sintattico con cui sono rappresentate le espressioni, e sottoclassi concrete relative ai diversi tipi di espressione (analogo all'esempio relativo ai parser top-down).
  
• expr.lex
  Il file di specifica lessicale è lo stesso delle versioni precedenti.
• Espressioni.java
  Applicazione Java per il calcolo delle espressioni, che utilizza il parser generato a partire dal file expr.cup precedente per costruire l'albero sintattico. L'albero viene attraversato per stampare l'espressione in notazione postfissa (metodo toString) e per calcolare il risultato (metodo calcola).

• Descrittore.java
  Le istanze di questa classe descrivono gli identificatori. In questo semplice esempio la descrizione è data dal nome dell'identificatore e dal valore intero a esso associato.
• SymbolTable.java
  La symbol table è implementata mediante un vettore di descrittori.
• expr.cup
  File di specifica sintattica per le espressioni aritmetiche. Rispetto alla versione precedente è stata aggiunta la produzione relativa agli identificatori e la variabile expr1, utilizzata come simbolo iniziale, corrispondente al riconoscimento dell'intera espressione.
  Il codice scritto nella sezione action code verrà riportato nella classe action interna al parser generato. Tale classe contiene tutte le azioni associate alle produzioni. In questo caso il codice è utilizzato per definire la variabile tabVariabili utilizzata poi per l'azione relativa alla produzione per gli identificatori.
• Expr.java
  Classe astratta Expr per la definizione dell'albero sintattico e sottoclassi concrete con esclusione di quella corrispondente agli identificatori (stesso file dell'esempio precedente).
  
  
• IdExpr.java
  Sottoclasse concreta di Expr corrispondente agli identificatori.
  
  
• ExprConTab.java
  Un'istanza della classe ExprConTab è un'espressione con associata una symbol table. Il metodo calcola di questa classe legge da input i valori da assegnare alle variabili ed effettua poi il calcolo dell'espressione (servendosi del metodo calcola di Expr).
• expr.lex
  File di specifica lessicale. Rispetto alle versioni precedenti è stato aggiunto il riconoscimento degli identificatori.
• Espressioni.java
  Applicazione Java per il calcolo delle espressioni, che utilizza il parser generato a partire dal file expr.cup precedente per costruire l'albero sintattico. L'albero viene attraversato per stampare l'espressione in notazione postfissa (metodo toString) e per calcolare il risultato (metodo calcola) dopo avere letto da input i valori delle variabili.

Generazione di codice

Negli esempi si utilizza una macchina a stack, implementata nella classe Macchina.java. Viene inoltre fornita la classe Codice.java, 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 compilare e utilizzare correttamente le classi si consiglia di definire all'interno di una directory lt2, una sottodirectory di nome macchina. La directory lt2 dovrà essere collocata in una posizione accessibile secondo la variabile d'ambiente CLASSPATH. I sorgenti delle due classi possono essere collocati in macchina e compilati.

I seguenti esempi 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, il seguente esempio rielabora quello delle espressioni con gli identificatori (file di specifica lessicale expr.lex, file di specifica sintattica expr.cup). Come nella versione precedente il parser produce un albero sintattico, secondo le definizioni date nella classe astratta Expr.java e nelle relative sottoclassi, corrispondenti ai tipi concreti di espressioni. Queste classi contengono un metodo generaCodice che si occupa di generare il codice relativo alla particolare sottoespressione considerata. Le classi ExprConTab.java, Descrittore.java e SymbolTable.java sono state modificate per questa nuova versione. Viene infine fornita la classe Espressioni.java contenente il metodo main.

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.

WebCounter segnala  accessi a queste pagine dal 22 febbraio 2000