Mokabyte Numero 7 - Aprile 1997 - Interprete di espressioni

		MokaByte Numero 07 - Aprile 1997

		Interprete di espressioni I parte
	di Rafael Andrés Marín de la Cruz	Analisi liessicale con l'ausilio della classe java.io.StreamTokenizer

Questo è il primo di tre articoli che avranno come obiettivo lo sviluppo di un interprete di espressioni. Nel corso di questi articoli si affronteranno tematiche di teoria di linguaggi e tecniche di compilazione; verranno inoltre descritte alcune classi Java, che saranno impiegate nel corso dell’implementazione: java.io.StreamTokenizer, java.util.HashTable, java.util.Vectore java.util.Stack.

La funzione dell’interprete è quella di accertare la validità delle espressioni e calcolare il risultato di esse. La verifica delle espressioni viene fatta attraverso le diverse fasi di analisi: lessicale, sintattica e semantica; nel calcolo invece intervengono la generazione e l’esecuzione di codice. La distribuzione delle diverse fasi nei tre articoli è la seguente:

Analisi lessicale
Analisi sintattica
Analisi semantica, generazione ed esecuzione di codice.

Ogni articolo avrà un applet dimostrativo delle tematiche che sono state affrontate.

La realizzazione di qualsiasi interprete prevede principalmente due processi di elaborazione: compilazione e interpretazione. Nella compilazione si verifica che l’input sia conforme alle specifiche del linguaggio per il quale è stato disegnato, e si genera il codice che rappresenta questo input. Nel processo di interpretazione viene eseguito il codice generato in compilazione. Se prendiamo Java come esempio di interprete, possiamo vedere, nella figura 1, che questi processi sono ben definiti. La maggioranza degli interpreti seguono questo schema, solo una minoranza di essi svolgono direttamente le azioni man mano che analizzano l’input. C’è da segnalare che in alcuni interpreti (es. Java) il codice, prima di venire eseguito, viene verificato contro eventuali errori o manomissioni.

Le fasi del processo di compilazione sono le seguenti:

Analisi lessicale: verifica che i caratteri di input appartengano all’insieme (alfabeto) di caratteri permessi dal linguaggio; inoltre consegna i tokens (v. definizione di seguito) all’analizzatore sintattico.
Analisi sintattica: controlla che l’input soddisfi le regole grammaticali del linguaggio.
Analisi semantica: verifica l’esistenza di eventuali errori semantici come la concordanza dei tipi con gli operatori, la dichiarazione delle variabili, ecc.
Generazione di codice intermedio: genera il codice intermedio corrispondente all’input accettato.
Ottimizzazione del codice: tenta di migliorare in velocità e/o in spazio il codice generato nella fase precedente. Alcune di queste ottimizzazioni sono triviali, come per esempio l’eliminazione di espressioni costanti all’interno delle espressioni (es. 10*2+x+2è uguale a 22+x).
Generazione di codice: fase finale dove viene generato il codice per il target (processore o interprete) a partire da quello ottimizzato.

Nel nostro caso specifico non avremmo le fasi di generazione di codice intermedio e ottimizzazione, anche se non escludo la possibilità di esporre in un altro articolo l’eliminazione di espressioni costanti all’interno delle espressioni.

In un linguaggio certe combinazioni di caratteri vengono trattate come singole entità. Alcuni esempi di queste possono essere: numeri, identificatori, operatori a più di un carattere come "&&", ecc. Il lavoro di un analizzatore lessicale è quello di estrarre queste singole entità, chiamate tokens, escludendo quei caratteri che non hanno un preciso significato (es. spazi, tabulazioni, ecc.). Le premesse per costruire un analizzatore lessicale sono le seguenti:

Definizione dell’alfabeto di caratteri del linguaggio (es. [‘+’,’*’,’0’..’9’]).
Definizione dei tipi di tokens (es. numero, variabile, operatore, ecc.).

