Lexer und Parser in Perl schreiben ist keineswegs langbärtigen Gurus vorbehalten. Am Beispiel eines mathematischen Formelparsers nimmt dieser Perl-Snapshot die Angst vor Token und RPN.

Für Compiler-Bauer und Erfinder neuer Programmiersprachen sind sie das tägliche Brot: Lexer und Parser prüfen beliebig komplexe Ausdrücke auf syntaktische Korrektheit und helfen dabei, sie aus der Menschen verständlichen in eine rechnertaugliche Sprache zu übersetzen. Allerdings ist das ein seltenes Vergnügen, denn Daten sind oft XML-formatiert und dafür gibt es eine ganze Reihe einfach zu bedienende Parser. Wer aber – beispielsweise vom Benutzer eingegebene – Formeln zu analysieren und auszuwerten hat, der kommt um einen eigenen Parser nicht herum.

Lex mich!

Wer einen Ausdruck wie »5+4*3« auswerten will, muss ihn zunächst in Operatoren und Operanden zerlegen. Wie Abbildung 1 zeigt, extrahiert zunächst ein so genannter Lexer die Symbole »5«, »+«, »4«, »*« und »3« aus dem String. Diese auch Tokens genannten Textstücke bekommt später der Parser verfüttert, der kontrolliert, ob die eingegebene Formel auch mathematischen Sinn ergibt. Dazu erzeugt der Parser typischerweise eine baumartige Struktur, mit deren Hilfe er prüft, ob der übergebene Ausdruck den Regeln einer vorher aufgestellten Grammatik gehorcht. Diese legt Dinge wie die Präzedenz der Operatoren (etwa Punkt vor Strich) oder die Reihenfolge der Auswertung fest (Assoziativität, von links nach rechts oder umgekehrt).

Sobald die exakte Bedeutung des Ausdrucks feststeht, kann ihn der Rechner schrittweise auswerten. Abbildung 1 zeigt als Beispiel einen RPN-Rechner (Reverse Polish Notation, umgekehrte polnische Notation). Die virtuelle Maschine wirft entweder Zahlen oder Operatoren oben auf den Stack und versucht anschließend die Operand-Operand-Operator-Kombinationen zu einem Einzelwert zu reduzieren.

Abbildung 1: Der Lexer zerlegt den String in Tokens, der Parser erzeugt den Parse-Tree. Der Übersetzer überführt ihn in die Reverse Polish Notation (RPN) und rechnet mit einem einfachen Algorithmus das Ergebnis aus.

So wird aus »4 3 *« der Wert 12, aus der dann auf dem Stack liegenden Kombination »5 12 +« das Ergebnis der Berechnung: 17. Zwar könnte man einen String wie »5+4*3« einfach an Perls Funktion »eval« weitergeben, die ihn dann nach Perls eigenen Mathematikregeln auswerten würde. Doch falls Variablen auftauchen, Operatoren, von denen Perl nichts weiß, oder gar If-else-Konstrukte, wenn also letztendlich eine Mini-Programmiersprache entsteht, muss ein ausgewachsener Parser ran.

Zurück zum Lexer: Auch Leerzeichen sollen im auszuwertenden String keine Rolle spielen, der Ausdruck »5 +4 *3« soll also die gleichen Symbole liefern wie »5+ 4*3«. Das Lexen ist allerdings nicht immer so trivial wie im vorgestellten Beispiel. Als Operand könnte beispielsweise auch eine reelle Zahl wie 1.23E40 auftauchen oder eine Funktion wie sin(x), die in die Tokens »sin(«, »x« und »)« zerlegt werden müsste. Für solche komplexen Lexer gibt es auf dem CPAN das Modul Parse::Lex. Bei seiner Installation ist zu beachten, dass es mindestens Version 0.37 des Moduls Parse::Template benötigt.

Mathesprachler

Das kurze Skript »mathlexer« aus Listing 1 nimmt einen verschachtelten mathematischen Ausdruck, gibt ihn an den Lexer weiter und lässt diesen die Kombinationen aus Tokentyp und Tokeninhalt zurückliefern und anschließend zu Testzwecken ausgeben.

