CFG

Wiederholung

Endliche Automaten, reguläre Ausdrücke, reguläre Grammatiken, reguläre Sprachen

• Wie sind DFAs und NFAs definiert?
• Was sind reguläre Ausdrücke?
• Was sind formale und reguläre Grammatiken?
• In welchem Zusammenhang stehen all diese Begriffe?
• Wie werden DFAs und reguläre Ausdrücke im Compilerbau eingesetzt?

Motivation

Wofür reichen reguläre Sprachen nicht?

Für z. B. alle Sprachen, in deren Wörtern Zeichen über eine Konstante hinaus gezählt werden müssen. Diese Sprachen lassen sich oft mit Variablen im Exponenten beschreiben, die unendlich viele Werte annehmen können.

• $a^ib^{2*i}$ ist nicht regulär

• $a^ib^{2*i}$ für $0 \leq i \leq 3$ ist regulär

• Wo finden sich die oben genannten Variablen bei einem DFA wieder?

• Warum ist die erste Sprache oben nicht regulär, die zweite aber?

Themen für heute

• PDAs: mächtiger als DFAs, NFAs
• kontextfreie Grammatiken und Sprachen: mächtiger als reguläre Grammatiken und Sprachen
• DPDAs und deterministisch kontextfreie Grammatiken: die Grundlage der Syntaxanalyse im Compilerbau
• Der Einsatz kontextfreier Grammatiken zur Syntaxanalyse mittels Top-Down-Techniken

Einordnung: Erweiterung der Automatenklasse DFA, um komplexere Sprachen als die regulären akzeptieren zu können

Wir spendieren den DFAs einen möglichst einfachen, aber beliebig großen, Speicher, um zählen und matchen zu können. Wir suchen dabei konzeptionell die "kleinstmögliche" Erweiterung, die die akzeptierte Sprachklasse gegenüber DFAs vergrößert.

• Der konzeptionell einfachste Speicher ist ein Stack. Wir haben keinen wahlfreien Zugriff auf die gespeicherten Werte.

• Es soll eine deterministische und eine indeterministische Variante der neuen Automatenklasse geben.

• In diesem Zusammenhang wird der Stack auch Keller genannt.

Kellerautomaten (Push-Down-Automata, PDAs)

Def.: Ein Kellerautomat (PDA) $P = (Q,\ \Sigma,\ \Gamma,\ \delta,\ q_0,\ \perp,\ F)$ ist ein Septupel mit:

Ein PDA ist per Definition nichtdeterministisch und kann spontane Zustandsübergänge durchführen.

Was kann man damit akzeptieren?

Strukturen mit paarweise zu matchenden Symbolen.

Bei jedem Zustandsübergang wird ein Zeichen (oder $\epsilon$) aus der Eingabe gelesen, ein Symbol von Keller genommen. Diese und das Eingabezeichen bestimmen den Folgezustand und eine Zeichenfolge, die auf den Stack gepackt wird. Dabei wird ein Symbol, (z. B. eines, das später mit einem Eingabesymbol zu matchen ist,) auf den Stack gepackt. Soll das automatisch vom Stack genommene Symbol auf dem Stack bleiben, muss es wieder gepusht werden.

Beispiel

Ein PDA für $L=\lbrace ww^{R}\mid w\in \lbrace a,b\rbrace^{\ast}\rbrace$:

Deterministische PDAs

Def. Ein PDA $P = (Q, \Sigma, \Gamma, \delta, q_0, \perp, F)$ ist deterministisch $: \Leftrightarrow$

• $\delta(q, a, X)$ hat höchstens ein Element für jedes $q \in Q, a \in\Sigma$ oder $(a = \epsilon$ und $X \in \Gamma)$.

• Wenn $\delta (q, a, x)$ nicht leer ist für ein $a \in \Sigma$, dann muss $\delta (q, \epsilon, x)$ leer sein.

Deterministische PDAs werden auch DPDAs genannt.

Der kleine Unterschied

Satz: Die von DPDAs akzeptierten Sprachen sind eine echte Teilmenge der von PDAs akzeptierten Sprachen.