Le espressioni tipo per questo interprete potranno contenere: numeri con punto decimale, variabili, associazione con parentesi, e operazioni di moltiplicazione, somma, sottrazione e divisione. Alcuni esempi sono: a, -var+2, 4-2, 4.5 * (x+333), Base_Somma * percentuale / 100.

Di seguito vengono riportate le definizioni formali di alfabeto e token per queste espressioni.

Alfabeto: [ ‘0’..’9’ | ‘a’..’z’ | ‘A’..’Z’ | ‘_’ | ‘+’ | ‘-‘ | ‘*’ | ‘/’ | ‘(‘ | ‘)’ | ‘ ‘ | ‘\t’ | ‘\r’ | ‘\n’ ].

Tipi di tokens sopportati:

Operatore: [ ‘*’, ‘+’ , ‘-‘ , ‘/’ ]
Numero: [ ‘0’..’9’ ]+ [ ‘.’ ]* [ ‘0’..’9’ ]+ (es. 9, 123, 2.45, .4)
Simbolo: [ '(' , ')' ]
Variabile: [ 'A'..'Z' , 'a'..'z' , '_' ] [ 'A'..'Z' , 'a'..'z' , '_' , ‘0’..’9’ ]*(es. x, val, _x, v12, y_32_old)

Adesso possiamo procedere con la definizione delle classi Java che rappresentano i diversi tipi di tokens. Innanzitutto dobbiamo definire una super classe che raggruppi tutti i tipi di tokens e che ne detenga l’identificatore di tipo di token.

18    class GenericToken {
19        public static final int SYMBOL = 0;
20        public static final int VARIABLE = 1;
21        public static final int NUMBER = 2;
22        public static final int OPERATOR = 3;
23        public static final int EOE = 4;
25        int tk_type;
26
28        public GenericToken( int _tk_type ) {
29            tk_type = _tk_type;
30        }
32        public int getType() {
33            return tk_type;
34        }
36        public String toString() {
37            String s;
38
39            switch (getType()) {
40                case SYMBOL:   s = "SIMBOLO "; break;
41                case VARIABLE: s = "VARIABILE"; break;
42                case NUMBER:   s = "NUMERO   "; break;
43                case OPERATOR: s = "OPERATORE"; break;
44                case EOE:      s = "FINE DI ESPRESSIONE"; break;
45                default: s = "NONE";
46            }
48            return s;
49        }
50    }

All’inizio della classe si trovano le costanti che rappresentano i diversi tipi di token. L’identifcatore EOEci serve per rilevare la fine della espressione. Il metodo toString() ci fornisce una rappresentazione a caratteri del tipo di token, e può essere utilizzato per inserire delle tracce all’interno del programma.

Dichiarazione delle classe derivanti da GenericToken.

