Reguläre Sprachen, Ausdrucksstärke

Motivation

Was muss ein Compiler wohl als erstes tun?

Hier entsteht ein Tafelbild.

Themen für heute

• Endliche Automaten
• Reguläre Sprachen
• Lexer

Endliche Automaten

Alphabete

Def.: Ein Alphabet $\Sigma$ ist eine endliche, nicht-leere Menge von Symbolen. Die Symbole eines Alphabets heißen Buchstaben.

Def.: Ein Wort $w$ über einem Alphabet $\Sigma$ ist eine endliche Folge von Symbolen aus $\Sigma$. $\epsilon$ ist das leere Wort. Die Länge $\vert w \vert$ eines Wortes $w$ ist die Anzahl von Buchstaben, die es enthält (Kardinalität).

Def.: Eine Sprache $L$ über einem Alphabet $\Sigma$ ist eine Menge von Wörtern über diesem Alphabet. Sprachen können endlich oder unendlich viele Wörter enthalten.

Beispiel

Hier entsteht ein Tafelbild.

Deterministische endliche Automaten

Hier entsteht ein Tafelbild.

Def.: Ein deterministischer endlicher Automat (DFA) ist ein 5-Tupel $A = (Q, \Sigma, \delta, q_0, F)$ mit

• $Q$ : endliche Menge von Zuständen

• $\Sigma$ : Alphabet von Eingabesymbolen

• $\delta$ : die (eventuell partielle) Übergangsfunktion $(Q \times \Sigma) \rightarrow Q$, $\delta$ kann partiell sein

• $q_0 \in Q$ : der Startzustand

• $F \subseteq Q$ : die Menge der Endzustände

Die Übergangsfunktion

Def.: Wir definieren $\delta^{\ast}: (Q \times \Sigma^{\ast}) \rightarrow Q$: induktiv wie folgt:

• Basis: $\delta^{\ast}(q, \epsilon) = q\ \forall q \in Q$

• Induktion: $\delta^{\ast}(q, a_1, \ldots, a_n) = \delta(\delta^{\ast}(q, a_1, \ldots , a_{n-1}), a_n)$

Def.: Ein DFA akzeptiert ein Wort $w \in \Sigma^{\ast}$ genau dann, wenn $\delta^{\ast}(q_0, w) \in F.$

Beispiel

Hier entsteht ein Tafelbild.

Nichtdeterministische endliche Automaten

Def.: Ein nichtdeterministischer endlicher Automat (NFA) ist ein 5-Tupel $A = (Q, \Sigma, \delta, q_0, F)$ mit

• $Q$ : endliche Menge von Zuständen

• $\Sigma$ : Alphabet von Eingabesymbolen

• $\delta$ : die (eventuell partielle) Übergangsfunktion $(Q \times \Sigma) \rightarrow Q$

• $q_0 \in Q$ : der Startzustand

• $F \subseteq Q$ : die Menge der Endzustände

Akzeptierte Sprachen

Def.: Sei A ein DFA oder ein NFA. Dann ist L(A) die von A akzeptierte Sprache, d. h.

Wozu NFAs im Compilerbau?

Pattern Matching (Erkennung von Schlüsselwörtern, Bezeichnern, ...) geht mit NFAs.

NFAs sind so nicht zu programmieren, aber:

Satz: Eine Sprache $L$ wird von einem NFA akzeptiert $\Leftrightarrow L$ wird von einem DFA akzeptiert.

D. h. es existieren Algorithmen zur

• Umwandlung von NFAs in DFAS
• Minimierung von DFAs

Reguläre Sprachen

Reguläre Ausdrücke definieren Sprachen

Def.: Induktive Definition von regulären Ausdrücken (regex) und der von ihnen repräsentierten Sprache L:

• Basis:

  • $\epsilon$ und $\emptyset$ sind reguläre Ausdrücke mit $L(\epsilon) = \lbrace \epsilon\rbrace$, $L(\emptyset)=\emptyset$
  • Sei $a$ ein Symbol $\Rightarrow$ $a$ ist ein regex mit $L(a) = \lbrace a\rbrace$

• Induktion: Seien $E,\ F$ reguläre Ausdrücke. Dann gilt:

  • $E+F$ ist ein regex und bezeichnet die Vereinigung $L(E + F) = L(E)\cup L(F)$
  • $EF$ ist ein regex und bezeichnet die Konkatenation $L(EF) = L(E)L(F)$
  • $E^{\ast}$ ist ein regex und bezeichnet die Kleene-Hülle $L(E^{\ast})=(L(E))^{\ast}$
  • $(E)$ ist ein regex mit $L((E)) = L(E)$

Vorrangregeln der Operatoren für reguläre Ausdrücke: *, Konkatenation, +

Beispiel

Hier entsteht ein Tafelbild.

Wichtige Identitäten

Satz: Sei $A$ ein DFA $\Rightarrow \exists$ regex $R$ mit $L(A) = L(R)$.

Satz: Sei $E$ ein regex $\Rightarrow \exists$ DFA $A$ mit $L(E) = L(A)$.

Formale Grammatiken

Hier entsteht ein Tafelbild.

Formale Definition formaler Grammatiken

Def.: Eine formale Grammatik ist ein 4-Tupel $G=(N,T,P,S)$ aus

• $N$: endliche Menge von Nichtterminalen

• $T$: endliche Menge von Terminalen, $N \cap T = \emptyset$

• $S \in N$: Startsymbol

• $P$: endliche Menge von Produktionen der Form

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

Ableitungen

Def.: Sei $G = (N, T, P, S)$ eine Grammatik, sei $\alpha A \beta$ eine Zeichenkette über $(N \cup T)^{\ast}$ und sei $A$ $\rightarrow \gamma$ eine Produktion von $G$.

Wir schreiben: $\alpha A \beta \Rightarrow \alpha \gamma \beta$ ($\alpha A \beta$ leitet $\alpha \gamma \beta$ ab).

Def.: Wir definieren die Relation $\overset{\ast}{\Rightarrow}$ induktiv wie folgt:

• Basis: $\forall \alpha \in (N \cup T)^{\ast} \alpha \overset{\ast}{\Rightarrow} \alpha$ (Jede Zeichenkette leitet sich selbst ab.)

• Induktion: Wenn $\alpha \overset{\ast}{\Rightarrow} \beta$ und $\beta\Rightarrow \gamma$ dann $\alpha \overset{\ast}{\Rightarrow} \gamma$

Def.: Sei $G = (N, T ,P, S)$ eine formale Grammatik. Dann ist $L(G) = \lbrace \text{Wörter}\ w\ \text{über}\ T \mid S \overset{\ast}{\Rightarrow} w\rbrace$ die von $G$ erzeugte Sprache.

Beispiel

Hier entsteht ein Tafelbild.

Reguläre Grammatiken

Def.: Eine reguläre (oder type-3-) Grammatik ist eine formale Grammatik mit den folgenden Einschränkungen:

• Alle Produktionen sind entweder von der Form

  • $X \to aY$ mit $X \in N, a \in T, Y \in N$ (rechtsreguläre Grammatik) oder
  • $X \to Ya$ mit $X \in N, a \in T, Y \in N$ (linksreguläre Grammatik)

• $X\rightarrow\epsilon$ ist erlaubt

Beispiel

Hier entsteht ein Tafelbild.

Reguläre Sprachen und ihre Grenzen

Satz: Die von endlichen Automaten akzeptiert Sprachklasse, die von regulären Ausdrücken beschriebene Sprachklasse und die von regulären Grammatiken erzeugte Sprachklasse sind identisch und heißen reguläre Sprachen.

Reguläre Sprachen