Die regulären Sprachen sind eine echte Teilmenge der von DPDAs akzeptierten Sprachen.

Kontextfreie Grammatiken und Sprachen

Kontextfreie Grammatiken

Def. Eine kontextfreie (cf-) Grammatik ist ein 4-Tupel $G = (N, T, P, S)$ mit $N, T, S$ wie in (formalen) Grammatiken und $P$ ist eine endliche Menge von Produktionen der Form:

$X \rightarrow Y$ mit $X \in N, Y \in {(N \cup T)}^{\ast}$.

$\Rightarrow, \overset{\ast}{\Rightarrow}$ sind definiert wie bei regulären Sprachen. Bei cf-Grammatiken nennt man die Ableitungsbäume oft Parse trees.

Beispiel

Ableitungsbäume für $a + a \ast a$:

Hier entsteht ein Tafelbild.

Nicht jede kontextfreie Grammatik ist eindeutig

Def.: Gibt es in einer von einer kontextfreien Grammatik erzeugten Sprache ein Wort, für das mehr als ein Ableitungsbaum existiert, so heißt diese Grammatik mehrdeutig. Anderenfalls heißt sie eindeutig.

Satz: Es ist nicht entscheidbar, ob eine gegebene kontextfreie Grammatik eindeutig ist.

Satz: Es gibt kontextfreie Sprachen, für die keine eindeutige Grammatik existiert.

Kontextfreie Grammatiken und PDAs

Satz: Die kontextfreien Sprachen und die Sprachen, die von PDAs akzeptiert werden, sind dieselbe Sprachklasse.

Satz: Eine von einem DPDA akzeptierteSprache hat eine eindeutige Grammatik.

Vorgehensweise im Compilerbau: Eine Grammatik für die gewünschte Sprache definieren und schauen, ob sich daraus ein DPDA generieren lässt (automatisch).

Syntaxanalyse

Was brauchen wir für die Syntaxanalyse von Programmen?

• einen Grammatiktypen, aus dem sich manuell oder automatisiert ein Programm zur deterministischen Syntaxanalyse (=Parser) erstellen lässt

• einen Algorithmus zum Parsen von Programmen mit Hilfe einer solchen Grammatik

Syntax

Wir verstehen unter Syntax eine Menge von Regeln, die die Struktur von Daten (z. B. Programmen) bestimmen.

Diese vorgegebene Syntax wird im Compilerbau mit einer kontextfreien Grammatik beschrieben und mit einem sogenannten Parser analysiert.

Heute: LL-Parsing, mit dem man eine Teilmenge der eindeutigen kontextfreien Grammatiken syntaktich analysieren kann.

Dabei wird der Ableitungsbaum von oben nach unten aufgebaut.

Ziele der Syntaxanalyse

• Bestimmung der syntaktischen Struktur eines Programms

• aussagekräftige Fehlermeldungen, wenn ein Eingabeprogramm syntaktisch nicht korrekt ist

• Erstellung des AST (abstrakter Syntaxbaum): Der Parse Tree ohne Symbole, die nach der Syntaxanalyse inhaltlich irrelevant sind (z. B. Semikolons, manche Schlüsselwörter)

• die Symboltablelle(n) mit Informationen bzgl. Bezeichner (Variable, Funktionen und Methoden, Klassen, benutzerdefinierte Typen, Parameter, ...), aber auch die Gültigkeitsbereiche.

LL(k)-Grammatiken

First-Mengen

Welche Produktion nehmen?

Wir brauchen die "terminalen k-Anfänge" von Ableitungen von Nichtterminalen, um eindeutig die nächste zu benutzende Produktion festzulegen. $k$ ist dabei die Anzahl der Vorschautoken.

Def.: Wir definieren $First$ - Mengen einer Grammatik wie folgt:

• $a \in T^\ast, |a| \leq k: {First}_k (a) = \lbrace a \rbrace$
• $a \in T^\ast, |a| > k: {First}_k (a) = \lbrace v \in T^\ast \mid a = vw, |v| = k \rbrace$
• $\alpha \in (N \cup T)^\ast \backslash T^\ast: {First}_k (\alpha) = \lbrace v \in T^\ast \mid \alpha \overset{\ast}{\Rightarrow} w,\text{mit}\ w \in T^\ast, First_k(w) = \lbrace v \rbrace \rbrace$