01#!/usr/bin/perl-w
02usestrict;
03useMathLexer;
04
05my$str="5*sin(x*-4.27e-14)**4*(e-pi)";
06print"$strnn";
07
08my$lex=MathLexer->new($str);
09
10while(1){
11my($tok,$val)=$lex->next();
12lastunlessdefined$tok;
13printf"%8s%sn",$tok,$val;
14}

01###########################################
02packageMathLexer;
03###########################################
04usestrict;
05useRegexp::Common;
06useParse::Lex;
07
08my@token=(
09OPPOW=>"[*][*]",
10OPSUB=>"[-]",
11OPADD=>"[+]",
12OPMULT=>"[*]",
13OPDIV=>"[/]",
14FUNC=>"[a-zA-Z]\w*\(",
15ID=>"[a-zA-Z]\w*",
16LEFTP=>"\(",
17RIGHTP=>"\)",
18NUM=>"$RE{num}{real}",
19ERROR=>".*",sub{
20dieqq(Can'tlex"$_[1]")},
21);
22
23###########################################
24subnew{
25###########################################
26my($class,$string)=@_;
27
28my$lexer=Parse::Lex->new(@token);
29$lexer->skip("[\s]");
30$lexer->from($string);
31
32my$self={
33lexer=>$lexer,
34};
35
36bless$self,$class;
37}
38
39###########################################
40subnext{
41###########################################
42my($self)=@_;
43
44my$tok=$self->{lexer}->next();
45returnundefif$self->{lexer}->eoi();
46
47return$tok->name(),$tok->text();
48}
49
501;

Das von »mathlexer« verwendete Listing definiert die Klasse »MathLexer«, die über den Konstruktor »new« einen String zu Analysezwecken entgegennimmt und gemäß den in der Variablen »@token« abgelegten regulären Ausdrücke durchforstet. Für jedes gefundene Lexem, also die Sequenz der gefundenen Zeichen, aus denen der Lexer ein Token zusammenstellt, reicht der mit der Methode »next()« weitergeschubste Lexer zwei Werte zurück. Das erste Element des als Referenz zurückgereichten Array ist der Name des gefundenen Token (zum Beispiel NUM, OPADD, RIGHTP). Im zweiten Element folgt die tatsächlich gefundene Zeichenkette (etwa »4.27e-14«, »+«, »)«). Abbildung 2 zeigt die Ausgabe zu Testzwecken, die im wirklichen Leben als Parserfutter dient.

Abbildung 2: Ein von »MathParser.pm« gelexter mathematischer Ausdruck.

Zu beachten ist, dass Parse::Lex die regulären Ausdrücke als Strings entgegennimmt. Darum müssen Backslashes als »\« maskiert sein, wenn ein Symbol wie »*« kein Regex-Metazeichen sein soll. Da Ausdrücke wie »\*\*« schwer zu entziffern sind, verwendet »MathLexer« in der ersten Tokendefinition den etwas merkwürdig formulierten, aber identischen Regex »[*][*]«.

Ein regulärer Ausdruck, der die vielfältigen Schreibweisen von reellen Zahlen abdeckt (zum Beispiel 1.23E40, .37, 7, 1e10), ist gar nicht so einfach zu erstellen. Aber zum Glück bietet das CPAN-Modul Regexp::Common bereits vorgekochte Ausdrücke für vie- le Zwecke an, darunter auch einen für reelle Zahlen mit allerlei zusätzlichem Schnickschnack. Nach einem »use Regexp::Common« im Programm greift man über einen globalen Hash auf diese Perlen der Regexkunst zu. Der entsprechende Ausdruck für reelle Zahlen liegt in »{num}{real}«.

Übrigens lässt dieser Ausdruck auch ein optionales Minuszeichen vor der reellen Zahl zu. Wegen der gewählten Reihenfolge der erkannten Lexeme in »@token« wird der Lexer ein vorangestelltes Minuszeichen aber immer als »OPSUB« erkennen. Taucht jedoch ein Minuszeichen im Exponenten der reellen Zahl auf, schnappt der Lexer es als Teil des Lexems »NUM« auf.

Weiter sorgt Methode »skip« in Zeile 29 von »MathLexer.pm« dafür, dass der Lexer Leerzeichen und Zeilenumbrüche ignoriert. Trifft er allerdings auf ein Zeichenkonstrukt wie zum Beispiel »”}”«, kommt das in Zeile 19 definierte »ERROR«-Pseudo-Token zum Einsatz, das zur Fehlerbehandlung eine Routine definiert, die den Lexer einfach mit einem »die«-Kommando abbricht.