53    class SymbolToken extends GenericToken {
54        char symbol;
55
56        public SymbolToken( char _symbol ) {
57            super(SYMBOL);
58            symbol = _symbol;
59        }
61        public char getSymbol() {
62            return symbol;
63        }
65        public String toString() {
66            return super.toString()+" -> "+"\""+getSymbol()+"\"";
67        }
68    }
71
72    class NumberToken extends GenericToken {
73        double val;
74
75        public NumberToken( double _val ) {
76            super(NUMBER);
77            val = _val;
78        }
80        public double getValue() {
81            return val;
82        }
84        public String toString() {
85            return super.toString()+" -> "+String.valueOf(getValue());
86        }
87    }
89
90    class VariableToken extends GenericToken {
91        String varname;
92
93        public VariableToken( String _varname ) {
94            super(VARIABLE);
95            varname = _varname;
96        }
98        public String getName() {
99            return varname;
100       }
102       public String toString() {
103           return super.toString()+" -> "+getName();
104       }
105   }
107
108   class OperatorToken extends GenericToken {
109       public static final int ADD = 0;
110       public static final int SUB = 1;
111       public static final int MUL = 2;
112       public static final int DIV = 3;
113       public static final int MINUS = 4;
115       int op;
116
117       public OperatorToken( int _op ) {
118           super(OPERATOR);
119           op = _op;
120       }
122       public int getOp() {
123           return op;
124       }
126       public int getArity() {
127           switch (getOp()) {
128               case ADD: return 2;
129               case SUB: return 2;
130               case MUL: return 2;
131               case DIV: return 2;
132               case MINUS: return 1;
133               default: return 0;
134           }
135       }
137       public double doOp( NumberToken left, NumberToken right ) throws ArithmeticException {

138           switch (getOp()) {
139               case ADD: return left.getValue()+right.getValue();
140               case SUB: return left.getValue()-right.getValue();
141               case MUL: return left.getValue()*right.getValue();
142               case DIV:
143                   if (right.getValue()==0)
144                       throw new ArithmeticException();
145                   else
146                       return left.getValue()/right.getValue();
147               case MINUS: return -left.getValue();
148               default: return 0;
149           }
150       }
152       public String toString() {
153           String s;
154
155           switch (getOp()) {
156               case ADD : s = "ADD(+)"; break;
157               case SUB : s = "SUB(-)"; break;
158               case MUL : s = "MUL(x)"; break;
159               case DIV : s = "DIV(/)"; break;
160               case MINUS: s = "MINUS(-)"; break;
161               default: s = "NONE"; break;
162           }
164           return super.toString()+" -> "+s;
165       }
166   }
Tutte le classi hanno una rappresentazione a caratteri delle loro proprietà attraverso il metodo toString(). Il metodo OperatorToken.getArity (r.126) fornisce la quantità di argomenti dell’operatore. Il metodo OperatorToken.doOp(r.137) realizzerà il calcolo assegnato all’operatore, prendendo come argomenti i valori dei due tokens numerici passati come parametri; nel caso che l’operatore sia unitario, il parametro da prendere sarà il primo. E’ da notare che l’operatore MINUSnon ha nessuna rilevanza dal punto di vista lessicale o sintattico, dato che la sua rappresentazione è uguale a SUB; il suo utilizzo sarà necessario nella fase di generazione del codice.
L’analizzatore lessicale è stato implementato in una nuova classe chiamata LexicalAnalizer. La spiegazione di questa classe sarà fatta attraverso i diversi pezzi del suo codice.
169   class LexicalAnalizer {
170       StreamTokenizer st;
172
173       public LexicalAnalizer( InputStream is ) {
174           st = new StreamTokenizer(is);
175           st.lowerCaseMode(true);
176           st.ordinaryChar('/');
177           st.ordinaryChar('+');
178           st.ordinaryChar('-');
179           st.ordinaryChar('*');
180           st.ordinaryChar('.');
181           st.ordinaryChars(124,255);
182           st.wordChars('_','_');
183           st.eolIsSignificant(false);
184       }

L’unica variabile è un oggetto di tipo StreamTokenizer, il quale ci servirà come analizzatore lessicale primario. Il costruttore della classe riceve un InputStream dal quale verranno letti i caratteri nella classe StreamTokenizer(r.174). Le altre istruzioni servono ad aggiustare alcuni parametri che sono diversi da quelle di default, vediamoli di seguito con più dettaglio.

lowerCaseMode(r.175) è stato messo a trueper convertire a minuscole le parole; in questo modo si ottiene di non fare distinzione tra maiuscole e minuscole nei nomi delle variabili.
ordinaryChar(‘/’) – ordinaryChar(‘*’)(r.176-179) servono a far ritornare questi caratteri come singole unità e non come parte di un'altra composizione lessicale (es. commenti /* , numero negativo -–, ecc.).
ordinaryChar(‘.’)(r.180) serve a far ritornare come singola unità il carattere '.'; con questo si riesce ad escludere questo carattere dai nomi delle variabili.
ordinaryChars(124,255)(r.181) serve a far ritornare come singole unità i caratteri estesi; con questo si riesce ad escludere questi caratteri dai nomi delle variabili.
wordChars(‘_’,’_’) (r182) indica che il carattere ‘_’ formerà parte delle parole, permettendo così il riconoscimento delle variabili che contengono questo carattere (es. produzione_annuale). Le lettere dell’alfabeto (es. ‘A’, ’a’, ’B’, ecc.) sono automaticamente definite come "wordChars" nel costruttore della classe.
eolIsSignificant(false) (r183) fa considerare il cambio di riga come un spazio bianco da scartare.

185       public GenericToken nextToken()
186         throws IOException, LexicalError {
187           int t;
188
189           t = st.nextToken();
191           switch (t) {
192               case st.TT_EOF: return new GenericToken(GenericToken.EOE);
193               case st.TT_NUMBER: return new NumberToken(st.nval);
194               case st.TT_WORD: return new VariableToken(st.sval);
195               case '+': return new OperatorToken(OperatorToken.ADD);
196               case '-': return new OperatorToken(OperatorToken.SUB);
197               case '*': return new OperatorToken(OperatorToken.MUL);
198               case '/': return new OperatorToken(OperatorToken.DIV);
199               case '(': case ')': return new SymbolToken((char)t);
200               default: throw new LexicalError("Carattere non valido \'"+(char)t+"\' ("+t+").");
201           }
202       }

Il metodo StreamTokenizer.nextToken(r.189) ci ritorna il tipo del token appena analizzato. I valori possibili per questo ritorno sono:

TT_EOF: si è arrivati alla fine dell’InputStream.
TT_EOL: si è arrivati alla fine della riga.
TT_WORD: è stato trovata una sequenza di caratteri ("parola") appartenenti all’insieme di wordChars, e il suo valore si incontra nella variabile StreamTokenizer.sval.
TT_NUMBER: è stato riconosciuto un numero, e il suo valore si trova nella variabile StreamTokenizer.nval.

Quando il tipo non è uguale a nessuno di questi, vuol dire che si tratta di uno dei caratteri definiti come "ordinary". Nel caso che un carattere non appartenga all’alfabeto delle espressioni, viene sollevata l’eccezione LexicalError (r.200). Questa eccezione è stata definita come una semplice estensione di Exception, e ci servirà a distinguere la provenienza degli errori di compilazione.

Oltre all’utilizzo che abbiamo fatto della classe StreamTokenizer, questa ci permette anche di riconoscere delle stringhe delimitate tra caratteri (es. "Questa è una stringa"). Per default il carattere delimitante è virgolette ("), ma può essere cambiato con il metodo quoteChar(int carattere). Quando una stringa viene riconosciuta, nextToken() ritorna il carattere delimitante e in svalviene depositata la stringa. Di seguito riportiamo un esempio con le stringhe Pascal (es. ‘apostrofi’).

Standard Input: ‘questa è una stringa’

Inizializzazione: quoteChar(‘\’’);

Riconoscimento:

StreamTokenizer st = new StreamTokenizer(System.in);

int t;

t = st.nextToken();

if (t==’\’’) System.out.println(st.sval);
Standard Output: questa è una stringa

Con i metodi commentChar, slashSlashCommentse slashStarCommentssi può gestire la permissività di commenti all’interno dell’input. Consultare la documentazione dello JDK per un approfondimento di questi metodi.

L’utilizzo della classe LexicalAnalizerverrà esemplificato con l’applet che si trova di fianco. I caratteri di input all’analizzatore devono essere inseriti nella casella di testo sotto "Espressione". Per eseguire l’analisi premere Invionella casella o premere il pulsante "Analisi Lessicale". I token ottenuti ed eventuali messaggi di errore saranno visualizzati nella casella "Risultati". Il sucesso dell'analisi viene notificato con un messaggio nella barra di stato del browser.

Di seguito faremo i commenti ai frammenti più rilevanti dell’applet.

4     public class ex1 extends java.applet.Applet {
5         List    li;
6         TextField edExpr;
7
8         public void init() {
9             /* Creazione e disposizione dei componenti nell'applet.
10               Il codice non è stato inserito per ragioni di spazio
11               ma i sorgenti completi possono essere scaricati come
12               indicato alla fine dell'articolo.                    */
40        }
56        void addError( Exception e ) {
57            li.addItem(e.toString());
58            li.select(li.countItems()-1);
59        }
61        void doIt() {
62            LexicalAnalizer la;
63            GenericToken gt;
64            boolean success = false;
65
66            try {
67                la = new LexicalAnalizer(new StringBufferInputStream(edExpr.getText()));
68                li.clear();
69                gt = la.nextToken();
70                while (gt.getType()!=GenericToken.EOE) {
71                    li.addItem(gt.toString());
72                    gt = la.nextToken();
73                }
74                success = true;
75            }
76            catch (IOException e) getAppletContext().showStatus(e.toString());
77            catch (LexicalError e) addError(e);
78            if (success)
79                getAppletContext().showStatus("Operazione completata con successo");
80            else
81                getAppletContext().showStatus("Operazione interrotta per errore");
82        }
84        public boolean handleEvent(Event evt) {
86            switch (evt.id) {
87                case Event.ACTION_EVENT: {
88                    if ("Analisi Lessicale".equals(evt.arg)) doIt();
89                    break;
90                }
91                case Event.KEY_PRESS: {
92                    if (evt.target instanceof TextField &&
93                        evt.key == '\n' ) doIt();
94                    break;
95                }
96            }
97            return false;
98        }
99    }

Nel metodo handleEvent(r.84) vengono catturati gli eventi di pressione del tasto Invioe del pulsante "Analisi Lessicale" per eseguire l’analisi nel metodo doIt (r.61).

La riga 67 crea una istanza della classe LexicalAnalizer usando come InputStreamil contenuto della casella "Espressione". Nella riga seguente viene pulito il contenuto della casella di elenco "Risultati". Dalla riga 69 alla 73 vengono aggiunti alla casella "Risultati", uno alla volta, tutti i tokens trovati. Se si verifica un errore, questo verrà catturato nelle istruzioni delle righe 76 e 77. La visualizzazione degli errori avviene con l’aggiunta del testo nella casella "Risultati" (r.57); dopodiché la riga viene selezionata (r.58) per garantire la sua visibilità. Le istruzioni finali del metododoIt(r.78-81) notificano, nella barra di stato, il successo dell’operazione.

Come avrete notato, la semplicità e la compattezza di implementazione della classe LexicalAnalizersi deve in grande misura alla classe Java StreamTokenizer, che costituisce un potenziale strumento in compiti di analisi lessicale come quello affrontato nel nostro caso. Nel prossimo articolo potremo vedere l’utilizzo, all’interno dell’analizzatore sintattico, della classe LexicalAnalizer.

Download

I sorgenti esposti possono essere scaricati ai seguenti indirizzi:

http://www.infomedia.it/………/LexicalAnalizer.java (classi GenericToken, NumberToken, VariableToken, SymbolToken, OperatorToken e LexicalAnalizer).
http://www.infomedia.it/………/ex1.java (applet di esempio).

Bibliografia

Documentazione API – JDK 1.0.2
"The theory of parsing, translation, and compiling", V. Aho and Jeffrey D. Ullman, 1973; ISBN 0-13-914564-8
"Peter Norton’s Guide to Java Programming", Peter Norton and William Stanek, 1996; ISBN 1-57521-088-6

Rafael Andrés Marín de la Cruz

Laureato in Matematica-Cibernetica all’Università dell’Avana (Cuba) nel 1990, da quattro anni vive e lavora a Milano. Con la sua società ha sviluppato software per non vedenti sotto DOS e un tool di installazione per Windows. Svolge inoltre consulenza, in qualità di progettista, nel campo delle telecomunicazioni.
Il suo sito si trova al seguente indirizzo: http://www.galactica.it/dialectica.

Può essere contattato tramite la redazione o direttamente all'indirizzo: dialectica.sas@galactica.it



	MokaByte rivista web su Java MokaByte ricerca nuovi collaboratori Chi volesse mettersi in contatto con noi può farlo scrivendo a mokainfo@mokabyte.it