Linksableitungen

Def.: Bei einer kontextfreien Grammatik $G$ ist die Linksableitung von $\alpha \in (N \cup T)^{\ast}$ die Ableitung, die man erhält, wenn in jedem Schritt das am weitesten links stehende Nichtterminal in $\alpha$ abgeleitet wird.

Man schreibt $\alpha \overset{\ast}{\Rightarrow}_l \beta.$

LL(k)-Grammatiken

Def.: Eine kontextfreie Grammatik $G = (N, T, P, S)$ ist genau dann eine LL(k)-Grammatik, wenn für alle Linksableitungen der Form:

und

mit $(w, x, y \in T^\ast, \alpha, \beta, \gamma \in (N \cup T)^\ast, A \in N)$ und $First_k(x) = First_k(y)$ gilt:

LL(1)-Grammatiken

Hier entsteht ein Tafelbild.

LL(k)-Sprachen

Die von LL(k)-Grammatiken erzeugten Sprachen sind eine echte Teilmenge der deterministisch parsbaren Sprachen.

Die von LL(k)-Grammatiken erzeugten Sprachen sind eine echte Teilmenge der von LL(k+1)-Grammatiken erzeugten Sprachen.

Für eine kontextfreie Grammatik $G$ ist nicht entscheidbar, ob es eine LL(1) - Grammatik $G'$ gibt mit $L(G) = L(G')$.

In der Praxis reichen LL(1) - Grammatiken oft. Hier gibt es effiziente Parsergeneratoren (hier: ANTLR), deren Eingabe eine LL-Grammatik ist, und die als Ausgabe den Quellcode eines (effizienten) tabellengesteuerten Parsers generieren.

Was brauchen wir zur Erzeugung eines LL(k)-Parsers?

• eine LL(k)-Grammatik
• die $First_k$-Mengen der rechten Seiten aller Produktionsregeln
• die $Follow_k$-Mengen aller Nichtterminale und der rechten Seiten aller Produktionsregeln
• das Endezeichen $\perp$ hinter dem Eingabewort

Def.: Wir definieren $Follow$ - Mengen einer Grammatik wie folgt:

Beispiel: First- und Follow-Mengen

Hier entsteht ein Tafelbild.

Algorithmus: Konstruktion einer LL-Parsertabelle

Eingabe: Eine Grammatik $G = (N, T, P, S)$

Ausgabe: Eine Parsertabelle $P$

Statt $First_1(\alpha)$ wird oft nur $First(\alpha)$ geschrieben.

Beispiel: LL-Parsertabellen

Hier entsteht ein Tafelbild.

LL-Parser

Rekursive Programmierung bedeutet, dass das Laufzeitsystem einen Stack benutzt. Diesen Stack kann man auch "selbst programmieren", d. h. einen PDA implementieren. Dabei wird ebenfalls die oben genannte Tabelle zur Bestimmung der nächsten anzuwendenden Produktion benutzt. Der Stack enthält die zu erwartenden Eingabezeichen, wenn immer eine Linksableitung gebildet wird. Diese Zeichen im Stack werden mit dem Input gematcht.

Algorithmus: Tabellengesteuertes LL-Parsen mit einem PDA

Eingabe: Eine Grammatik $G = (N, T, P, S)$, eine Parsertabelle $P$ mit "$w\perp$" als initialem Kellerinhalt

Ausgabe: Wenn $w \in L(G)$, eine Linksableitung von $w$, Fehler sonst

Beispiel: LL-Parsen

Hier entsteht ein Tafelbild.

Ergebnisse der Syntaxanalyse

• eventuelle Syntaxfehler mit Angabe der Fehlerart und des -Ortes

• Format für die Weiterverarbeitung:

  • Ableitungsbaum oder Syntaxbaum oder Parse Tree
  • abstrakter Syntaxbaum (AST): Der Parse Tree ohne Symbole, die nach der Syntaxanalyse inhaltlich irrelevant sind (z. B. ;, Klammern, manche Schlüsselwörter, $\ldots$)

