Struktur eines Compilers

Sprachen verstehen, Texte transformieren

The cat runs quickly.

=> Struktur? Bedeutung?

Wir können hier (mit steigender Abstraktionsstufe) unterscheiden:

• Sequenz von Zeichen

• Wörter: Zeichenketten mit bestimmten Buchstaben, getrennt durch bestimmte andere Zeichen; Wörter könnten im Wörterbuch nachgeschlagen werden

• Sätze: Anordnung von Wörtern nach einer bestimmten Grammatik, Grenze: Satzzeichen

  Hier (vereinfacht): Ein Satz besteht aus Subjekt und Prädikat. Das Subjekt besteht aus einem oder keinen Artikel und einem Substantiv. Das Prädikat besteht aus einem Verb und einem oder keinem Adverb.

• Sprache: Die Menge der in einer Grammatik erlaubten Sätze

Compiler: Big Picture

Quelle: A Map of the Territory (mountain.png) by Bob Nystrom on Github.com (MIT)

Begriffe und Phasen

Die obige Bergsteige-Metapher kann man in ein nüchternes Ablaufdiagramm mit verschiedenen Stufen und den zwischen den Stufen ausgetauschten Artefakten übersetzen:

Frontend, Analyse

Die ersten Stufen eines Compilers, die mit der Analyse des Inputs beschäftigt sind. Dies sind in der Regel der Scanner, der Parser und die semantische Analyse.

• Scanner, Lexer, Tokenizer, Lexikalische Analyse

  Zerteilt den Zeichenstrom in eine Folge von Wörtern. Mit regulären Ausdrücken kann definiert werden, was Klassen gültiger Wörter ("Token") sind. Ein Token hat i.d.R. einen Namen und einen Wert.

• Parser, Syntaxanalyse

  Der Parser erhält als Eingabe die Folge der Token und versucht mit Hilfe einer Grammatik zu bestimmen, ob es sich bei der Tokensequenz um gültige Sätze im Sinne der Grammatik handelt. Hier gibt es viele Algorithmen, die im Wesentlichen in die Klassen "top-down" und "bottom-up" fallen.

• Semantische Analyse, Kontexthandling

  In den vorigen Stufen wurde eher lokal gearbeitet. Hier wird über den gesamten Baum und die Symboltabelle hinweg geprüft, ob beispielsweise Typen korrekt verwendet wurden, in welchen Scope ein Name gehört etc. Mit diesen Informationen wird der AST angereichert.

• Symboltabellen

  Datenstrukturen, um Namen, Werte, Scopes und weitere Informationen zu speichern. Die Symboltabellen werden vor allem beim Parsen befüllt und bei der semantischen Analyse gelesen, aber auch der Lexer benötigt u.U. diese Informationen.

Backend, Synthese

Die hinteren Stufen eines Compilers, die mit der Synthese der Ausgabe beschäftigt sind. Dies sind in der Regel verschiedene Optimierungen und letztlich die Code-Generierung

• Codegenerierung

  Erzeugung des Zielprogramms aus der (optimierten) Zwischendarstellung. Dies ist oft Maschinencode, kann aber auch C-Code oder eine andere Ziel-Sprache sein.

• Optimierung

  Diverse Maßnahmen, um den resultierenden Code kleiner und/oder schneller zu gestalten.

• Symboltabellen

  Datenstrukturen, um Namen, Werte, Scopes und weitere Informationen zu speichern. Die Symboltabellen werden vor allem beim Parsen befüllt und bei der semantischen Analyse gelesen, aber auch der Lexer benötigt u.U. diese Informationen.

Weitere Begriffe

• Parse Tree, Concrete Syntax Tree

  Repräsentiert die Struktur eines Satzes, wobei jeder Knoten dem Namen einer Regel der Grammatik entspricht. Die Blätter bestehen aus den Token samt ihren Werten.

• AST, (Abstract) Syntax Tree

  Vereinfachte Form des Parse Tree, wobei der Bezug auf die Element der Grammatik (mehr oder weniger) weggelassen wird.

• Annotierter AST

  Anmerkungen am AST, die für spätere Verarbeitungsstufen interessant sein könnten: Typ-Informationen, Optimierungsinformationen, ...

• Zwischen-Code, IC

  Zwischensprache, die abstrakter ist als die dem AST zugrunde liegenden Konstrukte der Ausgangssprache. Beispielsweise könnten while-Schleifen durch entsprechende Label und Sprünge ersetzt werden. Wie genau dieser Zwischen-Code aussieht, muss der Compilerdesigner entscheiden. Oft findet man den Assembler-ähnlichen "3-Adressen-Code".

• Sprache

  Eine Sprache ist eine Menge gültiger Sätze. Die Sätze werden aus Wörtern gebildet, diese wiederum aus Zeichenfolgen.

• Grammatik

  Eine Grammatik beschreibt formal die Syntaxregeln für eine Sprache. Jede Regel in der Grammatik beschreibt dabei die Struktur eines Satzes oder einer Phrase.

Lexikalische Analyse: Wörter ("Token") erkennen

Die lexikalische Analyse (auch Scanner oder Lexer oder Tokenizer genannt) zerteilt den Zeichenstrom in eine Folge von Wörtern ("Token"). Die geschieht i.d.R. mit Hilfe von regulären Ausdrücken.

Dabei müssen unsinnige/nicht erlaubte Wörter erkannt werden.

Überflüssige Zeichen (etwa Leerzeichen) werden i.d.R. entfernt.

sp = 100;

<ID, sp>, <OP, =>, <INT, 100>, <SEM>

Anmerkung: In der obigen Darstellung werden die Werte der Token ("Lexeme") zusammen mit den Token "gespeichert". Alternativ können die Werte der Token auch direkt in der Symboltabelle gespeichert werden und in den Token nur der Verweis auf den jeweiligen Eintrag in der Tabelle.

Syntaxanalyse: Sätze erkennen

In der Syntaxanalyse (auch Parser genannt) wird die Tokensequenz in gültige Sätze unterteilt. Dazu werden in der Regel kontextfreie Grammatiken und unterschiedliche Parsing-Methoden (top-down, bottom-up) genutzt.

Dabei müssen nicht erlaubte Sätze erkannt werden.

<ID, sp>, <OP, =>, <INT, 100>, <SEM>

statement : assign SEM ;
assign : ID OP INT ;

                   statement                  =
                   /       \                 / \
               assign      SEM             sp  100
             /   |   \      |
           ID    OP  INT    ;
           |     |    |
           sp    =   100

Mit Hilfe der Produktionsregeln der Grammatik wird versucht, die Tokensequenz zu erzeugen. Wenn dies gelingt, ist der Satz (also die Tokensequenz) ein gültiger Satz im Sinne der Grammatik. Dabei sind die Token aus der lexikalischen Analyse die hier betrachteten Wörter!

Dabei entsteht ein sogenannter Parse-Tree (oder auch "Syntax Tree"; in der obigen Darstellung der linke Baum). In diesen Bäumen spiegeln sich die Regeln der Grammatik wider, d.h. zu einem Satz kann es durchaus verschiedene Parse-Trees geben.

Beim AST ("Abstract Syntax Tree") werden die Knoten um alle später nicht mehr benötigten Informationen bereinigt (in der obigen Darstellung der rechte Baum).

Anmerkung: Die Begriffe werden oft nicht eindeutig verwendet. Je nach Anwendung ist das Ergebnis des Parsers ein AST oder ein Parse-Tree.

Anmerkung: Man könnte statt OP auch etwa ein ASSIGN nutzen und müsste dann das "=" nicht extra als Inhalt speichern, d.h. man würde die Information im Token-Typ kodieren.

Vorschau: Parser implementieren

stat : assign | ifstat | ... ;
assign : ID '=' expr ';' ;

void stat() {
    switch (<<current token>>) {
        case ID : assign(); break;
        case IF : ifstat(); break;
        ...
        default : <<raise exception>>
    }
}
void assign() {
    match(ID);
    match('=');
    expr();
    match(';');
}

Der gezeigte Parser ist ein sogenannter "LL(1)"-Parser und geht von oben nach unten vor, d.h. ist ein Top-Down-Parser.

Nach dem Betrachten des aktuellen Tokens wird entschieden, welche Alternative vorliegt und in die jeweilige Methode gesprungen.

Die match()-Methode entspricht dabei dem Erzeugen von Blättern, d.h. hier werden letztlich die Token der Grammatik erkannt.

Semantische Analyse: Bedeutung erkennen

In der semantischen Analyse (auch Context Handling genannt) wird der AST zusammen mit der Symboltabelle geprüft. Dabei spielen Probleme wie Scopes, Namen und Typen eine wichtige Rolle.

Die semantische Analyse ist direkt vom Programmierparadigma der zu übersetzenden Sprache abhängig, d.h. müssen wir beispielsweise das Konzept von Klassen verstehen?

Als Ergebnis dieser Phase entsteht typischerweise ein annotierter AST.

{
    int x = 42;
    {
        int x = 7;
        x += 3;    // ???
    }
}

                                              = {type: real, loc: tmp1}
sp = 100;                                    / \
                                            /   \
                                          sp     inttofloat
                                  {type: real,       |
                                   loc: var b}      100

Zwischencode generieren

Aus dem annotierten AST wird in der Regel ein Zwischencode ("Intermediate Code", auch "IC") generiert. oft findet man hier den Assembler-ähnlichen "3-Adressen-Code", in manchen Compilern wird als IC aber auch der AST selbst genutzt.

                 = {type: real, loc: tmp1}
                / \
               /   \
             sp     inttofloat
     {type: real,       |
      loc: var b}      100

=> t1 = inttofloat(100)

Code optimieren

An dieser Stelle verlassen wir das Compiler-Frontend und begeben uns in das sogenannte Backend. Die Optimierung des Codes kann sehr unterschiedlich ausfallen, beispielsweise kann man den Zwischencode selbst optimieren, dann nach sogenanntem "Targetcode" übersetzen und diesen weiter optimieren, bevor das Ergebnis im letzten Schritt in Maschinencode übersetzt wird.

Die Optimierungsphase ist sehr stark abhängig von der Zielhardware. Hier kommen fortgeschrittene Mengen- und Graphalgorithmen zur Anwendung. Die Optimierung stellt den wichtigsten Teil aktueller Compiler dar.

Aus zeitlichen und didaktischen Gründen werden wir in dieser Veranstaltung den Fokus auf die Frontend-Phasen legen und die Optimierung nur grob streifen.

t1 = inttofloat(100) => t1 = 100.0

x = y*0; => x = 0;

Code generieren

• Maschinencode:

  STD  t1, 100.0

• Andere Sprache:

  • Bytecode
  • C
  • ...

Probleme

5*4+3

AST?

Problem: Vorrang von Operatoren

• Variante 1: +(*(5, 4), 3)
• Variante 2: *(5, +(4, 3))

stat : expr ';'
     | ID '(' ')' ';'
     ;
expr : ID '(' ')'
     | INT
     ;

Wrap-Up

• Compiler übersetzen Text in ein anderes Format

• Typische Phasen:

  1. Lexikalische Analyse
  2. Syntaxanalyse
  3. Semantische Analyse
  4. Generierung von Zwischencode
  5. Optimierung des (Zwischen-) Codes
  6. Codegenerierung

Bandbreite der Programmiersprachen

99 Bottles of Beer

99 bottles of beer on the wall, 99 bottles of beer. Take one down and pass it around, 98 bottles of beer on the wall.

98 bottles of beer on the wall, 98 bottles of beer. Take one down and pass it around, 97 bottles of beer on the wall.

[...]

2 bottles of beer on the wall, 2 bottles of beer. Take one down and pass it around, 1 bottle of beer on the wall.

1 bottle of beer on the wall, 1 bottle of beer. Take one down and pass it around, no more bottles of beer on the wall.

