Auf der Suche nach Lex und Yacc für Java? Du kennst Jack nicht

Sun hat Jack veröffentlicht, ein neues in Java geschriebenes Tool, das automatisch Parser generiert, indem es eine in einer Textdatei gespeicherte Grammatikspezifikation auf hoher Ebene kompiliert. Dieser Artikel dient als Einführung in dieses neue Tool. Der erste Teil des Artikels behandelt eine kurze Einführung in die automatische Parser-Generierung und meine ersten Erfahrungen mit ihnen. Dann konzentriert sich der Artikel auf Jack und wie Sie damit Parser und Anwendungen generieren können, die mit diesen Parsern erstellt wurden, basierend auf Ihrer Grammatik auf hoher Ebene.

Automatische Compiler-Parser-Generierung

Ein Parser ist eine der häufigsten Komponenten einer Computeranwendung. Es konvertiert Text, der von Menschen gelesen werden kann, in Datenstrukturen, sogenannte Analysebäume, die vom Computer verstanden werden. Ich erinnere mich deutlich an meine Einführung in die automatische Parser-Generierung: Im College hatte ich eine Klasse über Compiler-Konstruktion abgeschlossen. Mit der Hilfe meiner Frau hatte ich einen einfachen Compiler geschrieben, der Programme, die in einer für die Klasse bestimmten Sprache geschrieben waren, in ausführbare Programme umwandeln konnte. Ich erinnere mich, dass ich mich zu diesem Zeitpunkt sehr gut gefühlt habe.

In meinem ersten "richtigen" Job nach dem College bekam ich den Auftrag, eine neue Grafikverarbeitungssprache zu erstellen, um sie in Befehle für einen Grafik-Coprozessor zu kompilieren. Ich begann mit einer frisch komponierten Grammatik und bereitete mich darauf vor, das mehrwöchige Projekt der Zusammenstellung eines Compilers zu starten. Dann zeigte mir ein Freund die Unix-Dienstprogramme lex und yacc . Lex baute lexikalische Analysatoren aus regulären Ausdrücken und yacc reduzierte eine Grammatikspezifikation in einen tabellengesteuerten Compiler, der Code erzeugen konnte, wenn er Produktionen aus dieser Grammatik erfolgreich analysiert hatte. Ich habe Lex und Yacc verwendetund in weniger als einer Woche war mein Compiler betriebsbereit! Später produzierte das GNU-Projekt der Free Software Foundation "verbesserte" Versionen von Lex und Yacc - Flex und Bison genannt - zur Verwendung auf Plattformen, auf denen kein Derivat des Unix-Betriebssystems ausgeführt wurde.

Die Welt der automatischen Parser-Generierung entwickelte sich erneut, als Terrence Parr, damals Student an der Purdue University, das Purdue Compiler Construction Tool Set (PCCTS) erstellte. Zwei Komponenten von PCCTS - DFA und ANTLR - bieten dieselben Funktionen wie Lex und Yacc . Die Grammatiken, die ANTLR akzeptiert, sind jedoch LL (k) -Grammatiken im Gegensatz zu den von yacc verwendeten LALR-Grammatiken . Darüber hinaus ist der von PCCTS generierte Code viel besser lesbar als der von yacc generierte Code. Durch das Generieren von Code, der leichter zu lesen ist, erleichtert PCCTS einem Menschen, der den Code liest, leichter zu verstehen, was die verschiedenen Teile tun. Dieses Verständnis kann wichtig sein, wenn versucht wird, Fehler in der Grammatikspezifikation zu diagnostizieren. PCCTS entwickelte schnell eine Anhängerschaft von Leuten, die fanden, dass seine Dateien einfacher zu verwenden waren als yacc.

Die automatische Parser-Generierung ermöglicht es Benutzern, sich auf die Grammatik zu konzentrieren und sich nicht um die Richtigkeit der Implementierung zu kümmern. Dies kann sowohl bei einfachen als auch bei komplexen Projekten eine enorme Zeitersparnis bedeuten.

Jack tritt an den Teller

Ich bewerte Werkzeuge nach der Allgemeinheit des Problems, das sie lösen. Da die Anforderung, die Texteingabe zu analysieren, immer wieder auftaucht, ist die automatische Parser-Generierung in meiner Toolbox ziemlich hoch. In Kombination mit dem schnellen Entwicklungszyklus von Java bietet die automatische Parser-Generierung ein Tool für das Compiler-Design, das kaum zu übertreffen ist.

Jack (reimt sich auf yacc) ist ein Parser-Generator im Geiste von PCCTS, den Sun der Java-Programmier-Community kostenlos zur Verfügung gestellt hat. Jack ist ein außergewöhnlich einfach zu beschreibendes Tool: Einfach ausgedrückt, Sie geben ihm eine Reihe kombinierter Grammatik- und Lexierungsregeln in Form einer .jack-Datei und führen das Tool aus. Außerdem erhalten Sie eine Java-Klasse zurück, die diese Grammatik analysiert. Was könnte einfacher sein?