Wrap-Up

Das sollen Sie mitnehmen

• Die Struktur von gängigen Programmiersprachen lässt sich nicht mit regulären Ausdrücken beschreiben und damit nicht mit DFAs akzeptieren.
• Das Automatenmodell der DFAs wird um einen endlosen Stack erweitert, das ergibt PDAs.
• Kontextfreie Grammatiken (CFGs) erweitern die regulären Grammatiken.
• Deterministisch parsebare Sprachen haben eine eindeutige kontextfreie Grammatik.
• Es ist nicht entscheidbar, ob eine gegebene kontextfreie Grammatik eindeutig ist.
• Syntaxanalyse wird mit deterministisch kontextfreien Grammatiken durchgeführt.
• Eine Teilmenge der dazu gehörigen Sprachen lässt sich top-down parsen.
• Ein effizienter LL(k)-Parser realisiert einen DPDA und kann automatisch aus einer LL(k)-Grammatik generiert werden.
• Der Parser liefert in der Regel einen abstrakten Syntaxbaum.

Parser mit ANTLR generieren

Hello World

grammar Hello;

start : stmt* ;

stmt  : ID '=' expr ';' | expr ';' ;

expr  : term ('+' term)* ;
term  : atom ('*' atom)* ;

atom  : ID | NUM ;

ID    : [a-z][a-zA-Z]* ;
NUM   : [0-9]+ ;
WS    : [ \t\n]+ -> skip ;

Starten des Parsers

1. Grammatik übersetzen und Code generieren: antlr Hello.g4
2. Java-Code kompilieren: javac *.java
3. Parser ausführen:

   • grun Hello start -tree oder grun Hello start -gui (Grammatik "Hello", Startregel "start")

   • Alternativ mit kleinem Java-Programm:

     import org.antlr.v4.runtime.CharStreams;
     import org.antlr.v4.runtime.CommonTokenStream;
     import org.antlr.v4.runtime.tree.ParseTree;
     
     public class Main {
         public static void main(String[] args) throws Exception {
             HelloLexer lexer = new HelloLexer(CharStreams.fromStream(System.in));
             CommonTokenStream tokens = new CommonTokenStream(lexer);
             HelloParser parser = new HelloParser(tokens);
     
             ParseTree tree = parser.start();  // Start-Regel
             System.out.println(tree.toStringTree(parser));
         }
     }

Startregeln

• start ist eine Parser-Regel => Eine Parser-Regel pro Grammatik wird benötigt, damit man den generierten Parser am Ende auch starten kann ...
• Alle Regeln mit kleinem Anfangsbuchstaben sind Parser-Regeln
• Alle Regeln mit großem Anfangsbuchstaben sind Lexer-Regeln

Formen der Subregeln

stmt  : ID '=' expr ';' ;

Um die Regel stmt anwenden zu können, müssen alle Elemente auf der rechten Seite der Regel erfüllt werden. Dabei müssen die Token wie ID, = und ; matchen und die Subregel expr muss erfüllt werden können. Beachten Sie das abschließende Semikolon am Ende einer ANTLR-Regel!

stmt  : ID '=' expr ';' | expr ';' ;

Alternativen werden durch ein | getrennt. Hier muss genau eine Alternative erfüllt werden. Falls nötig, trennt man die Alternativen durch Einschließung in runden Klammern vom Rest der Regel ab: r : a (b | c) d ;.

expr  : term ('+' term)* ;

Der durch den * gekennzeichnete Teil kann beliebig oft vorkommen oder auch fehlen. Bei einem + müsste der Teil mind. einmal vorkommen und bei einem ? entsprechend einmal oder keinmal.

Auch hier kann man die Operatoren durch ein zusätzliches ? auf non-greedy umschalten (analog zu den Lexer-Regeln).

(vgl. github.com/antlr/antlr4/blob/master/doc/parser-rules.md)

Reihenfolge in Grammatik definiert Priorität

Falls mehr als eine Parser-Regel die selbe Input-Sequenz matcht, löst ANTLR diese Mehrdeutigkeit auf, indem es die erste Alternative nimmt, die an der Entscheidung beteiligt ist.

