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
     ;

Unbedingt lesenswert

Sie sollten diese beiden Paper unbedingt als Einstieg in das Modul lesen:

1. Programming Language Semantics
2. An Incremental Approach to Compiler Construction

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

Endliche Automaten

Deterministische endliche Automaten

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

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

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, +

Formale 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

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.

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

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

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

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

Kellerautomaten (Push-Down-Automata, PDAs)

Kellerautomaten (Push-Down-Automata, PDAs)

Einordnung: Erweiterung der Automatenklasse DFA um einen Stack

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

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, 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.

Reguläre 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.

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 akzeptierte Sprache hat eine eindeutige Grammatik.

Def.: Die Klasse der Sprachen, die von einem DPDA akzeptiert werden, heißt Klasse der deterministisch kontextfreien (oder LR(k)-) Sprachen.

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

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.
• Von DPDAs akzeptierte Sprachen haben eindeutige Grammatiken.

LL-Parser

Wiederholung

PDAs und kontextfreie Grammatiken

• Warum reichen uns DFAs nicht zum Matchen von Eingabezeichen?
• Wie könnnen wir sie minimal erweitern?
• Sind PDAs deterministisch?
• Wie sind kontextfreie Grammatiken definiert?
• Sind kontextfreie Grammatiken eindeutig?

Motivation

Was brauchen wir für die Syntaxanalyse von Programmen?

• einen Grammatiktypen, aus dem sich manuell oder automatisiert ein Programm zur deterministischen Syntaxanalyse erstellen lässt
• einen Algorithmus zum sog. Parsen von Programmen mit Hilfe einer solchen Grammatik

Themen für heute

• Syntaxanlyse
• Top-down-Analyse
• rekursiver Abstieg
• LL(k)-Analyse

Syntaxanalyse

Arten der Syntaxanalyse

Die Syntax bezieht sich auf die Struktur der zu analysierenden Eingabe, z. B. einem Computerprogramm in einer Hochsprache. Diese Struktur wird mit formalen Grammatiken beschrieben. Einsetzbar sind Grammatiken, die deterministisch kontextfreie Sprachen erzeugen.

• Top-Down-Analyse: Aufbau des Parse trees von oben nach unten
  • Parsen durch rekursiven Abstieg
  • tabellengesteuertes LL-Parsing
• Bottom-Up-Analyse: LR-Parsing

Bevor wir richtig anfangen...

Def.: Ein Nichtterminal A einer kontextfreien Grammatik G heißt unerreichbar, falls es kein $a,b \in {(N \cup T)}^{\ast}$ gibt mit $S \overset{\ast}{\Rightarrow} aAb$. Ein Nichtterminal A einer Grammatik G heißt nutzlos, wenn es kein Wort $w \in T^{\ast}$ gibt mit $A \overset{\ast}{\Rightarrow} w$.

Def.: Eine kontextfreie Grammatik $G=(N, T, P, S)$ heißt reduziert, wenn es keine nutzlosen oder unerreichbaren Nichtterminale in N gibt.

Bevor mit einer Grammatik weitergearbeitet wird, müssen erst alle nutzlosen und dann alle unerreichbaren Symbole eliminiert werden. Wir betrachten ab jetzt nur reduzierte Grammatiken.

Algorithmus: Rekursiver Abstieg

Hier ist ein einfacher Algorithmus, der (indeterministisch) top-down Ableitungen vom Nonterminal X aufbaut:

Eingabe: Ein Nichtterminal $X$ und das nächste zu verarbeitende Eingabezeichen $a$.

Tabellengesteuerte Parser: 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 sog. 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.$

Follow-Mengen

Manchmal müssen wir wissen, welche terminalen Zeichen hinter einem Nichtterminal stehen können.

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

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

Das hilft manchmal:

Für $k = 1$: G ist $LL(1): \forall A \rightarrow \alpha, A \rightarrow \beta \in P, \alpha \neq \beta$ gilt:

1. $\lnot \exists a \in T: \alpha \overset{\ast}{\Rightarrow}_l a\alpha_1$ und $\beta \overset{\ast}{\Rightarrow}_l a\beta_1$
2. $((\alpha \overset{\ast}{\Rightarrow}_l \epsilon) \Rightarrow (\lnot (\beta \overset{\ast}{\Rightarrow}_l \epsilon)))$ und $((\beta \overset{\ast}{\Rightarrow}_l \epsilon) \Rightarrow (\lnot (\alpha\overset{\ast}{\Rightarrow}_l \epsilon)))$
3. $((\beta \overset{\ast}{\Rightarrow}_l \epsilon)$ und $(\alpha \overset{\ast}{\Rightarrow}_l a\alpha_1)) \Rightarrow a \notin Follow(A)$
4. $((\alpha \overset{\ast}{\Rightarrow}_l \epsilon)$ und $(\beta \overset{\ast}{\Rightarrow}_l a\beta_1)) \Rightarrow a \notin Follow(A)$

Die ersten beiden Zeilen bedeuten:

$\alpha$ und $\beta$ können nicht beide $\epsilon$ ableiten, $First_1(\alpha) \cap First_1(\beta) = \emptyset$

Die dritte und vierte Zeile bedeuten:

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, deren Eingabe eine LL(k)- (meist LL(1)-) Grammatik ist, und die als Ausgabe den Quellcode eines (effizienten) tabellengesteuerten Parsers generieren.

Algorithmus: Konstruktion einer LL-Parsertabelle

Eingabe: Eine Grammatik G = (N, T, P, S) mit $\perp \in T$ als Endezeichen

Ausgabe: Eine Parsertabelle P

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

LL-Parsertabellen

Rekursive Programmierung bedeutet, dass das Laufzeitsystem einen Stack benutzt (bei einem Recursive-Descent-Parser, aber auch bei der Parsertabelle). 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

Wrap-Up

• Syntaxanalyse wird mit deterministisch kontextfreien Grammatiken durchgeführt.
• Eine Teilmenge der dazu gehörigen Sprachen lässt sich top-down parsen.
• Ein einfacher Recursive-Descent-Parser arbeitet mit Backtracking.
• 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 (AST).

