Compilerbau (2. Teil): Sprache und Lexer back to frontpage

Anknüpfend an meinen vorherigen Blogpost, der die Grundzüge eines Compilers zeichnete, werde ich nun zunächst die Sprache namens “Blogmath” (BM) vorstellen, die ich im Laufe meiner Blogpostserie entwickeln werde. Den gesamten Übersetzer und Interpreter programmiere ich in Python. Der vollständige Quelltext ist auf GitHub zum direkten Nachschlagen verfügbar (während ich die Blogpostserie schreibe, wird der Code jedoch nur sukzessive mit Veröffentlichung des jeweiligen Teiles von mir online gestellt).

Eine Übersicht über die Programmiersprache “Blogmath”

Wie bereits angedeutet, lassen sich in BM einfache mathematische Ausdrücke berechnen. Zur Verfügung stehen hierzu die Operationen

  • Addition (+) und Subtraktion (-),
  • Multiplikation (*) und Division (/) sowie
  • Potenzieren (^).

(In Klammern jeweils das in der Sprache genutzte Operatorsymbol.) Die übliche Präzedenzregel “Punkt- vor Strichrechnung” wird eingehalten. Ferner stehen zur Verfügung

  • Klammerausdrücke, um eine abweichende Rangfolge zu erzwingen,
  • Variablen- und Konstantendeklarationen sowie
  • anonyme Funktionen.

Als verwendbare Datentypen stehen der Einfachheit halber nur Integers / Floats (genauer: Fließpunktzahlen) zur Verfügung. Sie werden im Programm einfach als “Number” einheitlich behandelt. Damit wird möglichen Typeninkompatibilitäten entgangen; Typüberprüfungen sind daher nicht notwendig. Die semantische Analyse ist dennoch nicht obsolet, da unter anderem weiterhin geprüft werden muss, ob genutzte Variablen und Funktionen zuvor definiert wurden oder bereits existieren.

Kommentare können an beliebigen Stellen im Quelltext im C-Style angegeben werden. Alles nach // wird bis zum Zeilenende ignoriert.

// Das ist ein Kommentar

Den Programmen steht eine print()-Funktion zur Verfügung, mit der Berechnungen ausgegeben werden können.

Ein Beispielprogramm sieht wie folgt aus:

var c = 2; // Exponent
var s = 0.5;

// Funktion zur Potenzierung
lambda pow(a) = a^c;

// Funktion zum Wurzelziehen
lambda sqrt(a) = a^s;

// Ergebnis berechnen von 5^2
var result = pow(5);

// Ergebnis berechnen von 25^0.5
var result2 = sqrt(result);

// Ergebnis ausgeben
print(result);   // Gibt 25 aus
print(result2);  // Gibt 5 aus

Eine konkrete Grammatik, die die Sprache beschreibt, wird von mir im kommenden Teil (Parsing) meiner Blogpostreihe Schritt für Schritt entwickelt. Diese ist für den Lexer zunächst irrelevant.

Entwicklung eines Lexers

Wie bereits ausgeführt, zerlegt ein Lexer einen Input-String in die für die zu entwickelnde Programmiersprache charakteristischen Bestandteile.

Bevor der Lexer implementiert werden kann, müssen zunächst Tokenklassen definiert werden. Welche Zeichenketten von einer Tokenklasse akzeptiert werden, lässt sich am Besten über reguläre Ausdrücke beschreiben.

Exkurs: Reguläre Ausdrücke

Ein regulärer Ausdruck ist eine Zeichenkette, die eine Menge von Zeichenketten (die sogenannte reguläre Sprache) anhand syntaktischer Regeln beschreibt. Am ehesten lassen sich reguläre Ausdrücke durch endliche Automaten als Zustandsdiagramm visualisieren. Ein solcher endlicher Automat akzeptiert die durch einen regulären Ausdruck beschriebene reguläre Sprache.

