Lexikalische Analyse und Java: Teil 1
Lexikalische Analyse und Analyse
Wenn Sie Java-Anwendungen schreiben, müssen Sie am häufigsten einen Parser erstellen. Parser reichen von einfach bis komplex und werden für alles verwendet, von der Betrachtung von Befehlszeilenoptionen bis zur Interpretation von Java-Quellcode. In der Dezember-Ausgabe von JavaWorld habe ich Ihnen Jack gezeigt, einen automatischen Parser-Generator, der Grammatikspezifikationen auf hoher Ebene in Java-Klassen konvertiert, die den in diesen Spezifikationen beschriebenen Parser implementieren. Diesen Monat zeige ich Ihnen die Ressourcen, die Java zum Schreiben gezielter lexikalischer Analysatoren und Parser bereitstellt. Diese etwas einfacheren Parser füllen die Lücke zwischen dem einfachen String-Vergleich und den komplexen Grammatiken, die Jack kompiliert.
Der Zweck von lexikalischen Analysatoren besteht darin, einen Strom von Eingabezeichen zu nehmen und sie in Token höherer Ebene zu dekodieren, die ein Parser verstehen kann. Parser verbrauchen die Ausgabe des lexikalischen Analysators und analysieren die Reihenfolge der zurückgegebenen Token. Der Parser ordnet diese Sequenzen einem Endzustand zu, der einer von möglicherweise vielen Endzuständen sein kann. Die Endzustände definieren die Zieledes Parsers. Wenn ein Endzustand erreicht ist, führt das Programm, das den Parser verwendet, eine Aktion aus - entweder das Einrichten von Datenstrukturen oder das Ausführen eines aktionsspezifischen Codes. Darüber hinaus können Parser anhand der Reihenfolge der verarbeiteten Token erkennen, wann kein legaler Endzustand erreicht werden kann. Zu diesem Zeitpunkt identifiziert der Parser den aktuellen Status als Fehlerstatus. Es liegt an der Anwendung, zu entscheiden, welche Aktion ausgeführt werden soll, wenn der Parser entweder einen Endzustand oder einen Fehlerzustand identifiziert.
Die Standard-Java-Klassenbasis enthält einige lexikalische Analysatorklassen, definiert jedoch keine allgemeinen Parser-Klassen. In dieser Spalte werde ich mich eingehend mit den mit Java gelieferten lexikalischen Analysatoren befassen.
Java lexikalische Analysatoren
Die Java-Sprachspezifikation, Version 1.0.2, definiert zwei lexikalische Analysatorklassen StringTokenizerund StreamTokenizer. Von ihrem Namen können Sie feststellen , dass ableiten StringTokenizerAnwendungen StringObjekte als seine Eingabe und StreamTokenizerVerwendungen InputStreamObjekte.
Die StringTokenizer-Klasse
Von den beiden verfügbaren lexikalischen Analysatorklassen ist die am einfachsten zu verstehende StringTokenizer. Wenn Sie ein neues StringTokenizerObjekt erstellen, nimmt die Konstruktormethode nominell zwei Werte an - eine Eingabezeichenfolge und eine Trennzeichenfolge. Die Klasse erstellt dann eine Folge von Token, die die Zeichen zwischen den Trennzeichen darstellen.
Als lexikalischer Analysator StringTokenizerkönnte formal wie unten gezeigt definiert werden.
[~ delim1, delim2, ..., delim N ] :: Token
Diese Definition besteht aus einem regulären Ausdruck, der mit jedem Zeichen außer den Trennzeichen übereinstimmt . Alle benachbarten übereinstimmenden Zeichen werden in einem einzigen Token gesammelt und als Token zurückgegeben.
Die häufigste Verwendung der StringTokenizerKlasse ist das Trennen einer Reihe von Parametern, z. B. eine durch Kommas getrennte Liste von Zahlen. StringTokenizerist in dieser Rolle ideal, da die Trennzeichen entfernt und die Daten zurückgegeben werden. Die StringTokenizerKlasse bietet auch einen Mechanismus zum Identifizieren von Listen, in denen "Null" -Token vorhanden sind. Sie würden Null-Token in Anwendungen verwenden, in denen einige Parameter entweder Standardwerte haben oder nicht in allen Fällen vorhanden sein müssen.
Das Applet unten ist ein einfaches StringTokenizerTraining. Die Quelle für das StringTokenizer-Applet befindet sich hier. Um das Applet zu verwenden, geben Sie einen zu analysierenden Text in den Eingabezeichenfolgenbereich ein und geben Sie dann eine Zeichenfolge aus Trennzeichen in den Trennzeichenfolgenbereich ein. Klicken Sie abschließend auf Tokenize! Taste. Das Ergebnis wird in der Token-Liste unter der Eingabezeichenfolge angezeigt und als ein Token pro Zeile organisiert.
Betrachten Sie als Beispiel eine Zeichenfolge "a, b, d", die an ein StringTokenizerObjekt übergeben wird, das mit einem Komma (,) als Trennzeichen erstellt wurde. Wenn Sie diese Werte in das obige Übungs-Applet einfügen, sehen Sie, dass das TokenizerObjekt die Zeichenfolgen "a", "b" und "d" zurückgibt. Wenn Sie feststellen wollten, dass ein Parameter fehlte, war es möglicherweise überraschend, dass Sie in der Token-Sequenz keinen Hinweis darauf sehen. Die Fähigkeit, fehlende Token zu erkennen, wird durch den Booleschen Wert "Rückgabetrennzeichen" aktiviert, der beim Erstellen eines TokenizerObjekts festgelegt werden kann. Wenn dieser Parameter bei der TokenizerErstellung festgelegt wird, wird auch jedes Trennzeichen zurückgegeben. Aktivieren Sie das Kontrollkästchen für Rückgabetrennzeichen im Applet oben und lassen Sie die Zeichenfolge und das Trennzeichen in Ruhe. Jetzt dieTokenizergibt "a, Komma, b, Komma, Komma und d" zurück. Indem Sie feststellen, dass Sie zwei Trennzeichen nacheinander erhalten, können Sie feststellen, dass die Eingabezeichenfolge ein "Null" -Token enthält.
Der Trick für eine erfolgreiche Verwendung StringTokenizerin einem Parser besteht darin, die Eingabe so zu definieren, dass das Trennzeichen nicht in den Daten angezeigt wird. Natürlich können Sie diese Einschränkung vermeiden, indem Sie sie in Ihrer Anwendung entwerfen. Die folgende Methodendefinition kann als Teil eines Applets verwendet werden, das in seinem Parameterstrom eine Farbe in Form von Rot-, Grün- und Blauwerten akzeptiert.
/ ** * Analysiert einen Parameter der Form "10,20,30" als * RGB-Tupel für einen Farbwert. * / 1 Farbe getColor (String name) {2 String data; 3 StringTokenizer st; 4 int rot, grün, blau; 5 6 data = getParameter (name); 7 if (data == null) 8 return null; 9 10 st = neuer StringTokenizer (Daten, ","); 11 try {12 red = Integer.parseInt (st.nextToken ()); 13 grün = Integer.parseInt (st.nextToken ()); 14 blue = Integer.parseInt (st.nextToken ()); 15} catch (Ausnahme e) {16 return null; // (ERROR STATE) konnte es nicht analysieren 17} 18 return new Color (rot, grün, blau); // (END STATE) fertig. 19}
Der obige Code implementiert einen sehr einfachen Parser, der die Zeichenfolge "Nummer, Nummer, Nummer" liest und ein neues ColorObjekt zurückgibt . In Zeile 10 erstellt der Code ein neues StringTokenizerObjekt, das die Parameterdaten enthält (vorausgesetzt, diese Methode ist Teil eines Applets), und eine Trennzeichenliste, die aus Kommas besteht. Dann wird in den Zeilen 12, 13 und 14 jedes Token aus der Zeichenfolge extrahiert und unter Verwendung der Integer- parseIntMethode in eine Zahl umgewandelt . Diese Konvertierungen sind von einem try/catchBlock umgeben, falls die Zahlenzeichenfolgen keine gültigen Zahlen waren oder die TokenizerAuslöser eine Ausnahme darstellen, da keine Token mehr vorhanden sind. Wenn alle Zahlen konvertiert sind, ist der Endzustand erreicht und ein ColorObjekt wird zurückgegeben. Andernfalls wird der Fehlerstatus erreicht und null zurückgegeben.
Ein Merkmal der StringTokenizerKlasse ist, dass sie leicht gestapelt werden kann. Schauen Sie sich die getColorunten genannte Methode an , die die Zeilen 10 bis 18 der obigen Methode enthält.
/ ** * Analysiere ein Farbtupel "r, g, b" in ein AWT- ColorObjekt. * / 1 Farbe getColor (String data) {2 int rot, grün, blau; 3 StringTokenizer st = neuer StringTokenizer (Daten, ","); 4 try {5 red = Integer.parseInt (st.nextToken ()); 6 grün = Integer.parseInt (st.nextToken ()); 7 blue = Integer.parseInt (st.nextToken ()); 8} catch (Ausnahme e) {9 return null; // (ERROR STATE) konnte es nicht analysieren 10} 11 return new Color (rot, grün, blau); // (END STATE) fertig. 12}
Ein etwas komplexerer Parser wird im folgenden Code gezeigt. Dieser Parser ist in der Methode implementiert getColors, die definiert ist, um ein Array von ColorObjekten zurückzugeben.
/ ** * Analysiere eine Reihe von Farben "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" in * ein Array von AWT-Farbobjekten. * / 1 Color [] getColors (String data) {2 Vector accum = new Vector (); 3 Farbe cl, Ergebnis []; 4 StringTokenizer st = neuer StringTokenizer (Daten, ":"); 5 while (st.hasMoreTokens ()) {6 cl = getColor (st.nextToken ()); 7 if (cl! = Null) {8 accum.addElement (cl); 9} else {10 System.out.println ("Fehler - schlechte Farbe."); 11} 12} 13 if (accum.size () == 0) 14 return null; 15 Ergebnis = neue Farbe [accum.size ()]; 16 für (int i = 0; i <accum.size (); i ++) {17 result [i] = (Farbe) accum.elementAt (i); 18} 19 Ergebnis zurückgeben; 20}
Bei der obigen Methode, die sich nur geringfügig von der getColorMethode unterscheidet, erstellt der Code in den Zeilen 4 bis 12 eine neue Methode Tokenizerzum Extrahieren von Token, die vom Doppelpunkt (:) umgeben sind. Wie Sie im Dokumentationskommentar für die Methode lesen können, erwartet diese Methode, dass Farbtupel durch Doppelpunkte getrennt werden. Jeder Aufruf von nextTokenin der StringTokenizerKlasse gibt ein neues Token zurück, bis die Zeichenfolge erschöpft ist. Die zurückgegebenen Token sind die durch Kommas getrennten Zahlenfolgen. Diese Token-Strings werden eingespeist getColor, wodurch eine Farbe aus den drei Zahlen extrahiert wird. Wenn Sie ein neues StringTokenizerObjekt mit einem von einem anderen StringTokenizerObjekt zurückgegebenen Token erstellen, kann der von uns geschriebene Parser-Code die Interpretation der Zeichenfolgeneingabe etwas komplexer gestalten.
So nützlich es auch ist, Sie werden irgendwann die Fähigkeiten der StringTokenizerKlasse erschöpfen und müssen zu ihrem großen Bruder übergehen StreamTokenizer.
Die StreamTokenizer-Klasse
Wie der Name der Klasse andeutet, StreamTokenizererwartet ein Objekt, dass seine Eingabe von einer InputStreamKlasse stammt. Wie StringTokenizeroben konvertiert diese Klasse den Eingabestream in Blöcke, die Ihr Parsing-Code interpretieren kann, aber hier endet die Ähnlichkeit.
StreamTokenizerist ein tabellengesteuerter lexikalischer Analysator. Dies bedeutet, dass jedem möglichen Eingabezeichen eine Signifikanz zugewiesen wird und der Scanner die Signifikanz des aktuellen Zeichens verwendet, um zu entscheiden, was zu tun ist. Bei der Implementierung dieser Klasse werden Zeichen einer von drei Kategorien zugewiesen. Diese sind:
Whitespace characters -- their lexical significance is limited to separating words
Word characters -- they should be aggregated when they are adjacent to another word character
- Ordinary characters -- they should be returned immediately to the parser
Imagine the implementation of this class as a simple state machine that has two states -- idle and accumulate. In each state the input is a character from one of the above categories. The class reads the character, checks its category and does some action, and moves on to the next state. The following table shows this state machine.
| State | Input | Action | New state |
|---|---|---|---|
| idle | word character | push back character | accumulate |
| ordinary character | return character | idle | |
| whitespace character | consume character | idle | |
| accumulate | word character | add to current word | accumulate |
| ordinary character | return current word push back character |
idle | |
| whitespace character | return current word consume character |
idle |
On top of this simple mechanism the StreamTokenizer class adds several heuristics. These include number processing, quoted string processing, comment processing, and end-of-line processing.
The first example is number processing. Certain character sequences can be interpreted as representing a numerical value. For example, the sequence of characters 1, 0, 0, ., and 0 adjacent to each other in the input stream represent the numerical value 100.0. When all of the digit characters (0 through 9), the dot character (.), and the minus (-) character are specified as being part of the word set, the StreamTokenizer class can be told to interpret the word it is about to return as a possible number. Setting this mode is achieved by calling the parseNumbers method on the tokenizer object that you instantiated (this is the default). If the analyzer is in the accumulate state, and the next character would not be part of a number, the currently accumulated word is checked to see if it is a valid number. If it is valid, it is returned, and the scanner moves to the next appropriate state.
Das nächste Beispiel ist die Verarbeitung von Zeichenfolgen in Anführungszeichen. Es ist häufig wünschenswert, eine Zeichenfolge, die von einem Anführungszeichen (normalerweise doppeltes (") oder einfaches (') Anführungszeichen) umgeben ist, als einfaches Token zu übergeben. Mit dieser StreamTokenizerKlasse können Sie jedes Zeichen als Anführungszeichen angeben. Standardmäßig sind dies Zeichen sind die einfachen Anführungszeichen (') und doppelten Anführungszeichen ("). Die Zustandsmaschine wird so geändert, dass Zeichen im Akkumulationszustand verbraucht werden, bis entweder ein anderes Anführungszeichen oder ein Zeilenendezeichen verarbeitet wird. Damit Sie das Anführungszeichen in Anführungszeichen setzen können, behandelt der Analysator das Anführungszeichen, dem ein umgekehrter Schrägstrich (\) im Eingabestream und in einem Anführungszeichen vorangestellt ist, als Wortzeichen.