• einfache Struktur
• Matchen von Symbolen (z. B. Klammern) nicht möglich, da die fixe Anzahl von Zuständen eines DFAs die Erkennung solcher Sprachen verhindert.

Wozu reguläre Sprachen im Compilerbau?

• Reguläre Ausdrücke

  • definieren Schlüsselwörter und alle weiteren Symbole einer Programmiersprache, z. B. den Aufbau von Gleitkommazahlen
  • werden (oft von einem Generator) in DFAs umgewandelt
  • sind die Basis des Scanners oder Lexers

Lexer

Ein Lexer ist mehr als ein DFA

• Ein Lexer

  • wandelt mittels DFAs aus regulären Ausdrücken die Folge von Zeichen der Quelldatei in eine Folge von sog. Token um

  • bekommt als Input eine Liste von Paaren aus regulären Ausdrücken und Tokennamen, z. B. ("while", WHILE)

  • Kommentare und Strings müssen richtig erkannt werden. (Schachtelungen)

  • liefert Paare von Token und deren Werte, sofern benötigt, z. B. (WHILE, _), oder (IDENTIFIER, "radius") oder (INTEGERZAHL, "334")

Wie geht es weiter?

• Ein Parser

  • führt mit Hilfe des Tokenstreams vom Lexer die Syntaxanalyse durch

  • basiert auf einer sog. kontextfreien Grammatik, deren Terminale die Token sind

  • liefert die syntaktische Struktur in Form eines Ableitungsbaums (syntax tree, parse tree), bzw. einen AST (abstract syntax tree) ohne redundante Informationen im Ableitungsbaum (z. B. Semikolons)

  • liefert evtl. Fehlermeldungen

Wrap-Up

Wrap-Up

• Definition und Aufgaben von Lexern
• DFAs und NFAs
• Reguläre Ausdrücke
• Reguläre Grammatiken
• Zusammenhänge zwischen diesen Mechanismen und Lexern, bzw. Lexergeneratoren

Lexer mit ANTLR generieren

Lexer: Erzeugen eines Token-Stroms aus einem Zeichenstrom

Aus dem Eingabe(-quell-)text

/* demo */
a= [5  , 6]     ;

erstellt der Lexer (oder auch Scanner genannt) eine Sequenz von Token:

<ID, "a"> <ASSIGN> <LBRACK> <NUM, 5> <COMMA> <NUM, 6> <RBRACK> <SEMICOL>

• Input: Zeichenstrom (Eingabedatei o.ä.)
• Verarbeitung: Finden sinnvoller Sequenzen im Zeichenstrom ("Lexeme"), Einteilung in Kategorien und Erzeugen von Token (Paare: Typ/Name, Wert)
• Ausgabe: Tokenstrom

Normalerweise werden für spätere Phasen unwichtige Elemente wie White-Space oder Kommentare entfernt.

Durch diese Vorverarbeitung wird eine höhere Abstraktionsstufe erreicht und es können erste grobe Fehler gefunden werden. Dadurch kann der Parser auf einer abstrakteren Stufe arbeiten und muss nicht mehr den gesamten ursprünglichen Zeichenstrom verarbeiten.

Anmerkung: In dieser Phase steht die Geschwindigkeit stark im Vordergrund: Der Lexer "sieht" alle Zeichen im Input. Deshalb findet man häufig von Hand kodierte Lexer, obwohl die Erstellung der Lexer auch durch Generatoren erledigt werden könnte ...

Anmerkung: Die Token sind die Terminalsymbole in den Parserregeln (Grammatik).

Definition wichtiger Begriffe

