Open Source im professionellen Einsatz
Linux-Magazin 04/2006
© Stockxchng

© Stockxchng

Parser im Eigenbau mit Perl

Übersetzungskünstler

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.

991

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.

Listing 1:
»mathlexer«

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}

Listing 2:
»MathLexer.pm«

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.

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Erkenne die Zeichen

    Häufig müssen Programme strukturierte Eingabedateien verarbeiten und verstehen. Komplizierte Dateiformate erfordern dabei hohen Programmieraufwand - oder den Einsatz eines Parsergenerators. JavaCC deckt die wichtigsten Aspekte der Parsergenerierung für Java-Programme ab.

  • C++11

    Was dem Perl-Programmierer altvertraut ist, fehlte C++ bisher. Der neue Sprachstandard C++11 bringt reguläre Ausdrücke ins Spiel, mit denen sich Textmuster beschreiben und finden lassen.

  • Individuelle Lesehilfe

    Programmcode schreiben ohne Syntax-Highlighting ist mühsam und fehlerträchtig. Damit auch Liebhaber seltener Sprachen in den Genuss der praktischen Lesehilfe kommen, untersucht diese Bitparade, wie und wie gut sich in Kate, Emacs und Netbeans neue Sprachen integrieren lassen.

  • Bash Bashing

    Die Macher der Bash spendierten der Shell Rechenkenntnisse auf Vierte-Klasse-Niveau. Wer mehr als die Grundrechenarten benötigt, weicht auf bc aus. Dass die Ergebnisse rechnender Bash-Skripte trotz der simplen Möglichkeiten jedes Mal stimmen, ist gleichwohl nicht gesagt.

  • Ready, Set, Go!

    Von Google sind mehr als nur Suchergebnisse zu erwarten. Nun stellt sich der Suchmaschinenriese sogar bei den Programmiersprachen in die Startblöcke - glückt der schnelle Antritt?

comments powered by Disqus

Ausgabe 09/2017

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.