Syntaxanalyse: LR-Parser (LR(0), LALR)

Wiederholung

Top-Down-Analyse

• Baumaufbau von oben nach unten

• eine Möglichkeit: recursive-descent parser

• alternativ: tabellengesteuerter Parser

• First- und Follow-Mengen bestimmen Wahl der Ableitungen

• nicht mehr rekursiv, sondern mit PDA

Motivation

LL ist nicht alles

Die Menge der LL-Sprachen ist eine echte Teilmenge der deterministisch kontextfreien Sprachen.

Bei $LL$-Sprachen muss man nach den ersten $k$ Eingabezeichen entscheiden, welche Ableitung ganz oben im Baum als erste durchgeführt wird, also eine, die im Baum ganz weit weg ist von den Terminalen, die die Entscheidung bestimmen. Das ist nicht bei allen deterministisch parsebaren Grammatiken möglich und erschwert die Fehlerbehandlung.

Von unten nach oben

Bei der Bottom-Up-Analyse wird der Parse Tree wird von unten nach oben aufgebaut, von links nach rechts. Dabei entsteht eine Rechtsableitung.

Def.: Bei einer kontextfreien Grammatik $G$ ist die Rechtsableitung von $\alpha \in (N \cup T)^{\ast}$ die Ableitung, die man erhält, wenn das am weitesten rechts stehende Nichtterminal in $\alpha$ abgeleitet wird. Man schreibt $\alpha \overset{\ast}{\Rightarrow}_r \beta$.

Mit Hilfe der Produktionen und der Vorschautoken werden die Ableitungen "rückwärts" angewandt und "Reduktionen" genannt.

Versuchen wir es einmal

Hier entsteht ein Tafelbild.

Kann ein Stack helfen?

Hier entsteht ein Tafelbild.

So geht es vielleicht

Hier entsteht ein Tafelbild.

Da wollen wir hin

Theorie: LR(0)

Arbeitsweise

Im Stack stehen nur Zustandsnummern, am Anfang die Nummer des Startzustandes (+ Bottomzeichen, oft auch $\$$).

• Lesen des obersten Stackelements ergibt Zustand $q$

• Lesen des nächsten Eingabezeichens ergibt Zeichen $a$

• Nachschlagen der Reaktion auf $(q, a)$ in der Parse Table

• Durchführung der Reaktion

Mögliche "Actions" ohne Berücksichtigung von Vorschautoken

• Shift: Schiebe logisch das nächste Eingabesymbol auf den Stack (in Wirklichkeit Zustandsnummern)

• Reduce: (Identifiziere ein Handle oben auf dem Stack und ersetze es durch das Nichtterminal der dazugehörigen Produktion.) Das ist gleichbedeutend mit: Entferne so viele Zustände vom Stack wie die rechte Seite der zu reduzierenden Regel Elemente hat, und schreibe den Zustand, der im Goto-Teil für $(q, a)$ steht, auf den Stack.

• Accept: Beende das Parsen erfolgreich

• Reagiere auf einen Syntaxfehler

Berechnung der Zustände: Items

Def.: Ein (dotted) Item einer Grammatik $G$ ist eine Produktion von $G$ mit einem Punkt auf der rechten Seite der Regel vor, zwischen oder nach den Elementen.

Bsp.:

Zu der Produktion $A \rightarrow BC$ gehören die Items:

$[A\rightarrow B \cdot C$]

Das zu $A \rightarrow \epsilon$ gehörende Item ist $[A \rightarrow \cdot]$

Berechnung der Closure_0 von einer Menge I von Items

1. füge $I$ zu $CLOSURE_0 (I)$ hinzu

2. gibt es ein Item $[A \rightarrow \alpha \cdot B\beta]$ aus $CLOSURE_0 (I)$ und eine Produktion $(B \rightarrow \gamma)$, füge $[B \rightarrow \cdot \gamma]$ zu $CLOSURE_0 (I)$ hinzu

Berechnung der GOTO_0-Sprungmarken

für eine Itemmenge $I$ und $X \in N \cup T, A \in N, \alpha, \beta \in (N \cup T)^{\ast}$.

Konstruktion des $LR(0)$ - Automaten

1. Bilde die Hülle von $S' \rightarrow S$ und mache sie zum ersten Zustand.

2. Für jedes noch nicht betrachtete $\cdot X, X \in (N \cup T)$ in einem Zustand $q$ des Automaten berechne $GOTO_0(q, X)$ und mache $GOTO_0(q, X)$ zu einem neuen Zustand $r$. Verbinde $q$ mit einem Pfeil mit $r$ und schreibe $X$ an den Pfeil. Ist ein zu $r$ identischer Zustand schon vorhanden, wird $p$ mit diesem verbunden und kein neuer erzeugt.

Konstruktion der Parse Table

1. Erstelle eine leere Tabelle mit den Zuständen als Zeilenüberschriften. Für den Aktionstabellenteil überschreibe die Spalten mit den Terminalen, für den Sprungtabellenteil mit den Nonterminals.

2. Shift: Für jeden mit einem Terminal beschrifteten Pfeil aus einem Zustand erstelle in der Aktionstabelle die Aktion shift mit der Nummer des Zustands, auf den der Pfeil zeigt. Für Pfeile mit Nonterminals schreibe in die Sprungtabelle nur die Nummer des Folgezustands.