start : stmt ;

stmt  : expr | ID  ;
expr  : ID   | NUM ;

Bei der Eingabe "foo" würde die Alternative ID in der Regel expr "gewinnen", weil sie in der Grammatik vor der Alternative ID in der Regel stmt kommt und damit Vorrang hat.

Parse-Tree

Betrachten wir erneut die obige Grammatik.

Die Eingabe von "a = 42;" führt zu folgendem Parse-Tree:

Diese Eingabe führt zur Erkennung der Token [ID, WS, =, WS, NUM, ;], wobei die WS-Token verworfen werden und der Parser den Tokenstream [ID, =, NUM, ;] erhält.

Die Startregel hat auf der rechten Seite kein oder mehrere stmt-Regeln. Die stmt-Regel fordert auf der rechten Seite entweder die Token IDund = sowie die Regel expr gefolgt vom Token ;, oder die Regel expr gefolgt vom Token ;. In unserem Beispiel kann für das "a" das Token ID produziert werden, das "=" matcht ebenfalls. Die "42" wird erklärt, indem für expr ein term und dort ein atom aufgerufen wird. Für das atom muss entweder ein Token ID oder NUM als nächstes Token kommen - hier wird die "42" wird als Token NUM verarbeitet. Da die weiteren Regelteile in term und expr optional sind, haben wir damit ein expr erfüllt und das nachfolgende ;-Token schließt die erste Alternative der Regel stmt erfolgreich ab.

Im entstehenden Parse-Tree sind diese Abläufe und grammatikalischen Strukturen direkt erkennbar. Jede erfolgreich durchlaufene Parserregel wird zu einem Knoten im Parse-Tree. Die Token werden als Terminale (Blätter) in den Baum eingehängt.

Anmerkung: Der Parse-Tree ist das Ergebnis der Parsers-Phase im Compiler und dient damit als Input für die folgenden Compilerstufen. In der Regel benötigt man die oft recht komplexen Strukturen aber später nicht mehr und vereinfacht den Baum zu einem Abstract Syntax Tree (AST). Im Beispiel könnte man den Zweig stmt - expr - term - atom - 42 zu stmt - 42 vereinfachen.

Betrachten wir nun die Eingabe foo = 2+3*4; bar = 3*4+2;. Diese führt zu folgendem Parse-Tree:

Wie man sehen kann, sind in der Grammatik die üblichen Vorrangregeln für die Operationen + und * berücksichtigt - die Multiplikation wird in beiden Fällen korrekt "unter" der Addition im Baum eingehängt.

To EOF not to EOF?

Startregeln müssen nicht unbedingt den gesamten Input "konsumieren". Sie müssen per Default nur eine der Alternativen in der Startregel erfüllen.

Betrachten wir noch einmal einen leicht modifizierten Ausschnitt aus der obigen Grammatik:

start : stmt ;

Die Startregel wurde so geändert, dass sie nur noch genau ein Statement akzeptieren soll.

In diesem Fall würde die Startregel bei der Eingabe "aa; bb;" nur den ersten Teil "aa;" konsumieren (als Token ID) und das folgende "bb;" ignorieren. Das wäre in diesem Fall aber auch kein Fehler.

Wenn der gesamte Eingabestrom durch die Startregel erklärt werden soll, dann muss das vordefinierte Token EOF am Ende der Startregel eingesetzt werden:

start : stmt EOF;

Hier würde die Eingabe "aa; bb;" zu einem Fehler führen, da nur der Teil "aa;" durch die Startregel abgedeckt ist (Token ID), und der Rest "bb;" zwar sogar ein gültiges Token wären (ebenfalls ID und ;), aber eben nicht mehr von der Startregel akzeptiert. Durch das EOF soll die Startregel aber den gesamten Input konsumieren und erklären, was hier nicht geht und entsprechend zum Fehler führt.

(vgl. github.com/antlr/antlr4/blob/master/doc/parser-rules.md)

Expressions und Vorrang (Operatoren)