No more bottles of beer on the wall, no more bottles of beer. Go to the store and buy some more, 99 bottles of beer on the wall.

Quelle: nach "Lyrics of the song 99 Bottles of Beer" on 99-bottles-of-beer.net

Imperativ, Hardwarenah: C

 #define MAXBEER (99)
 void chug(int beers);
 main() {
    register beers;
    for(beers = MAXBEER; beers; chug(beers--))  puts("");
    puts("\nTime to buy more beer!\n");
 }
 void chug(register beers) {
    char howmany[8], *s;
    s = beers != 1 ? "s" : "";
    printf("%d bottle%s of beer on the wall,\n", beers, s);
    printf("%d bottle%s of beeeeer . . . ,\n", beers, s);
    printf("Take one down, pass it around,\n");
    if(--beers) sprintf(howmany, "%d", beers); else strcpy(howmany, "No more");
    s = beers != 1 ? "s" : "";
    printf("%s bottle%s of beer on the wall.\n", howmany, s);
 }

Quelle: "Language C" by Bill Wein on 99-bottles-of-beer.net

• Imperativ

• Procedural

• Statisches Typsystem

• Resourcenschonend, aber "unsicher": Programmierer muss wissen, was er tut

• Relativ hardwarenah

• Einsatz: Betriebssysteme, Systemprogrammierung

Imperativ, Objektorientiert: Java

class bottles {
    public static void main(String args[]) {
        String s = "s";
        for (int beers=99; beers>-1;) {
            System.out.print(beers + " bottle" + s + " of beer on the wall, ");
            System.out.println(beers + " bottle" + s + " of beer, ");
            if (beers==0) {
                System.out.print("Go to the store, buy some more, ");
                System.out.println("99 bottles of beer on the wall.\n");
                System.exit(0);
            } else
                System.out.print("Take one down, pass it around, ");
            s = (--beers == 1)?"":"s";
            System.out.println(beers + " bottle" + s + " of beer on the wall.\n");
        }
    }
}

Quelle: "Language Java" by Sean Russell on 99-bottles-of-beer.net

• Imperativ

• Objektorientiert

• Multi-Threading

• Basiert auf C/C++

• Statisches Typsystem

• Automatische Garbage Collection

• "Sichere" Architektur: Laufzeitumgebung fängt viele Probleme ab

• Architekturneutral: Nutzt Bytecode und eine JVM

• Einsatz: High-Level All-Purpose Language

Logisch: Prolog

bottles :-
    bottles(99).

bottles(1) :-
    write('1 bottle of beer on the wall, 1 bottle of beer,'), nl,
    write('Take one down, and pass it around,'), nl,
    write('Now they are all gone.'), nl,!.
bottles(X) :-
    write(X), write(' bottles of beer on the wall,'), nl,
    write(X), write(' bottles of beer,'), nl,
    write('Take one down and pass it around,'), nl,
    NX is X - 1,
    write(NX), write(' bottles of beer on the wall.'), nl, nl,
    bottles(NX).

Quelle: "Language Prolog" by M@ on 99-bottles-of-beer.net

• Deklarativ

• Logisch: Definition von Fakten und Regeln; eingebautes Beweissystem

• Einsatz: Theorem-Beweisen, Natural Language Programming (NLP), Expertensysteme, ...

Funktional: Haskell

bottles 0 = "no more bottles"
bottles 1 = "1 bottle"
bottles n = show n ++ " bottles"

verse 0   = "No more bottles of beer on the wall, no more bottles of beer.\n"
         ++ "Go to the store and buy some more, 99 bottles of beer on the wall."

verse n   = bottles n ++ " of beer on the wall, " ++ bottles n ++ " of beer.\n"
         ++ "Take one down and pass it around, " ++ bottles (n-1)
                                                 ++ " of beer on the wall.\n"

main      = mapM (putStrLn . verse) [99,98..0]

Quelle: "Language Haskell" by Iavor on 99-bottles-of-beer.net

• Deklarativ

• Funktional

• Lazy, pure

• Statisches Typsystem

• Typinferenz

• Algebraische Datentypen, Patternmatching

• Einsatz: Compiler, DSL, Forschung

Brainfuck

Quelle: Screenshot of "Language Brainfuck" by Michal Wojciech Tarnowski on 99-bottles-of-beer.net

• Imperativ

• Feldbasiert (analog zum Band der Turingmaschine)

• 8 Befehle: Zeiger und Zellen inkrementieren/dekrementieren, Aus- und Eingabe, Sprungbefehle

Programmiersprache Lox

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

var wuppie = fib;
wuppie(4);

• Die Sprache "Lox" finden Sie hier: craftinginterpreters.com/the-lox-language.html

• C-ähnliche Syntax

• Imperativ, objektorientiert, Funktionen als First Class Citizens, Closures

• Dynamisch typisiert

• Garbage Collector

• Statements und Expressions

• (Kleine) Standardbibliothek eingebaut

Die Sprache ähnelt stark anderen modernen Sprachen und ist gut geeignet, um an ihrem Beispiel Themen wie Scanner/Parser/AST, Interpreter, Object Code und VM zu studieren :)

Wrap-Up

• Compiler übersetzen formalen Text in ein anderes Format

• Berücksichtigung von unterschiedlichen

  • Sprachkonzepten (Programmierparadigmen)
  • Typ-Systemen
  • Speicherverwaltungsstrategien
  • Abarbeitungsstrategien

Anwendungen

Anwendung: Compiler

Wie oben diskutiert: Der Sourcecode durchläuft alle Phasen des Compilers, am Ende fällt ein ausführbares Programm heraus. Dieses kann man starten und ggf. mit Inputdaten versehen und erhält den entsprechenden Output. Das erzeugte Programm läuft i.d.R. nur auf einer bestimmten Plattform.

Beispiele: gcc, clang, ...

Anwendung: Interpreter

Beim Interpreter durchläuft der Sourcecode nur das Frontend, also die Analyse. Es wird kein Code erzeugt, stattdessen führt der Interpreter die Anweisungen im AST bzw. IC aus. Dazu muss der Interpreter mit den Eingabedaten beschickt werden. Typischerweise hat man hier eine "Read-Eval-Print-Loop" (REPL).

Beispiele: Python

Anwendung: Virtuelle Maschinen

Hier liegt eine Art Mischform aus Compiler und Interpreter vor: Der Compiler übersetzt den Quellcode in ein maschinenunabhängiges Zwischenformat ("Byte-Code"). Dieser wird von der virtuellen Maschine ("VM") gelesen und ausgeführt. Die VM kann also als Interpreter für Byte-Code betrachtet werden.

Beispiel: Java mit seiner JVM

Anwendung: C-Toolchain

Erinnern Sie sich an die LV "Systemprogrammierung" im dritten Semester :-)

Auch wenn es so aussieht, als würde der C-Compiler aus dem Quelltext direkt das ausführbare Programm erzeugen, finden hier dennoch verschiedene Stufen statt. Zuerst läuft ein Präprozessor über den Quelltext und ersetzt alle #include und #define etc., danach arbeitet der C-Compiler, dessen Ausgabe wiederum durch einen Assembler zu ausführbarem Maschinencode transformiert wird.

Beispiele: gcc, clang, ...

Anwendung: C++-Compiler

C++ hat meist keinen eigenen (vollständigen) Compiler :-)

In der Regel werden die C++-Konstrukte durch cfront nach C übersetzt, so dass man anschließend auf die etablierten Tools zurückgreifen kann.

Dieses Vorgehen werden Sie relativ häufig finden. Vielleicht sogar in Ihrem Projekt ...

Beispiel: g++

Anwendung: Bugfinder

Tools wie FindBugs analysieren den (Java-) Quellcode und suchen nach bekannten Fehlermustern. Dazu benötigen sie nur den Analyse-Teil eines Compilers!

Auf dem AST kann dann nach vorab definierten Fehlermustern gesucht werden (Stichwort "Graphmatching"). Dazu fällt die semantische Analyse entsprechend umfangreicher aus als normal.

Zusätzlich wird noch eine Reporting-Komponente benötigt, da die normalen durch die Analysekette erzeugten Fehlermeldungen nicht helfen (bzw. sofern der Quellcode wohlgeformter Code ist, würden ja keine Fehlermeldungen durch die Analyseeinheit generiert).

Beispiele: SpotBugs, Checkstyle, ESLint, ...

Anwendung: Pandoc

Pandoc ist ein universeller und modular aufgebauter Textkonverter, der mit Hilfe verschiedener Reader unterschiedliche Textformate einlesen und in ein Zwischenformat (hier JSON) transformieren kann. Über verschiedene Writer können aus dem Zwischenformat dann Dokumente in den gewünschten Zielformaten erzeugt werden.

Die Reader entsprechen der Analyse-Phase und die Writer der Synthese-Phase eines Compilers. Anstelle eines ausführbaren Programms (Maschinencode) wird ein anderes Textformat erstellt/ausgegeben.

Beispielsweise wird aus diesem Markdown-Schnipsel ...

Dies ist ein Satz mit
*  einem Stichpunkt, und
*  einem zweiten Stichpunkt.

... dieses Zwischenformat erzeugt, ...

{"blocks":[{"t":"Para","c":[{"t":"Str","c":"Dies"},{"t":"Space"},
           {"t":"Str","c":"ist"},{"t":"Space"},{"t":"Str","c":"ein"},
           {"t":"Space"},{"t":"Str","c":"Satz"},{"t":"Space"},
           {"t":"Str","c":"mit"}]},
           {"t":"BulletList","c":[[{"t":"Plain","c":[{"t":"Str","c":"einem"},{"t":"Space"},{"t":"Str","c":"Stichpunkt,"},{"t":"Space"},{"t":"Str","c":"und"}]}],[{"t":"Plain","c":[{"t":"Str","c":"einem"},{"t":"Space"},{"t":"Str","c":"zweiten"},{"t":"Space"},{"t":"Str","c":"Stichpunkt."}]}]]}],"pandoc-api-version":[1,17,0,4],"meta":{}}

... und daraus schließlich dieser TeX-Code.

Dies ist ein Satz mit
\begin{itemize}
\tightlist
\item einem Stichpunkt, und
\item einem zweiten Stichpunkt.
\end{itemize}

Im Prinzip ist Pandoc damit ein Beispiel für Compiler, die aus einem formalen Text nicht ein ausführbares Programm erzeugen (Maschinencode), sondern einen anderen formalen Text. Dieser werden häufig auch "Transpiler" genannt.

Weitere Beispiele:

• Lexer-/Parser-Generatoren: ANTLR, Flex, Bison, ...: formale Grammatik nach Sourcecode
• CoffeeScript: CoffeeScript (eine Art "JavaScript light") nach JavaScript
• Emscripten: C/C++ nach LLVM nach WebAssembly (tatsächlich kann LLVM-IR auch direkt als Input verwendet werden)
• Fitnesse: Word/Wiki nach ausführbare Unit-Tests

Was bringt mir das?

Auswahl einiger Gründe für den Besuch des Moduls "Compilerbau"

• Erstellung eigener kleiner Interpreter/Compiler
  • Einlesen von komplexen Daten
  • DSL als Brücke zwischen Stakeholdern
  • DSL zum schnelleren Programmieren (denken Sie etwa an CoffeeScript ...)
• Wie funktionieren FindBugs, Lint und ähnliche Tools?
  • Statische Codeanalyse: Dead code elimination
• Language-theoretic Security: LangSec
• Verständnis für bestimmte Sprachkonstrukte und -konzepte (etwa virtual in C++)
• Vertiefung durch Besuch "echter" Compilerbau-Veranstaltungen an Uni möglich :-)
• Wie funktioniert:
  • ein Python-Interpreter?
  • das Syntaxhighlighting in einem Editor oder in Doxygen?
  • ein Hardwarecompiler (etwa VHDL)?
  • ein Text-Formatierer (TeX, LaTeX, ...)?
  • CoffeeScript oder Emscripten?