3. Schreibe beim Zustand $[S' \rightarrow S \cdot]$ ein $accept$ bei dem Symbol $\bot$.

4. Für jedes Item mit $[A \rightarrow \beta \cdot]$ aus allen Zuständen schreibe für alle Terminals $reduce$ und die Nummer der entsprechenden Grammatikregel in die Tabelle.

Ein Beispiel zum Nachvollziehen

(0) $S^{'} \rightarrow S$

(1) $S \rightarrow a A b S c S$

(2) $S \rightarrow a A b S$

(3) $S \rightarrow d$

(4) $A \rightarrow e$

Der LR(0)-Automat zu G1

Die LR(0)-Parsertabelle zu G1

Und was gibt es noch?

Wenn LR(0) nicht reicht

Zunächst: Zu jeder LR(k)-Sprache gibt es eine LR(1)-Grammatik.

Ist eine Grammatik nicht LR(0), müssen nichtdeterminsistische Tabelleneinträge verhindert werden:

• SLR(1)-Parsing ($A \rightarrow \beta$ wird nur reduziert, wenn das Vorschautoken in der $FOLLOW$-Menge von $A$ ist.)

• (kanonisches) LR(1)-Parsing (wie LR(0) mit einem Vorschautoken)

• LALR(1)-Parsing (Zusammenfassung aller LR(1)-Zustände, die sich nur in den LOOKAHEAD-Mengen unterscheiden)

Mehrdeutige Grammatiken

Es gibt auch Auswege

Mehrdeutige Grammatiken sind oft leichter zu lesen und kleiner als die Grammatiken, die man erhält, wenn man die Mehrdeutigkeit auflöst, sofern möglich.

Folgendes kann bei Mehrdeutigkeiten helfen:

• Angabe von Vorrangregeln

• Angabe von Assoziativität

• Voreinstellung des Parsergenearators: z. B. Shiften bei Shift-Reduce-Konflikten

• Voreinstellung des Parsergenearators: z. B. Reduzieren nach der Regel, die in der Grammatik zuerst kommt bei Reduce-Reduce-Konflikten

Hierarchie der kontextfreien Sprachen

Wrap-Up

Wrap-Up

• LR-Analyse baut den Ableitungbaum von unten nach oben auf

• es wird ein DFA benutzt zusammen mit einem Stack, der Zustände speichert

• eine Parse-Tabelle steuert über Aktions- und Sprungbefehle das Verhalten des Parsers

• die Tabelle wird mit (dotted) Items und Closures konstruiert

• mit Bottom-Up-Parsing LR(1) kann man alle deterministisch kontextfreien Sprachen parsen

• LR(0)-, SLR- und LALR- Parsing sind vereinfachte Verfahren für Teilmengen der LR-Sprachen

Typen, Type Checking und Attributierte Grammatiken

Motivation

Ist das alles erlaubt?

Operation erlaubt?

Zuweisung erlaubt?

Welcher Ausdruck hat welchen Typ?

(Welcher Code muss dafür erzeugt werden?)

• a = b
• a = f(b)
• a = b + c
• a = b + o.nummer
• if (f(a) == f(b))

Taschenrechner: Parsen von Ausdrücken wie 3*5+4

expr : expr '+' term
     | term
     ;
term : term '*' DIGIT
     | DIGIT
     ;

DIGIT : [0-9] ;

=> Wie den Ausdruck ausrechnen?

Anmerkung: Heute geht es um die einfachste Form der semantischen Analyse: Anreichern einer Grammatik um Attribute und Aktionen, die während des Parsens oder bei der Traversierung des Parse-Trees ausgewertet werden.

Semantische Analyse

Das haben wir bis jetzt

Wir haben den AST vorliegen.

Idealerweise enthält er bei jedem Bezeichner einen Verweis in sogenannte Symboltabellen (siehe spätere Veranstaltung).

Was kann beim Parsen schon überprüft / bestimmt werden?

Hier entsteht ein Tafelbild.

Was fehlt jetzt noch?

Kontextsensitive Analysen

Hier entsteht ein Tafelbild.

Analyse von Datentypen

Typisierung

• stark oder statisch typisierte Sprachen: Alle oder fast alle Typüberprüfungen finden in der semantischen Analyse statt (C, C++, Java)

• schwach oder dynamisch typisierte Sprachen: Alle oder fast alle Typüberprüfungen finden zur Laufzeit statt (Python, Lisp, Perl)

• untypisierte Sprachen: keinerlei Typüberprüfungen (Maschinensprache)

Ausdrücke

Jetzt muss für jeden Ausdruck im weitesten Sinne sein Typ bestimmt werden.

Ausdrücke können hier sein:

• rechte Seiten von Zuweisungen

• linke Seiten von Zuweisungen

• Funktions- und Methodenaufrufe

• jeder einzelne aktuelle Parameter in Funktions- und Methodenaufrufen

• Bedingungen in Kontrollstrukturen

Typinferenz

Def.: Typinferenz ist die Bestimmung des Datentyps jedes Bezeichners und jedes Ausdrucks im Code.

• Die Typen von Unterausdrücken bestimmen den Typ eines Ausdrucks

• Kalkül mit sog. Inferenzregeln der Form

  $$\frac{f:s \rightarrow t\ \ \ \ \ x:s}{f(x) : t}$$

  (Wenn f den Typ $s \rightarrow t$ hat und x den Typ s, dann hat der Ausdruck f(x) den Typ t.)

• z. B. zur Auflösung von Überladung und Polymorphie zur Laufzeit

Statische Typprüfungen

Bsp.: Der + - Operator:

Typkonvertierungen

• Der Compiler kann implizite Typkonvertierungen vornehmen, um einen Ausdruck zu verifizieren (siehe Sprachdefiniton)

• Typerweiterungen, z.B. von int nach float oder

• Bestimmung des kleinsten umschließenden Typ vorliegender Typen

• Type Casts: explizite Typkonvertiereungen

Nicht grundsätzlich statisch mögliche Typprüfungen

Bsp.: Der ^-Operator $(a^b)$:

Attributierte Grammatiken

Was man damit macht

Die Syntaxanalyse kann keine kontextsensitiven Analysen durchführen

• Kontextsensitive Grammatiken benutzen: Laufzeitprobleme, das Parsen von cs-Grammatiken ist PSPACE-complete

• Parsergenerator Bison: generiert LALR(1)-Parser, aber auch sog. Generalized LR (GLR) Parser, die bei nichtlösbaren Konflikten in der Grammatik (Reduce/Reduce oder Shift/Reduce) parallel den Input mit jede der Möglichkeiten weiterparsen

• Anderer Ansatz: Berücksichtigung kontextsensitiver Abhängigkeiten mit Hilfe attributierter Grammatiken, zur Typanalyse, auch zur Codegenerierung

• Weitergabe von Informationen im Baum

Syntax-gesteuerte Übersetzung: Attribute und Aktionen

Berechnen der Ausdrücke

expr : expr '+' term ;

translate expr ;
translate term ;
handle + ;

Attributierte Grammatiken (SDD)

auch "syntax-directed definition"

Anreichern einer CFG:

• Zuordnung einer Menge von Attributen zu den Symbolen (Terminal- und Nicht-Terminal-Symbole)

• Zuordnung einer Menge von semantischen Regeln (Evaluationsregeln) zu den Produktionen

Definition: Attributierte Grammatik

Eine attributierte Grammatik AG = (G,A,R) besteht aus folgenden Komponenten:

• Mengen A(X) der Attribute eines Nonterminals X

• G = (N, T, P, S) ist eine cf-Grammatik

• A = $\bigcup\limits_{X \in (T \cup N)} A(X)$ mit $A(X) \cap A(Y) \neq \emptyset \Rightarrow X = Y$

• R = $\bigcup\limits_{p \in P} R(p)$ mit $R(p) = \lbrace X_i.a = f(\ldots) \vert p : X_0 \rightarrow X_1 \ldots X_n \in P, X_i.a \in A(X_i), 0 \leq i \leq n\rbrace$

Abgeleitete und ererbte Attribute

Die in einer Produktion p definierten Attribute sind

AF(p) = $\lbrace X_i.a \ \vert\ p : X_0 \rightarrow X_1 \ldots X_n \in P, 0 \leq i \leq n, X_i.a = f(\ldots) \in R(p)\rbrace$

Disjunkte Teilmengen der Attribute: abgeleitete (synthesized) Attributen AS(X) und ererbte (inherited) Attributen AI(X):

• AS(X) = $\lbrace X.a\ \vert \ \exists p : X \rightarrow X_1 \ldots X_n \in P, X.a \in AF(p)\rbrace$

• AI(X) = $\lbrace X.a\ \vert \ \exists q : Y \rightarrow uXv \in P, X.a\in AF(q)\rbrace$

Abgeleitete Attribute geben Informationen von unten nach oben weiter, geerbte von oben nach unten.

Abhängigkeitsgraphen stellen die Abhängigkeiten der Attribute dar.

Beispiel: Attributgrammatiken

Wenn ein Nichtterminal mehr als einmal in einer Produktion vorkommt, werden die Vorkommen nummeriert. (t, t1; t', t'1)

S-Attributgrammatiken und L-Attributgrammatiken

S-Attributgrammatiken

S-Attributgrammatiken: Grammatiken mit nur abgeleiteten Attributen, lassen sich während des Parsens mit LR-Parsern beim Reduzieren berechnen (Tiefensuche mit Postorder-Evaluation):

def visit(N):
    for each child C of N (from left to right):
        visit(C)
    eval(N)     # evaluate attributes of N

L-Attributgrammatiken

• Grammatiken, deren geerbte Atribute nur von einem Elternknoten oder einem linken Geschwisterknoten abhängig sind

• können während des Parsens mit LL-Parsern berechnet werden

• alle Kanten im Abhängigkeitsgraphen gehen nur von links nach rechts

• ein Links-Nach-Rechts-Durchlauf ist ausreichend

• S-attributierte SDD sind eine Teilmenge von L-attributierten SDD

Beispiel: S-Attributgrammatik

Beispiel: Annotierter Syntaxbaum für 5*8+2

Erzeugung des AST aus dem Parse-Tree für 5*8+2

Beispiel: L-Attributgrammatik, berechnete u. geerbte Attribute, ohne Links-Rekursion

Teil der vorigen SDD zum Parsen und Berechnen von Ausdrücken wie 5*8+2, hier umformuliert ohne Links-Rekursion und mit berechneten und geerbten Attributen:

5*8 =>

Vorgriff: Dies ist ein Beispiel für eine "L-attributierte SDD".

Beispiel: Typinferenz für 3+7+9 oder "hello"+"world"

Syntax-gesteuerte Übersetzung (SDT)

Erweiterung attributierter Grammatiken

Syntax-directed translation scheme:

Zu den Attributen kommen Semantische Aktionen: Code-Fragmente als zusätzliche Knoten im Parse Tree an beliebigen Stellen in einer Produktion, die, wenn möglich, während des Parsens, ansonsten in weiteren Baumdurchläufen ausgeführt werden.

e : e1  {print e1.val;}
    '+' {print "+";}
    t   {e.val = e1.val + t.val; print(e.val);}
  ;

S-attributierte SDD, LR-Grammatik: Bottom-Up-Parsierbar

Die Aktionen werden am Ende jeder Produktion eingefügt ("postfix SDT").

e : e1 '+' t  {e.val = e1.val + t.val; print(e.val);} ;
e : t         {e.val = t.val;} ;
t : t1 '*' D  {t.val = t1.val * D.lexval;} ;
t : D         {t.val = D.lexval;} ;

L-attributierte SDD, LL-Grammatik: top-down-parsebar (1/2)

t  : D {t'.inh = D.lexval;} t' {t.syn = t'.syn;} ;
t' : '*' D {t'1.inh = t'.inh * D.lexval;} t'1 {t'.syn = t'1.syn;} ;
t' : e {t'.syn = t'.inh;} ;

L-attributierte SDD, LL-Grammatik: Top-Down-Parsierbar (2/2)

• LL-Grammatik: Jede L-attributierte SDD direkt während des Top-Down-Parsens implementierbar/berechenbar

• SDT dazu:

  • Aktionen, die ein berechnetes Attribut des Kopfes einer Produktion berechnen, an das Ende der Produktion anfügen

  • Aktionen, die geerbte Attribute für ein Nicht-Terminalsymbol $A$ berechnen, direkt vor dem Auftreten von $A$ im Körper der Produktion eingefügen

Implementierung im rekursiven Abstieg

Implementierung im rekursiven Abstieg

• Geerbte Attribute sind Parameter für die Funktionen für die Nicht-Terminalsymbole

• berechnete Attribute sind Rückgabewerte dieser Funktionen.

T t'(T inh) {
    match('*');
    T t1inh = inh * match(D);
    return t'(t1inh);
}

Wrap-Up

Wrap-Up

• Die Typinferenz benötigt Informationen aus der Symboltabelle

• Einfache semantische Analyse: Attribute und semantische Regeln (SDD)

• Umsetzung mit SDT: Attribute und eingebettete Aktionen

• Reihenfolge der Auswertung u.U. schwierig

  Bestimmte SDT-Klassen können direkt beim Parsing abgearbeitet werden:

  • S-attributierte SDD, LR-Grammatik: bottom-up-parsebar

  • L-attributierte SDD, LL-Grammatik: top-down-parsebar

  Ansonsten werden die Attribute und eingebetteten Aktionen in den Parse-Tree, bzw. AST, integriert und bei einer (späteren) Traversierung abgearbeitet.

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 (in Interpreter) 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.

Zu Annotationen/Attributen, Typen und Type-Checks siehe VL Typprüfungen, Attributgrammatiken

=> 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

=> Verweis auf VL Typprüfungen, Attributgrammatiken

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

Syntaxgesteuerte Interpreter

Überblick 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.

Es gibt verschiedene Varianten, beispielsweise:

• Syntaxgesteuerte Interpreter

  • Einfachste Variante, wird direkt im Parser mit abgearbeitet
  • Keine Symboltabellen, d.h. auch keine Typprüfung oder Vorwärtsdeklarationen o.ä. (d.h. erlaubt nur vergleichsweise einfache Sprachen)
  • Beispiel: siehe nächste Folie

• AST-basierte Interpreter

  • Nutzt den AST und Symboltabellen
  • Beispiel: siehe weiter unten

• Stack-basierte Interpreter

  • Simuliert eine Stack Machine, d.h. hält alle (temporären) Werte auf einem Stack
  • Arbeitet typischerweise auf bereits stark vereinfachtem Zwischencode (IR), etwa Bytecode

• Register-basierte Interpreter

  • Simuliert eine Register Machine, d.h. hält alle (temporären) Werte in virtuellen Prozessor-Registern
  • Arbeitet typischerweise auf bereits stark vereinfachtem Zwischencode (IR), etwa Bytecode

Weiterhin kann man Interpreter danach unterscheiden, ob sie interaktiv sind oder nicht. Python kann beispielsweise direkt komplette Dateien verarbeiten oder interaktiv Eingaben abarbeiten. Letztlich kommen dabei aber die oben dargestellten Varianten zum Einsatz.

Syntaxgesteuerte Interpreter: Attributierte Grammatiken

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

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

DIGIT : [0-9] ;

Die einfachste Form des Interpreters wird direkt beim Parsen ausgeführt und kommt ohne AST aus. Der Nachteil ist, dass der AST dabei nicht vorverarbeitet werden kann, insbesondere entfallen semantische Prüfungen weitgehend.

Ü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.

Da in den Alternativen der Regel expr jeweils zwei "Aufrufe" dieser Regel auftauchen, muss man per "e1=expr" bzw. "e2=expr" eindeutige Namen für die "Aufrufe" vergeben, hier e1 und e2.

Eingebettete Aktionen in ANTLR I

Erinnerung: ANTLR generiert einen LL-Parser, d.h. es wird zu jeder Regel eine entsprechende Methode generiert.

Analog zum Rückgabewert der Regel (Methode) expr() kann auf die Eigenschaften der Token und Sub-Regeln zugegriffen werden: $name.eigenschaft. Dabei gibt es bei Token Eigenschaften wie text (gematchter Text bei Token), type (Typ eines Tokens), int (Integerwert eines Tokens, entspricht Integer.valueOf($Token.text)). Parser-Regeln haben u.a. ein text-Attribut und ein spezielles Kontext-Objekt (ctx).

Die allgemeine Form lautet:

rulename[args] returns [retvals] locals [localvars] : ... ;

Dabei werden die in "[...]" genannten Parameter mit Komma getrennt (Achtung: Abhängig von Zielsprache!).

Beispiel:

add[int x] returns [int r] : '+=' INT {$r = $x + $INT.int;} ;

Eingebettete Aktionen in ANTLR II

@members {
    int count = 0;
}

expr returns [int v]
      @after {System.out.println(count);}
      : e1=expr '*' e2=expr     {$v = $e1.v * $e2.v; count++;}
      | e1=expr '+' e2=expr     {$v = $e1.v + $e2.v; count++;}
      | DIGIT                   {$v = $DIGIT.int;}
      ;

DIGIT : [0-9] ;

Mit @members { ... } können im generierten Parser weitere Attribute angelegt werden, die in den Regeln normal genutzt werden können.

Die mit @after markierte Aktion wird am Ende der Regel list ausgeführt. Analog existiert @init.

ANTLR: Traversierung des AST und Auslesen von Kontext-Objekten

Mit dem obigen Beispiel, welches dem Einsatz einer L-attributierten SDD in ANTLR entspricht, können einfache Aufgaben bereits beim Parsen erledigt werden.

Für den etwas komplexeren Einsatz von attributierten Grammatiken kann man die von ANTLR erzeugten Kontext-Objekte für die einzelnen AST-Knoten nutzen und über den AST mit dem Visitor- oder dem Listener-Pattern iterieren.

Die Techniken sollen im Folgenden kurz vorgestellt werden.

ANTLR: 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.

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.

ANTLR: 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.

ANTLR: Arbeiten mit dem Listener-Pattern

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 einen passenden Listener (Interface calcListener) generieren. Weiterhin generiert ANTLR eine leere Basisimplementierung (Klasse calcBaseListener):

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

public static class MyListener extends calcBaseListener {
    Stack<Integer> stack = new Stack<Integer>();

    public void exitMULT(calcParser.MULTContext ctx) {
        int right = stack.pop();
        int left = stack.pop();
        stack.push(left * right);   // {$v = $e1.v * $e2.v;}
    }
    public void exitADD(calcParser.ADDContext ctx) {
        int right = stack.pop();
        int left = stack.pop();
        stack.push(left + right);   // {$v = $e1.v + $e2.v;}
    }
    public void exitZAHL(calcParser.ZAHLContext ctx) {
        stack.push(Integer.valueOf(ctx.DIGIT().getText()));
    }
}

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
        System.out.println(tree.toStringTree(parser));

        ParseTreeWalker walker = new ParseTreeWalker();
        MyListener eval = new MyListener();
        walker.walk(eval, tree);
        System.out.println(eval.stack.pop());
    }
}

ANTLR: Arbeiten mit dem Visitor-Pattern

ANTLR (generiert ebenfalls auf Wunsch) zur Grammatik passende Visitoren (Interface und leere Basisimplementierung). Hier muss man allerdings selbst für eine geeignete Traversierung des Parse-Trees sorgen. Dafür hat man mehr Freiheiten im Vergleich zum Listener-Pattern, 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. Weiterhin generiert ANTLR eine leere Basisimplementierung (Klasse calcBaseVisitor<T>):

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 visit(ctx.e1) * visit(ctx.e2);   // {$v = $e1.v * $e2.v;}
    }
    public Integer visitADD(calcParser.ADDContext ctx) {
        return visit(ctx.e1) + visit(ctx.e2);   // {$v = $e1.v + $e2.v;}
    }
    public Integer visitZAHL(calcParser.ZAHLContext ctx) {
        return Integer.valueOf(ctx.DIGIT().getText());
    }
}

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
        System.out.println(tree.toStringTree(parser));

        MyVisitor eval = new MyVisitor();
        System.out.println(eval.visit(tree));
    }
}