Betrachten wir noch einmal den Ausschnitt für die Ausdrücke (Expressions) in der obigen Beispielgrammatik:

expr  : term ('+' term)* ;
term  : atom ('*' atom)* ;
atom  : ID ;

Diese typische, etwas komplex anmutende Struktur soll sicher stellen, dass die Vorrangregeln für Addition und Multiplikation korrekt beachtet werden, d.h. dass 2+3*4 als 2+(3*4) geparst wird und nicht fälschlicherweise als (2+3)*4 erkannt wird.

Zusätzlich muss bei LL-Parsern Links-Rekursion vermieden werden: Die Parser-Regeln werden in Funktionsaufrufe übersetzt, d.h. bei einer Links-Rekursion würde man die selbe Regel immer wieder aufrufen, ohne ein Token aus dem Token-Strom zu entnehmen.

ANTLR (ab Version 4) kann mit beiden Aspekten automatisch umgehen:

• ANTLR kann direkte Linksrekursion automatisch auflösen. Die Regel r : r T U | V ; kann also in ANTLR verarbeitet werden.
• ANTLR besitzt einen Mechanismus zur Auflösung von Mehrdeutigkeiten. Wie oben geschrieben, wird bei der Anwendbarkeit von mehreren Alternativen die erste Alternative genutzt.

Damit lässt sich die typische Struktur für Expression-Grammatiken deutlich lesbarer gestalten:

expr  : expr '*' expr
      | expr '+' expr
      | ID
      ;

Die Regel expr ist links-rekursiv, was normalerweise bei LL-Parsern problematisch ist. ANTLR löst diese Links-Rekursion automatisch auf (vgl. github.com/antlr/antlr4/blob/master/doc/left-recursion.md).

Da bei Mehrdeutigkeit in der Grammatik, also bei der Anwendbarkeit mehrerer Alternativen stets die erste Alternative genommen wird, lassen sich die Vorrangregeln durch die Reihenfolge der Alternativen in der expr-Regel implementieren: Die Multiplikation hat Vorrang von der Addition, und diese hat wiederum Vorrang von einer einfachen ID.

Direkte vs. indirekte Links-Rekursion

ANTLR kann nur direkte Links-Rekursion auflösen. Regeln wie r : r T U | V ; stellen in ANTLR also kein Problem dar.

Indirekte Links-Rekursion erkennt ANTLR dagegen nicht:

r : s T U | V ;
s : r W X ;

Hier würden sich die Regeln r und s gegenseitig aufrufen und kein Token aus dem Tokenstrom entfernen, so dass der generierte LL-Parser hier in einer Endlosschleife stecken bleiben würde. Mit indirekter Links-Rekursion kann ANTLR nicht umgehen.

Konflikte in Regeln

Wenn mehrere Alternativen einer Regel anwendbar sind, entscheidet sich ANTLR für die erste Alternative.

Wenn sich mehrere Tokenregeln überlappen, "gewinnt" auch hier die zuerst definierte Regel.

def : 'func' ID '(' ')' block ;

FOR : 'for' ;
ID  : [a-z][a-zA-Z]* ;

Hier werden ein implizites Token 'func' sowie die expliziten Token FOR und ID definiert. Dabei sind die Lexeme für 'func' und FOR auch in ID enthalten. Dennoch werden 'func' und FOR erkannt und nicht über ID gematcht, weil sie vor der Regel ID definiert sind.

Tatsächlich sortiert ANTLR die Regeln intern um, so dass alle Parser-Regeln vor den Lexer-Regeln definiert sind. Die impliziten Token werden dabei noch vor den expliziten Token-Regeln angeordnet. Im obigen Beispiel hat also 'func' eine höhere Priorität als FOR, und FOR hat eine höhere Priorität als ID. Aus diesem Grund gibt es die Konvention, die Parser-Regeln in der Grammatik vor den Lexer-Regeln zu definieren - dies entspricht quasi der Anordnung, die ANTLR bei der Verarbeitung sowieso erzeugen würde.

Aus diesem Grund würde auch eine Umsortierung der obigen Grammatik funktionieren:

FOR : 'for' ;
ID  : [a-z][a-zA-Z]* ;