• Wie kann man einen eigenen Compiler/Interpreter basteln, etwa für
  • MiniJava (mit C-Backend)
  • Brainfuck
  • Übersetzung von JSON nach XML
• Um eine profundes Kenntnis von Programmiersprachen zu erlangen, ist eine Beschäftigung mit ihrer Implementierung unerlässlich.
• Viele Grundtechniken der Informatik und elementare Datenstrukturen wie Keller, Listen, Abbildungen, Bäume, Graphen, Automaten etc. finden im Compilerbau Anwendung. Dadurch schließt sich in gewisser Weise der Kreis in der Informatikausbildung ...
• Aufgrund seiner Reife gibt es hervorragende Beispiele von formaler Spezifikation im Compilerbau.
• Mit dem Gebiet der formalen Sprachen berührt der Compilerbau interessante Aspekte moderner Linguistik. Damit ergibt sich letztlich eine Verbindung zur KI ...
• Die Unterscheidung von Syntax und Semantik ist eine grundlegende Technik in fast allen formalen Systeme.

Parser-Generatoren (Auswahl)

Diese Tools könnte man beispielsweise nutzen, um seine eigene Sprache zu basteln.

• ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files: github.com/antlr/antlr4
• Grammars written for ANTLR v4; expectation that the grammars are free of actions: github.com/antlr/grammars-v4
• An incremental parsing system for programmings tools: github.com/tree-sitter/tree-sitter
• Flex, the Fast Lexical Analyzer - scanner generator for lexing in C and C++: github.com/westes/flex
• Bison is a general-purpose parser generator that converts an annotated context-free grammar into a deterministic LR or generalized LR (GLR) parser employing LALR(1) parser tables: gnu.org/software/bison
• Parser combinators for binary formats, in C: github.com/UpstandingHackers/hammer
• Eclipse Xtext is a language development framework: github.com/eclipse/xtext

Statische Analyse, Type-Checking und Linter

Als Startpunkt für eigene Ideen. Oder Verbessern/Erweitern der Projekte ...

• Pluggable type-checking for Java: github.com/typetools/checker-framework
• SpotBugs is FindBugs' successor. A tool for static analysis to look for bugs in Java code: github.com/spotbugs/spotbugs
• An extensible cross-language static code analyzer: github.com/pmd/pmd
• Checkstyle is a development tool to help programmers write Java code that adheres to a coding standard: github.com/checkstyle/checkstyle
• JaCoCo - Java Code Coverage Library: github.com/jacoco/jacoco
• Sanitizers: memory error detector: github.com/google/sanitizers
• JSHint is a tool that helps to detect errors and potential problems in your JavaScript code: github.com/jshint/jshint
• Haskell source code suggestions: github.com/ndmitchell/hlint
• Syntax checking hacks for vim: github.com/vim-syntastic/syntastic

DSL (Domain Specific Language)

• NVIDIA Material Definition Language SDK: github.com/NVIDIA/MDL-SDK
• FitNesse -- The Acceptance Test Wiki: github.com/unclebob/fitnesse

Hier noch ein Framework, welches auf das Erstellen von DSL spezialisiert ist:

• Eclipse Xtext is a language development framework: github.com/eclipse/xtext

Konverter von X nach Y

• Emscripten: An LLVM-to-JavaScript Compiler: github.com/kripken/emscripten
• "Unfancy JavaScript": github.com/jashkenas/coffeescript
• Universal markup converter: github.com/jgm/pandoc
• Übersetzung von JSON nach XML

Odds and Ends

• How to write your own compiler: staff.polito.it/silvano.rivoira/HowToWriteYourOwnCompiler.htm
• Building a modern functional compiler from first principles: github.com/sdiehl/write-you-a-haskell
• Language-theoretic Security: LangSec
• Generierung von automatisierten Tests mit Esprima: heise.de/-4129726
• Eigener kleiner Compiler/Interpreter, etwa für
  • MiniJava mit C-Backend oder sogar LLVM-Backend
  • Brainfuck

Als weitere Anregung: Themen der Mini-Projekte im W17

• Java2UMLet
• JavaDoc-to-Markdown
• Validierung und Übersetzung von Google Protocol Buffers v3 nach JSON
• svg2tikz
• SwaggerLang -- Schreiben wie im Tagebuch
• Markdown zu LaTeX
• JavaDocToLaTeX
• MySQL2REDIS-Parser

Wrap-Up

• Compiler übersetzen formalen Text in ein anderes Format

• Nicht alle Stufen kommen immer vor => unterschiedliche Anwendungen

  • "Echte" Compiler: Sourcecode nach Maschinencode
  • Interpreter: Interaktive Ausführung
  • Virtuelle Maschinen als Zwischending zwischen Compiler und Interpreter
  • Transpiler: formaler Text nach formalem Text
  • Analysetools: Parsen den Sourcecode, werten die Strukturen aus

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

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

SymbTab0: Überblick Symboltabellen

Was passiert nach der Syntaxanalyse?

int x = 42;
int f(int x) {
    int y = 9;
    return y+x;
}

x = f(x);

Nach der Syntaxanalyse braucht der Compiler für die darauf folgenden Phasen semantische Analyse, Optimierung und Codegenerierung Informationen über Bezeichner, z.B.

• Welcher Bezeichner ist gemeint?
• Welchen Typ hat ein Bezeichner?

Auf dem Weg zum Interpreter/Compiler müssen die Symbole im AST korrekt zugeordnet werden. Dies geschieht über Symboltabellen. Im Folgenden werden wir verschiedene Aspekte von Symboltabellen betrachten und eine mögliche Implementierung erarbeiten, bevor wir uns um die Auswertung (Interpretation) des AST kümmern können.

Logische Compilierungsphasen

• Die lexikalische Analyse generiert eine Folge von Token.

• Die Syntaxanalyse generiert einen Parse Tree.

• Die semantische Analyse macht folgendes:

  • Der Parse Tree wird in einen abstrakten Syntaxbaum (AST) umgewandelt.
  • Dieser wird häufig mit Attributen annotiert.
  • Dabei sind oft mehrere Baumdurchläufe nötig (z.B. wegen der Abhängigkeiten der Attribute).

• Nachfolgende Stufen:

  • Der AST wird in einen Zwischencode umgewandelt mit Registern und virtuellen Adressen.
  • Der Zwischencode wird optimiert.
  • Aus dem optimierten Zwischencode wird der endgültige Code, aber immer noch mit virtuellen Adressen, generiert.
  • Der generierte Code wird nachoptimiert.
  • Der Linker ersetzt die virtuellen Adressen durch reale Adressen.

Abgrenzung der Phasen

Diese Phasen sind oft nicht klar unterscheidbar. Schon allein zur Verbesserung der Laufzeit baut der Parser oft schon den abstrakten Syntaxbaum auf, der Lexer trägt schon Bezeichner in Symboltabellen ein, der Parser berechnet beim Baumaufbau schon Attribute, ...

Oft werden gar nicht alle Phasen und alle Zwischendarstellungen benötigt.

Semantische Analyse und Symboltabellen

Syntax und Semantik

• Syntaxregeln: Formaler Aufbau eines Programms

• Semantik: Bedeutung eines (syntaktisch korrekten) Programms

=> Keine Codegenerierung für syntaktisch/semantisch inkorrekte Programme!

Zur Erinnerung: Die Syntaxregeln einer Programmiersprache bestimmen den formalen Aufbau eines zu übersetzenden Programms. Die Semantik gibt die Bedeutung eines syntaktisch richtigen Programms an.

Lexikalische und syntaktische Analyse können formalisiert mit regulären Ausdrücken und endlichen Automaten, sowie mit CFG und Parsern durchgeführt werden.

Die Durchführung der semantischen Analyse ist stark von den Eigenschaften der zu übersetzenden Sprache, sowie der Zielsprache abhängig und kann hier nur beispielhaft für einige Eigenschaften erklärt werden.

Es darf kein lauffähiges Programm erstellt werden können, dass nicht syntaktisch und semantisch korrekt ist. Ein lauffähiges Programm muss syntaktisch und semantisch korrekt sein!

Aufgaben der semantischen Analyse

• Identifikation und Sammlung der Bezeichner

• Zuordnung zur richtigen Ebene (Scopes)

• Typ-Inferenz

• Typkonsistenz (Ausdrücke, Funktionsaufrufe, ...)

• Validieren der Nutzung von Symbolen

  • Vermeidung von Mehrfachdefinition
  • Zugriff auf nicht definierte Bezeichner
  • (Lesender) Zugriff auf nicht initialisierte Bezeichner
  • Funktionen werden nicht als Variablen genutzt
  • ...

Die semantische Analyse überprüft die Gültigkeit eines syntaktisch korrekten Programms bzgl. statischer semantischer Eigenschaften und liefert die Grundlage für die (Zwischen-) Codeerzeugung und -optimierung. Insbesondere wird hier die Typkonsistenz (in Ausdrücken, von Parametern, ...) überprüft, und implizite Typumwandlungen werden vorgenommen. Oft müssen Typen automatisch bestimmt werden (z.B. bei Polymorphie, Typinferenz). Damit Typen bestimmt oder angepasst werden können, müssen Bezeichner zunächst identifiziert werden, d.h. bei namensgleichen Bezeichnern der richtige Bezug bestimmt werden.

=> Ein wichtiges Hilfsmittel dazu sind Symboltabellen

Identifizierung von Objekten

Beim Compiliervorgang müssen Namen immer wieder den dazugehörigen Definitionen zugeordnet, ihre Eigenschaften gesammelt und geprüft und darauf zugegriffen werden. Symboltabellen werden im Compiler fast überall gebraucht (siehe Abbildung unter "Einordnung").

Welche Informationen zu einem Bezeichner gespeichert und ermittelt werden, ist dann abhängig von der Klasse des Bezeichners.

Validieren der Nutzung von Symbolen

Hier sind unendlich viele Möglichkeiten denkbar. Dies reicht von den unten aufgeführten Basisprüfungen bis hin zum Prüfen der Typkompatibilität bei arithmetischen Operationen. Dabei müssen für alle Ausdrücke die Ergebnistypen berechnet werden und ggf. automatische Konvertierungen vorgenommen werden, etwa bei 3+4.1 ...

• Zugriff auf Variablen: Müssen sichtbar sein
• Zugriff auf Funktionen: Vorwärtsreferenzen sind OK
• Variablen werden nicht als Funktionen genutzt
• Funktionen werden nicht als Variablen genutzt

Da Funktionen bereits vor dem Bekanntmachen der Definition aufgerufen werden dürfen, bietet sich ein zweimaliger Durchlauf (pass) an: Beim ersten Traversieren des AST werden alle Definitionen in der Symboltabelle gesammelt. Beim zweiten Durchlauf werden dann die Referenzen aufgelöst.

Das Mittel der Wahl: Tabellen für die Symbole (= Bezeichner)

Def.: Symboltabellen sind die zentrale Datenstruktur zur Identifizierung und Verwaltung von bezeichneten Elementen.

Die Organisation der Symboltabellen ist stark anwendungsabhängig. Je nach Sprachkonzept gibt es eine oder mehrere Symboltabellen, deren Einträge vom Lexer oder Parser angelegt werden. Die jeweiligen Inhalte jedes einzelnen Eintrags kommen aus den verschiedenen Phasen der Compilierung. Symboltabellen werden oft als Hashtables oder auch als Bäume implementiert, manchmal als verkettete Listen. In seltenen Fällen kommt man auch mit einem Stack aus.

Eine Symboltabelle enthält benutzerdefinierte Bezeichner (oder Verweise in eine Hashtable mit allen vorkommenden Namen), manchmal auch die Schlüsselwörter der Programmiersprache. Die einzelnen Felder eines Eintrags variieren stark, abhängig vom Typ des Bezeichners (= Bezeichnerklasse).