Wrap-Up

• Interpreter simulieren die Programmausführung

• Syntaxgesteuerter Interpreter (attributierte Grammatiken)

• Beispiel ANTLR: Eingebettete Aktionen, Kontextobjekte, Visitors/Listeners (AST-Traversierung)

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

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

Instanzen einer Klasse werden durch den funktionsartigen "Aufruf" der Klassen angelegt (parameterloser Konstruktor). Eine Instanz hält die Attribute (hier nicht gezeigt) und eine Referenz auf die Klasse, um später an die Methoden heranzukommen.

Zugriff auf Methoden (und Attribute)

getExpr : obj "." ID ;

def getExpr(self, AST t):
    obj = eval(t.obj())

    if isinstance(obj, Instance):
        return ((Instance)obj).get(t.ID().getText())

    raise RuntimeError(t.obj().getText(), "no object")

Beim Zugriff auf Attribute muss das Objekt im aktuellen Kontext evaluiert werden. Falls es eine Instanz von Instance ist, wird auf das Feld per interner Hash-Map zugriffen; sonst Exception.

Methoden und this oder self

class Fun(Callable):
    def bind(self, Instance i):
        e = Environment(self.closure)
        e.define("this", i)
        e.define("self", i)
        return Fun(self.decl, e)

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

Nach dem Interpretieren von Klassendefinitionen sind die Methoden in der Klasse selbst gespeichert, wobei der jeweilige closure auf den Klassenkontext zeigt.