Jack in den Griff zu bekommen ist auch ziemlich einfach. Zuerst laden Sie eine Kopie von der Jack-Homepage herunter. Dies kommt zu Ihnen in Form einer selbst entpackenden Java-Klasse namens install. Um Jack zu installieren, müssen Sie diese installKlasse aufrufen. Auf einem Windows 95-Computer wird der folgende Befehl ausgeführt : C:>java install.

Der oben gezeigte javaBefehl setzt voraus, dass sich der Befehl in Ihrem Befehlspfad befindet und dass der Klassenpfad entsprechend eingerichtet wurde. Wenn der obige Befehl nicht funktioniert hat oder Sie nicht sicher sind, ob die Dinge richtig eingerichtet sind oder nicht, öffnen Sie ein MS-DOS-Fenster, indem Sie die Menüelemente Start-> Programme-> MS-DOS-Eingabeaufforderung durchlaufen. Wenn Sie das Sun JDK installiert haben, können Sie folgende Befehle eingeben:

C:> Pfad C: \ java \ bin;% Pfad% C:> setze CLASSPATH =.; C: \ java \ lib \ classes.zip 

Wenn Symantec Cafe Version 1.2 oder höher installiert ist, können Sie folgende Befehle eingeben:

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

Der Klassenpfad sollte bereits in einer Datei namens sc.ini im bin-Verzeichnis von Cafe eingerichtet sein.

Geben Sie als Nächstes den java installBefehl von oben ein. Das Installationsprogramm fragt Sie, in welches Verzeichnis Sie installieren möchten, und das Jack-Unterverzeichnis wird darunter erstellt.

Mit Jack

Jack ist vollständig in Java geschrieben. Wenn Sie also die Jack-Klassen haben, ist dieses Tool sofort auf jeder Plattform verfügbar, die die virtuelle Java-Maschine unterstützt. Dies bedeutet jedoch auch, dass Sie auf Windows-Boxen Jack über die Befehlszeile ausführen müssen. Angenommen, Sie haben den Verzeichnisnamen JavaTools gewählt, als Sie Jack auf Ihrem System installiert haben. Um Jack zu verwenden, müssen Sie Jacks Klassen zu Ihrem Klassenpfad hinzufügen. Sie können dies in Ihrer autoexec.bat- Datei oder in Ihrer .cshrc- Datei tun, wenn Sie ein Unix-Benutzer sind. Der kritische Befehl entspricht in etwa der folgenden Zeile:

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

Note that Symantec Cafe users can edit the sc.ini file and include the Jack classes there, or they can set CLASSPATH explicitly as shown above.

Setting the environment variable as shown above puts the Jack classes in the CLASSPATH between "." (the current directory) and the base system classes for Java. The main class for Jack is COM.sun.labs.jack.Main. Capitalization is important! There are exactly four capital letters in the command ('C', 'O', 'M', and another 'M'). To run Jack manually, type the command:

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

If you don't have the Jack files in your class path, you can use this command:

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

As you can see, this gets a bit long. To minimize typing, I put the invocation into a .bat file named Jack.bat. At some point in the future, a simple C wrapper program will become available, perhaps even as you read this. Check out the Jack home page for the availability of this and other programs.

When Jack is run, it creates several files in the current directory that you will later compile into your parser. Most are either prefixed with the name of your parser or are common to all parsers. One of these, however, ASCII_CharStream.java, may collide with other parsers, so it is probably a good idea to start off in a directory containing only the .jack file you are going to use to generate the parser.

Once you run Jack, if the generation has gone smoothly you will have a bunch of .java files in the current directory with various interesting names. These are your parsers. I encourage you to open them up with an editor and look them over. When you are ready you can compile them with the command

C:> javac -d . ParserName.java

where ParserName is the name you gave your parser in the input file. More on that in a bit. If all of the files for your parser don't compile, you can use the brute force method of typing:

C:> javac *.java 

This will compile everything in the directory. At this point your new parser is ready to use.

Jack parser descriptions

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 : { }    

Diese Definitionen decken die grundlegenden Terminals ab, in denen die Grammatik angegeben ist. Das erste mit dem Namen IGNORE_IN_BNF ist ein spezielles Token. Alle vom Parser gelesenen Token, die mit den in einem IGNORE_IN_BNF- Token definierten Zeichen übereinstimmen, werden stillschweigend verworfen. Wie Sie in unserem Beispiel sehen können, ignoriert der Parser Leerzeichen, Tabulatoren und Wagenrücklaufzeichen in der Eingabe.