Manchmal gibt es für Datentypen eine Extra-Tabelle, ebenso eine für die Werte von Konstanten.

Manchmal werden die Namen selbst in eine (Hash-) Tabelle geschrieben. Die Symboltabelle enthält dann statt der Namen Verweise in diese (Hash-) Tabelle.

Einfache Verwaltung von Variablen primitiven Typs

int x = 0;
int i = 0;

for (i=0; i<10; i++) {
    x++;
}

Bsp.: Die zu übersetzende Sprache hat nur einen (den globalen) Scope und kennt nur Bezeichner für Variablen.

• Eine Symboltabelle für alle Bezeichner
• Jeder Bezeichner ist der Name einer Variablen
• Symboltabelle wird evtl. mit Einträgen aller Schlüsselwörter initialisiert -- warum?
• Scanner erkennt Bezeichner und sucht ihn in der Symboltabelle
• Ist der Bezeichner nicht vorhanden, wird ein (bis auf den Namen leerer) Eintrag angelegt
• Scanner übergibt dem Parser das erkannte Token und einen Verweis auf den Symboltabelleneintrag

Die Symboltabelle könnte hier eine (Hash-) Tabelle oder eine einfache verkettete Liste sein.

Was kann jetzt weiter passieren?

int x = 0;
int i = 0;

for (i=0; i<10; i++) {
    x++;
}

a = 42;

In vielen Sprachen muss überprüft werden, ob es ein definierendes Vorkommen des Bezeichners oder ein angewandtes Vorkommen ist.

Definitionen und Deklarationen von Bezeichnern

Def.: Die Definition eines (bisher nicht existenten) Bezeichners in einem Programm generiert einen neuen Bezeichner und legt für ihn seinem Typ entsprechend Speicherplatz an.

Def.: Unter der Deklaration eines (bereits existierenden) Bezeichners verstehen wir seine Bekanntmachung, damit er benutzt werden kann. Er ist oft in einem anderen Scope definiert und bekommt dort Speicherplatz zugeteilt.

Insbesondere werden auch Typen deklariert. Hier gibt es in der Regel gar keine Speicherplatzzuweisung.

Ein Bezeichner kann beliebig oft deklariert werden, während er in einem Programm nur einmal definiert werden kann. Oft wird bei der Deklarationen eines Elements sein Namensraum mit angegeben.

Vorsicht: Die Begriffe werden auch anders verwendet. Z.B. findet sich in der Java-Literatur der Begriff Deklaration anstelle von Definition.

Anmerkung: Deklarationen beziehen sich auf Definitionen, die woanders in einer Symboltabelle stehen, evtl. in einer anderen Datei, also in diesem Compilerlauf nicht zugänglich sind und erst von Linker aufgelöst werden können. Beim Auftreten einer Deklaration muss die dazugehörige Definition gesucht werden,und wenn vorhanden, im Symboltabelleneintrag für den deklarierten Bezeichner festgehalten werden. Hier ist evtl. ein zweiter Baumdurchlauf nötig, um alle offenen Deklarationen, die sich auf Definitionen in derselben Datei beziehen, aufzulösen.

Wird bei objektorientierten Sprachen ein Objekt definiert, dessen Klassendefinition in einer anderen Datei liegt, kann man die Definition des Objekts gleichzeitig als Deklaration der Klasse auffassen (Java).

Wo werden Verweise in Symboltabellen gebraucht?

=> Parse Tree und AST enthalten Verweise auf Symboltabelleneinträge

• Im Parse Tree enthält der Knoten für einen Bezeichner einen Verweis auf den Symboltabelleneintrag.
• Parser und semantische Analyse (AST) vervollständigen die Einträge.
• Attribute des AST können Feldern der Symboltabelle entsprechen, bzw. sich aus ihnen berechnen.
• Für Debugging-Zwecke können die Symboltabellen die ganze Compilierung und das Linken überleben.

Grenzen der semantischen Analyse

Welche semantischen Eigenschaften einer Sprache kann die semantische Analyse nicht überprüfen?

• Wer ist dann dafür verantwortlich?
• Wie äußert sich das im Fehlerfall?

Dinge, die erst durch eine Ausführung/Interpretation eines Programms berechnet werden können.

Beispielsweise können Werte von Ausdrücken oft erst zur Laufzeit bestimmt werden. Insbesondere kann die semantische Analyse in der Regel nicht feststellen, ob ein Null-Pointer übergeben wird und anschließend dereferenziert wird.

Wrap-Up

• Semantische Analyse:

  • Identifikation und Sammlung der Bezeichner
  • Zuordnung zur richtigen Ebene (Scopes)
  • Validieren der Nutzung von Symbolen
  • Typ-Inferenz
  • Typkonsistenz (Ausdrücke, Funktionsaufrufe, ...)

• Symboltabellen: Verwaltung von Symbolen und Typen (Informationen über Bezeichner)

• Symboltabelleneinträge werden an verschiedenen Stellen des Compilers generiert und benutzt

SymbTab1: Nested Scopes

Scopes und Name Spaces

Def.: Unter dem Gültigkeitsbereich (Sichtbarkeitsbereich, Scope) eines Bezeichners versteht man den Programmabschnitt, in dem der Bezeichner sichtbar und nutzbar ist. Das ist oft der kleinste umgebende Block, außer darin enthaltene Scopes, die ein eigenes Element dieses Namens benutzen.

Scopes sind fast immer hierarchisch angeordnet.

Def.: Unter einem Namensraum (name space) versteht man die Menge der zu einem Zeitpunkt sichtbaren Bezeichner.

Es gibt Sprachen, in denen man eigene Namensräume explizit definieren kann (z.B. C++).

Vorsicht: Diese Begriffe werden nicht immer gleich definiert und auch gerne verwechselt.

Symbole und (nested) Scopes

int x = 42;
float y;
{
    int x;
    x = 1;
    y = 2;
    { int y = x; }
}

Aufgaben:

• bind(): Symbole im Scope definieren
• resolve(): Symbole aus Scope oder Eltern-Scope abrufen

Hinzunahme von Scopes

Bsp.: Die zu übersetzende Sprache ist scope-basiert und kennt nur Bezeichner für Variablen

Scopes können ineinander verschachtelt sein. Die Spezifikation der zu übersetzenden Sprache legt fest, in welcher Reihenfolge Scopes zu durchsuchen sind, wenn auf einen Bezeichner Bezug genommen wird, der nicht im aktuellen Scope definiert ist.

Insgesamt bilden die Scopes oft eine Baumstruktur, wobei jeder Knoten einen Scope repräsentiert und seine Kinder die direkt in ihm enthaltenen Scopes sind. Dabei ist es in der Regel so, dass Scopes sich entweder vollständig überlappen oder gar nicht. Wenn ein Bezeichner nicht im aktuellen Scope vorhanden ist, muss er in der Regel in umschließenden Scopes gesucht werden. Hier kann ein Stack aller "offenen" Scopes benutzt werden.

Grundlegendes Vorgehen

Das Element, das einen neuen Scope definiert, steht selbst in dem aktuell behandelten Scope. Wenn dieses Element selbst ein Bezeichner ist, gehört dieser in den aktuellen Scope. Nur das, was nur innerhalb des oben genannten Elements oder Bezeichners definiert wird, gehört in den Scope des Elements oder Bezeichners.

Nested Scopes: Symbole und Scopes

Implementierung mit hierarchischen (verketteten) Tabellen

Pro Scope wird eine Symboltabelle angelegt, dabei enthält jede Symboltabelle zusätzlich einen Verweis auf ihre Vorgängersymboltabelle für den umgebenden Scope. Die globale Symboltabelle wird typischerweise mit allen Schlüsselwörtern initialisiert.

• Wenn ein neuer Scope betreten wird, wird eine neue Symboltabelle erzeugt.
• Scanner: Erkennt Bezeichner und sucht ihn in der Symboltabelle des aktuellen Scopes bzw. trägt ihn dort ein und übergibt dem Parser das erkannte Token und einen Verweis auf den Symboltabelleneintrag (Erinnerung: Der Scanner wird i.d.R. vom Parser aus aufgerufen, d.h. der Parser setzt den aktuellen Scope!)
• Parser:
  • Wird ein neues Element (ein Bezeichner) definiert, muss bestimmt werden, ob es einen eigenen Scope hat. Wenn ja, wird eine neue Symboltabelle für den Scope angelegt. Sie enthält alle Definitionen von Elementen, die in diesem Scope liegen. Der Bezeichner selbst wird in die aktuelle Symboltabelle eingetragen mit einem Verweis auf die neue Tabelle, die all die Bezeichner beinhaltet, die außerhalb dieses Scopes nicht sichtbar sein sollen. Die Tabellen werden untereinander verzeigert.
  • Wird ein Element deklariert oder benutzt, muss sein Eintrag in allen sichtbaren Scopes in der richtigen Reihenfolge entlang der Verzeigerung gesucht (und je nach Sprachdefinition auch gefunden) werden.
• Der Parse-Tree enthält im Knoten für den Bezeichner den Verweis in die Symboltabelle

Klassenhierarchie für Scopes

Für die Scopes wird eine Klasse Scope definiert mit den Methoden bind() (zum Definieren von Symbolen im Scope) und resolve() (zum Abrufen von Symbolen aus dem Scope oder dem umgebenden Scope).

Für lokale Scopes wird eine Instanz dieser Klasse angelegt, die eine Referenz auf den einschließenden Scope im Attribut enclosingScope hält. Für den globalen Scope ist diese Referenz einfach leer (None).

Klassen und Interfaces für Symbole

Für die Symbole gibt es die Klasse Symbol, wo für jedes Symbol Name und Typ gespeichert wird. Variablensymbole leiten direkt von dieser Klasse ab. Für die eingebauten Typen wird ein "Marker-Interface" Type erstellt, um Variablen- und Typ-Symbole unterscheiden zu können.

Quelle: Eigene Modellierung nach einer Idee in [Parr2010, p. 142]

Alternative Implementierung über einen Stack

• Der Parse Tree bzw. der AST enthalten an den Knoten, die jeweils einen ganzen Scope repräsentieren, einen Verweis auf die Symboltabelle dieses Scopes.
• Die Scopes werden in einem Stack verwaltet.
• Wird ein Scope betreten beim Baumdurchlauf, wird ein Verweis auf seine Symboltabelle auf den Stack gepackt.
• Die Suche von Bezeichnern in umliegenden Scopes erfordert ein Durchsuchen des Stacks von oben nach unten.
• Beim Verlassen eines Scopes beim Baumdurchlauf wird der Scope vom Stack entfernt.

Nested Scopes: Definieren und Auflösen von Namen

class Scope:
    Scope enclosingScope    # None if global (outermost) scope
    Symbol<String, Symbol> symbols

    def resolve(name):
        # do we know "name" here?
        if symbols[name]: return symbols[name]
        # if not here, check any enclosing scope
        if enclosingScope: return enclosingScope.resolve(name)
        else: return None     # not found

    def bind(symbol):
        symbols[symbol.name] = symbol
        symbol.scope = self     # track the scope in each symbol

Quelle: Eigene Implementierung nach einer Idee in [Parr2010, p. 169]

Anmerkung: In der Klasse Symbol kann man ein Feld scope vom Typ Scope implementieren. Damit "weiss" jedes Symbol, in welchem Scope es definiert ist und man muss sich auf der Suche nach dem Scope eines Symbols ggf. nicht erst durch die Baumstruktur hangeln. Aus technischer Sicht verhindert das Attribut das Aufräumen eines lokalen Scopes durch den Garbage Collector, wenn man den lokalen Scope wieder verlässt: Jeder Scope hat eine Referenz auf den umgebenden (Eltern-) Scope (Feld enclosingScope). Wenn man den aktuellen Scope "nach oben" verlässt, würde der eben verlassene lokale Scope bei nächster Gelegenheit aufgeräumt, wenn es keine weiteren Referenzen auf diesen gäbe. Da nun aber die Symbole, die in diesem Scope definiert wurden, auf diesen verweisen, passiert das nicht :)

