ANTLR 2 - Eine Einführung (german)

ANTLR  Another Tool for Language Recognition

Der Zusammenhang zwischen Lexer, Parser und TreeParser

Im Compilerbau unterscheidet man zwischen mehreren Phasen, die bei der Umsetzung der jeweiligen Programmiersprache in eine für die Maschine, also den Computer, brauchbare Form, durchlaufen werden. Diese Phasen führen verschiedene Analysen und Operationen mit dem eingegebnenen Code durch.
Im Einzelnen sind dies:

• Lexikalische Analyse (Scanning)
• Syntaktische Analyse (Parsing)
• Semantische Analyse
• Erzeugung von Zwischencode
• Codegenerierung (ggf. Optimierung)

Lexikalische Analyse

Bei der Lexikalischen Analyse wird der Quellcode, also der Eingabestrom, in einzelne Symbole (Tokens) zerlegt. Dabei unterscheidet der Lexer (oder auch Scanner genannt) zwischen, den durch den Sprachsyntax vorgegebenen Symbolen, Variablen und Operatoren.

Syntaktische Analyse

Der in diesem Stadium verwendete Programmteil wird Parser genannt und liest den vom Lexer in einzele Token zerteilten Strom ein, prüft diese auf syntaktische Richtigkeit und erstellt daraus Symbol-Gruppen mit hierarchischer Struktur. Die Struktur ist oft ein Baum und wird dann Parse-tree genannt.

Semantische Analyse

Die auf die Syntaktische Analyse folgende prüft nun die semantische Korrektheit des Programms. Dazu gehören die Prüfung auf korrekte Typisierung, die Einhaltung von Gültigkeitsbereichen und eventuelle Typanpassungen.

Semantische Analyse

Wurde die semantische Analyse erfolgreich durchlaufen, erstellt der Compiler im allgemeinen zuerst einen als Zwischencode bezeichneten pseudocode, der noch nicht genau auf die Zielmaschinenspezifische Maschinencode-Definition eingeht.

Da dieses Dokument kein Script für Compilerbau werden soll und kann, wird hier nur auf die ersten drei Phasen der Coderzeugung eingegangen und die Zusammenhänge mit dem Java-Tool ANTLR erklärt.

ANTLR

Da das Erstellen von Lexern und Parsern, gerade bei komplexen Programmiersprachen wie C oder C++ eine sehr mühsame Angelegenheit werden kann, wurden Tools entwickelt, die Compiler-Compiler genannt werden und aus einer angegebenen Grammatik den Quellcode für einen Lexer und Parser generieren. Das bekannteste Gespann hierführ sind Lex (ein Lexergenerator) und Yacc (der dazugehörige Parsergenerator). Der größte Unterschied zwischen diesen und ANTLR besteht darin, daß ANTLR ein LL(k) Compiler-Compiler, Lex / Yacc nur LL(1) Compiler-Compiler sind was bei Lex / Yacc zu relativ komplexen Grammatiken führt.
Es bleibt noch anzumerken, daß man mit "handgeschriebenen" Lexern / Parser eine ca. 20% höhere Verarbeitungsgeschwindigkeit ereicht, was allerdings durch die Erstellung des Quellcodes und der damit verbundnene Schwierigkeiten "erkauft" werden muß.

Die Grammatik von ANTLR

Für die Erstellung von Lexern und Parsern muß eine Grammatik-Datei erstellt werden, welche die zu implementierende Sprache spezifiziert. Dabei müssen die für ANTLR geltenden Regeln beachtet werden.

• Alle Lexer Bezeichner werden am Wortanfang groß geschrieben.
• Alle Parser Bezeichner werden am Wortanfang klein geschrieben.

Besondere Sprachmittel
Innerhalb einer Regel können Unterregeln definiert werden. Diese sogenannten EBNF-Regeln kann man sich als "unbenannte" Regeln vorstellen, durch die man die zu scannende Sprache weiter auflösen kann.

EBNF Regel-Elemente

AST Erstellung

Um den Quellcode weiter verarbeiten zu können kann dieser in einen oder mehrere ASTs (Abstract Syntax Tree) aufgeteilt werden. Auch hier spielt ANTLR eine Rolle, denn ANTLR kann durch die Option "builtAST=true" dazu veranlaßt werden einen AST zu erstellen. Nur in Verbindung mit dieser Option gibt es einen erweiterten Token-Syntax der ansonsten einfach ignoriert wird.

Erweiterter AST Token-Syntax

In Verbindung mit zusätzlichen Aktionen innerhalb einer Regel können die folgenden Bezeichner verwendet werden:

AST-Syntax

Zusätzlicher Quellcode

ANTLR bietet mehrere Möglichkeiten zusätzlichen Quellcode der Zielsprache (also C++ oder Java) in die Regeln oder Klassen einzufügen. Des weiteren können natülich auch Klassen von den ANTLR Basisklassen abgeleitet werden um eine erweiterte Funktionalität zu erreichen. Zum Beispiel könnte der Nutzer mehr Informationen über ein einzelnes Token speichern wollen und leitet daher eine Klasse von antlr.CommonToken ab:

public class CToken extends antlr.CommonToken {
  // TokenKlasse mit zusötzlicher Quelldatei Information
  String source = "";
  public String getSource() { return source; };
  public void setSource(String src) { source = src; };
};

Allgemeines Grammarfile

Jedes Grammarfile ist in mehrere Abschnitte unterteilt, mittels denen man die Codeerzeugung steuern und den zusätzlichen Quellcode in den richtigen Dateien "plazieren" kann.
options Block
Anstatt, wie in früheren Versionen, ANTLR mit einer Unmenge von Schaltern zu starten, wurde ein options-Block eingeführt. Dies ermöglicht aussagekräftigere Namen und führt zu mehr Übersicht.
header-Block
Es kann ein oder mehrere Header-Blöcke angegeben werden, die zumeist dau verwendet werden Zielsprachenspezifische Includedateien einzufügen. Wird der Block ohne flag definiert, wird der innerhalb des Blocks stehende Quellcode in alle von ANTLR generierten Headerdateien eingefügt.

options {
  // ANTLR spezifische Optionen
  // z.Zt. einzig und allein:
  language = "Cpp"; (oder "Java")
}

header ["flag"]{
  // sourcecode, der in alle Header-Dateien eingefügt wird
  // optional: Für flag kann stehen (ab ANTLR 2.70)
  //           pre_include_hpp, pre_include_cpp
  //           post_include_hpp, post_reinclude_cpp
}
header {
}

{
  // Quellcode für die cpp Datei
}
Myclass extends Lexer;
options {
  // ANTLR spezifische Optionen zur erstellung dieser Klasse
}
{
  // Quellcode für die hpp Datei
}