Syntaxkontrolle, die Tokens bitte!

Ein Parser untersucht anschließend die syntaktische Gültigkeit eines Ausdrucks. »2+*3« wäre ungültig, der Parser sollte in solchen Fällen einen Fehler melden und das Programm abbrechen. Parser prüfen aber nicht nur die Syntax eines Ausdrucks, sondern halten oft auch als Übersetzer her. Während der Parser einen arithmetischen Ausdruck durchkämmt, kann er auch gleich ausrechnen, was dabei herauskommt.

»AddMult.yp« (Listing 3) definiert eine Grammatik für den Parser. Sie bestimmt, wie der Parser die aus dem Lexer herausströmenden Tokens zu vorgegebenen Strukturen zusammenfasst. Die erste so genannte Produktion »expr: add | mult | NUM;« bestimmt, dass der Parser die Sequenz aller Tokens am Ende zu einem Konstrukt vom Typ »expr« zusammenfassen muss. Gelingt dies, war er erfolgreich. Ist dies dagegen unmöglich, genügen die Tokens des untersuchten Ausdrucks nicht der Grammatik. Es liegt ein Syntaxfehler vor und der Parse-Vorgang bricht ab.

01%leftOPADD
02%leftOPMULT
03
04%%
05expr:add|mult|NUM;
06
07add:exprOPADDexpr{
08return$_[1]+$_[3]
09};
10mult:exprOPMULTexpr{
11return$_[1]*$_[3]
12};
13%%

Schritt für Schritt

Produktionen wie die in Listing 3 zeigen auf der linken Seite ein so genanntes Nicht-Terminal-Symbol (Non-Terminal). Das ist ein Ausdruck, der sich aus gelexten Tokens (auch Terminals genannt) zusammensetzt, aber auch weitere Non-Terminals enthalten kann. »expr« in Zeile 5 kann zum Beispiel dreierlei sein, wie die mit »|« getrennten Alternativen auf der rechten Seite des Doppelpunkts zeigen: »add« (eine Addition), »mult« (eine Multiplikation) oder ein Terminal »NUM«, also eine reelle Zahl, die vom Lexer kommt.

Die Non-Terminals »add« und »mult« werden in den nächsten Produktionen in »AddMult.yp« definiert. »add: expr OPADD expr« in Zeile 7 bestimmt, dass ein Non-Terminal »add« sich aus zwei mit dem +-Operator verknüpften »expr«-Non-Terminals zusammensetzen soll, die – wie bereits vorher definiert – sich wiederum aus Additionen, Multiplikationen oder einfachen Zahlen zusammensetzen lassen.

Die Grammatikdatei »AddMult.yp« dient dem Modul Parse::Yapp als abstrakte Beschreibung eines Parsers. Sie teilt sich in drei Teile, die jeweils durch die Zeichensequenz »%%« voneinander getrennt sind. Oben thront der Header, der Parser-Instruktionen oder Perl-Code enthalten kann. In der Mitte stehen die Produktionen der Grammatik und unten folgt der Footer, der weiteren Perl-Code definieren darf. »AddMult.yp« wird mit dem Parse::Yapp beiliegenden Utility »yapp« in ein Perl-Modul umgewandelt, das den Parser implementiert.