Nested Scopes: Listener

Mit einem passenden Listener kann man damit die nötigen Scopes aufbauen:

• enterStart:
  • erzeuge neuen globalen Scope
  • definiere und pushe die eingebauten Typen
• exitVarDecl:
  • löse den Typ der Variablen im aktuellen Scope auf
  • definiere ein neues Variablensymbol im aktuellen Scope
• exitVar:
  • löse die Variable im aktuellen Scope auf
• enterBlock:
  • erzeuge neuen lokalen Scope, wobei der aktuelle Scope der Elternscope ist
  • ersetze den aktuellen Scope durch den lokalen Scope
• exitBlock:
  • ersetze den aktuellen Scope durch dessen Elternscope

start   :   stat+ ;

stat    : block | varDecl | expr ';' ;
block   : '{' stat* '}' ;

varDecl : type ID ('=' expr)? ';' ;
expr    : var '=' INT ;

var     : ID ;
type    : 'float' | 'int' ;

int x = 42;

{ int y = 9; x = 7; }

class MyListener(BaseListener):
    Scope scope

    def enterStart(Parser.FileContext ctx):
        globals = Scope()
        globals.bind(BuiltIn("int"))
        globals.bind(BuiltIn("float"))
        scope = globals

    def enterBlock(Parser.BlockContext ctx):
        scope = Scope(scope)
    def exitBlock(Parser.BlockContext ctx):
        scope = scope.enclosingScope

    def exitVarDecl(Parser.VarDeclContext ctx):
        t = scope.resolve(ctx.type().getText())
        var = Variable(ctx.ID().getText(), t)
        scope.bind(var)
    def exitVar(Parser.VarContext ctx):
        name = ctx.ID().getText()
        var = scope.resolve(name)
        if var == None: error("no such var: " + name)

In der Methode exitVar() wird das Variablensymbol beim Ablaufen des AST lediglich aufgelöst und ein Fehler geworfen, wenn das Variablensymbol (noch) nicht bekannt ist. Hier könnte man weiteres Type-Checking und/oder -Propagation ansetzen.

Später im Interpreter muss an dieser Stelle dann aber auch der Wert der Variablen abgerufen werden ...

Löschen von Symboltabellen

Möglicherweise sind die Symboltabellen nach der Identifizierungsphase der Elemente überflüssig, weil die zusammengetragenen Informationen als Attribute im AST stehen. Die Knoten enthalten dann Verweise auf definierende Knoten von Elementen, nicht mehr auf Einträge in den Symboltabellen. In diesem Fall können die Symboltabellen nach der Identifizierung gelöscht werden, wenn sie nicht z.B. für einen symbolischen Debugger noch gebraucht werden.

Wrap-Up

• Symboltabellen: Verwaltung von Symbolen und Typen (Informationen über Bezeichner)

• Blöcke: Nested Scopes => hierarchische Organisation

• Binden von Bezeichner gleichen Namens an ihren jeweiligen Scope => bind()

• Abrufen von Bezeichnern aus dem aktuellen Scope oder den Elternscopes => resolve()

SymbTab2: Funktionen

Funktionen und Scopes

int x = 42;
int y;
void f() {
    int x;
    x = 1;
    y = 2;
    { int y = x; }
}
void g(int z){}

Behandlung von Funktionsdefinitionen

• Jeder Symboltabelleneintrag braucht ein Feld, das angibt, ob es sich um eine Variable, eine Funktion, ... handelt. Alternativ eine eigene Klasse ableiten ...
• Der Name der Funktion steht als Bezeichner in der Symboltabelle des Scopes, in dem die Funktion definiert wird.
• Der Symboltabelleneintrag für den Funktionsnamen enthält Verweise auf die Parameter.
• Der Symboltabelleneintrag für den Funktionsnamen enthält Angaben über den Rückgabetypen.
• Jede Funktion wird grundsätzlich wie ein neuer Scope behandelt.
• Die formalen Parameter werden als Einträge in der Symboltabelle für den Scope der Funktion angelegt and entsprechend als Parameter gekennzeichnet.

Behandlung von Funktionsaufrufen

• Der Name der Funktion steht als Bezeichner in der Symboltabelle des Scopes, in dem die Funktion aufgerufen wird und wird als Aufruf gekennzeichnet.
• Der Symboltabelleneintrag für den Funktionsnamen enthält Verweise auf die aktuellen Parameter.
• Die Definition der Funktion wird in den zugänglichen Scopes gesucht (wie oben) und ein Verweis darauf in der Symboltabelle gespeichert.

Erweiterung des Klassendiagramms für Funktions-Scopes

Quelle: Eigene Modellierung nach einer Idee in [Parr2010, p. 147]

Funktionen sind Symbole und Scopes

class Function(Scope, Symbol):
    def __init__(name, retType, enclScope):
        Symbol.__init__(name, retType)      # we are "Symbol" ...
        enclosingScope = enclScope          # ... and "Scope"

Funktionen: Listener

Den Listener zum Aufbau der Scopes könnte man entsprechend erweitern:

• enterFuncDecl:
  • löse den Typ der Funktion im aktuellen Scope auf
  • lege neues Funktionssymbol an, wobei der aktuelle Scope der Elternscope ist
  • definiere das Funktionssymbol im aktuellen Scope
  • ersetze den aktuellen Scope durch das Funktionssymbol
• exitFuncDecl:
  • ersetze den aktuellen Scope durch dessen Elternscope
• exitParam: analog zu exitVarDecl
  • löse den Typ der Variablen im aktuellen Scope auf
  • definiere ein neues Variablensymbol im aktuellen Scope
• exitCall: analog zu exitVar
  • löse das Funktionssymbol (und die Argumente) im aktuellen Scope auf

funcDecl : type ID '(' params? ')' block ;
params   : param (',' param)* ;
param    : type ID ;

call     : ID '(' exprList? ')' ;
exprList : expr (',' expr)* ;

int f(int x) {
    int y = 9;
}

int x = f(x);

def enterFuncDecl(Parser.FuncDeclContext ctx):
    name = ctx.ID().getText()
    type = scope.resolve(ctx.type().getText())
    func = Function(name, type, scope)
    scope.bind(func)
    # change current scope to function scope
    scope = func

def exitFuncDecl(Parser.FuncDeclContext ctx):
    scope = scope.enclosingScope
def exitParam(Parser.ParamContext ctx):
    t = scope.resolve(ctx.type().getText())
    var = Variable(ctx.ID().getText(), t)
    scope.bind(var)

def exitCall(Parser.CallContext ctx):
    name = ctx.ID().getText()
    func = scope.resolve(name)
    if func == None:
        error("no such function: " + name)
    if func.type == Variable:
        error(name + " is not a function")

Im Vergleich zu den einfachen nested scopes kommt hier nur ein weiterer Scope für den Funktionskopf dazu. Dieser spielt eine Doppelrolle: Er ist sowohl ein Symbol (welches im Elternscope bekannt ist) als auch ein eigener (lokaler) Scope für die Funktionsparameter.

Um später im Interpreter eine Funktion tatsächlich auswerten zu können, muss im Scope der Funktion zusätzlich der AST-Knoten der Funktionsdefinition gespeichert werden (weiteres Feld/Attribut in Function)!

Wrap-Up

• Symboltabellen: Verwaltung von Symbolen und Typen (Informationen über Bezeichner)

• Funktionen: Nested Scopes => hierarchische Organisation

• Umgang mit dem Funktionsnamen, den Parametern und dem Funktionskörper

SymbTab3: Strukturen und Klassen

Strukturen

struct A {
    int x;
    struct B {int x;};
    B b;
    struct C {int z;};
};
A a;
void f() {
    A a;
    a.b.x = 42;
}

Strukturen: Erweiterung der Symbole und Scopes

Quelle: Eigene Modellierung nach einer Idee in [Parr2010, p. 162]

Strukturen stellen wie Funktionen sowohl einen Scope als auch ein Symbol dar.

Zusätzlich stellt eine Struktur (-definition) aber auch einen neuen Typ dar, weshalb Struct auch noch das Interface Type "implementiert".

Strukturen: Auflösen von Namen

class Struct(Scope, Symbol, Type):
    def resolveMember(name):
        return symbols[name]

=> Auflösen von "a.b" (im Listener in exitMember()):

• a im "normalen" Modus mit resolve() über den aktuellen Scope
• Typ von a ist Struct mit Verweis auf den eigenen Scope
• b nur innerhalb des Struct-Scopes mit resolveMember()

In der Grammatik würde es eine Regel member geben, die auf eine Struktur der Art ID.ID anspricht (d.h. eigentlich den Teil .ID), und entsprechend zu Methoden enterMember() und exitMember() im Listener führt.

Das Symbol für a hat als type-Attribut eine Referenz auf die Struct, die ja einen eigenen Scope hat (symbols-Map). Darin muss dann b aufgelöst werden.

Klassen

class A {
public:
    int x;
    void foo() { ; }
};
class B : public A {
public
    int y;
    void foo() {
        int z = x+y;
    }
};

Klassen: Erweiterung der Symbole und Scopes

Quelle: Eigene Modellierung nach einer Idee in [Parr2010, p. 167]

Bei Klassen kommt in den Tabellen ein weiterer Pointer parentClazz auf die Elternklasse hinzu (in der Superklasse ist der Wert None).

Klassen: Auflösen von Namen

class Clazz(Struct):
    Clazz parentClazz   # None if base class

    def resolve(name):
        # do we know "name" here?
        if symbols[name]: return symbols[name]
        # NEW: if not here, check any parent class ...
        if parentClazz and parentClazz.resolve(name): return parentClazz.resolve(name)
        else:
            # ... or enclosing scope if base class
            if enclosingScope: return enclosingScope.resolve(name)
            else: return None     # not found

    def resolveMember(name):
        if symbols[name]: return symbols[name]
        # NEW: check parent class
        if parentClazz: return parentClazz.resolveMember(name)
        else: return None

Quelle: Eigene Implementierung nach einer Idee in [Parr2010, p. 172]

Hinweis: Die obige Implementierungsskizze soll vor allem das Prinzip demonstrieren - sie ist aus Gründen der Lesbarkeit nicht besonders effizient: beispielsweise wird parentClazz.resolve(name) mehrfach evaluiert ...

Beim Auflösen von Attributen oder Methoden muss zunächst in der Klasse selbst gesucht werden, anschließend in der Elternklasse.

Beispiel (mit den obigen Klassen A und B):

B foo;
foo.x = 42;

Hier wird analog zu den Structs zuerst foo mit resolve() im lokalen Scope aufgelöst. Der Typ des Symbols foo ist ein Clazz, was zugleich ein Scope ist. In diesem Scope wird nun mit resolveMember() nach dem Symbol x gesucht. Falls es hier nicht gefunden werden kann, wird in der Elternklasse (sofern vorhanden) weiter mitresolveMember() gesucht.

Die normale Namensauflösung wird ebenfalls erweitert um die Auflösung in der Elternklasse.

Beispiel:

int wuppie;
class A {
public:
    int x;
    void foo() { ; }
};
class B : public A {
public
    int y;
    void foo() {
        int z = x+y+wuppie;
    }
};

Hier würde wuppie als Symbol im globalen Scope definiert werden. Beim Verarbeiten von int z = x+y+wuppie; würde mit resolve() nach wuppie gesucht: Zuerst im lokalen Scope unterhalb der Funktion, dann im Funktions-Scope, dann im Klassen-Scope von B. Hier sucht resolve() auch zunächst lokal, geht dann aber die Vererbungshierarchie entlang (sofern wie hier vorhanden). Erst in der Superklasse (wenn der parentClazz-Zeiger None ist), löst resolve() wieder normal auf und sucht um umgebenden Scope. Auf diese Weise kann man wie gezeigt in Klassen (Methoden) auf globale Variablen verweisen ...

