Cerchi lex e yacc per Java? Non conosci Jack

Sun ha rilasciato Jack, un nuovo strumento scritto in Java che genera automaticamente parser compilando una specifica grammaticale di alto livello memorizzata in un file di testo. Questo articolo servirà come introduzione a questo nuovo strumento. La prima parte dell'articolo copre una breve introduzione alla generazione automatica di parser e le mie prime esperienze con essi. Quindi l'articolo si concentrerà su Jack e su come utilizzarlo per generare parser e applicazioni costruite con quei parser, in base alla tua grammatica di alto livello.

Generazione automatica del parser del compilatore

Un parser è uno dei componenti più comuni di un'applicazione per computer. Converte il testo che può essere letto dagli esseri umani in strutture di dati note come alberi di analisi, che vengono compresi dal computer. Ricordo distintamente la mia introduzione alla generazione automatica di parser: al college avevo completato un corso sulla costruzione del compilatore. Con l'aiuto di mia moglie, avevo scritto un semplice compilatore che poteva trasformare programmi scritti in un linguaggio composto per la classe in programmi eseguibili. Ricordo di essermi sentito molto realizzato a quel punto.

Nel mio primo "vero" lavoro dopo il college, ho ricevuto l'incarico di creare un nuovo linguaggio di elaborazione grafica da compilare in comandi per un coprocessore grafico. Ho iniziato con una grammatica appena composta e mi sono preparato a lanciarmi nel progetto multi-settimanale di mettere insieme un compilatore. Poi un amico mi ha mostrato le utilità Unix lex e yacc . Lex ha costruito analizzatori lessicali da espressioni regolari e yacc ha ridotto una specifica grammaticale in un compilatore basato su tabelle che poteva produrre codice dopo aver analizzato con successo le produzioni di quella grammatica. Ho usato lex e yacce in meno di una settimana il mio compilatore era attivo e funzionante! Successivamente, il progetto GNU della Free Software Foundation ha prodotto versioni "migliorate" di lex e yacc - chiamate flex e bison - per l'uso su piattaforme che non eseguivano un derivato del sistema operativo Unix.

Il mondo della generazione automatica del parser è avanzato di nuovo quando Terrence Parr, allora studente della Purdue University, ha creato il Purdue Compiler Construction Tool Set o PCCTS. Due componenti di PCCTS - DFA e ANTLR - forniscono le stesse funzioni di lex e yacc ; tuttavia le grammatiche che ANTLR accetta sono grammatiche LL (k) in contrapposizione alle grammatiche LALR utilizzate da yacc . Inoltre, il codice generato da PCCTS è molto più leggibile del codice generato da yacc. Generando codice che è più facile da leggere, PCCTS rende più facile per un essere umano che legge il codice capire cosa stanno facendo i vari pezzi. Questa comprensione può essere essenziale quando si cerca di diagnosticare errori nelle specifiche grammaticali. PCCTS ha sviluppato rapidamente un seguito di persone che hanno trovato i suoi file più facili da usare rispetto a yacc.

La potenza della generazione automatica di parser è che consente agli utenti di concentrarsi sulla grammatica e non preoccuparsi della correttezza dell'implementazione. Questo può essere un enorme risparmio di tempo sia in progetti semplici che complessi.

Jack si avvicina al piatto

Valuto gli strumenti in base alla generalità del problema che risolvono. Poiché la necessità di analizzare l'input di testo si ripresenta ancora e ancora, la generazione automatica di parser è piuttosto alta nella mia cassetta degli attrezzi. In combinazione con il rapido ciclo di sviluppo di Java, la generazione automatica di parser fornisce uno strumento per la progettazione del compilatore difficile da battere.

Jack (fa rima con yacc) è un generatore di parser, nello spirito di PCCTS, che Sun ha rilasciato gratuitamente alla comunità di programmazione Java. Jack è uno strumento eccezionalmente facile da descrivere: in poche parole, gli dai una serie di regole grammaticali e lessicali combinate sotto forma di un file .jack ed esegui lo strumento, e ti restituisce una classe Java che analizzerà quella grammatica. Cosa potrebbe esserci di più facile?

Anche entrare in contatto con Jack è abbastanza facile. Per prima cosa scarichi una copia dalla home page di Jack. Questo ti arriva sotto forma di una classe Java auto-decompressa chiamata install. Per installare Jack è necessario richiamare questa installclasse, che, su un computer Windows 95 viene fatto usando il comando: C:>java install.