• Token: Tupel (Tokenname, optional: Wert)

  Der Tokenname ist ein abstraktes Symbol, welches eine lexikalische Einheit repräsentiert (Kategorie). Die Tokennamen sind die Eingabesymbole für den Parser.

  Token werden i.d.R. einfach über ihren Namen referenziert. Token werden häufig zur Unterscheidung von anderen Symbolen in der Grammatik in Fettschrift oder mit großen Anfangsbuchstaben geschrieben.

  Ein Token kann einen Wert haben, etwa eine Zahl oder einen Bezeichner, der auf das zum Token gehörende Pattern gematcht hatte (also das Lexem). Wenn der Wert des Tokens eindeutig über den Namen bestimmt ist (im Beispiel oben beim Komma oder den Klammern), dann wird häufig auf den Wert verzichtet.

• Lexeme: Sequenz von Zeichen im Eingabestrom, die auf ein Tokenpattern matcht und vom Lexer als Instanz dieses Tokens identifiziert wird.

• Pattern: Beschreibung der Form eines Lexems

  Bei Schlüsselwörtern oder Klammern etc. sind dies die Schlüsselwörter oder Klammern selbst. Bei Zahlen oder Bezeichnern (Namen) werden i.d.R. reguläre Ausdrücke zur Beschreibung der Form des Lexems formuliert.

Typische Muster für Erstellung von Token

1. Schlüsselwörter

   • Ein eigenes Token (RE/DFA) für jedes Schlüsselwort, oder
   • Erkennung als Name und Vergleich mit Wörterbuch und nachträgliche Korrektur des Tokentyps

   Wenn Schlüsselwörter über je ein eigenes Token abgebildet werden, benötigt man für jedes Schlüsselwort einen eigenen RE bzw. DFA. Die Erkennung als Bezeichner und das Nachschlagen in einem Wörterbuch (geeignete Hashtabelle) sowie die entsprechende nachträgliche Korrektur des Tokentyps kann die Anzahl der Zustände im Lexer signifikant reduzieren!

2. Operatoren

   • Ein eigenes Token für jeden Operator, oder
   • Gemeinsames Token für jede Operatoren-Klasse

3. Bezeichner: Ein gemeinsames Token für alle Namen

4. Zahlen: Ein gemeinsames Token für alle numerischen Konstante (ggf. Integer und Float unterscheiden)

   Für Zahlen führt man oft ein Token "NUM" ein. Als Attribut speichert man das Lexem i.d.R. als String. Alternativ kann man (zusätzlich) das Lexem in eine Zahl konvertieren und als (zusätzliches) Attribut speichern. Dies kann in späteren Stufen viel Arbeit sparen.

5. String-Literale: Ein gemeinsames Token

6. Komma, Semikolon, Klammern, ...: Je ein eigenes Token

7. Regeln für White-Space und Kommentare etc. ...

   Normalerweise benötigt man Kommentare und White-Spaces in den folgenden Stufen nicht und entfernt diese deshalb aus dem Eingabestrom. Dabei könnte man etwa White-Spaces in den Pattern der restlichen Token berücksichtigen, was die Pattern aber sehr komplex macht. Die Alternative sind zusätzliche Pattern, die auf die White-Space und anderen nicht benötigten Inhalt matchen und diesen "geräuschlos" entfernen. Mit diesen Pattern werden keine Token erzeugt, d.h. der Parser und die anderen Stufen bemerken nichts von diesem Inhalt.

   Gelegentlich benötigt man aber auch Informationen über White-Spaces, beispielsweise in Python. Dann müssen diese Token wie normale Token an den Parser weitergereicht werden.

Jedes Token hat i.d.R. ein Attribut, in dem das Lexem gespeichert wird. Bei eindeutigen Token (etwa bei eigenen Token je Schlüsselwort oder bei den Interpunktions-Token) kann man sich das Attribut auch sparen, da das Lexem durch den Tokennamen eindeutig rekonstruierbar ist.

Anmerkung: Wenn es mehrere matchende REs gibt, wird in der Regel das längste Lexem bevorzugt. Wenn es mehrere gleich lange Alternativen gibt, muss man mit Vorrangregeln bzgl. der Token arbeiten.