Anmerkung: Durch dieses Vorgehen wird im Prinzip in Methoden aus dem Zugriff auf ein Feld x implizit ein this.x aufgelöst, wobei this die Klasse auflöst und x als Attribut darin.

Wrap-Up

• Symboltabellen: Verwaltung von Symbolen und Typen (Informationen über Bezeichner)

• Strukturen und Klassen bilden eigenen Scope

• Strukturen/Klassen lösen etwas anders auf: Zugriff auf Attribute und Methoden

package a.b;

import u.Y;

class X extends Y {
    int f(int x) {
        int x,y;
        { int x; x - y + 1; }
        x = y + 1;
    }
}

class Z {
    class W extends X {
        int x;
        void foo() { f(34); }
    }
    int x,z;
    int f(int x) {
        int y;
        y = x;
        z = x;
    }
}

Überblick Zwischencode

Einordnung

Die Schritte in der letzten Phase der Compiler-Pipeline können sehr unterschiedlich ausfallen.

Beispielsweise könnte direkt aus dem AST der Ziel-Machine-Code erzeugt werden. Auf der anderen Seite könnte aus dem AST ein Zwischenformat erzeugt werden, darauf Optimierungen vorgenommen werden, daraus ein weiteres Zwischenformat erzeugt werden, darauf weitere Optimierungen vorgenommen werden, ..., bis schließlich nach mehreren Zwischenstufen das Zielformat erzeugt wird.

Nachfolgend betrachten wir verschiedene Beispiele, wie das Zwischenformat aussehen kann.

AST als Zwischencode (Beispiel Pandoc)

Häufig wird der AST selbst als Zwischencode verwendet. Ein Beispiel dafür ist Pandoc.

Dies ist ein Absatz mit
*  einem Stichpunkt, und
*  einem zweiten Stichpunkt.

{"blocks":[{"t":"Para","c":[{"t":"Str","c":"Dies"},
                            {"t":"Space"},
                            {"t":"Str","c":"ist"},
                            {"t":"Space"},
                            {"t":"Str","c":"ein"},
                            {"t":"Space"},
                            {"t":"Str","c":"Absatz"},
                            {"t":"Space"},
                            {"t":"Str","c":"mit"}]},
           {"t":"BulletList","c":[
               [{"t":"Plain","c":[{"t":"Str","c":"einem"},
                                  {"t":"Space"},
                                  {"t":"Str","c":"Stichpunkt,"},
                                  {"t":"Space"},
                                  {"t":"Str","c":"und"}]}],
               [{"t":"Plain","c":[{"t":"Str","c":"einem"},
                                  {"t":"Space"},
                                  {"t":"Str","c":"zweiten"},
                                  {"t":"Space"},
                                  {"t":"Str","c":"Stichpunkt."}]}]]}],
"pandoc-api-version":[1,17,0,4],"meta":{}}

Der Pandoc-AST spiegelt direkt die Dokumentstruktur wider. Im obigen Beispiel haben wir einen Absatz mit dem Text "Dies ist ein Absatz mit", der als Para repräsentiert wird mit einer Liste von Strings (Str) und Leerzeichen (Space).

Die Stichpunktliste besteht pro Stichpunkt aus einem Plain-Knoten mit dem eigentlichen Inhalt (wieder Strings und Leerzeichen).

Dieser AST ist der Dreh- und Angelpunkt in Pandoc. Verschiedene Reader können unterschiedliche Textformate parsen und in einen AST überführen.

Auf diesem kann man mit Filtern Transformationen vornehmen.

Anschließend können diverse Writer den AST in das gewünschte Zielformat überführen.

Zwischenformat: Drei-Adressen-Code

Eine weitere häufig eingesetzte Zwischenform kurz vor der Code-Generierung ist der sogenannte "Drei-Adressen-Code". Dieser besteht jeweils aus einer Operation auf bis zu drei Adressen.

Im Prinzip handelt es sich hier um eine Art "High-Level Assembler" mit beliebig vielen Registern ...

Adressen sind dabei Namen, Konstanten oder vom Compiler generierte temporäre Werte. Die typische Form ist x = y op z (binäre Operationen) oder x = op z (unäre Operationen). Werte werden mit x = y kopiert. Jeder Teilausdruck erhält typischerweise eine eigene temporäre Variable zur Speicherung des Ergebnisses. Weiterhin gibt es bedingte und unbedingte Sprünge und Prozedur-Aufrufe.

Index-Zugriffe werden über Pointerarithmetik aufgelöst (s.u.).

Eine Spezialform ist die sogenannte "Static Single-Assignment"-Form (SSA). Hierbei wird für jede Zuweisung eine neue temporäre Variable generiert, d.h. jede im IR-Code verwendete Adresse (temporäre Variable) hat genau eine Zuweisung. Dies wirkt sich günstig auf spezielle Optimierungen aus.

i = i+1;
if (a[i] >= v) {
    i = 0;
}

    t1 = i + 1
    i  = t1
    t2 = i * 8
    t3 = a + t2
    if t3 >= v goto L1
    goto L2
L1: i  = 0
L2: ...

Im obigen Beispiel wurde davon ausgegangen, dass die Einträge im Array a 8 Bit breit sind. Das muss der Compiler wissen, um jeweils den korrekten Offset zu benutzen.

Außerdem könnte man den Code gleich noch optimieren und die Anzahl der Sprünge reduzieren:

    t1 = i + 1
    i  = t1
    t2 = i * 8
    t3 = a + t2
    if t3 < v goto L
    i  = 0
L:  ...

LLVM IR

Low Level Virtual Machine

int main() {
    int x = 7;
    int y = x + 35;

    return 0;
}

define i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  store i32 7, i32* %2, align 4
  %4 = load i32, i32* %2, align 4
  %5 = add nsw i32 %4, 35
  store i32 %5, i32* %3, align 4
  ret i32 0
}

Der obige Output ist auf die relevanten Zeilen gekürzt; der gesamte Output im LLVM-Format sieht wie folgt aus:

; ModuleID = 'hello.c'
source_filename = "hello.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: noinline nounwind optnone uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  store i32 7, i32* %2, align 4
  %4 = load i32, i32* %2, align 4
  %5 = add nsw i32 %4, 35
  store i32 %5, i32* %3, align 4
  ret i32 0
}

attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final)"}

Es werden drei "virtuelle Register" (Variablen) %1, %2 und %3 auf dem Stack angelegt (32-bit Integer; align 4: alle Adressen sind Vielfache von 4).

Mit store i32 0, ... wird in %1 der Wert 0 geschrieben (vergleichbar mit *p = 0). In %2 wird analog der Wert 7 geschrieben (x=7).

Dann wird der Wert aus %2 in eine neue Variable %4 geladen und das Ergebnis der Addition aus %4 und dem Wert 35 in eine weitere neue Variable %5 geschrieben. Der Wert dieser Variablen wird dann auf dem Stack in %3 gespeichert (y = x+35).

Vgl. auch LLVM Language Reference Manual und blog.regehr.org/archives/1453.

Bytecode (Beispiel Python)

x = 7
y = x + 35

  1  0 LOAD_CONST    0 (7)
     3 STORE_NAME    0 (x)

  2  6 LOAD_NAME     0 (x)
     9 LOAD_CONST    1 (35)
    12 BINARY_ADD
    13 STORE_NAME    1 (y)
    16 LOAD_CONST    2 (None)
    19 RETURN_VALUE

Python pflegt 3 Listen: co_names für die Namen plus co_values für die dazugehörigen Werte sowie co_consts für Konstanten. Die Listen der Namen und Werte sind gleich lang, ein Index bezieht sich jeweils auf das selbe Symbol. Werte werden über einen Stack verarbeitet. Die Opcodes stehen in einer weiteren Liste co_code. (Die Opcodes sind oben der besseren Lesbarkeit halber als Text ausgegeben, LOAD_CONST hat beispielsweise den Wert 100.)

Nach dem Laden des Programms ist x in co_names[0], y in co_names[1]. Der Wert 7 steht in co_const[0], die 35 in co_const[1].

Das LOAD_CONST 0 (co_code[0]) lädt den Inhalt von co_consts[0] auf den Stack (push()), d.h. der Wert 7 wird auf den Stack gepusht. Mit STORE_NAME 0 (co_code[3]) wird der Inhalt des obersten Stackeintrags in co_values[0] geschrieben und der Eintrag vom Stack entfernt (pop()). Dies entspricht Zeile 1 im Quellcode: x = 7.

LOAD_NAME 0 pusht co_values[0] auf den Stack (Wert von x), gefolgt von der 35 per LOAD_CONST 1 (co_const[1]). Das BINARY_ADD entfernt die beiden obersten Einträge, addiert die Werte und pusht das Ergebnis wieder auf den Stack. Mit STORE_NAME 1 wird der Wert in co_values[1] geschrieben, d.h. y bekommt den Wert zugewiesen.

Bytecode (Beispiel Java)

public class Hello {

    void wuppie() {
        int x = 7;
        int y = x + 35;
   }

}

Compiled from "Hello.java"
public class Hello {
  public Hello();
    Code:
       0: aload_0
       1: invokespecial #1 // Method java/lang/Object."<init>":()V
       4: return

  void wuppie();
    Code:
       0: bipush        7
       2: istore_1
       3: iload_1
       4: bipush        35
       6: iadd
       7: istore_2
       8: return
}

Für jeden Methodenaufruf wird ein entsprechender Frame auf den Stack gepusht. Dieser enthält ein Array mit den lokalen Variablen, durchnummeriert von 0 bis n-1. (long und double bekommen je 2 lokale Variablen) Zusätzlich gibt es im Frame einen Operandenstack, auf dem Funktionsparameter und -rückgabewerte übergeben werden und auf dem die Operanden für die auszuführenden Operationen sowie deren Zwischenergebnisse hinterlegt werden.

• bipush 7: Pushe den Integer-Wert 7 auf den Stack
• istore_1: Poppe den ersten Wert vom Stack und speichere ihn in der lokalen Integer-Variable mit Index 1 (x=7)
• iload_1: Pushe lokale Integer-Variable mit Index 1 auf den Stack (x)
• bipush 35: Pushe den Integer-Wert 35 auf den Stack
• iadd: Führe Integer-Addition aus mit den beiden obersten Werten auf Stack und ersetze diese mit dem Ergebnis
• istore_2: Poppe den ersten Wert vom Stack und speichere ihn in der lokalen Integer-Variable mit Index 2 (y=x+35)

Die Konstanten n für iconst_ funktionieren nur für kleinere Integer. Größere Werte muss man mit bipush auf den Stack pushen.

Vgl. auch dzone.com/articles/introduction-to-java-bytecode und www.beyondjava.net/java-programmers-guide-java-byte-code.

Assembler

int main() {
    int x = 7;
    int y = x + 35;

    return 0;
}

    .file   "hello.c"
    .text
    .globl  main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    $7, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    $35, %eax
    movl    %eax, -4(%rbp)
    movl    $0, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size       main, .-main
    .ident      "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
    .section    .note.GNU-stack,"",@progbits

Die Ausgabe unterscheidet sich je nach Architektur, auf dem der C-Code in Assembler-Code compiliert wird!

Mit .text beginnt das Textsegment. main: ist eine Sprungmarke, die hier auch als Startpunkt für das Programm dient.

Auf X86-64 stehen %rbp und %rsp für 8-Byte-Register. Mit %eax greift man auf die Bytes 0 bis 3 des 8-Byte-Registers %rax zu.

Da in %rbp Werte übergeben werden (können), wird das Register mit pushq %rbp auf den Stack gesichert und am Ende mit popq %rbp wiederhergestellt.