Il comando mostrato sopra presuppone che il javacomando si trovi nel percorso del comando e che il percorso della classe sia stato impostato in modo appropriato. Se il comando precedente non ha funzionato o se non sei sicuro di aver impostato correttamente le cose, apri una finestra di MS-DOS attraversando le voci del menu Start-> Programmi-> Prompt di MS-DOS. Se hai installato Sun JDK, puoi digitare questi comandi:

C:> percorso C: \ java \ bin;% percorso% C:> set CLASSPATH = .; c: \ java \ lib \ classes.zip 

Se è installato Symantec Cafe versione 1.2 o successiva, è possibile digitare questi comandi:

C:> percorso C: \ cafe \ java \ bin;% percorso% 

Il percorso della classe dovrebbe già essere impostato in un file chiamato sc.ini nella directory bin di Cafe.

Quindi, digita il java installcomando dall'alto. Il programma di installazione ti chiederà in quale directory desideri eseguire l'installazione e la sottodirectory Jack verrà creata sotto di essa.

Usando Jack

Jack è scritto interamente in Java, quindi avere le classi Jack significa che questo strumento è immediatamente disponibile su ogni piattaforma che supporta la macchina virtuale Java. Tuttavia, significa anche che sulle scatole Windows devi eseguire Jack dalla riga di comando. Supponiamo che tu abbia scelto il nome della directory JavaTools quando hai installato Jack sul tuo sistema. Per usare Jack dovrai aggiungere le classi di Jack al tuo percorso di classe. Puoi farlo nel tuo file autoexec.bat o nel tuo file .cshrc se sei un utente Unix. Il comando critico è qualcosa come la riga mostrata di seguito:

C:> set CLASSPATH = .; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ classes.zip 

Si noti che gli utenti di Symantec Cafe possono modificare il file sc.ini e includervi le classi Jack, oppure possono impostare CLASSPATHesplicitamente come mostrato sopra.