Hello World

grammar Hello;

start       : 'hello' GREETING ;

GREETING    : [a-zA-Z]+ ;
WHITESPACE  : [ \t\n]+ -> skip ;

Hinweis zur Grammatik (Regeln)

• start ist eine Parser-Regel => Eine Parser-Regel pro Grammatik wird benötigt, damit man den generierten Parser am Ende auch starten kann ...
• Die anderen beiden Regeln (mit großem Anfangsbuchstaben) aus der obigen Grammatik zählen zum Lexer

ANTLR einrichten

• Aktuelle Version herunterladen: antlr.org, für Java als Zielsprache: "Complete ANTLR 4.x Java binaries jar"
• CLASSPATH setzen: export CLASSPATH=".:/<pathToJar>/antlr-4.11.1-complete.jar:$CLASSPATH"
• Aliase einrichten (.bashrc):
  • alias antlr='java org.antlr.v4.Tool'
  • alias grun='java org.antlr.v4.gui.TestRig'
• Alternativ über den Python-Installer: pip install antlr4-tools
• Im Web ohne lokale Installation: ANTLR Lab

(vgl. github.com/antlr/antlr4/blob/master/doc/getting-started.md)

"Hello World" übersetzen und ausführen

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

   • grun Hello start -tokens (Grammatik "Hello", Startregel "start")

   • Alternativ mit kleinem Java-Programm:

     import org.antlr.v4.runtime.*;
     
     public class Main {
         public static void main(String[] args) throws Exception {
             Lexer l = new HelloLexer(CharStreams.fromStream(System.in));
             Token t = l.nextToken();
             while (t.getType() != Token.EOF) {
                 System.out.println(t);
                 t = l.nextToken();
             }
         }
     }

Generierte Dateien und Klassen

Nach dem Übersetzen finden sich folgende Dateien und Klassen vor:

.
├── bin
│   ├── HelloBaseListener.class
│   ├── HelloBaseVisitor.class
│   ├── HelloLexer.class
│   ├── HelloListener.class
│   ├── HelloParser.class
│   ├── HelloParser$RContext.class
│   ├── HelloVisitor.class
│   └── Main.class
├── Hello.g4
└── src
    ├── HelloBaseListener.java
    ├── HelloBaseVisitor.java
    ├── HelloLexer.java
    ├── HelloLexer.tokens
    ├── HelloListener.java
    ├── HelloParser.java
    ├── Hello.tokens
    ├── HelloVisitor.java
    └── Main.java

Anmerkung: Die Ordnerstruktur wurde durch ein ANTLR-Plugin für Eclipse erzeugt. Bei Ausführung in der Konsole liegen alle Dateien in einem Ordner.

Anmerkung: Per Default werden nur die Listener angelegt, für die Visitoren muss eine extra Option mitgegeben werden.

Die Dateien Hello.tokens und HelloLexer.tokens enthalten die Token samt einer internen Nummer. (Der Inhalt beider Dateien ist identisch.)

Die Datei HelloLexer.java enthält den generierten Lexer, der eine Spezialisierung der abstrakten Basisklasse Lexer darstellt. Über den Konstruktor wird der zu scannende CharStream gesetzt. Über die Methode Lexer#nextToken() kann man sich die erkannten Token der Reihe nach zurückgeben lassen. (Diese Methode wird letztlich vom Parser benutzt.)

Die restlichen Dateien werden für den Parser und verschiedene Arten der Traversierung des AST generiert (vgl. AST-basierte Interpreter).

Bedeutung der Ausgabe

Wenn man dem Hello-Lexer die Eingabe

hello world
<EOF>

(das <EOF> wird durch die Tastenkombination STRG-D erreicht) gibt, dann lautet die Ausgabe

$ grun Hello start -tokens
hello world
<EOF>
[@0,0:4='hello',<'hello'>,1:0]
[@1,6:10='world',<GREETING>,1:6]
[@2,12:11='<EOF>',<EOF>,2:0]

