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