Ansonsten kann man die Bedeutung erraten: movl $7, -8(%rbp) entspricht mem[rbp-8] = 7, movl -8(%rbp), %eax entspricht eax = mem[rbp-8], addl $35, %eax entspricht eax = eax + 35, movl %eax, -4(%rbp) entspricht mem[rbp-4] = eax.

Vgl. auch cs.brown.edu/courses/cs033/docs/guides/x64_cheatsheet.pdf und en.wikibooks.org/wiki/X86_Assembly/GAS_Syntax.

Wrap-Up

• Compiler generieren aus AST Zwischencode ("IC" oder "IR")
• Kein allgemein definiertes Format, große Bandbreite:
  • AST als IR
  • LLVM IR
  • Drei-Adressen-Code
  • Diverse Arten von Bytecode
  • Assemblercode

LLVM als IR

Motivation

Es ist ein neuer Prozessor entwickelt worden mit einem neuen Befehlssatz, und es sollen für zwei Programmiersprachen Compiler entwickelt werden, die diesen Befehlssatz als Ziel haben.

Was tun?

Thema für heute: Ein Zwischencodeformat für verschiedene Programmiersprachen und Prozessoren

Hier entsteht ein Tafelbild.

LLVM - Ein Überblick

Was ist LLVM?

• ursprünglich: Low Level Virtual Machine
• Open-Source-Framework
• zur modularen Entwicklung von Compilern u. ä.
• für Frontends für beliebige Programmiersprachen
• für Backends für beliebige Befehlssatzarchitekturen

"Macht aus dem Zwischencode LLVR IR automatisch Maschinencode oder eine VM."

Kernstücke des LLVM:

• ein virtueller Befehlssatz
• ein virtuelle Maschine
• LLVM IR: eine streng typisierte Zwischensprache
• ein flexibel konfigurierbarer Optimierer
• ein Codegenerator für zahlreiche Architekturen
• LMIR: mit Dialekten des IR arbeiten

Was kann man damit entwickeln?

• Debugger
• JIT-Systeme (virtuelle Maschine)
• AOT-Compiler
• virtuelle Maschinen
• Optimierer
• Systeme zur statischen Analyse
• etc.

mit entkoppelten Komponenten, die über APIs kommunizieren (Modularität)

Wie arbeitet man damit?

• (mit Generatoren) ein Frontend entwickeln, das Programme über einen AST in LLVM IR übersetzt
• mit LLVM den Zwischencode optimieren
• mit LLVM Maschinencode oder VM-Code generieren

Was bringt uns das?

n Sprachen für m Architekturen übersetzen:

• n Frontends entwickeln
• Optimierungen spezifizieren
• m Codegeneratoren spezifizieren

statt n x m Compiler zu schreiben.

Wer setzt LLVM ein?

Adobe      AMD      Apple      ARM      Google

IBM        Intel        Mozilla      Nvidia      Qualcomm

Samsung       ...

Externe LLVM-Projekte

Für folgende Sprachen gibt es Compiler oder Anbindungen an LLVM (neben Clang):

Crack      Go     Haskell      Java      Julia      Kotlin

Lua      Numba      Python     Ruby      Rust      Swift      ...

Für weitere Projekte siehe Projects built with LLVM

Unterstützte Prozessorarchitekturen

x86      AMD64      PowerPC      PowerPC 64Bit      Thumb

SPARC      Alpha      CellSPU      PIC16      MIPS

MSP430     System z      XMOS      Xcore      ...

Einige Komponenten von LLVM

Einige Komponenten (Projekte) von LLVM

• Der LLVM-Kern incl. Optimierer
• MLIR für IR-Dialekte
• Der Compiler Clang
• Die Compiler-Runtime-Bibliothek

Der LLVM-Kern

LLVM Core: Optimierer und Codegenerator für viele CPU- und auch GPU-Architekturen

• Optimierer arbeitet unabhängig von der Zielarchitektur (nur auf der LLVM IR)
• sehr gut dokumentiert
• verwendete Optimierungspässe fein konfigurierbar
• Optimierer auch einzeln als Tool opt aufrufbar
• wird für eigene Sprachen als Optimierer und Codegenerator eingesetzt

Wozu ein Optimierer?

• zur Reduzierung der Codegröße
• zur Generierung von möglichst schnellem Code
• Zur Generierung von Code, der möglichst wenig Energie verbraucht

Allgegenwärtig in LLVM: Der Optimierer

Der Optimierer in LLVM

• Teil von LLVM Core
• kann zur Compilezeit, Linkzeit und Laufzeit eingesetzt werden
• nutzt auch Leerlaufzeit des Prozessors
• läuft in einzelnen unabhängig konfigurierbaren Pässen über den Code

Einige Optimierungen in LLVM

• Dead Code Elimination
• Aggressive Dead Code Elimination
• Dead Argument Elimination
• Dead Type Elimination
• Dead Instruction Elimination
• Dead Store Elimination
• Dead Global Elimination

MLIR

• Framework zur Definition eigener Zwischensprachendialekte
• zur high-level Darstellung spezieller Eigenschaften der zu übersetzenden Sprache
• erleichtert die Umsetzung des AST in Zwischencode
• z. B. für domänenspezifische Sprachen (DSLs)
• z. B. für bestimmte Hardware
• mehrere Abstraktionen gleichzeitig benutzbar

Der Compiler Clang

Clang: schneller C/C++/Objective-C - Compiler auf Basis von LLVM mit aussagekräftigen Fehlermeldungen und Warnungen

Die Sanitizer in der Compiler-Runtime-Bibliothek

Sanitizer: Methoden zur Instrumentierung (Code der in das kompilierte Programm eingebettet wird) zur Erleichterung der Lokalisierung und Analyse verschiedenster Fehlerquellen, z. B.:

• Speicherfehler und Speicherlecks (z. B. use-after-free)
• Race Conditions
• undefiniertes Verhalten (Overflows, Benutzung von Null-Pointern)
• Benutzung von nicht-initialisierten Variablen

Wrap-Up

LLVM ist eine (fast) komplette Infrastruktur zur Entwicklung von Compilern und compilerähnlichen Programmen.

Die wichtigsten Bestandteile:

• der Zwischencode LLVM IR
• der LLVM Optimierer
• der Codegenarator mit Sanitizern

AST-basierte Interpreter: Basics

Aufgaben im Interpreter

Im Allgemeinen reichen einfache syntaxgesteuerte Interpreter nicht aus. Normalerweise simuliert ein Interpreter die Ausführung eines Programms durch den Computer. D.h. der Interpreter muss über die entsprechenden Eigenschaften verfügen: Prozessor, Code-Speicher, Datenspeicher, Stack ...

int x = 42;
int f(int x) {
    int y = 9;
    return y+x;
}

x = f(x);

AST-basierte Interpreter: Visitor-Dispatcher

def eval(self, AST t):
    if   t.type == Parser.BLOCK  : block(t)
    elif t.type == Parser.ASSIGN : assign(t)
    elif t.type == Parser.RETURN : ret(t)
    elif t.type == Parser.IF     : ifstat(t)
    elif t.type == Parser.CALL   : return call(t)
    elif t.type == Parser.ADD    : return add(t)
    elif t.type == Parser.MUL    : return mul(t)
    elif t.type == Parser.INT    : return Integer.parseInt(t.getText())
    elif t.type == Parser.ID     : return load(t)
    else : ...  # catch unhandled node types
    return None;

Nach dem Aufbau des AST durch Scanner und Parser und der semantischen Analyse anhand der Symboltabellen müssen die Ausdrücke (expressions) und Anweisungen (statements) durch den Interpreter ausgewertet werden. Eine Möglichkeit dazu ist das Traversieren des AST mit dem Visitor-Pattern. Basierend auf dem Typ des aktuell betrachteten AST-Knotens wird entschieden, wie damit umgegangen werden soll. Dies erinnert an den Aufbau der Symboltabellen ...

Die eval()-Methode bildet das Kernstück des (AST-traversierenden) Interpreters. Hier wird passend zum aktuellen AST-Knoten die passende Methode des Interpreters aufgerufen.

Hinweis: Im obigen Beispiel wird nicht zwischen der Auswertung von Ausdrücken und Anweisungen unterschieden, es wird die selbe Methode eval() genutzt. Allerdings liefern Ausdrücke einen Wert zurück (erkennbar am return im jeweiligen switch/case-Zweig), während Anweisungen keinen Wert liefern.

In den folgenden Beispielen wird davon ausgegangen, dass ein komplettes Programm eingelesen, geparst, vorverarbeitet und dann interpretiert wird.

Für einen interaktiven Interpreter würde man in einer Schleife die Eingaben lesen, parsen und vorverarbeiten und dann interpretieren. Dabei würde jeweils der AST und die Symboltabelle ergänzt, damit die neuen Eingaben auf frühere verarbeitete Eingaben zurückgreifen können. Durch die Form der Schleife "Einlesen -- Verarbeiten -- Auswerten" hat sich auch der Name "Read-Eval-Loop" bzw. "Read-Eval-Print-Loop" (REPL) eingebürgert.

Auswertung von Literalen und Ausdrücken

• Typen mappen: Zielsprache => Implementierungssprache

  Die in der Zielsprache verwendeten (primitiven) Typen müssen auf passende Typen der Sprache, in der der Interpreter selbst implementiert ist, abgebildet werden.

  Beispielsweise könnte man den Typ nil der Zielsprache auf den Typ null des in Java implementierten Interpreters abbilden, oder den Typ number der Zielsprache auf den Typ Double in Java mappen.

• Literale auswerten:

  INT: [0-9]+ ;

  elif t.type == Parser.INT : return Integer.parseInt(t.getText())

  Das ist der einfachste Teil ... Die primitiven Typen der Zielsprache, für die es meist ein eigenes Token gibt, müssen als Datentyp der Interpreter-Programmiersprache ausgewertet werden.

• Ausdrücke auswerten:

  add: e1=expr "+" e2=expr ;

  def add(self, AST t):
      lhs = eval(t.e1())
      rhs = eval(t.e2())
      return (double)lhs + (double)rhs  # Semantik!

  Die meisten möglichen Fehlerzustände sind bereits durch den Parser und bei der semantischen Analyse abgefangen worden. Falls zur Laufzeit die Auswertung der beiden Summanden keine Zahl ergibt, würde eine Java-Exception geworfen, die man an geeigneter Stelle fangen und behandeln muss. Der Interpreter soll sich ja nicht mit einem Stack-Trace verabschieden, sondern soll eine Fehlermeldung präsentieren und danach normal weiter machen ...

Kontrollstrukturen

ifstat: 'if' expr 'then' s1=stat ('else' s2=stat)? ;

def ifstat(self, AST t):
    if eval(t.expr()): eval(t.s1())
    else:
        if t.s2(): eval(t.s2())

Analog können die anderen bekannten Kontrollstrukturen umgesetzt werden, etwa switch/case, while oder for.

Dabei können erste Optimierungen vorgenommen werden: Beispielsweise könnten for-Schleifen im Interpreter in while-Schleifen transformiert werden, wodurch im Interpreter nur ein Schleifenkonstrukt implementiert werden müsste.

Zustände: Auswerten von Anweisungen

int x = 42;
float y;
{
    int x;
    x = 1;
    y = 2;
    { int y = x; }
}

Das erinnert nicht nur zufällig an den Aufbau der Symboltabellen :-)

Und so lange es nur um Variablen ginge, könnte man die Symboltabellen für das Speichern der Werte nutzen. Allerdings müssen wir noch Funktionen und Strukturen bzw. Klassen realisieren, und spätestens dann kann man die Symboltabelle nicht mehr zum Speichern von Werten einsetzen. Also lohnt es sich, direkt neue Strukturen für das Halten von Variablen und Werten aufzubauen.

Detail: Felder im Interpreter

Eine mögliche Implementierung für einen Interpreter basierend auf einem ANTLR-Visitor ist nachfolgend gezeigt.