Die erkannten Token werden jeweils auf einer eigenen Zeile ausgegeben.

• @0: Das erste Token (fortlaufend nummeriert, beginnend mit 0)
• 0:4: Das Token umfasst die Zeichen 0 bis 4 im Eingabestrom
• ='hello': Das gefundene Lexem (Wert des Tokens)
• <'hello'>: Das Token (Name/Typ des Tokens)
• 1:0: Das Token wurde in Zeile 1 gefunden (Start der Nummerierung mit Zeile 1), und startet in dieser Zeile an Position 0

Entsprechend bekommt man mit

$ grun Hello start -tokens
hello
  world

<EOF>
[@0,0:4='hello',<'hello'>,1:0]
[@1,8:12='world',<GREETING>,2:2]
[@2,15:14='<EOF>',<EOF>,4:0]

ANTLR-Grammatik für die Lexer-Generierung

• Start der Grammatik mit dem Namen "XYZ" mit

  grammar XYZ;
  

  oder (nur Lexer)

  lexer grammar XYZ;
  

• Token und Lexer-Regeln starten mit großen Anfangsbuchstaben (Ausblick: Parser-Regeln starten mit kleinen Anfangsbuchstaben)

  Format: TokenName : Alternative1 | ... | AlternativeN ;

  Rekursive Lexer-Regeln sind erlaubt. Achtung: Es dürfen keine links-rekursiven Regeln genutzt werden, etwa wie ID : ID '*' ID ; ... (Eine genauere Definition und die Transformation in nicht-linksrekursive Regeln siehe CFG).

• Alle Literale werden in einfache Anführungszeichen eingeschlossen (es erfolgt keine Unterscheidung zwischen einzelnen Zeichen und Strings wie in anderen Sprachen)

• Zeichenmengen: [a-z\n] umfasst alle Zeichen von 'a' bis 'z' sowie '\n'

  'a'..'z' ist identisch zu [a-z]

• Schlüsselwörter: Die folgenden Strings stellen reservierte Schlüsselwörter dar und dürfen nicht als Token, Regel oder Label genutzt werden:

  import, fragment, lexer, parser, grammar, returns, locals, throws, catch, finally, mode, options, tokens
  

  Anmerkung: rule ist zwar kein Schlüsselwort, wird aber als Methodenname bei der Codegenerierung verwendet. => Wie ein Schlüsselwort behandeln!

(vgl. github.com/antlr/antlr4/blob/master/doc/lexicon.md)

Greedy und Non-greedy Lexer-Regeln

Die regulären Ausdrücke (...)?, (...)* und (...)+ sind greedy und versuchen soviel Input wie möglich zu matchen.

Falls dies nicht sinnvoll sein sollte, kann man mit einem weiteren ? das Verhalten auf non-greedy umschalten. Allerdings können non-greedy Regeln das Verhalten des Lexers u.U. schwer vorhersehbar machen!

Die Empfehlung ist, non-greedy Lexer-Regeln nur sparsam einzusetzen (vgl. github.com/antlr/antlr4/blob/master/doc/wildcard.md).

Verhalten des Lexers: 1. Längster Match

Primäres Ziel: Erkennen der längsten Zeichenkette

CHARS   : [a-z]+ ;
DIGITS  : [0-9]+ ;
FOO     : [a-z]+ [0-9]+ ;

Die Regel, die den längsten Match für die aktuelle Eingabesequenz produziert, "gewinnt".

Im Beispiel würde ein "foo42" als FOO erkannt und nicht als CHARS DIGITS.

Verhalten des Lexers: 2. Reihenfolge

Reihenfolge in Grammatik definiert Priorität

FOO     : 'f' .*? 'r' ;
BAR     : 'foo' .*? 'bar' ;