Beim Auflösen eines Methodenaufrufs wird die gefundene Methode an die Instanz gebunden, d.h. es wird eine neue Funktion angelegt, deren closure auf den Kontext der Instanz zeigt. Zusätzlich wird in diesem Kontext noch die Variable "this" definiert, damit man damit auf die Instanz zugreifen kann.

In Python wird das in der Methodensignatur sichtbar: Der erste Parameter ist eine Referenz auf die Instanz, auf der diese Methode ausgeführt werden soll ...

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 Funktionen (Deklaration/Aufruf, native Funktionen)

• Interpretation von Klassen und Instanzen

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

x = f(x);

Optimierung und Datenflussanalyse

Motivation

Was geschieht hier?

01  {
02    var a;
03    var b = 2;
04    b = a;
05  }

Zwischencode ist eine gute Idee

Eine Sprache, viele Maschinen vs. viele Sprachen, eine Maschine

Hier entsteht ein Tafelbild.

... und beides zusammen?

Hier entsteht ein Tafelbild.

Zwischencode (intermediate code); hier: Drei-Adress-Code

• registerbasiert
• Formen: x = y op z, x = op z, x = y
• temporäre Variablen für Zwischenergebnisse
• bedingte und unbedingte Sprünge
• Pointerarithmetik für Indizierung