L'impostazione della variabile d'ambiente come mostrato sopra mette le classi Jack CLASSPATHtra "." (la directory corrente) e le classi di sistema di base per Java. La lezione principale per Jack è COM.sun.labs.jack.Main. Le maiuscole sono importanti! Ci sono esattamente quattro lettere maiuscole nel comando ("C", "O", "M" e un'altra "M"). Per eseguire Jack manualmente, digita il comando:

C:> java COM.sun.labs.jack.Main parser-input.jack

Se non hai i file Jack nel tuo percorso di classe, puoi usare questo comando:

C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ classes.zip COM.sun.labs.jack.Main parser-input.jack 

Come puoi vedere, questo diventa un po 'lungo. Per ridurre al minimo la digitazione, inserisco l'invocazione in un file .bat denominato Jack.bat . Ad un certo punto in futuro, sarà disponibile un semplice programma wrapper C, forse anche mentre leggi questo. Controlla la home page di Jack per la disponibilità di questo e altri programmi.

Quando Jack viene eseguito, crea diversi file nella directory corrente che successivamente compilerai nel tuo parser. La maggior parte è preceduta dal nome del tuo parser o è comune a tutti i parser. Uno di questi, tuttavia, ASCII_CharStream.javapotrebbe entrare in conflitto con altri parser, quindi è probabilmente una buona idea iniziare in una directory contenente solo il file .jack che utilizzerai per generare il parser.

Una volta eseguito Jack, se la generazione è andata a buon fine, avrai un mucchio di .javafile nella directory corrente con vari nomi interessanti. Questi sono i tuoi parser. Ti incoraggio ad aprirli con un editore e esaminarli. Quando sei pronto puoi compilarli con il comando

C:> javac -d. ParserName.java

dov'è ParserNameil nome che hai dato al tuo parser nel file di input. Ne parleremo tra un po '. Se tutti i file per il tuo parser non vengono compilati, puoi utilizzare il metodo della forza bruta per digitare:

C:> javac * .java 

Questo compilerà tutto nella directory. A questo punto il tuo nuovo parser è pronto per l'uso.

Descrizioni del parser di Jack

Jack parser description files have the extension .jack and are divided into three basic parts: options and base class; lexical tokens; and non-terminals. Let's look at a simple parser description (this is included in the examples directory that comes with Jack).

options { LOOKAHEAD = 1; } PARSER_BEGIN(Simple1) public class Simple1 { public static void main(String args[]) throws ParseError { Simple1 parser = new Simple1(System.in); parser.Input(); } } PARSER_END(Simple1) 

The first few lines above describe options for the parser; in this case LOOKAHEAD is set to 1. There are other options, such as diagnostics, Java Unicode handling, and so on, that also can be set here. Following the options comes the base class of the parser. The two tags PARSER_BEGIN and PARSER_END bracket the class that becomes the base Java code for the resulting parser. Note that the class name used in the parser specification must be the same in the beginning, middle, and ending part of this section. In the example above, I've put the class name in bold face to make this clear. As you can see in the code above, this class defines a static main method so that the class can be invoked by the Java interpreter on the command line. The main method simply instantiates a new parser with an input stream (in this case System.in) and then invokes the Input method. The Input method is a non-terminal in our grammar, and it is defined in the form of an EBNF element. EBNF stands for Extended Backus-Naur Form. The Backus-Naur form is a method for specifying context-free grammars. The specification consists of a terminal on the left-hand side, a production symbol, which is typically "::=", and one or more productions on the right-hand side. The notation used is typically something like this:

 Keyword ::= "if" | "then" | "else" 

This would be read as, "The Keyword terminal is one of the string literals 'if', 'then', or 'else.'" In Jack, this form is extended to allow the left-hand part to be represented by a method, and the alternate expansions may be represented by regular expressions or other non-terminals. Continuing with our simple example, the file contains the following definitions:

void Input() : {} { MatchedBraces() "\n"  } void MatchedBraces() : {} { "{" [ MatchedBraces() ] "}" } 

This simple parser parses the grammar shown below:

Input ::= MatchedBraces "\n"
MatchedBraces ::= "{" [ MatchedBraces ] "}"

I've used italics to show the non-terminals on the right side of the productions and boldface to show literals. As you can see, the grammar simply parses matched sets of brace "{" and "}" characters. There are two productions in the Jack file to describe this grammar. The first terminal, Input, is defined by this definition to be three items in sequence: a MatchedBraces terminal, a newline character, and an end-of-file token. The token is defined by Jack so that you don't have to specify it for your platform.

When this grammar is generated, the left-hand sides of the productions are turned into methods inside the Simple1 class; when compiled, the Simple1 class reads characters from System.in and verifies that they contain a matching set of braces. This is accomplished by invoking the generated method Input, which is transformed by the generation process into a method that parses an Input non-terminal. If the parse fails, the method throws the exception ParseError, which the main routine can catch and then complain about if it so chooses.

Of course there's more. The block delineated by "{" and "}" after the terminal name -- which is empty in this example -- can contain arbitrary Java code that is inserted at the front of the generated method. Then, after each expansion, there is another optional block that can contain arbitrary Java code to be executed when the parser successfully matches that expansion.

A more complicated example

So how about an example that's a bit more complicated? Consider the following grammar, again broken down into pieces. This grammar is designed to interpret mathematical equations using the four basic operators -- addition, multiplication, subtraction, and division. The source can be found here:

options { LOOKAHEAD=1; } PARSER_BEGIN(Calc1) public class Calc1 { public static void main(String args[]) throws ParseError { Calc1 parser = new Calc1(System.in); while (true) { System.out.print("Enter Expression: "); System.out.flush(); try { switch (parser.one_line()) { case -1: System.exit(0); default: break; } } catch (ParseError x) { System.out.println("Exiting."); throw x; } } } } PARSER_END(Calc1) 

The first part is nearly the same as Simple1, except that the main routine now calls the terminal one_line repeatedly until it fails to parse. Next comes the following code:

IGNORE_IN_BNF : {}  " "  TOKEN : { } {  } TOKEN : /* OPERATORS */ { }    TOKEN : { }    

Queste definizioni coprono i terminali di base in cui è specificata la grammatica. Il primo, denominato IGNORE_IN_BNF , è un token speciale. Tutti i token letti dal parser che corrispondono ai caratteri definiti in un token IGNORE_IN_BNF vengono eliminati silenziosamente. Come puoi vedere nel nostro esempio, questo fa sì che il parser ignori caratteri di spazio, tabulazioni e caratteri di ritorno a capo nell'input.