28 Jan 09 Blatt 12 (Lexer und Parser)
Heute befasse ich mich schon einmal früher mit dem nächsten Blatt als sonst´. Das liegt einerseits daran, dass das Thema schön ist, und andererseits daran, dass es wahrscheinlich nicht möglich ist, alles sonst so in den 3 Sunden vom Praktikum unterzubringen, dass man den größt-möglichen Nutzen daraus ziehen kann.
Vorbereitung und Informationen zu den Aufgaben
Bei dem Übungsblatt geht es um das Erstellen eines Parsers und Lexers. (Am besten einmal die Aufgabenstellung überfliegen!)
Die Aufgaben benutzen BNF-Regeln, also macht es auch Sinn, diese kurz zu wiederholen, falls man sich nicht mehr so sicher fühlt.
Wie immer verweise ich auf Wikipedia (die englischen Artikel sind hier eindeutig besser) um die Begriffe zu klären:
Die einzigen Parser, die man auch ohne weitergehende Studien selber schreiben kann, sind rekursiv-absteigende Parser. Interessanterweise sind sie auch so ziemlich die einzigen Parser, deren Code leicht verständlich und wartbar ist (also insbesondere auch lesbar).
Für alle Typen gibt es sogenannte Parser Generatoren (es gibt auch Lexer Generatoren), die automatisch für einen den Quellcode eines Parsers aus vorgegebenen Regeln (BNF-Regeln meistens) erstellen.
Bekannte Beispiele sind Yacc (und Lex für den dazugehörigen Lexer Generator). Beide erstellen unlesbaren Code und um die Funktionsweise zu verstehen (bzw. um zu verstehen wie man von den Regeln auf den erstellten Code kommt) benötigt man fundiertes Wissen über Automatentheorie.
Ein für Anfänger besser geeignetes Tool (das auch Java-Code ausgibt) ist ANTLR. Zu dem Parser (der aber auch sehr mächtig ist) wurde auch ein sehr gutes Buch geschrieben (das sei hier aber nur erwähnt). Meine Beispiele benutzen später auch ANTLR.
Rekursiv-absteigende Parser
Rekursiv-absteigende Parser setzen die BNF-Regeln mehr oder weniger direkt in den Quellcode um und benutzen rekursive Aufrufe um die Regeln zu kodieren.
Wir können Exceptions benutzen um Fehler zu propagieren, doch dazu später.
Um die Struktur besser zu verstehen, möchte ich ein primitives (und nicht wirklich funktionierendes) Beispiel anführen:
Beispiel:
A ::= B | C B ::= X Y Z* C ::= A | C
Das würde wie folgt in (Pseudo-)Code umgesetzt werden (dabei besagt der Rückgabewert einer Funktion, ob die Regel gematcht werden konnte oder nicht (dies ist hilfreich bei Alternativen ;-)):
boolean ruleA() {
// A ::= B | C
return ruleB() || ruleC();
}
boolean ruleB() {
// X
if( !ruleX() )
return false;
// Y
if( !ruleY() )
return false;
// Z* (null, eines oder mehrere Zs)
while( ruleZ() )
;
return true;
}
boolean ruleC() {
// A | C
return ruleA() || ruleC();
}
Man kann folgendes feststellen:
- Diese Regeln bringen natürlich nichts, weil nie Zeichen (Fachwort: Literale) gematcht werden.
- Die Reihenfolge der Abarbeitung von Alternativen ist wichtig für die Programmausführung:
Wäre C ::= C | A und würden wir das dann auch so im Quellcode schreiben (return ruleC() || ruleA()), würde, wie man unschwer erkennt, sofort eine Endlosschleife enstehen und der Regel A würde niemals Beachtung geschenkt werden. - Die Struktur des Codes entspricht sehr stark der Struktur der Regeln – Konstrukte wie ‘mehr als eines’, etc. werden durch Schleifen kodiert, Alternativen durch “VerODERung” und Sequenzen durch “VerUNDerung”
Das ist natürlich nur ein Stück davon, wie ein Parser funktioniert (aber der wichtigste Teil, da er die Struktur beschreibt). Wir müssen jetzt “nur” noch Zeichen einlesen und “verbrauchen” können.
Lexer
In der Aufgabe (und allgemein ist es auch so) bekommen wir eine Zeichenkette und müssen aus dieser eine Struktur herausziehen.
Dazu ist es hilfreich die verschiedenen semantischen Einheiten, die man bekommt, anfangs zu klassifizieren, also zum Beispiel zu sagen: Das hier ist ein Variablenname oder das hier ist eine Zahl usw.
Dann kann man in der Grammatik bzw. im Parser direkt mit den Konzepten Zahl und Variablenname arbeiten anstatt mit irgendwelchen Zeichenregeln ala {‘a’-‘z’}+ bzw. statt mit einer Zeichenkette “x” oder “42” arbeiten zu müssen, haben wir Objekte der Typen VarToken (dessen Attribut name “x” ist) und ConstToken (dessen Attribut value 42 ist).
Der Lexer übernimmt die Aufgabe dieser Klassifierzung bzw. Zerlegung der Eingabe in ihre semantischen Einheiten:
Während ein Parser immer eine Startregel hat und von dort aus beginnt Regeln zu matchen, besteht die Aufgabe eines Lexers darin, die sogenannten Token zu bestimmen. Token sind die semantischen Einheiten, aus denen der Text besteht.
Die Aufgabe des Lexers ist also, die Zeichen einzulesen und in einem ersten Schritt zu verschiedenen Token zusammenzufassen.
Dieser Tokenstream (also Tokenstrom) wird dann vom Parser weiterverwendet (anstatt der Eingabe). In unserer Aufgabe würde der Parser nur Instanzen der Klassen VarToken, OperatorToken, etc. sehen (siehe b)) und mit diesen arbeiten.
Das heißt der Ablauf sieht folgendermaßen aus:
- Der Lexer zerlegt die Eingabe in Tokens und speichert diese in einer Liste (welche Datenstruktur bietet sich da an?
- Der Parser bekommt den Tokenstream und fängt bei der Startregel an Token zu “verbauchen”. Die Startregel verzweigt dann an ihre Unterregeln und diese machen das gleiche´.
Keine Angst, ich gehe darauf noch genauer ein.
Beispiel
Die Aufgabenstellung unterscheidet nicht zwischen Parserregeln und Lexerregeln, sondern mischt das ganze, deswegen werde ich das jetzt auch zuerst so machen.
Im Folgenden benutze ich Grafiken und Grammatiken, die mit und für ANTLR erstellt wurden (ich werde auch den Code posten, aber keine Sorge, man muss da nicht ganz durchsteigen, sondern erst reicht die Ähnlichkeit mit den BNF-Regeln aus Info1 zu sehen).
Die ANTLR-Grammatik für unsere Aufgabe sieht wie folgt aus:
grammar arithmetic;
term : factor ( ('+' | '-') term)?;
factor : atom ( ('*' | '/') factor)?;
atom : CONST | VAR | '(' term ')';
CONST : '0' | ('1'..'9' ('0'..'9')*);
VAR : ('a'..'z')+;
// eat whitespace
WS : (' '|'\n'|'\r'|'\t')+ {$channel=HIDDEN;};
Damit können wir einen Ableitungsbaum erstellen – als Beispiel: 2 * x * (y + 3):
"2 * x * (y + 3)" als Ableitungsbaum
An den Blättern stehen jeweils die Token, die gemacht wurden. “Root” ist eine Eigenart von ANTLR und wird immer noch über die Startregel gesetzt.
Ich empfehle, dass man als Übung selber auch einmal versucht den Ableitungsbaum aufzustellen (siehe Teilaufgabe a)).
Lexer, die zweite
Die Aufgabe in der b) besteht darin, sich zu überlegen, welche Attribute die verschiedenen Token haben sollen (bzw ob überhaupt).
Die verschiedenen Klassen sollen alle IToken implementieren, damit wir später Polymorphie benutzen können und auch alle Token in einer Queue<IToken> speichern können.
Wir können dann das instanceof Schlüsselwort benutzen um später festzustellen, mit was für einem Token wir es eigentlich zu tun haben 
IToken token = tokenStream.poll(); if( token instanceof ConstToken ) { // ja, token ist ein ConstToken ...In der c) sollen wir dann eine Klasse Lexer schreiben, die z.B. eine statische Methode lex hat mit der Signatur:
public static Queue<IToken> lex(String expression)Diese Methode soll, wie oben schon beschrieben, die Zeichenkette expression in eine Folge von Token aufspalten und diese zurückgeben.
Parser, die zweite
Der Parser benutzt den Lexer um die Tokens zu bekommen und benutzt dann rekursive Funktionen (für jede Regel eine) um die Token zu verarbeiten.
Hätten wir zum Beispiel eine Regel:
<beispielRegel> ::= <const> <term> <const> {<var>}*dann könnte der Quellcode zum Parsen der selbigen so aussehen wie gleich im Beispiel.
Dabei ist die Methode Teil der Klasse Parser und der Tokenstream vom Typ Queue<IToken> ist in einem Attribut private Queue<IToken> tokenStream gespeichert.
Desweiteren haben wir eine Exception TokensExpectedException definiert. Der Rückgabetyp ist hier im Beispiel void, könnte aber zum Beispiel vom Typ int sein, falls wir vielleicht einen Wert durch den Ausdruck berechnen möchten.private void parseBeispielRegel() throws TokensExpectedException { if( tokenStream.peek() instanceof ConstToken ) { tokenStream.remove(); parseTerm(); if( tokenStream.peek() instanceof ConstToken ) { tokenStream.remove(); while( tokenStream.peek() instanceof VarToken ) { tokenStream.remove(); } } else { // kein 2. const gefunden throw new TokensExpectedException( "Const expected" ); } } else { // kein 1. const gefunden throw new TokensExpectedException( "Const expected" ); } }Einleitende Aufgabe zur Aufgabe 1 und 2 für’s Praktikum:
Wir schreiben zuerst einen Interpreter, also eine Parser, der gleich die Ausdrücke interpretiert und die Werte ausrechnet und als Rückgabewert der “Regel-Funktionen” zurückgibt.
Abstrakter Syntaxbaum
Auf Wikipedia findet schon einmal eine Definition: [[wikipdia:Abstract_syntax_tree#Abstract Syntax Tree]].
Ziel der Teilaufgaben d), e) und f) ist es, anstatt die Werte direkt auszuwerten, eine Baumstruktur zu benutzen um die Struktur des geparsten Textes zu speichern. Dieser kann dann getrennt (siehe Aufgabe 2) ausgewertet werden und wir brauchen ihn nur einmal zu parsen, selbst wenn wir verschiedene Operationen auf einem Ausdruck ausführen wollen – z.B. den Wert berechnen oder feststellen, welche Variablen er braucht, etc..
Was für Knotentypen kann dieser Baum haben?
In der Teilaufgabe d) sollen diese Klassen mit den entsprechenden Attributen und Methoden implementiert werden. Wir implementieren wieder ein Interface – nämlich IArithmetic – um eine Baumstruktur zu ermöglichen.
Dazu möchte ich auf Composite Pattern verweisen´, damit man versteht, welche Idee dahinter steckt.
Tree Walker
Bei der Aufgabe 2 geht es darum, einen mit dem Parser erstellten Evaluationsbaum zudurchlaufen und die Ausdrücke auszuwerten um den Wert des gesamtem Ausdruckes zu bestimmen. Dazu fügen wir eine Methode public int evaluate() zum Interface IArithmetic hinzu und implementieren sie dann für jeden Knotentyp derart, dass der Knotentyp seine Teilausdrücke auswertet und seine Operation darauf anwendet (falls er Teilausdrücke hat und ein Operator ist :D).
Dank Polymorphie und dem Composite Pattern geht das relativ schmerzlos.
Zusatzaufgabe (oder alternative Aufgabe)
Statt das Interface nachträglich zu ändern, kann man ein anderes, ebenfalls sehr mächtiges Design Pattern benutzen: das Visitor Pattern´ .
Damit können wir beliebig Operationen auf dem ganzen Baum definieren (wie das Auswerten oder Variablen bestimmen, etc.) ohne mehr als einmal das Interface und die Knotentypen anpassen zu müssen.
Das ist aber wirklich nur eine Zusatzaufgabe, falls noch Zeit bleibt.
Falls ich aber noch Zeit finde, werde ich auch noch Lösungen für alle Aufgaben in ANTLR entwickeln – es dürften nicht mehr als 100 Zeilen sein, aber mein ANTLR-Wissen ist etwas eingerostet..
Grüße,
AndreasTags: ANTLR, Blatt 12, Composite Pattern, Exceptions, Lexer, Parser, Vistor Pattern
Leave a Comment
You must be logged in to post a comment.