def : 'func' ID '(' ')' block ;

Intern würde ANTLR die Parser-Regel def wieder vor den beiden Lexer-Regeln anordnen, und zwischen den Parser-Regeln und den Lexer-Regeln die impliziten Token (hier 'func').

Kontext-Objekte für Parser-Regeln

s    : expr         {List<EContext> x = $expr.ctx.e();}
     ;
expr : e '*' e ;

Jede Regel liefert ein passend zu dieser Regel generiertes Kontext-Objekt zurück. Darüber kann man das/die Kontextobjekt(e) der Sub-Regeln abfragen.

Die Regel s liefert entsprechend ein SContext-Objekt und die Regel expr liefert ein ExprContext-Objekt zurück.

In der Aktion fragt man das Kontextobjekt über ctx ab, in den Listener- und Visitor-Methoden erhält man die Kontextobjekte als Parameter.

Für einfache Regel-Aufrufe liefert die parameterlose Methode nur ein einziges Kontextobjekt (statt einer Liste) zurück.

Anmerkung: ANTLR generiert nur dann Felder für die Regel-Elemente im Kontextobjekt, wenn diese in irgendeiner Form referenziert werden. Dies kann beispielsweise durch Benennung (Definition eines Labels, siehe nächste Folie) oder durch Nutzung in einer Aktion (siehe obiges Beispiel) geschehen.

Benannte Regel-Elemente oder Alternativen

stat  : 'return' value=e ';'    # Return
      | 'break' ';'             # Break
      ;

public static class StatContext extends ParserRuleContext { ... }
public static class ReturnContext extends StatContext {
    public EContext value;
    public EContext e() { ... }
}
public static class BreakContext extends StatContext { ... }

Mit value=e wird der Aufruf der Regel e mit dem Label value belegt, d.h. man kann mit $e.text oder $value.text auf das text-Attribut von e zugreifen. Falls es in einer Produktion mehrere Aufrufe einer anderen Regel gibt, muss man für den Zugriff auf die Attribute eindeutige Label vergeben.

Analog wird für die beiden Alternativen je ein eigener Kontext erzeugt.

Arbeiten mit ANTLR-Listeners

ANTLR (generiert auf Wunsch) zur Grammatik passende Listener (Interface und leere Basisimplementierung). Beim Traversieren mit dem Default-ParseTreeWalker wird der Parse-Tree mit Tiefensuche abgelaufen und jeweils beim Eintritt in bzw. beim Austritt aus einen/m Knoten der passende Listener mit dem passenden Kontext-Objekt aufgerufen.

Damit kann man die Grammatik "für sich" halten, d.h. unabhängig von einer konkreten Zielsprache und die Aktionen über die Listener (oder Visitors, s.u.) ausführen.

expr : e1=expr '*' e2=expr      # MULT
     | e1=expr '+' e2=expr      # ADD
     | DIGIT                    # ZAHL
     ;

ANTLR kann zu dieser Grammatik calc.g4 einen passenden Listener (Interface calcListener) generieren (Option -listener beim Aufruf von antlr). Weiterhin generiert ANTLR eine leere Basisimplementierung (Klasse calcBaseListener):

(Nur "interessante" Methoden gezeigt.)

Von dieser Basisklasse leitet man einen eigenen Listener ab und implementiert die Methoden, die man benötigt.

public static class MyListener extends calcBaseListener {
    public void exitMULT(calcParser.MULTContext ctx) {
        ...
    }
    public void exitADD(calcParser.ADDContext ctx) {
        ...
    }
    public void exitZAHL(calcParser.ZAHLContext ctx) {
        ...
    }
}

Anschließend baut man das alles in eine Traversierung des Parse-Trees ein:

public class TestMyListener {
    public static class MyListener extends calcBaseListener {
        ...
    }

    public static void main(String[] args) throws Exception {
        calcLexer lexer = new calcLexer(CharStreams.fromStream(System.in));
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        calcParser parser = new calcParser(tokens);

        ParseTree tree = parser.s();    // Start-Regel

        ParseTreeWalker walker = new ParseTreeWalker();
        MyListener eval = new MyListener();
        walker.walk(eval, tree);
    }
}