Das so entstehende Modul »AddMult.pm« implementiert einen so genannten Bottom-up-Parser. Dieser liest den Tokenstrom aus dem Lexer und versucht den in Abbildung 1 gezeigten Parse-Baum von unten nach oben aufzubauen. Hierzu fasst er gelesene Einheiten gemäß der Grammatik zu übergeordneten Konstrukten so lange zusammen, bis am Ende die linke Seite der Startproduktion herauskommt.

Mit jedem Schritt führt der Parser eine von zwei Aktionen aus: Shift oder Reduce. Mit Shift holt er das nächste Token aus dem Eingabestrom und legt es oben auf den Stack. Mit Reduce fasst der Parser die auf dem Stack liegenden Terminals und Non-Terminals entsprechend der Grammatik zu weiteren Non-Terminals zusammen und reduziert damit die Höhe des Stack. Ist dann die Eingabeschlange leer und die letzte Reduktion lässt nur die linke Seite der Startproduktion auf dem Stack liegen, war der Parse-Vorgang erfolgreich.

Tabelle 1 zeigt, wie ein entsprechend der Grammatik in »AddMult.yp« implementierter Bottom-up-Parser den in Tokens zerlegten Eingabestring »5+4*3« Schritt für Schritt abarbeitet: In Schritt 0 liegen in der Eingabe die Tokens [NUM, 5], [OPADD, +], [NUM, 4], [OPMULT, *] und [NUM, 3] vor.

In Schritt 1 holt der Parser die 5 auf den Stack (Shift) und reduziert das »NUM«-Terminal in Schritt 2 gemäß der Grammatik (dritte Alternative der ersten Produktion) zu »expr«. Anschließend holt der Parser die Tokens [OPADD, +] und [NUM, 4] aus der Eingabe und reduziert Letzteres ebenfalls wieder zu »add«.

Dann stellt sich die Frage: Was tun? Der Parser könnte »expr OPADD expr« gemäß der Grammatik zu »expr« reduzieren (zweite Produktion). Andererseits könnte er auch [OPMULT, *] aus der Eingabe holen und darauf hoffen, später einmal »expr OPMULT expr« zu reduzieren (dritte Produktion).

Im Konflikt

Grammatiken sind oft nicht eindeutig. Gäbe es beispielsweise nicht die uralte Mathematikregel “Punkt vor Strich”, stünde der Parser bei einem Ausdruck wie 5+4*3 vor dem eben erläuterten Shift-Reduce-Konflikt. Was tun? Im Fall von 5+4*3 umschifft die Präzedenz der Algebra-Operatoren den Konflikt. Der Parser muss mit dem Reduzieren warten und den Operator »*« mit Shift auf den Stack hieven, denn »*« bindet seine Operanden stärker als das schwache »+«. Kommen gleiche Operatoren mehrmals hintereinander zum Einsatz, wie bei 5-3-2, sind alle Operationen gleichberechtigt und der Shift-Reduce-Konflikt stellt sich ebenfalls ein.

Entscheidet sich der Parser nach dem Lesen von »5-3« für ein Reduce, wertet er die Operatoren von links nach rechts aus und verhält sich damit gemäß den Regeln der Algebra. Ein Shift hätte den Ausdruck wie »5-(3-2)« ausgewertet, was statt des mathematisch erwarteten Werts 0 das überraschende Ergebnis 6 gebracht hätte. Den Minus-Operator nennt man deswegen links-assoziativ.

Assoziativität und Präzedenz

Diese Mehrdeutigkeit der Grammatik fällt auch dem Parser-Generator »yapp« auf, der aus der Datei »AddMult.yp« das Parser-Modul »AddMult.pm« erzeugt. Er kommentiert sie mit:

$yapp-mAddMultAddMult.yp
4shift/reduceconflicts

Die ersten zwei Zeilen in Listing 3 lösen das Problem:

%leftOPADD
%leftOPMULT