i = 0
while(f[i] > 100)
    i = i + 1;

    i = 0
L1: t1 = i * 8
    t2 = f + t1
    if t2 <= 100 goto L2
    t3 = i + 1
    i = t3
    goto L1
L2: ...

Optimierungen

Was ist Optimierung in Compilern?

Verändern von Quellcode, Zwischencode oder Maschinencode eines Programms mit dem Ziel,

• Laufzeit,
• Speicherplatz oder
• Energieverbrauch

zu verbessern.

Was ist machbar?

Manche Optimierungen machen den Code nur in bestimmten Fällen schneller, kleiner oder stromsparender.

Den optimalen Code zu finden, ist oft NP-vollständig oder sogar unentscheidbar.

• Heuristiken kommen zum Einsatz.

• Der Code wird verbessert, nicht in jedem Fall optimiert, manchmal auch verschlechtert.

• Der Einsatz eines Debuggers ist meist nicht mehr möglich.

Anforderungen an Optimierung

• sichere Transformationen durchführen

• möglichst keine nachteiligen Effekte erzeugen

Optimierung zur Übersetzungszeit vs. Optimierung zur Laufzeit

• Just-in-time-Compilierung (JIT), z. B. Java:

  Fast alle Optimierungsmaßnahmen finden in der virtuellen Maschine zur Laufzeit statt.

• Ahead-of-time-Compilierung (AOT), z. B. C:

  Der Compiler erzeugt Maschinencode, die Optimierung findet zur Übersetzungszeit statt.

Beide haben ihre eigenen Optimierungsmöglichkeiten, es gibt aber auch Methoden, die bei beiden einsetzbar sind.

Welcher Code wird optimiert?

• Algebraische Optimierung: Transformationen des Quellcodes