Arbeiten mit dem Visitor-Pattern

ANTLR (generiert ebenfalls auf Wunsch) zur Grammatik passende Visitoren (Interface und leere Basisimplementierung).

Hier muss man im Gegensatz zu den Listeners allerdings selbst für eine geeignete Traversierung des Parse-Trees sorgen. Dafür hat man mehr Freiheiten im Vergleich zum Einsatz von Listeners, insbesondere im Hinblick auf Rückgabewerte.

expr : e1=expr '*' e2=expr      # MULT
     | e1=expr '+' e2=expr      # ADD
     | DIGIT                    # ZAHL
     ;

ANTLR kann zu dieser Grammatik einen passenden Visitor (Interface calcVisitor<T>) generieren (Option -visitor beim Aufruf von antlr). Weiterhin generiert ANTLR eine leere Basisimplementierung (Klasse calcBaseVisitor<T>):

(Nur "interessante" Methoden gezeigt.)

Von dieser Basisklasse leitet man einen eigenen Visitor ab und überschreibt die Methoden, die man benötigt. Wichtig ist, dass man selbst für das "Besuchen" der Kindknoten sorgen muss (rekursiver Aufruf der geerbten Methode visit()).

public static class MyVisitor extends calcBaseVisitor<Integer> {
    public Integer visitMULT(calcParser.MULTContext ctx) {
        return ...
    }
    public Integer visitADD(calcParser.ADDContext ctx) {
        return ...
    }
    public Integer visitZAHL(calcParser.ZAHLContext ctx) {
        return ...
    }
}

Anschließend baut man das alles in eine manuelle Traversierung des Parse-Trees ein:

public class TestMyVisitor {
    public static class MyVisitor extends calcBaseVisitor<Integer> {
        ...
    }

    public static void main(String[] args) throws Exception {
        calcLexer lexer = new calcLexer(CharStreams.fromStream(System.in));
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        calcParser parser = new calcParser(tokens);

        ParseTree tree = parser.s();    // Start-Regel

        MyVisitor eval = new MyVisitor();
        eval.visit(tree);
    }
}

Eingebettete Aktionen und Attribute

s   : expr                      {System.err.println($expr.v);}
    ;

expr returns [int v]
    : e1=expr '*' e2=expr       {$v = $e1.v * $e2.v;}
    ;

Auch die Parser-Regeln können mit eingebetteten Aktionen ergänzt werden, die in die (für die jeweilige Regel) generierte Methode eingefügt werden und bei erfolgreicher Anwendung der Parser-Regel ausgeführt werden.

Über returns [int v] fügt man der Regel expr ein Attribut v (Integer) hinzu, welches man im jeweiligen Kontext abfragen bzw. setzen kann (agiert als Rückgabewert der generierten Methode). Auf diesen Wert kann in den Aktionen mit $v zugegriffen werden.

Anmerkung: Durch den Einsatz von eingebetteten Aktionen und Attributen wird die Grammatik abhängig von der Zielsprache des generierten Lexers/Parsers!

Ausblick

Damit haben wir die sprichwörtliche "Spitze des Eisbergs" gesehen. Mit ANTLR sind noch viele weitere Dinge möglich. Bitte nutzen Sie aktiv die Dokumentation auf github.com/antlr/antlr4.

Wrap-Up

Parser mit ANTLR generieren: Parser-Regeln werden mit Kleinbuchstaben geschrieben

• Regeln können Lexer- und Parser-Regeln "aufrufen"
• Regeln können Alternativen haben
• Bei Mehrdeutigkeit: Vorrang für erste Alternative
• ANTLR erlaubt direkte Links-Rekursion
• ANTLR erzeugt Parse-Tree
• Benannte Alternativen und Regel-Elemente
• Traversierung des Parse-Tree: Listener oder Visitoren, Zugriff auf Kontextobjekte

fun fib(x) {
    if (x == 0) {
        return 0;
    } else {
        if (x == 1) {
            return 1;
        } else {
            fib(x - 1) + fib(x - 2);
        }
    }
}

var wuppie = fib(4);