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

(P1 | P2 | P3) Finde P1, P2 oder P3 genau einmal
(P1 | P2 | P3)? Finde nichts oder P1, P2 oder P3 genau einmal
(P1 | P2 | P3)+ Finde P1, P2 oder P3 mehrmals
(P1 | P2 | P3)* Finde nichts oder P1, P2 oder P3 mehrmals



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

TOKEN^ Verwende TOKEN als "Root-Token" bei der Erstellung des AST
TOKEN! Ignoriere TOKEN bei der Erstellung des AST

 

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

AST-Syntax

#label Ein AST-Blatt, der durch diese Regel
#regel Bezeichnet den resultierenden AST, der durch diese Regel erzeugt wird. Dies erlaubt den von der Regel zurückgelieferten AST zu bestimmen oder auf ihn innerhalb der Regel zuzugreifen.
Diese Möglichkeit kann bei der Erstellung eines AST sehr hilfreich sein, wenn man das folgende Beispiel betrachtet:

decl : ( TYPE ID )+
{ #decl = #([DECL,"decl"], #decl); } ;


Hier wird ANTLR die Arbeit zum Aufbau des AST überlassen und nur zum Schluß eine spezielle Wurzel hinzugefügt.
#label_in Dieser Bezeichner wird normalerweise nicht bennötigt.
#label_in bezeichnet den AST der an in die Regel übergeben wird.
#bezeichner ANTLR unterstützt auch unbenannte Token-Referenzen solange der Bezeichner eindeutig innerhalb des Scopes einer Alternative ist. In diesem Fall ist die Verwendung von unbenannten Token-Referenzen mit der Verwendung von #label gleichbedeutend. Beispielsweise ist
r! : A { #r = #A; }
gleichbedeutend mit
r! : a:A { #r = #a; }
#[TOKEN_TYPE] oder #[TOKEN_TYPE,"text"] Kann als Kurzbezeichner zur Erstellung eines AST-Blattes verwendet werden. ANTLR übersetzt diese Anweisung in einen ASTFactory.create() Aufruf.
Zum Beispiel wird
#[T] zu ASTFactory.create(T)
übersetzt.
#(root, c1, ..., cn) Kann als Kurzbezeichner zur Erstellung eines AST verwendet werden. ANTLR übersetzt diese Anweisung in einen ASTFactory.make(root, c1, ..., cn); Aufruf.


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
}