• Maschinenunabhängige Optimierung: Transformationen des Zwischencodes

• Maschinenabhängige Optimierung: Transformationen des Assemblercodes oder Maschinencodes

Viele Transformationen sind auf mehr als einer Ebene möglich. Wir wenden hier die meisten auf den Zwischencode an.

Welche Arten von Transformationen sind möglich?

• Eliminierung unnötiger Berechnungen

• Ersetzung von teuren Operationen durch kostengünstigere

Basisblöcke und Flussgraphen

Def.: Ein Basisblock ist eine Sequenz maximaler Länge von Anweisungen, die immer hintereinander ausgeführt werden.

Ein Sprungbefehl kann nur der letzte Befehl eines Basisblocks sein.

Def.: Ein (Kontroll)Flussgraph $G = (V, E)$ ist ein Graph mit

$V = \lbrace B_i \ \vert \ B_i \text{ ist ein Basisblock des zu compilierenden Programms} \rbrace$,

Häufig benutzte Strategie: Peephole-Optimierung

Ein Fenster mit wenigen Zeilen Inhalt gleitet über den Quellcode, Zwischencode oder den Maschinencode. Der jeweils sichtbare Code wird mit Hilfe verschiedener Verfahren optimiert, wenn möglich.

Peephole-Optimierung ist zunächst ein lokales Verfahren, kann aber auch auf den gesamten Kontrollflussgraphen erweitert werden.

=> Anwendung von Graphalgorithmen!

Algebraische Optimierung

Ersetzen von Teilbäumen im AST durch andere Bäume

    x = x*2         =>      x << 1

    x = x + 0       // k.w.
    x = x * 1       // k.w.

    x = x*0         =>      x = 0
    x = x*8         =>      x = x << 3

Sei $s = 2^a + 2^b$ die Summe zweier Zweierpotenzen:

    x = n*s         =>      (n << a) + (n << b)

Diese Umformungen können zusätzlich mittels Peephole-Optimierung in späteren Optimierungsphasen durchgeführt werden.

Maschinenunabhängige Optimierung

Maschinenunabhängige Optimierung

• lokal (= innerhalb eines Basisblocks), z. B. Peephole-Optimierung

  Einige Strategien sind auch global einsetzbar (ohne die sog. Datenflussanalyse s. u.)

• global, braucht nicht-lokale Informationen

  • meist unter Zuhilfenahme der Datenflussanalyse
  • Schleifenoptimierung

Lokale Optimierung

Constant Folding und Common Subexpression elimination

• "Constant Folding": Auswerten von Konstanten zur Compile-Zeit

  x = 6 * 7         =>      x = 42
  if 2 > 0 jump L   =>      jump L
  

• "Common Subexpression Elimination"

  x = y + z
  ...
  a = y + z
  

  ersetze mit (falls in ... keine weiteren Zuweisungen an x, y, z erfolgen)

  x = y + z
  ...
  a = x
  

Elimination redundanter Berechnungen in einem Basisblock mitels DAGs

Hier werden sog. DAGs benötigt:

Ein DAG directed acyclic graph ist ein gerichteter, kreisfreier Graph.

DAGs werden für Berechnungen in Basisblöcken generiert, um gemeinsame Teilausdrücke zu erkennen.

Bsp.: a = (b + c) * (b + c) / 2

Copy propagation

• "Copy Propagation"

  x = y + z
  a = x
  b = 2*a
  

  ersetze mit

  x = y + z
  a = x
  b = 2*x
  

Wenn auf a vor seiner nächsten Zuweisung nicht mehr lesend zugegriffen wird, kann a hier entfallen.

Globale Optimierung

Control Flow und Dead Code

• Kontrollfluss-Optimierungen

      if debug == 1 goto L1           if debug != 1 goto L2
      goto L2                         print debug info
  L1: print debug info            L2: ...
  L2: ...
  

• Elimination of unreachable code

       goto L1                        L1: a = b+c
       ...
   L1: a = b+c
  

Schleifenoptimierung

Loop unrolling:

        for i = 1 to 3                  print("1")
            print(i)                    print("2")
                                        print("3")

Code Hoisting:

• Invarianten vor die Schleife schieben

     x = 0                           x = 0
  L: a = n*7                         a = n*7
     x = x + a                    L: x = x + a
     if x<42 jump L                  if x<42 jump L
  

Kombination zweier Verfahren

• Loop Unrolling (für eine Iteration), danach Common Subexpression Elimination

  while (cond) {                  if (cond) {
      body                            body
  }                                   while (cond) {
                                          body
                                      }
                                  }
  

Datenflussanalyse

Die Datenflussanalyse (auf 3-Adress-Code) basiert auf dem Wissen der Verfügbarkeit von Variablen und Ausdrücken am Anfang oder Ende von Basisblöcken, und zwar für alle möglichen Programmläufe.

Man unterscheidet:

• Vorwärtsanalyse (in Richtung der Nachfolger eines Basisblocks)

• Rückwärtsanalyse (in Richtung der Vorgänger eines Basisblocks)

In beiden Fällen gibt es zwei Varianten:

• any analysis: Es wird die Vereinigung von Informationen benachbarter Block berücksichtigt.

• all analysis: Es wird die Schnittmenge von Informationen benachbarter Block berücksichtigt.

Forward-any-analysis

Diese Analyse wird zur Propagation von Konstanten und Variablen benutzt und bildet sukzessive Mengen von Zeilen mit Variablendefinitionen.

$out(B_i)$: alle Zeilennummern von Variablendefinitionen, die am Ende von $B_i$ gültig sind

$in(B_i)$: alle Zeilennummern von Variablendefinitionen, die am Ende von Vorgängerblöcken von $B_i$ gültig sind

$gen(B_i)$: alle Zeilennummern von letzten Variablendefinitionen in $B_i$

$kill(B_i)$: alle Zeilennummern von Variablendefinitionen außerhalb von $B_i$, die in $B_i$ überschrieben werden

Zunächst ist $in(B_1) = \emptyset$, danach ist $in(B_i) = \bigcup out(B_j)$ mit $B_j$ ist Vorgänger von $B_i$.