Als Beispiel soll die Erkennung eines Bezeichners dienen, der nur mit einem Groß- oder Kleinbuchstaben beginnen, dann jedoch zudem Zahlen und Unterstriche enthalten darf. Ein Bezeichner muss mindestens ein Zeichen enthalten. Der zugehörige reguläre Ausdruck lautet wie folgt:

[a-zA-Z][a-zA-Z0-9_]* 

Eckige Klammern geben eine Menge für ein akzeptiertes Zeichen an. Statt jeden einzelnen Buchstaben des Alphabets aufzuführen, ist die Angabe von Bereichen zulässig (Beispiel: a-f). In regulären Ausdrücken sind Iterationen möglich: Ein Stern (*) nach einem Zeichen (oder einer Menge von Zeichen) bedeutet “mindestens 0”, ein Plus (+) hingegen “mindestens 1”, ein Fragezeichen (?) “entweder 0 oder 1”.

Folgender endlicher Automat akzeptiert die durch diesen Ausdruck beschriebene Sprache.

Zustandsdiagramm eines endlichen Automaten, der eine reguläre Sprache akzeptiert

Dieses Wissen genügt bereits, um die Tokenklassen für BM zu definieren. Folgende Tokenklassen mit dem dazugehörigen regulären Ausdruck erscheinen für die Sprache sinnvoll:

  1. Identifier: [a-zA-Z][a-zA-Z0-9_]*
  2. Number: [0-9]+\.?[0-9]*
  3. Operation: [+-/*^]
  4. BraceOpen: (
  5. BraceClose: )
  6. Assign: =
  7. Semicolon: ;

Hinweis: Der Punkt steht in regulären Ausdrücken üblicherweise für ein beliebiges Zeichen, wird deshalb bei Number mit Backslash escaped.

Identifier sind Bezeichner für Variablen, Funktionen, Parametern und Keywords (s. u.). Number sind entweder Ganzzahlen oder Fließpunktzahlen beliebiger Länge. Operationen bestehen aus den entsprechenden Symbolen (s. o.), BraceOpen, BraceClose, Assign und Semicolon sollten selbsterklärend sein.

Whitespaces (also Leerzeichen, Zeilenumbrüche, Tabs) führen in der Regel nicht zu einer Produktion von Token, sofern sie nicht für die Syntax/Semantik weiter von Belang sind (anders also zum Beispiel in Programmiersprachen, die Einrückung zur Strukturierung des Quelltextes nutzen, z. B. Python). Zeilenumbrüche werden im folgenden Lexer ausschließlich zur Zählung der jeweils aktuellen Zeile genutzt, um exakte Fehlermeldungen ausgeben zu können.

Eine weitere Klasse stellen die Keywords dar, die jedoch wie die Identifier erkannt werden. Keywords sind reservierte Worte in einer Programmiersprache, die nicht überschrieben und beispielsweise als Variablen- oder Funktionsname genutzt werden können. Keywords von BM sind var und lambda. Zweckmäßig wird nach Erkennen eines Identifiers zunächst geprüft, ob der Inhalt dem eines Keywords entspricht. Ist dem so, wird statt eines Identifiertokens ein entsprechendes Keywordtoken emittiert (siehe unten die Implementation).

Jeder Tokenklasse wird zunächst eine eindeutige Konstante zugewiesen. Mangels Enumerationstyp in Python werden hierfür einfache globale Variablen genutzt:

TOKEN_IDENTIFIER = 1
TOKEN_KEYWORD = 2
TOKEN_NUMBER = 3
TOKEN_OPERATION = 4
TOKEN_BRACEOPEN = 5
TOKEN_BRACECLOSE = 6
TOKEN_ASSIGN = 7

Die Keywords werden in einer globalen Liste vorgehalten und können so beliebig erweitert werden.

RESERVED_KEYWORDS = ["var", "lambda"] 

Einzelne produzierte Tokenobjekte enthalten das sogenannte Lexem (den erkannten Inhalt) sowie die Spalte (column) und Zeile (line) des Auftretens. Die Definition in Python sieht daher wie folgt aus:

class Token(object):
    def __init__(self, line, col, typ, content):
        self.line = line
        self.col = col
        self.type = typ
        self.content = content

Typ spezifiziert die Tokenklasse, content das Lexem.

Die Idee in Bezug auf die Implementation eines Lexers (das sogenannte Tokenizing) ist nun, den (noch verbliebenen) Input sukzessive mittels der regulären Ausdrücke zu untersuchen und bei Erkennen ein entsprechendes Token in eine Ergebnisliste einzureihen. Der Anfang des Inputs wird daraufhin um die Länge des Lexems verschoben (insgesamt also gekürzt) und die Prozedur wiederholt. Das Tokenizing endet entweder dann, wenn ein Zeichen nicht erkannt werden konnte (Programmabbruch mit Fehlermeldung) oder der gesamte Input verbraucht wurde (Erfolg). Die produzierte Tokenliste wird im Erfolgsfall daraufhin an den Parser übergeben (realisiert durch einfache Rückgabe der Liste als Funktionswert der Funktion tokenize()).

Bevor jedoch die Funktion entwickelt werden kann, müssen die regulären Ausdrücke in die Implementation übernommen werden. Dabei werden nur komplexe reguläre Ausdrücke mittels der Python-Bibliothek re implementiert; einfache reguläre Ausdrücke, die nur ein Zeichen erkennen sollen, werden direkt in der tokenize()-Funktion der Einfachheit halber abgebildet (ausgenommen Operations, für die eine globale Liste von Operationssymbolen angelegt wird).

re_identifier = re.compile("^[a-zA-Z][a-zA-Z0-9_]*")
re_number = re.compile("^[0-9]+\.?[0-9]*")
OPERATIONS = ["+", "-", "*", "/"]

Hinweis: Die regulären Ausdrücke wurden am Anfang durch das Startsymbol ^ ergänzt. Dieses gibt an, dass nur der Anfang einer Zeichenkette (im Lexer-Fall also stets die als nächstes zu erkennenden Zeichen) berücksichtigt wird (und nicht etwa vorkommende Identifier mitten im Input).

Es ist durchaus möglich, auf eine Bibliothek für reguläre Ausdrücke zu verzichten und diese in hinreichender Form selbst zu entwickeln. Hierzu würde man die einzelnen Zustände und Zustandsübergänge, die sich in den endlichen Automaten der einzelnen regulären Ausdrücke ergeben, abbilden und stets dann, wenn ein Endzustand verlassen wird, ein Token emittieren. Da es in diesen Blogposts jedoch darum gehen soll, die grundsätzliche Funktionsweise eines Übersetzers darzustellen, wird darauf verzichtet und eine übersichtlichere, kürzere und vor allem pragmatischere Methode bevorzugt. Ein Verfahren, mit dem man einen regulären Ausdruck in einen nichtdeterministischen endlichen Automaten überführen kann, ist das Berry-Sethi-Verfahren. Lex ist beispielsweise ein Programm, das solche Lexer automatisch anhand definierter regulärer Ausdrücke als Quelltext generiert und bei Aufruf der Tokenizer-Funktion ein entsprechendes Token emittiert.

Die tokenize()-Funktion wird wie folgt aufgebaut (exemplarisch für den Identifier, die vollständige Implementation kann auf GitHub eingesehen werden):

def tokenize(src):
    tokens = []

    line = 1
    col = 1

    while len(src) > 0:
        if re_identifier.match(src):
            content = re_identifier.findall(src)[0]
            if content in RESERVED_KEYWORDS:
                tokens.append(Token(line, col,
                    TOKEN_KEYWORD, content))
            else:
                tokens.append(Token(line, col,
                    TOKEN_IDENTIFIER, content))

            # Anfang des src verschieben
            src = src[len(content):]
                        # Column addieren
            col += len(content)
        # (weitere Tokenklassen ausgelassen)
        else:
            error(line, col,
              "Unknown character '%c' (%d)" % \
              (src[0], ord(src[0])))

    return tokens

Ich rekapituliere noch einmal die Funktionsweise für die Erkennung einer Tokenklasse: Zunächst wird überprüft, ob der Anfang des verbliebenen Inputs (src) von dem jeweiligen regulären Ausdruck (im obigen Fall re_identifier für einen Identifier) erkannt wurde. Ist dem so, wird das erkannte Lexem bezogen (content, mittels findall()). Im Falle des Identifiers wird zunächst geprüft, ob es sich bei dem erkannten Text um ein Keyword handelt. Sollte ein Keyword vorliegen, wird ein Keywordtoken produziert, im anderen Fall ein Identifiertoken. Nachdem der Token in die Ergebnisliste eingereiht wurde, wird der Anfang des Input-Textes nach Rechts um die Länge des Lexems verschoben und die neue Position der Spalte gesetzt, indem die Länge des Lexems addiert wird.

Auf größere Optimierungen wurde verzichtet, um die Nachvollziehbarkeit zu gewährleisten. Diese erkauft man sich in diesem Fall mit etwas Redundanz im Code, die jedoch nicht weiter schlimm ist.

Auf eine Besonderheit sollte noch eingegangen werden: Die Rangfolge der Erkennung von Tokens. Wie oben definiert, werden Kommentare mit einem Doppelslash eingeleitet. Dies kollidiert jedoch mit der Erkennung eines Divisor-Operators, weshalb es notwendig ist, die Erkennung des Doppelslashes in der Reihenfolge vor der Operatorerkennung durchzuführen. Dies ist im Quelltext entsprechend berücksichtigt. Werden zwei Slashs am Anfang des (verbliebenen) Inputs gefunden, wird der gesamte Input solange ignoriert, bis entweder das Ende des Inputs erreicht oder ein Zeilenumbruch gefunden wurde:

[...]
elif src.startswith("//"):
    # Behandlung des Kommentars
    while len(src) > 0 and src[0] != "\n":
        src = src[1:]

    # Zeilenende erreicht
    line += 1
    col = 1
    src = src[1:]
[...] 

Ergänzt man die Tokenklasse um eine “pretty print”-Funktion (formatierte __str__-Methode) und gibt die produzierten Token der Reihe nach aus, so erhält man zu obigem Beispielquelltext den folgenden Anfang der Tokenliste:

$ python lexer.py
<Token line=1 col=1 type=Keyword content='var'>
<Token line=1 col=5 type=Identifier content='c'>
<Token line=1 col=7 type=Assign content='='>
<Token line=1 col=9 type=Number content='2'>
<Token line=1 col=10 type=Semicolon content=';'>
<Token line=2 col=5 type=Keyword content='var'>
<Token line=2 col=9 type=Identifier content='s'>
<Token line=2 col=11 type=Assign content='='>
<Token line=2 col=13 type=Number content='0.5'>
<Token line=2 col=16 type=Semicolon content=';'>
[...]

Wird dem Lexer ein Input präsentiert, der von ihm nicht erkannt werden kann (zum Beispiel ein “&“), quittiert er seine Arbeit wie folgt:

$ python lexer.py
[Syntaxerror Line 1 Col 1] Unknown character '&' (38)

Der Lexer ist nun soweit fertig! Spannend wird im nächsten Blogpost, wie der Parser die produzierten Tokens nutzt, um anhand einer noch näher zu definierenden Grammatik einen Baum abzuleiten.

Bei Fragen zu meiner Blogpostserie nutzt gerne die Kommentarfunktion. Bis dahin!

Weiter zum Teil 3


New comment

Comments are moderated and therefore are not published instantly.





Comments

No comments yet. Be the first! :-)