Sie bestimmen, dass sowohl der »+«- als auch der »*«-Operator links-assoziativ arbeiten und – wichtiger – dass »OPMULT« eine höhere Priorität als »OPADD« besitzt, da »%left OPMULT« in einer Zeile nach »%left OPADD« steht. Definierte der Parser auch eine OPMINUS Operation mit dem »-«-Operator, wäre es dringend notwendig, auch »%left OPMINUS« (und zwar vor der Definition von OPMULT) einzufügen.

Wenn statt »%left OPMINUS« im Header der »yp«-Datei hingegen »%right OPMINUS« stünde, würde der Parser Ausdrücke wie 5-3-2 von rechts nach links auswerten. Das hätte fatale Folgen, denn 5-(3-2) ergibt 6, nicht wie 5-3-2 den Wert 0. Mit diesen Tricks läuft der Parser gemäß Tabelle 2 bis zum Ende durch.

Und auch das »yapp«-Kommando erzeugt die Datei »AddMult.pm« jetzt ohne zu meckern. Außer der Grammatik definiert »AddMult.yp« neben manchen Produktionen auch noch ausführbaren Perl-Code. So legt

mult:exprOPMULTexpr{
return$_[1]*$_[3]
};

fest, dass der Rückgabewert der Produktion (zusätzlich zum erzeugten Non-Terminal) das Produkt aus den Rückgabewerten der beiden »expr«-Ausdrücke ist. Damit schleift der Parser das Ergebnis des untersuchten arithmetischen Ausdrucks immer weiter nach oben durch, bis es schließlich der Startproduktion beiliegt und vom Parser an den Aufrufer zurückgegeben wird. Auf diese Weise wird aus dem Syntaxprüfer automatisch auch ein Formelberechner. Die Tabellen 1 und 2 zeigen in der Spalte “Return” jeweils den Rückgabewert einer gerade ausgeführten Reduktion.

Zu beachten ist, dass »« sich in den Codestücken auf den ersten Ausdruck auf der rechten Seite der Produktion bezieht (also »expr«). Die sonst übliche Zählung von 0 gilt hier per Definition nicht, da »« in Parse::Yapp-Produktionen grundsätzlich eine Referenz auf den Parser bereithält. Enthält eine Produktion mehrere durch »|« getrennte Alternativen, kann jede einen eigenen Codeblock definieren. Dabei ist zu beachten, dass sich ein Codeblock immer nur auf die Alternative bezieht, neben der er steht.

Bevor der Parser loslegen kann, noch ein Zwischenschritt: Da das Interface zu »yapp«-Parsern etwas exotisch ist und der vorliegende »MathLexer« zum Einsatz kommen soll, definiert Listing 5 eine einfachere Schnittstelle. Die Methode »parse()« von »MathParser.pm« nimmt damit einfach den zu parsenden String entgegen und liefert das arithmetische Ergebnis zurück. Bei einem Fehler springt der Parser die in Zeile 28 des Moduls »MathParser.pm« definierte Routine an und steigt anschließend aus.

Listing 4 zeigt eine relativ einfache Anwendung, die vier verschiedene arithmetische Ausdrücke parst und gleichzeitig auswertet. Es zeigt sich, dass der Parser die Präzedenzregeln beachtet:

5+4*3:17
5+4+3:12
5*4*3:60
5*4+3:23

Der Präzedenzkonflikt lässt sich auch anders lösen: Wird die Grammatik wie in Listing 6 umformuliert, ergibt sich die höhere Präzedenz des »*«-Operators einfach aus den Zusammenhängen zwischen den Produktionen. Eine Multiplikation wird zunächst in dem Non-Terminal »term« zusammengefasst, bevor eventuell bestehende Additions-Reduktionen ausgeführt werden.

