Compiler 1: Grundlagen
Lexer/Parser-Generierung mit ANTLR
WS 2014/15
Andreas Koch
FG Eingebettete Systeme und ihre Anwendungen
Informatik, TU Darmstadt
ANTLR - Einführung 1
ANTLR 4.x
I
Adaptive LL(*) Compiler Generator
I
Eingabe: Grammatik in EBNF (und mehr!)
I
Ausgabe: Erkenner für Sprache mittels rekursivem Abstieg
I
Erzeugt (akt. Version 4.5) Erkenner in ...
I
Java, C#, C++, JavaScript, Python
I
weitere Sprachen geplant.
Arten von Eingabedaten
I
Zeichenströme (bearbeitet mit Lexer)
I
Token-Ströme (bearbeitet mit Parser)
Alternative Compiler-Generatoren
I
Lexer/Scanner: lex, flex, JFlex
I
Parser: yacc/bison, JCup, JavaCC, SableCC, SLADE
| WS 2014/15 | A. Koch | FG ESA | 4 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
ANTLR - Einführung 1
ANTLR 4.x
I
Adaptive LL(*) Compiler Generator
I
Eingabe: Grammatik in EBNF (und mehr!)
I
Ausgabe: Erkenner für Sprache mittels rekursivem Abstieg
I
Erzeugt (akt. Version 4.5) Erkenner in ...
I
Java, C#, C++, JavaScript, Python
I
weitere Sprachen geplant.
Arten von Eingabedaten
I
Zeichenströme (bearbeitet mit Lexer)
I
Token-Ströme (bearbeitet mit Parser)
Alternative Compiler-Generatoren
I
Lexer/Scanner: lex, flex, JFlex
I
Parser: yacc/bison, JCup, JavaCC, SableCC, SLADE
| WS 2014/15 | A. Koch | FG ESA | 4 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
ANTLR - Einführung 1
ANTLR 4.x
I
Adaptive LL(*) Compiler Generator
I
Eingabe: Grammatik in EBNF (und mehr!)
I
Ausgabe: Erkenner für Sprache mittels rekursivem Abstieg
I
Erzeugt (akt. Version 4.5) Erkenner in ...
I
Java, C#, C++, JavaScript, Python
I
weitere Sprachen geplant.
Arten von Eingabedaten
I
Zeichenströme (bearbeitet mit Lexer)
I
Token-Ströme (bearbeitet mit Parser)
Alternative Compiler-Generatoren
I
Lexer/Scanner: lex, flex, JFlex
I
Parser: yacc/bison, JCup, JavaCC, SableCC, SLADE
| WS 2014/15 | A. Koch | FG ESA | 4 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Neuerungen in ANTLR 4.x
I
ANTLR verarbeitet jede gültige Grammatik
I
Versucht Konflikte und Mehrdeutigkeiten automatisch aufzulösen
I
Anhand von Heuristiken für die praktisch relevantesten Stellen
I
Einschränkung: Indirekt links-rekursive Regeln werden nicht unterstützt
I
Adaptiver Parser mit variablem Lookahead: ALL(?)
I
Die Grammatik wird zur Laufzeit des generierten Parsers analysiert
I
Parser kann Entscheidungen auf konkreten Eingabedaten treffen
I
Automatischer Aufbau von Parse Trees
I
Automatische Generierung von Visitors und Listeners
I
Bevorzuge saubere Trennung zwischen Grammatik und
Implementierungssprache
I
Wesentliche Änderung des APIs im Vergleich zu ANTLR v3
| WS 2014/15 | A. Koch | FG ESA | 5 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Neuerungen in ANTLR 4.x
I
ANTLR verarbeitet jede gültige Grammatik
I
Versucht Konflikte und Mehrdeutigkeiten automatisch aufzulösen
I
Anhand von Heuristiken für die praktisch relevantesten Stellen
I
Einschränkung: Indirekt links-rekursive Regeln werden nicht unterstützt
I
Adaptiver Parser mit variablem Lookahead: ALL(?)
I
Die Grammatik wird zur Laufzeit des generierten Parsers analysiert
I
Parser kann Entscheidungen auf konkreten Eingabedaten treffen
I
Automatischer Aufbau von Parse Trees
I
Automatische Generierung von Visitors und Listeners
I
Bevorzuge saubere Trennung zwischen Grammatik und
Implementierungssprache
I
Wesentliche Änderung des APIs im Vergleich zu ANTLR v3
| WS 2014/15 | A. Koch | FG ESA | 5 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Neuerungen in ANTLR 4.x
I
ANTLR verarbeitet jede gültige Grammatik
I
Versucht Konflikte und Mehrdeutigkeiten automatisch aufzulösen
I
Anhand von Heuristiken für die praktisch relevantesten Stellen
I
Einschränkung: Indirekt links-rekursive Regeln werden nicht unterstützt
I
Adaptiver Parser mit variablem Lookahead: ALL(?)
I
Die Grammatik wird zur Laufzeit des generierten Parsers analysiert
I
Parser kann Entscheidungen auf konkreten Eingabedaten treffen
I
Automatischer Aufbau von Parse Trees
I
Automatische Generierung von Visitors und Listeners
I
Bevorzuge saubere Trennung zwischen Grammatik und
Implementierungssprache
I
Wesentliche Änderung des APIs im Vergleich zu ANTLR v3
| WS 2014/15 | A. Koch | FG ESA | 5 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Neuerungen in ANTLR 4.x
I
ANTLR verarbeitet jede gültige Grammatik
I
Versucht Konflikte und Mehrdeutigkeiten automatisch aufzulösen
I
Anhand von Heuristiken für die praktisch relevantesten Stellen
I
Einschränkung: Indirekt links-rekursive Regeln werden nicht unterstützt
I
Adaptiver Parser mit variablem Lookahead: ALL(?)
I
Die Grammatik wird zur Laufzeit des generierten Parsers analysiert
I
Parser kann Entscheidungen auf konkreten Eingabedaten treffen
I
Automatischer Aufbau von Parse Trees
I
Automatische Generierung von Visitors und Listeners
I
Bevorzuge saubere Trennung zwischen Grammatik und
Implementierungssprache
I
Wesentliche Änderung des APIs im Vergleich zu ANTLR v3
| WS 2014/15 | A. Koch | FG ESA | 5 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Weiterführendes Material
Internet
I
http://www.antlr.org
I
Dort: Wiki, Thema “FAQ und Getting Started”
I
Sehr umfangreiche Materialsammlung
I
Leider unstrukturiert
I
Vortrag von Terence Parr: http://www.youtube.com/watch?v=q8p1voEiu8Q
| WS 2014/15 | A. Koch | FG ESA | 6 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Hello World
grammar Hello;
r : ’hello’ ID ;
ID : [a-z]+ ;
WS : [ \r\t\n]+ -> skip ;
Definiere Grammatik "Hello" (der Dateiname muss Hello.g4 sein)
Erkenne Schlüsselwort hello gefolgt von einem Bezeichner
Erkenne Bezeichner in Kleinbuchstaben
Erkenne Leerzeichen und ignoriere sie
| WS 2014/15 | A. Koch | FG ESA | 7 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Setup
I
ANTLR herunterladen
$ cd ~/xyz
$ wget http://antlr4.org/download/antlr-4.5-complete.jar
I
Umgebungsvariable CLASSPATH (für die Java-Werkzeuge) setzen
$ export CLASSPATH=".:~/xyz/antlr-4.5-complete.jar:$CLASSPATH"
I
Aliase für ANTLR und das TestRig erstellen (unixoide Systeme)
$ alias antlr4=’java -jar ~/xyz/antlr-4.5-complete.jar’
$ alias grun=’java org.antlr.v4.runtime.misc.TestRig’
| WS 2014/15 | A. Koch | FG ESA | 8 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
TestRig
Generischer Testtreiber für die Grammatik
I
ANTLR aufrufen und generierte Dateien übersetzen
$ antlr4 Hello.g4
$ javac
*
.java
I
Eingabe in Token zerlegen
$ echo "hello students" | grun Hello r -tokens
[@0,0:4=’hello’,<1>,1:0]
[@1,6:13=’students’,<2>,1:6]
[@2,15:14=’<EOF>’,<-1>,2:0]
I
Eingabe parsen
$ echo "hello students" | grun Hello r -gui
r
hello students
| WS 2014/15 | A. Koch | FG ESA | 9 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Struktur einer Grammatik-Datei
/
*
comments
*
/ // more comments
[lexer|parser] grammar <Name>;
options { ... }
import ...
tokens { ... }
@header { ... }
@members { ... }
rule1: alternative1
| alternative2
;
RULE2: ...
Kommentare (Java-Style)
Spezifikation Grammatikart und -name
Optionen, z.B. Zielsprache
Import anderer Grammatiken
(optionale) Tokenspezifikation
Aktionen: Fügen Code in den Parser ein
Parser-Regeln
Lexer-Regeln (Tokens)
| WS 2014/15 | A. Koch | FG ESA | 10 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Aufbau einer Regel
rulename : alternative1 # label
|
anotherParserRule LEXERRULE ’literal’ # concat
| A ’x’ (B | C) # subrule
| D
*
E+ F? (G H | I)+ # repeat
;
I
Eine Regeln besteht aus einem Namen
I
gefolgt von einer Menge an Alternativen.
I
Parserregeln beginnen immer mit einem Kleinbuchstaben
I
Lexerrregeln (Tokens) beginnen immer mit einem Großbuchstaben
I
Eine Alternative referenziert
I
andere Parserregeln
I
Lexerregeln
I
Literale in einfachen Anführungszeichen
I
Alternativen können mit einem Label versehen werden.
I
Außerdem: Parameter, Rückgabewerte, eingebettete Aktionen, Optionen, ...
| WS 2014/15 | A. Koch | FG ESA | 11 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Aufbau einer Regel
rulename : alternative1 # label
|
anotherParserRule LEXERRULE ’literal’ # concat
| A ’x’ (B | C) # subrule
| D
*
E+ F? (G H | I)+ # repeat
;
I
Eine Regeln besteht aus einem Namen
I
gefolgt von einer Menge an Alternativen.
I
Parserregeln beginnen immer mit einem Kleinbuchstaben
I
Lexerrregeln (Tokens) beginnen immer mit einem Großbuchstaben
I
Eine Alternative referenziert
I
andere Parserregeln
I
Lexerregeln
I
Literale in einfachen Anführungszeichen
I
Alternativen können mit einem Label versehen werden.
I
Außerdem: Parameter, Rückgabewerte, eingebettete Aktionen, Optionen, ...
| WS 2014/15 | A. Koch | FG ESA | 11 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Aufbau einer Regel
rulename : alternative1 # label
|
anotherParserRule LEXERRULE ’literal’ # concat
| A ’x’ (B | C) # subrule
| D
*
E+ F? (G H | I)+ # repeat
;
I
Eine Regeln besteht aus einem Namen
I
gefolgt von einer Menge an Alternativen.
I
Parserregeln beginnen immer mit einem Kleinbuchstaben
I
Lexerrregeln (Tokens) beginnen immer mit einem Großbuchstaben
I
Eine Alternative referenziert
I
andere Parserregeln
I
Lexerregeln
I
Literale in einfachen Anführungszeichen
I
Alternativen können mit einem Label versehen werden.
I
Außerdem: Parameter, Rückgabewerte, eingebettete Aktionen, Optionen, ...
| WS 2014/15 | A. Koch | FG ESA | 11 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Aufbau einer Regel
rulename : alternative1 # label
|
anotherParserRule LEXERRULE ’literal’ # concat
| A ’x’ (B | C) # subrule
| D
*
E+ F? (G H | I)+ # repeat
;
I
Eine Regeln besteht aus einem Namen
I
gefolgt von einer Menge an Alternativen.
I
Parserregeln beginnen immer mit einem Kleinbuchstaben
I
Lexerrregeln (Tokens) beginnen immer mit einem Großbuchstaben
I
Eine Alternative referenziert
I
andere Parserregeln
I
Lexerregeln
I
Literale in einfachen Anführungszeichen
I
Alternativen können mit einem Label versehen werden.
I
Außerdem: Parameter, Rückgabewerte, eingebettete Aktionen, Optionen, ...
| WS 2014/15 | A. Koch | FG ESA | 11 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Aufbau einer Regel
rulename : alternative1 # label
|
anotherParserRule LEXERRULE ’literal’ # concat
| A ’x’ (B | C) # subrule
| D
*
E+ F? (G H | I)+ # repeat
;
I
Eine Regeln besteht aus einem Namen
I
gefolgt von einer Menge an Alternativen.
I
Parserregeln beginnen immer mit einem Kleinbuchstaben
I
Lexerrregeln (Tokens) beginnen immer mit einem Großbuchstaben
I
Eine Alternative referenziert
I
andere Parserregeln
I
Lexerregeln
I
Literale in einfachen Anführungszeichen
I
Alternativen können mit einem Label versehen werden.
I
Außerdem: Parameter, Rückgabewerte, eingebettete Aktionen, Optionen, ...
| WS 2014/15 | A. Koch | FG ESA | 11 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Aufbau einer Regel
rulename : alternative1 # label
| anotherParserRule LEXERRULE ’literal’ # concat
| A ’x’ (B | C) # subrule
| D
*
E+ F? (G H | I)+ # repeat
;
I
Hintereinanderschreiben von Grammatiksymbolen entspricht der
Konkatenation.
I
Unterregeln (subrules) werden durch Klammern eingeleitet
I
Sie können weitere Alternativen getrennt durch | beeinhalten.
I
Weitere Operatoren sind * (0-n Wdh.), + (1-n Wdh.), ? (0-1 Wdh.).
I
Die Operatoren lassen sich auch auf Unterregeln anwenden.
| WS 2014/15 | A. Koch | FG ESA | 12 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Aufbau einer Regel
rulename : alternative1 # label
| anotherParserRule LEXERRULE ’literal’ # concat
| A ’x’ (B | C) # subrule
| D
*
E+ F? (G H | I)+ # repeat
;
I
Hintereinanderschreiben von Grammatiksymbolen entspricht der
Konkatenation.
I
Unterregeln (subrules) werden durch Klammern eingeleitet
I
Sie können weitere Alternativen getrennt durch | beeinhalten.
I
Weitere Operatoren sind * (0-n Wdh.), + (1-n Wdh.), ? (0-1 Wdh.).
I
Die Operatoren lassen sich auch auf Unterregeln anwenden.
| WS 2014/15 | A. Koch | FG ESA | 12 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Aufbau einer Regel
rulename : alternative1 # label
| anotherParserRule LEXERRULE ’literal’ # concat
| A ’x’ (B | C) # subrule
| D
*
E+ F? (G H | I)+ # repeat
;
I
Hintereinanderschreiben von Grammatiksymbolen entspricht der
Konkatenation.
I
Unterregeln (subrules) werden durch Klammern eingeleitet
I
Sie können weitere Alternativen getrennt durch | beeinhalten.
I
Weitere Operatoren sind * (0-n Wdh.), + (1-n Wdh.), ? (0-1 Wdh.).
I
Die Operatoren lassen sich auch auf Unterregeln anwenden.
| WS 2014/15 | A. Koch | FG ESA | 12 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Aufbau einer Regel
rulename : alternative1 # label
| anotherParserRule LEXERRULE ’literal’ # concat
| A ’x’ (B | C) # subrule
| D
*
E+ F? (G H | I)+ # repeat
;
I
Hintereinanderschreiben von Grammatiksymbolen entspricht der
Konkatenation.
I
Unterregeln (subrules) werden durch Klammern eingeleitet
I
Sie können weitere Alternativen getrennt durch | beeinhalten.
I
Weitere Operatoren sind * (0-n Wdh.), + (1-n Wdh.), ? (0-1 Wdh.).
I
Die Operatoren lassen sich auch auf Unterregeln anwenden.
| WS 2014/15 | A. Koch | FG ESA | 12 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Kurzschreibweisen
CharClass1 : [a-z] ;
CharClass2 : ’a’..’z’ ;
Negation : ~[abc] ;
NonGreedy : ’//’ .
*
? ’\n’ ;
Zeichenklasse: Alle Zeichen zwischen a und z.
Alternative Schreibweise für obige Zeichenklasse
Negation: Alle Zeichen außer a, b oder c
Der *?-Operator ist die “nicht-gierige” (non-greedy)
Variante des Kleene-Sterns.
Damit werden alle Zeichen (.) bis zum ersten
Auftreten des folgenden Zeichens (’\n’) erkannt.
| WS 2014/15 | A. Koch | FG ESA | 13 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
ArrayInit
I
Grammatik, die (geschachtelte) Array-Initialisierer erkennt
I
z.B. {1,2,3} oder {17, {42, 55, 31}, 28, 0}
grammar ArrayInit;
init :
’{’ value (’,’ value)
*
’}’ ;
value : init
| INT
;
INT : [0-9]+ ;
WS : [ \t\r\n]+ -> skip ;
Erkenne komma-separierte Werte
zwischen geschweiften Klammern
(mindestens einen)
Ein ’value’ ist entweder wieder eine Liste, ...
oder eine Zahl.
| WS 2014/15 | A. Koch | FG ESA | 14 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Erzeugte Dateien
antlr4 ArrayInit.g4 erzeugt:
I
ArrayInitParser.java
I
public class ArrayInitParser extends Parser { ... }
I
ArrayInitLexer.java
I
public class ArrayInitLexer extends Lexer { ... }
I
Erzeugt Tokenstrom für den Parser.
I
ArrayInit.tokens
ArrayInitLexer.tokens
I
*
.tokens-Dateien nur für Datenaustausch zwischen Grammatiken
I
(hier nicht notwendig)
I
ArrayInitListener.java
ArrayInitBaseListener.java
I
Listener-Interface (Alternative zum Visitor-Pattern, später mehr dazu)
| WS 2014/15 | A. Koch | FG ESA | 15 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Parser
Parser erzeugt einen abstrakten Parse-Baum, bestehend aus
I
ParserRuleContext-Objekten
I
“Kontext”: hier Speicherung aller Information über erkannte Phrase
I
Eigene Subklasse für jede Regel (bzw. für Alternative mit Label)
I
Attribute für Nichtterminals und benannte Literaltokens
I
Nicht-benannte Literale werden verworfen
I
Entspricht den phrasenspezifischen AST-Knoten in Triangle
I
Enthält u.a. Zugriffsmethoden auf
I
Start- und Endtokens
I
Kinder und Elter im AST
I
TerminalNode-Objekten (repräsentieren die Terminals)
| WS 2014/15 | A. Koch | FG ESA | 16 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Parser
AST für {1,{2,3},4}
grammar ArrayInit;
init :
’{’ value (’,’ value)
*
’}’ ;
value : init
| INT
;
INT : [0-9]+ ;
WS : [ \t\r\n]+ -> skip ;
InitContext
’{’
ValueContext
’1’
’,’
InitContext
’{’
ValueContext
’2’
’,’
ValueContext
’3’
’}’
’,’
ValueContext
’4’
’}’
| WS 2014/15 | A. Koch | FG ESA | 17 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Parser
Generierter Code
public class ArrayInitParser extends Parser {
...
public static class InitContext extends ParserRuleContext {
...
public List<ValueContext> value() { ... }
...
}
public final InitContext init() throws RecognitionException { ... }
public static class ValueContext extends ParserRuleContext {
...
public TerminalNode INT() { ... }
public InitContext init() { ... }
...
}
public final ValueContext value() throws RecognitionException { ... }
...
}
Zugriff auf Kinder im AST
| WS 2014/15 | A. Koch | FG ESA | 18 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Parser
Integration
import org.antlr.v4.runtime.
*
;
import org.antlr.v4.runtime.tree.
*
;
public class Test {
public static void main(String[] args) throws Exception {
ANTLRInputStream input = new ANTLRInputStream(System.in);
ArrayInitLexer lexer = new ArrayInitLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
ArrayInitParser parser = new ArrayInitParser(tokens);
ParseTree tree = parser.init();
System.out.println(tree.toStringTree(parser));
}
}
init ist der Name der Regel
→ Lexer und Parser mit Tokenstream verbinden
Methode für Startsymbol aufrufen
| WS 2014/15 | A. Koch | FG ESA | 19 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Verwendung des Parsers
I
Bislang wird nur erkannt, ob die Eingabe zur Grammatik passt.
I
In ANTLR ≤ 3: Semantische Aktionen (= Java-Code) in Grammatik einbetten.
I
Aktionen werden beim Erkennen einer Regel ausgeführt.
I
In v4 weiterhin möglich, es wird aber davon abgeraten
I
Da nun Konstrukte der Zielsprache und Grammatik vermischt
I
Traversieren des ASTs
I
Neu und viel bequemer in ANTLRv4
I
Automatische Generierung von passenden Interfaces und Implementierungen
I
Listener (traversiert auch Unterbäume automatisch)
I
Visitor (explizite Traversierung von Unterbäumen erforderlich)
| WS 2014/15 | A. Koch | FG ESA | 20 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Verwendung des Parsers
I
Bislang wird nur erkannt, ob die Eingabe zur Grammatik passt.
I
In ANTLR ≤ 3: Semantische Aktionen (= Java-Code) in Grammatik einbetten.
I
Aktionen werden beim Erkennen einer Regel ausgeführt.
I
In v4 weiterhin möglich, es wird aber davon abgeraten
I
Da nun Konstrukte der Zielsprache und Grammatik vermischt
I
Traversieren des ASTs
I
Neu und viel bequemer in ANTLRv4
I
Automatische Generierung von passenden Interfaces und Implementierungen
I
Listener (traversiert auch Unterbäume automatisch)
I
Visitor (explizite Traversierung von Unterbäumen erforderlich)
| WS 2014/15 | A. Koch | FG ESA | 20 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Listener
I
Ein Listener reagiert auf Ereignisse (events).
Hier:
I
Der AST wird mittels Tiefensuche von links nach rechts traversiert.
I
Wird ein Knoten X besucht, wird die Methode enterX(..) aufgerufen.
I
Nachdem alle Kinder von X besucht wurden, wird exitX(..) aufgerufen.
I
Für die Grammatik ArrayInit ANTLR generiert automatisch
I
das Listener-Interface ArrayInitListener
I
eine Defaultimplementiertung (mit leeren Eventmethoden)
ArrayInitBaseListener
| WS 2014/15 | A. Koch | FG ESA | 21 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Listener
I
Ein Listener reagiert auf Ereignisse (events).
Hier:
I
Der AST wird mittels Tiefensuche von links nach rechts traversiert.
I
Wird ein Knoten X besucht, wird die Methode enterX(..) aufgerufen.
I
Nachdem alle Kinder von X besucht wurden, wird exitX(..) aufgerufen.
I
Für die Grammatik ArrayInit ANTLR generiert automatisch
I
das Listener-Interface ArrayInitListener
I
eine Defaultimplementiertung (mit leeren Eventmethoden)
ArrayInitBaseListener
| WS 2014/15 | A. Koch | FG ESA | 21 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Listener
Beispiel: {1,{2,3},4}
grammar ArrayInit;
init :
’{’ value (’,’ value)
*
’}’ ;
value : init
| INT
;
INT : [0-9]+ ;
WS : [ \t\r\n]+ -> skip ;
InitContext
’{’
ValueContext
’1’
’,’
InitContext
’{’
ValueContext
’2’
’,’
ValueContext
’3’
’}’
’,’
ValueContext
’4’
’}’
enterInit exitInit
enterInit exitInit
enterValue
exitValue
enter
Value
exit
Value
enter
Value
exit
Value
enterValue
exitValue
| WS 2014/15 | A. Koch | FG ESA | 22 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Listener
Anwendungsbeispiel
I
Ziel: Array-Initialisierer wie {1, 2, 3} in Unicode-Strings wie
“\u0001\u0002\u0003” umwandeln.
I
Ist tatsächlich sinnvoll, letzteres wird effizienter von JVM ausgeführt
I
Vorgehensweise:
I
Geschweifte Klammern zu Anführungszeichen machen
I
Elemente in hexadezimale Darstellung umwandeln und jeweils \u davor schreiben
| WS 2014/15 | A. Koch | FG ESA | 23 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Listener
Code-Beispiel
public class ShortToUnicodeString extends ArrayInitBaseListener {
public void enterInit(ArrayInitParser.InitContext ctx) {
System.out.print(’"’);
}
public void exitInit(ArrayInitParser.InitContext ctx) {
System.out.print(’"’);
}
public void enterValue(ArrayInitParser.ValueContext ctx) {
int value = Integer.valueOf(ctx.INT().getText());
System.out.printf("\\u%04x", value);
}
}
Annahme:
keine geschachtelten Initialisierer
| WS 2014/15 | A. Koch | FG ESA | 24 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Listener
Anwendungsbeispiel (Integration)
import org.antlr.v4.runtime.
*
;
import org.antlr.v4.runtime.tree.
*
;
public class Test {
public static void main(String[] args) throws Exception {
ANTLRInputStream input = new ANTLRInputStream(System.in);
ArrayInitLexer lexer = new ArrayInitLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
ArrayInitParser parser = new ArrayInitParser(tokens);
ParseTree tree = parser.init();
ParseTreeWalker walker = new ParseTreeWalker();
walker.walk(new ShortToUnicodeString(), tree);
System.out.println();
}
}
| WS 2014/15 | A. Koch | FG ESA | 25 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Expression-Grammatik
grammar Expr;
import ExprLexerRules;
prog: stat+ ;
stat: expr NEWLINE # printExpr
| ID ’=’ expr NEWLINE # assign
| NEWLINE # blank
;
expr: expr op=(’
*
’|’/’) expr # MulDiv
| expr op=(’+’|’-’) expr # AddSub
| INT # int
| ID # id
| ’(’ expr ’)’ # parens
;
Andere Grammatik importieren (hier: die Lexer-Regeln)
Benennung (Labeling) der
Alternativen
→ getrennte Event/
Visitor-Methoden
Benennung der Unterregel → Name des Kinds im AST
Links-rekursive Regel (!) → Rekursion wird von ANTLR intern eliminiert
| WS 2014/15 | A. Koch | FG ESA | 26 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Expression-Grammatik
Importierte Lexer-Regeln
lexer grammar ExprLexerRules;
MUL : ’
*
’ ;
DIV : ’/’ ;
ADD : ’+’ ;
SUB : ’-’ ;
ID : [a-zA-Z]+ ;
INT : [0-9]+ ;
NEWLINE: ’\r’? ’\n’ ;
WS : [ \t]+ -> skip ;
Deklaration, dass diese Grammatik nur Lexer-Regeln enthält
Benennung der Tokens
| WS 2014/15 | A. Koch | FG ESA | 27 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Visitor-Pattern
Anwendungsbeispiel
I
Ziel: Interaktiver Taschenrechner
I
Benutzung des von ANTLR generierten Visitor-Patterns
I
Unterschied zum Listener-Mechanismus
I
Traversierung von Unterbäumen muß nun explizit ausformuliert werden
I
Damit Eingriff in Traversierung möglich, z.B.
I
Veränderte Reihenfolge
I
Überspringen von Unterbäumen
I
ANTLR Visitor-Methoden können Ergebnis an Aufrufer zurückgeben
I
Haben aber keine Argumente außer besuchtem AST-Knoten
I
Erzeugen von Visitor statt Listener:
I
antlr4 -no-listener -visitor Expr.g4
I
Erzeugt
I
Interface ExprVisitor
I
Leere Default-Implementierung ExprBaseVisitor
I
Besucht alle Unterbäume, führt aber sonst keine Operationen aus
| WS 2014/15 | A. Koch | FG ESA | 28 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Visitor-Pattern
Anwendungsbeispiel
I
Ziel: Interaktiver Taschenrechner
I
Benutzung des von ANTLR generierten Visitor-Patterns
I
Unterschied zum Listener-Mechanismus
I
Traversierung von Unterbäumen muß nun explizit ausformuliert werden
I
Damit Eingriff in Traversierung möglich, z.B.
I
Veränderte Reihenfolge
I
Überspringen von Unterbäumen
I
ANTLR Visitor-Methoden können Ergebnis an Aufrufer zurückgeben
I
Haben aber keine Argumente außer besuchtem AST-Knoten
I
Erzeugen von Visitor statt Listener:
I
antlr4 -no-listener -visitor Expr.g4
I
Erzeugt
I
Interface ExprVisitor
I
Leere Default-Implementierung ExprBaseVisitor
I
Besucht alle Unterbäume, führt aber sonst keine Operationen aus
| WS 2014/15 | A. Koch | FG ESA | 28 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Visitor-Pattern
Implementierung des Beispiels I
public class EvalVisitor extends ExprBaseVisitor<Integer> {
Map<String, Integer> memory = new HashMap<String, Integer>();
public Integer visitAssign(ExprParser.AssignContext ctx) {
String id = ctx.ID().getText();
int value = visit(ctx.expr());
memory.put(id, value);
return value;
}
public Integer visitPrintExpr(ExprParser.PrintExprContext ctx) {
Integer value = visit(ctx.expr());
System.out.println(value);
return 0;
}
public Integer visitInt(ExprParser.IntContext ctx) {
return Integer.valueOf(ctx.INT().getText());
}
| WS 2014/15 | A. Koch | FG ESA | 29 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Visitor-Pattern
Implementierung des Beispiels II
public Integer visitId(ExprParser.IdContext ctx) {
String id = ctx.ID().getText();
if ( memory.containsKey(id) ) return memory.get(id);
return 0;
}
public Integer visitAddSub(ExprParser.AddSubContext ctx) {
int left = visit(ctx.expr(0));
int right = visit(ctx.expr(1));
if ( ctx.op.getType() == ExprParser.ADD )
return left + right;
return left - right;
}
public Integer visitMulDiv(ExprParser.MulDivContext ctx) { ... }
public Integer visitParens(ExprParser.ParensContext ctx) {
return visit(ctx.expr());
} } // EvalVisitor
Möglich durch Benennung
der Token und Unterregeln
| WS 2014/15 | A. Koch | FG ESA | 30 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Visitor-Pattern
Integration
import org.antlr.v4.runtime.
*
;
import org.antlr.v4.runtime.tree.ParseTree;
public class Calc {
public static void main(String[] args) throws Exception {
ANTLRInputStream input = new ANTLRInputStream(System.in);
ExprLexer lexer = new ExprLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
ExprParser parser = new ExprParser(tokens);
ParseTree tree = parser.prog();
EvalVisitor eval = new EvalVisitor();
eval.visit(tree);
}
}
| WS 2014/15 | A. Koch | FG ESA | 31 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Fortgeschrittene Themen
I
Links- und Rechtsassoziativität
I
Operatorpräzedenzen
I
Das “Dangling Else”-Problem
I
Semantische Prädikate
I
Fehlerbehandlung
| WS 2014/15 | A. Koch | FG ESA | 32 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Linksassoziativität
ANTLR v3: Formulierung der Grammatik
I
Linksassoziativer Operator ⊗:
a ⊗ b ⊗ c = (a ⊗ b) ⊗ c
I
Produktion (linksrekursiv!)
E ::= E ⊗ T |T
I
In EBNF
E ::= T (⊗T )
∗
© Theo Ruys
33
VB HC 4
ANTLR - Introduction
Some ANTLR Tips
• left associative
• right associative
• operator precedence
• dangling-else
Second lecture on ANTLR (lecture #9) will discuss
some more advanced ANTLR Tips and Techniques.
© Theo Ruys
34
VB HC 4
ANTLR - Introduction
Left associative
• Left associative operator ! :
a ! b ! c " (a ! b) ! c
• Production rule:
E ::= E ! T | T
which can be written (by eliminating left recursion) as
E ::= X Y
X ::= T
Y ::= ! T Y
| empty
• or using EBNF:
E ::= T (! T)*
!
!
E
b
c
parse tree
E
E
T
T
T
a
© Theo Ruys
35
VB HC 4
ANTLR - Introduction
Right associative
• Right associative operator ! :
a ! b ! c " a ! (b ! c)
• Production rule:
E ::= T ! E | T
which can be written (using left factorisation) as
E ::= T X
X ::= ! E
| empty
• or using EBNF:
E ::= T (! E)?
!
!
b
E
a
parse tree
E
E
T
T
T
c
© Theo Ruys
36
VB HC 4
ANTLR - Introduction
Operator Precedence (1)
• Consider the following example
a + b * c - d
• which should be parsed as
(a + (b * c)) - d
-
+
a *
d
b
c
• This means that the operator * has precedence over the
operators + and -. This can be reflected in the grammar by
making sure that * is ‘closer to the operands’ than + and -.
expr1 : expr2 ((PLUS^ | MINUS^) expr2)*
expr2 : operand (TIMES^ operand)*
operand : IDENTIFIER
expr2
| WS 2014/15 | A. Koch | FG ESA | 33 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Rechtsassoziativität
ANTLR v3: Formulierung in der Grammatik
I
Rechtsassoziativer Operator ⊗:
a ⊗ b ⊗ c = a ⊗ (b ⊗ c)
I
Produktion (linksrekursiv!)
E ::= T ⊗ E |T
I
In EBNF (? = 0- oder 1-mal)
E ::= T (⊗E)?
© Theo Ruys
33
VB HC 4
ANTLR - Introduction
Some ANTLR Tips
• left associative
• right associative
• operator precedence
• dangling-else
Second lecture on ANTLR (lecture #9) will discuss
some more advanced ANTLR Tips and Techniques.
© Theo Ruys
34
VB HC 4
ANTLR - Introduction
Left associative
• Left associative operator ! :
a ! b ! c " (a ! b) ! c
• Production rule:
E ::= E ! T | T
which can be written (by eliminating left recursion) as
E ::= X Y
X ::= T
Y ::= ! T Y
| empty
• or using EBNF:
E ::= T (! T)*
!
!
E
b
c
parse tree
E
E
T
T
T
a
© Theo Ruys
35
VB HC 4
ANTLR - Introduction
Right associative
• Right associative operator ! :
a ! b ! c " a ! (b ! c)
• Production rule:
E ::= T ! E | T
which can be written (using left factorisation) as
E ::= T X
X ::= ! E
| empty
• or using EBNF:
E ::= T (! E)?
!
!
b
E
a
parse tree
E
E
T
T
T
c
© Theo Ruys
36
VB HC 4
ANTLR - Introduction
Operator Precedence (1)
• Consider the following example
a + b * c - d
• which should be parsed as
(a + (b * c)) - d
-
+
a *
d
b
c
• This means that the operator * has precedence over the
operators + and -. This can be reflected in the grammar by
making sure that * is ‘closer to the operands’ than + and -.
expr1 : expr2 ((PLUS^ | MINUS^) expr2)*
expr2 : operand (TIMES^ operand)*
operand : IDENTIFIER
expr2
| WS 2014/15 | A. Koch | FG ESA | 34 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Operatorpräzedenz 1
ANTLR v3: Formulierung in der Grammatik
I
Beispiel:
a + b × c − d
I
. . . sollte geparsed werden als
(a + (b × c)) − d
© Theo Ruys
33
VB HC 4
ANTLR - Introduction
Some ANTLR Tips
• left associative
• right associative
• operator precedence
• dangling-else
Second lecture on ANTLR (lecture #9) will discuss
some more advanced ANTLR Tips and Techniques.
© Theo Ruys
34
VB HC 4
ANTLR - Introduction
Left associative
• Left associative operator ! :
a ! b ! c " (a ! b) ! c
• Production rule:
E ::= E ! T | T
which can be written (by eliminating left recursion) as
E ::= X Y
X ::= T
Y ::= ! T Y
| empty
• or using EBNF:
E ::= T (! T)*
!
!
E
b
c
parse tree
E
E
T
T
T
a
© Theo Ruys
35
VB HC 4
ANTLR - Introduction
Right associative
• Right associative operator ! :
a ! b ! c " a ! (b ! c)
• Production rule:
E ::= T ! E | T
which can be written (using left factorisation) as
E ::= T X
X ::= ! E
| empty
• or using EBNF:
E ::= T (! E)?
!
!
b
E
a
parse tree
E
E
T
T
T
c
© Theo Ruys
36
VB HC 4
ANTLR - Introduction
Operator Precedence (1)
• Consider the following example
a + b * c - d
• which should be parsed as
(a + (b * c)) - d
-
+
a *
d
b
c
• This means that the operator * has precedence over the
operators + and -. This can be reflected in the grammar by
making sure that * is ‘closer to the operands’ than + and -.
expr1 : expr2 ((PLUS^ | MINUS^) expr2)*
expr2 : operand (TIMES^ operand)*
operand : IDENTIFIER
expr2
I
Operator × hat höhere Präzedenz als + und −
I
In Grammatik ausdrücken, durch Platzieren von × “näher an Operanden” als
+ und −
© Theo Ruys
33
VB HC 4
ANTLR - Introduction
Some ANTLR Tips
• left associative
• right associative
• operator precedence
• dangling-else
Second lecture on ANTLR (lecture #9) will discuss
some more advanced ANTLR Tips and Techniques.
© Theo Ruys
34
VB HC 4
ANTLR - Introduction
Left associative
• Left associative operator ! :
a ! b ! c " (a ! b) ! c
• Production rule:
E ::= E ! T | T
which can be written (by eliminating left recursion) as
E ::= X Y
X ::= T
Y ::= ! T Y
| empty
• or using EBNF:
E ::= T (! T)*
!
!
E
b
c
parse tree
E
E
T
T
T
a
© Theo Ruys
35
VB HC 4
ANTLR - Introduction
Right associative
• Right associative operator ! :
a ! b ! c " a ! (b ! c)
• Production rule:
E ::= T ! E | T
which can be written (using left factorisation) as
E ::= T X
X ::= ! E
| empty
• or using EBNF:
E ::= T (! E)?
!
!
b
E
a
parse tree
E
E
T
T
T
c
© Theo Ruys
36
VB HC 4
ANTLR - Introduction
Operator Precedence (1)
• Consider the following example
a + b * c - d
• which should be parsed as
(a + (b * c)) - d
-
+
a *
d
b
c
• This means that the operator * has precedence over the
operators + and -. This can be reflected in the grammar by
making sure that * is ‘closer to the operands’ than + and -.
expr1 : expr2 ((PLUS^ | MINUS^) expr2)*
expr2 : operand (TIMES^ operand)*
operand : IDENTIFIER
expr2
| WS 2014/15 | A. Koch | FG ESA | 35 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Operatorpräzedenz 2
a + b × c − d
© Theo Ruys
37
VB HC 4
ANTLR - Introduction
Operator Precedence (2)
expr1 : expr2 ((PLUS^ | MINUS^) expr2)*
expr2 : operand (TIMES^ operand)*
operand : IDENTIFIER
a + b * c - d
expr1
expr2 expr2 expr2 PLUS^ MINUS^
operand
ID
a
operand operand
ID
b
ID
c
operand
ID
d
TIMES^
parse tree:
PLUS
MINUS
ID
a
ID
b
ID
c
ID
d
TIMES
constructed AST:
© Theo Ruys
38
VB HC 4
ANTLR - Introduction
Greedy (1)
• Consider the classic if-then-else ambiguity (i.e., dangling else)
stat : 'if' expr 'then' stat ('else' stat)?
| ... ;
if b1 then if b2 then s1 else s2
e.g.
if
then if
then else
b1
s1 b2 s2
stat
stat
if
then if
then
else
b1
s1 b2
s2
stat
stat
Two possible parse trees:
© Theo Ruys
39
VB HC 4
ANTLR - Introduction
Greedy (2)
warning(200): Foo.g:12:33: Decision can match input
such as "'else'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that
input
stat : 'if' expr 'then' stat
(options {greedy=true;} : 'else' stat)?
| ... ;
• If you make it clear to ANTLR that you want the subrule to match
greedily (i.e. the default behavior), ANTLR will not generate the
warning.
• So this ambiguity (which statement should the “else” be attached to)
results in a parser nondeterminism. ANTLR 3 warns you:
Note: this is the way it should work according to the
documentation. However, ANTLR 3 still shows the warning.
(Note that the generated compiler will work correctly though)
| WS 2014/15 | A. Koch | FG ESA | 36 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Assoziativität und Präzedenz in ANTLRv4
expr: expr ’^’<assoc=right> expr
| expr op=(’
*
’|’/’) expr
| expr op=(’+’|’-’) expr
| INT
| ID
| ’(’ expr ’)’
;
I
Operatorpräzedenz wird durch Reihenfolge der Alternativen implizit kodiert
I
Rechts-assoziative Operatoren durch Token-Option assoc=right
kennzeichnen
Präzedenz
I
ANTLR kann links-rekursive Regeln dieser Art automatisch transformieren.
→ Verfahren: “Precedence climbing”, mehr Details
I
ANTLR v4 Buch
I
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
| WS 2014/15 | A. Koch | FG ESA | 37 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Assoziativität und Präzedenz in ANTLRv4
expr: expr ’^’<assoc=right> expr
| expr op=(’
*
’|’/’) expr
| expr op=(’+’|’-’) expr
| INT
| ID
| ’(’ expr ’)’
;
I
Operatorpräzedenz wird durch Reihenfolge der Alternativen implizit kodiert
I
Rechts-assoziative Operatoren durch Token-Option assoc=right
kennzeichnen
Präzedenz
I
ANTLR kann links-rekursive Regeln dieser Art automatisch transformieren.
→ Verfahren: “Precedence climbing”, mehr Details
I
ANTLR v4 Buch
I
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
| WS 2014/15 | A. Koch | FG ESA | 37 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Hängendes else
dangling else
Klassisches Problem von Mehrdeutigkeit beim Parsen
© Theo Ruys
37
VB HC 4
ANTLR - Introduction
Operator Precedence (2)
expr1 : expr2 ((PLUS^ | MINUS^) expr2)*
expr2 : operand (TIMES^ operand)*
operand : IDENTIFIER
a + b * c - d
expr1
expr2 expr2 expr2 PLUS^ MINUS^
operand
ID
a
operand operand
ID
b
ID
c
operand
ID
d
TIMES^
parse tree:
PLUS
MINUS
ID
a
ID
b
ID
c
ID
d
TIMES
constructed AST:
© Theo Ruys
38
VB HC 4
ANTLR - Introduction
Greedy (1)
• Consider the classic if-then-else ambiguity (i.e., dangling else)
stat : 'if' expr 'then' stat ('else' stat)?
| ... ;
if b1 then if b2 then s1 else s2
e.g.
if
then if
then else
b1
s1 b2 s2
stat
stat
if
then if
then
else
b1
s1 b2
s2
stat
stat
Two possible parse trees:
© Theo Ruys
39
VB HC 4
ANTLR - Introduction
Greedy (2)
warning(200): Foo.g:12:33: Decision can match input
such as "'else'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that
input
stat : 'if' expr 'then' stat
(options {greedy=true;} : 'else' stat)?
| ... ;
• If you make it clear to ANTLR that you want the subrule to match
greedily (i.e. the default behavior), ANTLR will not generate the
warning.
• So this ambiguity (which statement should the “else” be attached to)
results in a parser nondeterminism. ANTLR 3 warns you:
Note: this is the way it should work according to the
documentation. However, ANTLR 3 still shows the warning.
(Note that the generated compiler will work correctly though)
Zwei mögliche Parse-Bäume. ANTLR tut automatisch das richtige (1. Baum), da ?
greedy ist.
© Theo Ruys
37
VB HC 4
ANTLR - Introduction
Operator Precedence (2)
expr1 : expr2 ((PLUS^ | MINUS^) expr2)*
expr2 : operand (TIMES^ operand)*
operand : IDENTIFIER
a + b * c - d
expr1
expr2 expr2 expr2 PLUS^ MINUS^
operand
ID
a
operand operand
ID
b
ID
c
operand
ID
d
TIMES^
parse tree:
PLUS
MINUS
ID
a
ID
b
ID
c
ID
d
TIMES
constructed AST:
© Theo Ruys
38
VB HC 4
ANTLR - Introduction
Greedy (1)
• Consider the classic if-then-else ambiguity (i.e., dangling else)
stat : 'if' expr 'then' stat ('else' stat)?
| ... ;
if b1 then if b2 then s1 else s2
e.g.
if
then if
then else
b1
s1 b2 s2
stat
stat
if
then if
then
else
b1
s1 b2
s2
stat
stat
Two possible parse trees:
© Theo Ruys
39
VB HC 4
ANTLR - Introduction
Greedy (2)
warning(200): Foo.g:12:33: Decision can match input
such as "'else'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that
input
stat : 'if' expr 'then' stat
(options {greedy=true;} : 'else' stat)?
| ... ;
• If you make it clear to ANTLR that you want the subrule to match
greedily (i.e. the default behavior), ANTLR will not generate the
warning.
• So this ambiguity (which statement should the “else” be attached to)
results in a parser nondeterminism. ANTLR 3 warns you:
Note: this is the way it should work according to the
documentation. However, ANTLR 3 still shows the warning.
(Note that the generated compiler will work correctly though)
| WS 2014/15 | A. Koch | FG ESA | 38 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate 1
I
Zur Laufzeit ausgewertete Prädikate qualifizieren Alternativen
I
Formuliert als Konstrukte der Zielsprache
I
TRUE: Alternative ist möglich
I
FALSE: Alternative ist nicht möglich
I
Vorteil: Mächtigerer Parser
I
Ist f(1) Funktionsaufruf oder Zugriff auf Array-Element?
I
Leicht entscheidbar, wenn Typ von f während Parsen abgerufen werden kann
I
Nachteil: Nun keine zielsprachenunabhängige Grammatik mehr
| WS 2014/15 | A. Koch | FG ESA | 39 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate 1
I
Zur Laufzeit ausgewertete Prädikate qualifizieren Alternativen
I
Formuliert als Konstrukte der Zielsprache
I
TRUE: Alternative ist möglich
I
FALSE: Alternative ist nicht möglich
I
Vorteil: Mächtigerer Parser
I
Ist f(1) Funktionsaufruf oder Zugriff auf Array-Element?
I
Leicht entscheidbar, wenn Typ von f während Parsen abgerufen werden kann
I
Nachteil: Nun keine zielsprachenunabhängige Grammatik mehr
| WS 2014/15 | A. Koch | FG ESA | 39 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate 2
Beispiel
Erkenne Gruppen in einem Zahlenstrom, in dem die jeweils erste Zahl die Länge
der Gruppe angibt.
2 4 5 3 1 7 9 5 0 0 0 17 0 → (4, 5); (1, 7, 9); (0, 0, 0, 17, 0)
Problem:
I
Die Gruppengröße ist Teil der (variablen!) Eingabedaten
I
Kann nicht statisch in der Grammatik ausformuliert werden
| WS 2014/15 | A. Koch | FG ESA | 40 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate 2
Beispiel
Erkenne Gruppen in einem Zahlenstrom, in dem die jeweils erste Zahl die Länge
der Gruppe angibt.
2 4 5 3 1 7 9 5 0 0 0 17 0 → (4, 5); (1, 7, 9); (0, 0, 0, 17, 0)
Problem:
I
Die Gruppengröße ist Teil der (variablen!) Eingabedaten
I
Kann nicht statisch in der Grammatik ausformuliert werden
| WS 2014/15 | A. Koch | FG ESA | 40 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate
Grammatik
grammar Data;
file : group+ ;
group: INT sequence[$INT.int] ;
sequence[int n]
locals [int i = 1;]
: ( {$i<=$n}? INT {$i++;} )
*
;
INT : [0-9]+ ;
WS : [ \t\n\r]+ -> skip ;
Parametrisierte Regel. Das Argument
ist der Integerwert des INT-Tokens,
welches vorher erkannt wurde.
Definition der Regel mit Parameter n und lokaler Variable i
Das semantische Prädikat. In der Grammatik
deklarierte Variablen werden mit
vorangestelltem $ zugegriffen.
Eine “normale” Aktion.
Der Code wird in die entsprechende
Methode des Parser kopiert.
| WS 2014/15 | A. Koch | FG ESA | 41 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate
Grammatik
grammar Data;
file : group+ ;
group: INT sequence[$INT.int] ;
sequence[int n]
locals [int i = 1;]
: ( {$i<=$n}? INT {$i++;} )
*
;
INT : [0-9]+ ;
WS : [ \t\n\r]+ -> skip ;
Parametrisierte Regel. Das Argument
ist der Integerwert des INT-Tokens,
welches vorher erkannt wurde.
Definition der Regel mit Parameter n und lokaler Variable i
Das semantische Prädikat. In der Grammatik
deklarierte Variablen werden mit
vorangestelltem $ zugegriffen.
Eine “normale” Aktion.
Der Code wird in die entsprechende
Methode des Parser kopiert.
| WS 2014/15 | A. Koch | FG ESA | 41 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate
Effekt
file : group+ ;
group: INT sequence[$INT.int] ;
sequence[int n] locals [int i = 1;]
: ( {$i<=$n}? INT {$i++;} )
*
;
Beispiel: 2 4 5 3 ...
I
In der Regel group wird 2 als INT erkannt und an sequence übergeben
I
Das semantische Prädikat 1 <= 2 wird zu true ausgewertet, so dass 4 als
INT erkannt wird. Die folgende Aktion inkrementiert i
I
Analog wird 5 erkannt und i zu 3 inkrementiert
I
Nun deaktiviert i <= 2 → false die (einzige) Alternative von sequence
I
Der Parser kehrt erst zu group und dann zu file zurück, und beginnt mit dem
Parsen einer neuen Gruppe
| WS 2014/15 | A. Koch | FG ESA | 42 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate
Effekt
file : group+ ;
group: INT sequence[$INT.int] ;
sequence[int n] locals [int i = 1;]
: ( {$i<=$n}? INT {$i++;} )
*
;
Beispiel: 2 4 5 3 ...
I
In der Regel group wird 2 als INT erkannt und an sequence übergeben
I
Das semantische Prädikat 1 <= 2 wird zu true ausgewertet, so dass 4 als
INT erkannt wird. Die folgende Aktion inkrementiert i
I
Analog wird 5 erkannt und i zu 3 inkrementiert
I
Nun deaktiviert i <= 2 → false die (einzige) Alternative von sequence
I
Der Parser kehrt erst zu group und dann zu file zurück, und beginnt mit dem
Parsen einer neuen Gruppe
| WS 2014/15 | A. Koch | FG ESA | 42 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate
Effekt
file : group+ ;
group: INT sequence[$INT.int] ;
sequence[int n] locals [int i = 1;]
: ( {$i<=$n}? INT {$i++;} )
*
;
Beispiel: 2 4 5 3 ...
I
In der Regel group wird 2 als INT erkannt und an sequence übergeben
I
Das semantische Prädikat 1 <= 2 wird zu true ausgewertet, so dass 4 als
INT erkannt wird. Die folgende Aktion inkrementiert i
I
Analog wird 5 erkannt und i zu 3 inkrementiert
I
Nun deaktiviert i <= 2 → false die (einzige) Alternative von sequence
I
Der Parser kehrt erst zu group und dann zu file zurück, und beginnt mit dem
Parsen einer neuen Gruppe
| WS 2014/15 | A. Koch | FG ESA | 42 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate
Effekt
file : group+ ;
group: INT sequence[$INT.int] ;
sequence[int n] locals [int i = 1;]
: ( {$i<=$n}? INT {$i++;} )
*
;
Beispiel: 2 4 5 3 ...
I
In der Regel group wird 2 als INT erkannt und an sequence übergeben
I
Das semantische Prädikat 1 <= 2 wird zu true ausgewertet, so dass 4 als
INT erkannt wird. Die folgende Aktion inkrementiert i
I
Analog wird 5 erkannt und i zu 3 inkrementiert
I
Nun deaktiviert i <= 2 → false die (einzige) Alternative von sequence
I
Der Parser kehrt erst zu group und dann zu file zurück, und beginnt mit dem
Parsen einer neuen Gruppe
| WS 2014/15 | A. Koch | FG ESA | 42 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Semantische Prädikate
Effekt
file : group+ ;
group: INT sequence[$INT.int] ;
sequence[int n] locals [int i = 1;]
: ( {$i<=$n}? INT {$i++;} )
*
;
Beispiel: 2 4 5 3 ...
I
In der Regel group wird 2 als INT erkannt und an sequence übergeben
I
Das semantische Prädikat 1 <= 2 wird zu true ausgewertet, so dass 4 als
INT erkannt wird. Die folgende Aktion inkrementiert i
I
Analog wird 5 erkannt und i zu 3 inkrementiert
I
Nun deaktiviert i <= 2 → false die (einzige) Alternative von sequence
I
Der Parser kehrt erst zu group und dann zu file zurück, und beginnt mit dem
Parsen einer neuen Gruppe
| WS 2014/15 | A. Koch | FG ESA | 42 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Fehlerbehandlung
I
ANTLR-generierte Erkenner behandeln Fehler durch Java-Exceptions.
I
RecognitionException ist Basisklasse aller ANTLR-Exceptions.
I
Standardverhalten der generierten Parserregeln:
I
Fange alle RecognitionExceptions,
I
Gebe Fehlermeldung aus,
I
Setze dann das Parsen fort.
try {
...
} catch (RecognitionException re) {
_errHandler.reportError(this, re);
_errHandler.recover(this, re);
} finally {
exitRule();
}
| WS 2014/15 | A. Koch | FG ESA | 43 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Fortsetzen nach Fehler
I
Wichtig, z.B. für Compiler
I
Benutzer möchte nicht jeden Fehler einzeln präsentiert bekommen
(Einfache) Möglichkeiten für den Parser im Fehlerfall
I
Token ignorieren: class 3 Color { int x; }
→ Wenn das darauf folgende Token passen würde
→ Ignoriert hier 3.
I
Fehlendes Token annehmen/einfügen: class { int x; }
→ Wenn das aktuelle Token auf das nächste Element der Regel passen würde
→ Nimmt fiktiven Bezeichner als Klassennamen an
| WS 2014/15 | A. Koch | FG ESA | 44 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
Zusammenfassung
I
ANTLR erlaubt Entwickler . . .
I
. . . sich auf Spezifikation der Eingabesprache zu konzentrieren
I
Übernimmt dann Implementation von Lexer/Parser
I
Unterstützt bei Implementierung von Passes auf AST
I
Gleiche Syntax zur Spezifikation von Lexer/Scanner und Parser
I
Trennung von Grammatik und Code in der Zielsprache
I
Grammatik bleibt portabel/wiederverwendbar
I
Anwendung kann in gewohnter Sprache programmiert werden
I
Mächtiges ALL(?) Parsing-Verfahren
I
Automatisierte Grammatiktransformationen
I
Gut unterstützt und aktive Benutzergemeinschaft
I
Sehr gute graphische IDE ANTLRWorks2:
http://tunnelvisionlabs.com/products/demo/antlrworks
| WS 2014/15 | A. Koch | FG ESA | 45 / 45
Compiler 1 Einleitung Parser und Listener-Interface Expressions und Visitor-Interface Fortgeschrittene Themen Zusammenfassung
