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.

© Stockxchng

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.

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.