01#!/usr/bin/perl
02usestrict;
03usewarnings;
04
05useMathParser;
06useAddMult;
07
08my$mp=MathParser->new(AddMult->new());
09
10for(qw(5+4*35+4+35*4*35*4+3)){
11print"$_:",$mp->parse($_),"n";

01packageMathParser;
02###########################################
03useMathLexer;
04usestrict;
05usewarnings;
06
07###########################################
08subnew{
09###########################################
10my($class,$parser)=@_;
11
12my$self={
13parser=>$parser
14};
15
16bless$self,$class;
17}
18
19###########################################
20subparse{
21###########################################
22my($self,$str,$debug)=@_;
23
24my$lexer=MathLexer->new($str);
25
26my$result=$self->{parser}->YYParse(
27yylex=>sub{$lexer->next();},
28yyerror=>sub{die"Error"},
29yydebug=>$debug?0x1F:undef,
30);
31}
32
331;

01###########################################
02#UnAmb.yp-Unambiguous+/*grammar
03###########################################
04%%
05expr:exprOPADDterm{
06return$_[1]+$_[3];
07}
08|term{
09return$_[1];
10};
11
12term:termOPMULTNUM{
13return$_[1]*$_[3];
14}
15|NUM{
16return$_[1];
17};
18%%

Mit diesem Verfahren lässt sich auch das Verhalten von im Eingabestring zugelassenen Klammern implementieren, um zum Beispiel (5+4)*3 zu erzwingen. Hierzu wird einfach die »term«-Produktion umdefiniert und eine weitere Produktion »force« hinzugefügt:

term:termOPMULTforce
{...}
|force
force:LEFTPexprRIGHTP
{return$_[2];}
|NUM

Nun genießen geklammerte Ausdrücke höchste Priorität, der Parser führt sie noch vor den Multiplikationen aus.

Statt den arithmetischen Ausdruck direkt auszuwerten, bietet es sich an, ihn in eine leicht berechenbare Form wie RPN zu überführen. Listing 7 zeigt die zugehörige Grammatik. Nur die Codestücke an den Produktionen sind verändert. Sie geben nun nicht mehr berechnete Werte weiter, sondern schieben Zahlen und Operationen nach RPN-Manier in einen Array, der als Referenz Stufe um Stufe zurückgereicht wird und schließlich beim Aufrufer ankommt.

01###########################################
02#RPN.yp
03###########################################
04%leftOPADD
05%leftOPMULT
06
07%%
08expr:add
09|mult
10|NUM{return[$_[1]];};
11
12add:exprOPADDexpr{
13return[
14@{$_[1]},@{$_[3]},$_[2]
15];
16};
17
18mult:exprOPMULTexpr{
19return[
20@{$_[1]},@{$_[3]},$_[2]
21];
22};
23%%

Listing 8 ist das zugehörige aufrufende Skript und erzeugt – wie erwartet – grundsätzlich unterschiedliche Umwandlungen für »5+4*3« und »5+4+3«:

5+4+3:[5,4,+,3,+,]
5+4*3:[5,4,3,*,+,]

01#!/usr/bin/perl
02
03usestrict;
04usewarnings;
05
06useMathParser;
07useRPN;
08
09my$mp=MathParser->new(RPN->new());
10
11formy$string(qw(5+4+35+4*3)){
12print"$string:[";
13for(@{$mp->parse($string)}){
14print"$_,";
15}
16print"]n";
17}

Im oberen Ausdruck geht der Übersetzer einfach stur von links nach rechts durch und addiert die Einzelwerte, zuerst 5 und 4 addiert, dann 3.

Im unteren Ausdruck dürfen »5+4« jedoch wegen der Punkt-vor-Strich-Regelung nicht sofort addiert werden. Vielmehr schiebt der Übersetzer zunächst die nächste Zahl »3« auf den Stack, führt die verlangte Multiplikation aus und addiert das Ergebnis erst danach.

Zum Thema Parsen gibt es reichlich Bücher, das Drachenbuch [2] ist der Klassiker. Neben dem Bottom-up-Parsergenerator Parse::Yapp, der an die Unix-Tools »lex« und »yacc« [5] angelehnt ist, führt das CPAN auch noch den Top-Down-Parser-Generator Parse::RecDescent. Aber selbstverständlich kann man Parser auch von Hand schreiben. Besonders mit funktionaler Programmierung geht das sehr effektiv, wie zum Beispiel [3] und [6] beschreiben. (jcb)