Hinweis: Bei der Ableitung des BaseVisitor<T> muss der Typ T festgelegt werden. Dieser fungiert als Rückgabetyp für die Visitor-Methoden. Entsprechend können alle Methoden nur einen gemeinsamen (Ober-) Typ zurückliefern, weshalb man sich an der Stelle oft mit Object behilft und dann manuell den konkreten Typ abfragen und korrekt casten muss.

class Interpreter(BaseVisitor<Object>):
    __init__(self, AST t):
        BaseVisitor<Object>.__init__(self)
        self.root = t
        self.env = Environment()

Quelle: Eigener Code basierend auf einer Idee nach Interpreter.java by Bob Nystrom on Github.com (MIT)

Ausführen einer Variablendeklaration

varDecl: "var" ID ("=" expr)? ";" ;

def varDecl(self, AST t):
    # deklarierte Variable (String)
    name = t.ID().getText()

    value = None;  # TODO: Typ der Variablen beachten (Defaultwert)
    if t.expr(): value = eval(t.expr())

    self.env.define(name, value)

    return None

Wenn wir bei der Traversierung des AST mit eval() bei einer Variablendeklaration vorbeikommen, also etwa int x; oder int x = wuppie + fluppie;, dann wird im aktuellen Environment der String "x" sowie der Wert (im zweiten Fall) eingetragen.

Ausführen einer Zuweisung

assign: ID "=" expr;

def assign(self, AST t):
    lhs = t.ID().getText()
    value = eval(t.expr())

    self.env.assign(lhs, value)  # Semantik!
}

class Environment:
    def assign(self, String n, Object v):
        if self.values[n]: self.values[n] = v
        elif self.enclosing: self.enclosing.assign(n, v)
        else: raise RuntimeError(n, "undefined variable")

Quelle: Eigener Code basierend auf einer Idee nach Environment.java by Bob Nystrom on Github.com (MIT)

Wenn wir bei der Traversierung des AST mit eval() bei einer Zuweisung vorbeikommen, also etwa x = 7; oder x = wuppie + fluppie;, dann wird zunächst im aktuellen Environment die rechte Seite der Zuweisung ausgewertet (Aufruf von eval()). Anschließend wird der Wert für die Variable im Environment eingetragen: Entweder sie wurde im aktuellen Environment früher bereits definiert, dann wird der neue Wert hier eingetragen. Ansonsten wird entlang der Verschachtelungshierarchie gesucht und entsprechend eingetragen. Falls die Variable nicht gefunden werden kann, wird eine Exception ausgelöst.

An dieser Stelle kann man über die Methode assign in der Klasse Environment dafür sorgen, dass nur bereits deklarierte Variablen zugewiesen werden dürfen. Wenn man stattdessen wie etwa in Python das implizite Erzeugen neuer Variablen erlaubten möchte, würde man statt Environment#assign einfach Environment#define nutzen ...

Anmerkung: Der gezeigte Code funktioniert nur für normale Variablen, nicht für Zugriffe auf Attribute einer Struct oder Klasse!

Blöcke: Umgang mit verschachtelten Environments

block:  '{' stat* '}' ;

def block(self, AST t):
    prev = self.env

    try:
        self.env = Environment(self.env)
        for s in t.stat(): eval(s)
    finally: self.env = prev

    return None;

Quelle: Eigener Code basierend auf einer Idee nach Interpreter.java by Bob Nystrom on Github.com (MIT)

Beim Interpretieren von Blöcken muss man einfach nur eine weitere Verschachtelungsebene für die Environments anlegen und darin dann die Anweisungen eines Blockes auswerten ...

Wichtig: Egal, was beim Auswerten der Anweisungen in einem Block passiert: Es muss am Ende die ursprüngliche Umgebung wieder hergestellt werden (finally-Block).

Wrap-Up

• Interpreter simulieren die Programmausführung

  • Namen und Symbole auflösen
  • Speicherbereiche simulieren
  • Code ausführen: Read-Eval-Loop

• Traversierung des AST: eval(AST t) als Visitor-Dispatcher

• Scopes mit Environment (analog zu Symboltabellen)

• Interpretation von Blöcken und Variablen (Deklaration, Zuweisung)

AST-basierte Interpreter: Funktionen und Klassen

Funktionen

int foo(int a, int b, int c) {
    print a + b + c;
}

foo(1, 2, 3);

def makeCounter():
    var i = 0
    def count():
        i = i + 1
        print i
    return count;

counter = makeCounter()
counter()   # "1"
counter()   # "2"

Die Funktionsdeklaration muss im aktuellen Kontext abgelegt werden, dazu wird der AST-Teilbaum der Deklaration benötigt.

Beim Aufruf muss man das Funktionssymbol im aktuellen Kontext suchen, die Argumente auswerten, einen neuen lokalen Kontext anlegen und darin die Parameter definieren (mit den eben ausgewerteten Werten) und anschließend den AST-Teilbaum des Funktionskörpers im Interpreter mit eval() auswerten ...

Ausführen einer Funktionsdeklaration

funcDecl : type ID '(' params? ')' block ;
funcCall : ID '(' exprList? ')' ;

def funcDecl(self, AST t):
    fn = Fun(t, self.env)
    self.env.define(t.ID().getText(), fn)

Quelle: Eigener Code basierend auf einer Idee nach LoxFunction.java by Bob Nystrom on Github.com (MIT)

Man definiert im aktuellen Environment den Funktionsnamen und hält dazu den aktuellen Kontext (aktuelles Environment) sowie den AST-Knoten mit der eigentlichen Funktionsdefinition fest.

Für Closures ist der aktuelle Kontext wichtig, sobald man die Funktion ausführen muss. In [Parr2010, S.236] wird beispielsweise einfach nur ein neuer Memory-Space (entspricht ungefähr hier einem neuen lokalen Environment) angelegt, in dem die im Funktionskörper definierten Symbole angelegt werden. Die Suche nach Symbolen erfolgt dort nur im Memory-Space (Environment) der Funktion bzw. im globalen Scope (Environment).

Ausführen eines Funktionsaufrufs

funcDecl : type ID '(' params? ')' block ;
funcCall : ID '(' exprList? ')' ;

def funcCall(self, AST t):
    fn = (Fun)eval(t.ID())
    args = [eval(a)  for a in t.exprList()]

    prev = self.env;  self.env = Environment(fn.closure)
    for i in range(args.size()):
        self.env.define(fn.decl.params()[i].getText(), args[i])

    eval(fn.decl.block())
    self.env = prev

Quelle: Eigener Code basierend auf einer Idee nach LoxFunction.java by Bob Nystrom on Github.com (MIT)

Zunächst wird die ID im aktuellen Kontext ausgewertet. In der obigen Grammatik ist dies tatsächlich nur ein Funktionsname, aber man könnte über diesen Mechanismus auch Ausdrücke erlauben und damit Funktionspointer bzw. Funktionsreferenzen realisieren ... Im Ergebnis hat man das Funktionsobjekt mit dem zugehörigen AST-Knoten und dem Kontext zur Deklarationszeit.

Die Argumente der Funktion werden nacheinander ebenfalls im aktuellen Kontext ausgewertet.

Um den Funktionsblock auszuwerten, legt man einen neuen temporären Kontext über dem Closure-Kontext der Funktion an und definiert darin die Parameter der Funktion samt den aktuellen Werten. Dann lässt man den Interpreter über den Visitor-Dispatch den Funktionskörper evaluieren und schaltet wieder auf den Kontext vor der Funktionsauswertung zurück.

Funktionsaufruf: Rückgabewerte

def funcCall(self, AST t):
    ...

    eval(fn.decl.block())

    ...
    return None  # (Wirkung)

class ReturnEx(RuntimeException):
    __init__(self, v): self.value = v

def return(self, AST t):
    raise ReturnEx(eval(t.expr()))

def funcCall(self, AST t):
    ...
    erg = None
    try: eval(fn.decl.block())
    except ReturnEx as r: erg = r.value
    ...
    return erg;

Quelle: Eigener Code basierend auf einer Idee nach Return.java und LoxFunction.java by Bob Nystrom on Github.com (MIT)

Rückgabewerte für den Funktionsaufruf werden innerhalb von block berechnet, wo eine Reihe von Anweisungen interpretiert werden, weshalb block ursprünglich keinen Rückgabewert hat. Im Prinzip könnte man block etwas zurück geben lassen, was durch die möglicherweise tiefe Rekursion relativ umständlich werden kann.

An dieser Stelle kann man den Exceptions-Mechanismus missbrauchen und bei der Auswertung eines return mit dem Ergebniswert direkt zum Funktionsaufruf zurück springen. In Methoden, wo man einen neuen lokalen Kontext anlegt und die globale env-Variable temporär damit ersetzt, muss man dann ebenfalls mit try/catch arbeiten und im finally-Block die Umgebung zurücksetzen und die Exception erneut werfen.

Native Funktionen

class Callable:
    def call(self, Interpreter i, List<Object> a): pass
class Fun(Callable): ...
class NativePrint(Fun):
    def call(self, Interpreter i, List<Object> a):
        for o in a: print a  # nur zur Demo, hier sinnvoller Code :-)

# Im Interpreter (Initialisierung):
self.env.define("print", NativePrint())

def funcCall(self, AST t):
    ...
#    prev = self.env;  self.env = Environment(fn.closure)
#    for i in range(args.size()): ...
#    eval(fn.decl.block()); self.env = prev
    fn.call(self, args)
    ...

Quelle: Eigener Code basierend auf einer Idee nach LoxCallable.java und LoxFunction.java by Bob Nystrom on Github.com (MIT)

Normalerweise wird beim Interpretieren eines Funktionsaufrufs der Funktionskörper (repräsentiert durch den entsprechenden AST-Teilbaum) durch einen rekursiven Aufruf von eval ausgewertet.

Für native Funktionen, die im Interpreter eingebettet sind, klappt das nicht mehr, da hier kein AST vorliegt.

Man erstellt ein neues Interface Callable mit der Hauptmethode call() und leitet die frühere Klasse Fun davon ab: class Fun(Callable). Die Methode funcCall() des Interpreters ruft nun statt der eval()-Methode die call()-Methode des Funktionsobjekts auf und übergibt den Interpreter (== Zustand) und die Argumente. Die call()-Methode der Klasse Fun muss nun ihrerseits im Normalfall den im Funktionsobjekt referenzierten AST-Teilbaum des Funktionskörpers mit dem Aufruf von eval() interpretieren ...

Für die nativen Funktionen leitet man einfach eine (anonyme) Klasse ab und speichert sie unter dem gewünschten Namen im globalen Kontext des Interpreters. Die call()-Methode wird dann entsprechend der gewünschten Funktion implementiert, d.h. hier erfolgt kein weiteres Auswerten des AST.

Klassen und Instanzen I

classDef : "class" ID "{" funcDecl* "}" ;

def classDef(self, AST t):
    methods = HashMap<String, Fun>()
    for m in t.funcDecl():
        fn = Fun(m, self.env)
        methods[m.ID().getText()] = fn

    clazz = Clazz(methods)
    self.env.define(t.ID().getText(), clazz)

Quelle: Eigener Code basierend auf einer Idee nach Interpreter.java by Bob Nystrom on Github.com (MIT)

Anmerkung: In dieser Darstellung wird der Einfachheit halber nur auf Methoden eingegangen. Für Attribute müssten ähnliche Konstrukte implementiert werden.

Klassen und Instanzen II

class Clazz(Callable):
    __init__(self, Map<String, Fun> methods):
        self.methods = methods

    def call(self, Interpreter i, List<Object> a):
        return Instance(self)

    def findMethod(self, String name):
        return self.methods[name]

class Instance:
    __init__(self, Clazz clazz):
        self.clazz = clazz

    def get(self, String name):
        method = self.clazz.findMethod(name)
        if method != None: return method.bind(self)
        raise RuntimeError(name, "undefined method")