Falls mehr als eine Lexer-Regel die selbe Inputsequenz matcht, dann hat die in der Grammatik zuerst genannte Regel Priorität.

Im Beispiel würden für die Eingabe "foo42bar" beide Regeln den selben längsten Match liefern - die Regel FOO ist in der Grammatik früher definiert und "gewinnt".

Verhalten des Lexers: 3. Non-greedy Regeln

Non-greedy Regeln versuchen so wenig Zeichen wie möglich zu matchen

FOO     : 'foo' .*? 'bar' ;
BAR     : 'bar' ;

Hier würde ein "foo42barbar" zu FOO gefolgt von BAR erkannt werden.

Achtung: Nach dem Abarbeiten einer non-greedy Sub-Regel in einer Lexer-Regel gilt "first match wins"

.*? ('4' | '42')

=> Der Teil '42' auf der rechten Seite ist "toter Code" (wegen der non-greedy Sub-Regel .*?)!

Die Eingabe "x4" würde korrekt erkannt, währende "x42" nur als "x4" erkannt wird und für die verbleibende "2" würde ein token recognition error geworfen.

(vgl. github.com/antlr/antlr4/blob/master/doc/wildcard.md)

Attribute und Aktionen

grammar Demo;

@header {
import java.util.*;
}

@members {
String s = "";
}

start   : TYPE ID '=' INT ';' ;

TYPE    : ('int' | 'float') {s = getText();} ;
INT     : [0-9]+            {System.out.println(s+":"+Integer.valueOf(getText()));};
ID      : [a-z]+            {setText(String.valueOf(getText().charAt(0)));} ;
WS      : [ \t\n]+ -> skip ;

Attribute bei Token (Auswahl)

Token haben Attribute, die man abfragen kann. Dies umfasst u.a. folgende Felder:

• text: Das gefundene Lexem als String
• type: Der Token-Typ als Integer
• index: Das wievielte Token (als Integer)

(vgl. github.com/antlr/antlr4/blob/master/doc/actions.md)

Zur Auswertung in den Lexer-Regeln muss man anders vorgehen als in Parser-Regeln: Nach der Erstellung eines Tokens kann man die zum Attribut gehörenden getX() und setX()-Methoden aufrufen, um die Werte abzufragen oder zu ändern.

Dies passiert im obigen Beispiel für das Attribut text: Abfrage mit getText(), Ändern/Setzen mit setText().

Die Methodenaufrufe wirken sich immer auf das gerade erstellte Token aus.

Achtung: Bei Aktionen in Parser-Regeln gelten andere Spielregeln!

Aktionen mit den Lexer-Regeln

Aktionen für Lexer-Regeln sind Code-Blöcke in der Zielsprache, eingeschlossen in geschweifte Klammern. Die Code-Blöcke werden direkt in die generierten Lexer-Methoden kopiert.

Zusätzlich:

• @header: Package-Deklarationen und/oder Importe (wird vor der Klassendefinition eingefügt)
• @members: zusätzliche Attribute für die generierten Lexer- (und Parser-) Klassen.

Mit @lexer::header bzw. @lexer::members werden diese Codeblöcke nur in den generierten Lexer eingefügt.

Anmerkung: Lexer-Aktionen müssen am Ende der äußersten Alternative erscheinen. Wenn eine Lexer-Regel mehr als eine Alternative hat, müssen diese in runde Klammern eingeschlossen werden.

(vgl. github.com/antlr/antlr4/blob/master/doc/grammars.md)

Wrap-Up

Lexer mit ANTLR generieren: Lexer-Regeln werden mit Großbuchstaben geschrieben

• Längster Match gewinnt, Gleichstand: zuerst definierte Regel
• non greedy-Regeln: versuche so wenig Zeichen zu matchen wie möglich
• Aktionen beim Matchen

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);

Heinz 030 5346 983
Kalle +49 30 1234 567
Lina +49.571.8385-255
Rosi (0571) 8385-268