johannes-asal.de

Nach der Entwicklung eines Parsers fuer Konfigurationsdateien in C++ kam mir der Gedanke, auch fuer andere Programmiersprachen entsprechende Parser zu schreiben, um die gemeinsame Nutzung ein und derselben Konfigurationen in mehreren Sprachen zu ermoeglichen. Dies ist insbesondere in der Entwicklung von Applikationen von Interesse, die ein prozessbasiertes mehrschichtiges Design aufweisen und jeweils die am besten geeignete Programmiersprache fuer jede Schicht verwenden. Hat man in solchen Faellen kein gemeinsames Konfigurationsmodell zur Verfuegung, so muessen saemtliche relevanten Daten von der Controller Applikation an die anderen Prozesse weitergegeben werden, was aber wiederum die Verwendung eines speziellen Protokolls voraussetzt, um die Daten zwischen den Prozessen auszutauschen. Fuer solche Anwendungen ist es sicherlich einfacher, die Konfiguration zentral zu verwalten und in jedem Prozess separat einzulesen.

Die erste Programmiersprache, die ich in diesem Zusammenhang angegangen habe, ist Python. Fuer Python existiert mit PLY ein einfacher aber dennoch leistungsfaehiger Parser Generator, der gegenueber dem C++-Pendant boost::spirit auf die Vorteile einer dynamischen Sprache zurueckgreifen kann. Bereits nach 15 Minuten hatte ich einen funktionsfaehigen Lexer implementiert, der mir einen Tokenstream fuer das Konfigurationsformat lieferte. Nach weiteren 20 Minuten war auch der Parser fertiggestellt. Das zeigt, dass PLY viel besser als boost::spirit fuer Rapid Prototyping geeignet ist, zumal auch das Testen von Lexer und Parser dank schneller Instanziierung im Python Interpreter zuegig von der Hand geht.

In diesem Artikel moechte ich kurz anreissen, wie sich ein Parser fuer unser Konfigurationsformat (siehe vorangegangene Artikel) mit PLY implementieren laesst. Details sollen diesmal aussen vor bleiben, dazu verweise ich auf den Sourcecode, der am Ende des zweiten Teils verlinkt ist. Fuer ein erstes Experimentieren mit PLY sollten die Ausfuehrungen jedoch ausreichend sein, zumal Python mit seinem Interpreter eine ideale Testumgebung bietet.

Um den zu parsenden String in einzelne Tokens zu zerlegen, benoetigen wir einen Lexer. Dieser muss sowohl Keywords (in unserem Fall sind das ‘true’ und ‘false’), einzelne Zeichen (Klammern, Semikolon, Komma und ‘=’) sowie die atomaren Datentypen (double, long und string) erkennen koennen. Im Gegensatz zu boost::spirit koennen wir in PLY direkt regulaere Ausdruecke verwenden, um die einzelnen Token zu spezifizieren. Diese fassen wir geeigneterweise in einer Klasse zusammen (auch alle folgenden Codesegmente sollen als Member dieser Klasse angelegt werden). Zunaechst definieren wir eine Liste ‘tokens’ (der Name ist vorgegeben), die die (frei waehlbaren) Namen der Tokens enthaelt.

class CfgLexer(object):
  keywords = ('TRUE', 'FALSE')
  tokens = keywords + (
    'LPAREN', 'RPAREN',
    'LBRACKET', 'RBRACKET',
    'LBRACE', 'RBRACE',
    'COMMA',
    'EQUALS',
    'SEMICOLON',
    'LITERAL',
    'DOUBLE',
    'LONG',
    'STRING_LITERAL'
  )

Fuer die beiden Keywords ‘TRUE’ und ‘FALSE’ habe ich zudem eine separate Liste angelegt; der Grund dafuer ist, dass fuer die Keywords beim Parsen nicht zwischen Gross- und Kleinschreibung unterschieden werden soll und diese deshalb spaeter gesondert behandelt werden muessen.

Um die Tokens festzulegen, fuegen wir der Klasse nun regulaere Ausdruecke fuer jedes der Tokens hinzu und weisen diese jeweils einer Variablen ‘t_TOKENNAME’ hinzu, also folgendermassen:

t_LPAREN = "\("
t_RPAREN = "\)"
t_LBRACKET = "\["
t_RBRACKET = "\]"
t_LBRACE = "\{"
t_RBRACE = "\}"
t_COMMA = ","
t_EQUALS = "="
t_SEMICOLON = ";"

Beachten Sie, dass die Klammern escaped werden muessen, da es sich bei den Strings um regulaere Ausdruecke handelt, und die Klammern sonst als Steuerzeichen interpretiert werden.

Fuer die uebrigen Tokens reicht ein einfaches Matching nicht aus, wir muessen ausserdem Aktionen verknuepfen, die bei einem erfolgreichen Match ausgefuehrt werden. Dazu koennen wir wie zuvor eine Variable mit einem regulaeren Ausdruck definieren und diese anschliessend an eine Funktion binden:

literal = "[a-zA-Z_][0-9a-zA-Z]*"
 
@TOKEN(literal)
def t_LITERAL(self, t):
  t.type = self.keyword_map.get(t.value.lower(), "LITERAL")
  return t

Nach einem erfolgreichen Match des regulaeren Ausdrucks suchen wir also zuerst in einer Keyword Map, ob wir ein passendes Keyword finden (beachten Sie die lowercase Transformation!) und verwenden dieses fuer den Typ des Tokens, ansonsten weisen wir den Typ ‘LITERAL’ zu. Die Keyword Map definieren wir wie folgt:

keyword_map = {}
for k in keywords:
  keyword_map[k.lower()] = k

Auch fuer die uebrigen Tokens muessen wir Funktionen definieren:

string_literal = r'"[^"\n]*"' + '|' + r"'[^'\n]*'"
double_constant = r"\-?([1-9]\d* | 0)\.\d*"
long_constant = r"\-?[1-9]\d* | 0"
 
@TOKEN(string_literal)
def t_STRING_LITERAL(self, t):
  t.type = "STRING_LITERAL"
  t.value = t.value.strip("\"'")
  return t
 
@TOKEN(double_constant)
def t_DOUBLE(self, t):
  t.type = "DOUBLE"
  t.value = float(t.value)
  return t
 
@TOKEN(long_constant)
def t_LONG(self, t):
  t.type = "LONG"
  t.value = int(t.value)

Bei den String Literals entfernen wir die Anfuehrungszeichen am Anfang und Ende, waehrend wir die value Felder der ‘DOUBLE’ und ‘LONG’ Tokens in den jeweiligen Datentyp konvertieren. Es fehlt nun nur noch ein Skip Parser, der den insignifikanten Whitespace ueberspringt (d.h. kein Token dafuer anlegt). Dazu weisen wir einen String mit zu ignorierenden Zeichen der (reservierten) Variablen t_ignore zu:

t_ignore = " \t"

Wir ueberspringen damit sowohl Leerzeichen als auch Tabs. Was geschieht aber mit den Linefeeds? Diese beduerfen wieder einer Sonderbehandlung:

def t_newline(self, t):
  r'\n+'
  t.lexer.lineno += len(t.value)

Hier missbrauchen wir den Docstring, um den regulaeren Ausdruck unterzubringen (der Lexer interpretiert diesen automatisch als die zu verwendende Regular Expression) und addieren anschliessend die Anzahl der gematchten Linefeeds zur Variablen t.lexer.lineno, um in den Fehlermeldungen auch die richtige Zeilennummer des fehlerhaften Tokens ausgeben zu koennen.

Wie wird nun ein solches Lexer Objekt erzeugt und auf die gelexten Tokens zugegriffen? Dazu definieren wir noch drei weitere Funktionen:

def build(self):
  self.lexer = ply.lex.lex(object=self)
 
def input(self, text):
  self.lexer.input(text)
 
def token(self):
  t = self.lexer.token()
  return t

Nachdem wir noch die Import Statements “import ply.lex” und “from ply.lex import TOKEN” hinzugefuegt haben, koennen wir den Lexer bereits testen. Wir starten eine Python Konsole und importieren das Modul (das wir beispielsweise als cfg_lexer.py) gespeichert haben:

>>> import cfg_lexer
>>> lexer = cfg_lexer.CfgLexer()
>>> lexer.build()
>>> lexer.input("a=5; b=(1,2,"Hallo"); c = { test = "test"; hallo = "welt"; };")
>>> lexer.token()
LexToken(LITERAL,'a',1,0)
>>> lexer.token()
LexToken(EQUALS,'=',1,1)
>>> lexer.token()
LexToken(LONG,5,1,2)
[...]


Wie funktioniert das ganze nun ueberhaupt? Eine solch lose Zusammenstellung von Funktionen in einer Klasse kann doch unmoeglich einen funktionsfaehigen Lexer darstellen! Der Trick ist, dass PLY die Liste der Tokens benutzt, um dynamisch die passenden Variablen bzw. Funktionen mit den regulaeren Ausdruecken in der Klasse zu suchen. Daraus wird on-the-fly Python Code fuer das Lexing generiert. Damit wird auch klar, warum die Benennung der Member unserer CfgLexer Klasse wichtig ist. Werden sie falsch bezeichnet, so findet PLY waehrend dem build() Prozess die regulaeren Ausdruecke bzw. semantischen Aktionen nicht und kann den Lexer nicht erstellen. Die Fehlermeldungen sind aber in diesem Fall deutlich besser verstaendlich als die C++ Templateerrors, die einen bei der Parserentwicklung mit boost::spirit erwarten.

Im naechsten Teil werden wir unseren Lexer als Tokenfeed benutzen und darauf aufbauend einen Parser implementieren.