Forward-all-analysis

Diese Analyse wird zur Berechnung verfügbarer Ausdrücke der Form $x = y\ op\ z$ für die Eliminierung redundanter Berechnungen benutzt und bildet sukzessive Mengen von Ausdrücken.

$out(B_i)$: alle am Ende von $B_i$ verfügbaren Ausdrücke

$in(B_i)$: alle Ausdrücke, die am Anfang von $B_i$ verfügbar sind

$gen(B_i)$: alle in $B_i$ berechneten Ausdrücke

$kill(B_i)$: alle Ausdrücke $x\ op\ y$ mit einer Definition von $x$ oder $y$ in $B_i$ und $x\ op\ y$ ist nicht in $B_i$

Zunächst ist $gen(B_1) = \emptyset$, danach ist $in(B_i) = \bigcap out(B_j)$ mit $B_j$ ist Vorgänger von $B_i$.

Backward-any-analysis

Diese Analyse dient der Ermittlung von lebenden und toten Variablen (für die Registerzuweisung) und bildet sukzessive Mengen von Variablen.

$out(B_i)$: alle Variablen, die am Ende von $B_i$ lebendig sind

$in(B_i)$: alle Variablen, die am Ende von Vorgängerblöcken von $B_i$ lebendig sind

$gen(B_i)$: alle Variablen, deren erstes Vorkommen auf der echten Seite einer Zuweisung steht

$kill(B_i)$: alle Variablen, denen in $B_i$ Werte zugewiesen werden.

Zunächst ist $out(B_n) = \emptyset$, danach ist $out(B_i) = \bigcup in(B_j)$ mit $B_j$ ist Nachfolger von $B_i$.

Backward-all-analysis

Diese Analyse wird zur Berechnung von "very busy" Ausdrücken der Form $x = y\ op\ z$, die auf allen möglichen Wegen im Flussgraphen vom aktuellen Basisblock aus mindestens einmal benutzt werden. Ausdrücke sollten dort berechnet werden, wo sie very busy sind, um den Code kürzer zu machen.

$out(B_i)$: alle Ausdrücke $x\ op\ y$, die am Ende von $B_i$ very busy sind

$in(B_i)$: alle Ausdrücke, die am Anfang von $B_i$ very busy sind

$gen(B_i)$: alle in $B_i$ benutzen Ausdrücke

$kill(B_i)$: alle Ausdrücke $x\ op\ y$, deren Operanden in $B_i$ nicht redefiniert werden.

Zunächst ist $out(B_n) = \emptyset$, danach ist $out(B_i) = \bigcap in(B_j)$ mit $B_j$ ist Nachfolger von $B_i$.

Maschinenabhängige Optimierung

Elimination redundanter Lade-, Speicher- und Sprungoperationen

    LD a, R0
    ST R0, a        // k.w.

        goto L1         goto L2
        ...             ...
    L1: goto L2     L1: goto L2

Register Allocation: Liveness Analysis

a = b + c
d = a + b
e = d - 1

r1 = r2 + r3
r1 = r1 + r2
r1 = r1 - 1

=> a und d sind nach Gebrauch "tot"

Berechnung der minimal benötigten Anzahl von Registern

=> Liveness-Graph, Färbungsproblem für Graphen!

Es wird ein Graph $G = (V, E)$ erzeugt mit

$V = \lbrace v \ \vert \ v \text{ ist eine benötigte Variable} \rbrace$ und $E = \lbrace (v_1, v_2)\ \vert \ v_1 \text{ und } v_2 \text{ sind zur selben Zeit "lebendig"} \rbrace$

Heuristisch wird jetzt die minimale Anzahl von Farben für Knoten bestimmt, bei der benachbarte Knoten nicht dieselbe Farbe bekommen.

=> Das Ergebnis ist die Zahl der benötigten Register.

Und wenn man nicht so viele Register zur Verfügung hat?

Registerinhalte temporär in den Speicher auslagern ("Spilling").

Kandidaten dafür werden mit Heuristiken gefunden, z. B. Register mit vielen Konflikten (= Kanten) oder Register mit selten genutzten Variablen.

In Schleifen genutzte Variablen werden eher nicht ausgelagert.

Optimierung zur Reduzierung des Energieverbrauchs

Energieverbrauch verschiedener Maschinenbefehle

Maschinenoperationen, die nur auf Registern arbeiten, verbrauchen die wenigste Energie.

Operationen, die nur lesend auf Speicherzellen zugreifen, verbrauchen ca. ein Drittel mehr Energie.

Operationen, die Speicherzellen beschreiben, benötigen zwei Drittel mehr Energie als die Operationen ausschließlich auf Register.

Energieeinsparung durch laufzeitbezogene Optimierung

Kürzere Programmlaufzeiten führen in der Regel auch zu Energieeinsparungen.

gcc -O1 spart 2% bis 70% (durchschnittlich 20%) Energie

Umgekehrt: Energiebezogene Optimierung führt in der Regel zu kürzeren Laufzeiten.

Prozessorspannung variieren

Viele Prozessoren ermöglichen es, die Betriebsspannung per Maschinenbefehl zu verändern.

Eine höhere Spannung bewirkt eine proportionale Steigerung der Prozessorgeschwindigkeit und des fließenden Stroms, aber einen quadratischen Anstieg des Energieverbrauchs. $(P = U \times I, U = R \times I)$

Folgendes kann man ausnutzen:

Die Verringerung der Spannung um 20% führt zu einer um 20% geringeren Prozessorgeschwindigkeit, d. h. das Programm braucht 25% mehr Zeit, verbraucht aber 36% $(1-(1-0,2)^2)$ weniger Energie.

=> Wenn das Programm durch Optimierung um 25% schneller wird und die Prozessorspannung um 20% verringert wird, verändert sich die Laufzeit des Programms nicht, man spart aber 36% Energie.

Wrap-Up

Wrap-Up

• Verschiedene Optimierungsverfahren auf verschiedenen Ebenen, Peephole
• Datenflussanalyse
• Senkung des Energieverbrauchs durch Optimierung