Lessons Learned

In diesem Kapitel geht es darum folgende Dinge zu verstehen und zu können

• Aufbau und Anwendung von formalen Grammatiken
  • Idee hinter einer formalen Grammatik
  • Backus-Naur-Form
• Bezug zu Programmiersprachen

Ein anschauliches Beispiel

Was ist eine Sprache?

Grundlegende Grundlagen

Eine formale Sprache …

• … dient nicht zur Kommunikation, sondern zur eindeutigen Darstellung von Informationen
  • z.B. Programmiersprachen
• … hat eine Grammatik, die den Aufbau der Sprache regelt und deren Syntax festlegt
• … hat ein Alphabet erlaubter Zeichen
• … besteht aus Worten, die aus den Zeichen des Alphabets aufgebaut sind

Grammatik - Doch nicht etwa…?

Beispiel einer Grammatik

1. Satz:= Subjekt " " Verb " " Präposition " " Nomen Ende
2. Subjekt:= Nomen
3. Nomen:= Artikel Substantiv
4. Artikel:= “der” | “die” | “das”
5. Substantiv:= “mann” | “frau” | “haus”
6. Verb:= “geht”
7. Präposition:= “in”
8. Ende:= “. "

Backus-Naur-Form (BNF)

Eine Grammatik beschreibt bzw. regelt die Syntax einer formalen Sprache

• Terminale Symbole
  • Elemente aus Zeichen des Alphabets der Sprache
• Nicht-terminale Symbole
  • Symbole, die nach den Syntaxregeln aus anderen Symbolen zusammengesetzt sind
• Grundidee
  • Angabe der terminalen Symbole
  • Rekursive Definition der nicht-terminalen Symbole

Beispiel einer Grammatik

Grammatik – BNF

• Symbole werden durch eine Zuweisung [ := ] definiert
  • Non-terminale Symbole beziehen sich auf mindestens ein anderes Symbol
  • Terminale Symbole beziehen sich auf kein anderes Symbol
• Verknüpfungen bei einer Zuweisung
  • Ein Zwischenraum bedeutet „und“ und legt die Reihenfolge der Symbole fest
  • Ein senkrechter Strich [ | ] bedeutet „oder“
• Wiederholungen
  • Mit {} geklammerte Ausdrücke können beliebig oft wiederholt werden
  • Mit [] geklammerte Ausdrücke können 0 oder 1 mal auftreten
• Klammerung mit () dient zur logischen Gliederung

Produktionen

Eine Produktion ist eine syntaktisch mögliche Kombination von terminalen Symbolen

• In einer Produktion kommen keine nicht-terminalen Symbole vor
  • Die Regeln der Grammatik müssen „bis zum Schluss“ angewendet werden
• Beispiel einer Produktion
  • der mann geht in das haus.
  • der mann geht in der haus.
  • die frau geht in das mann.

Semantik

Die Semantik beschreibt die Bedeutung der Zeichen

• Syntaktisch mögliche Produktionen sind unter Umständen „sinnlos“
  • Der Grammatik müssen weitere Regeln hinzugefügt werden, damit alle syntaktisch möglichen Produktionen auch einen Sinn ergeben
• Beispiel
  • In der bekannten Grammatik ist es sinnvoll, dass eine Produktion von Nomen nur aus Artikel und Substantiv des gleichen „Geschlechtes“ bestehen darf

Nomen := ( wArtikel wSubstantiv ) | ( mArtikel mSubstantiv )
wArtikel := "die"
mArtikel := "der"
wSubstantiv := "frau"
mSubstantiv := "mann"

Beispiel einer Grammatik in BNF

Programm := "PROGRAM " Bezeichner
            "BEGIN"
                { Zuweisung \[";"\] }
            "END"
Bezeichner := Buchstabe { ( Buchstabe | Ziffer ) } ;
Zahl := \[ "-" \] Ziffer { Ziffer } ;
String := """ { Buchstabe | Ziffer } """ ;
Zuweisung := Bezeichner “=" ( Zahl | Bezeichner | String ) ;
Buchstabe := "A" | "B" | "C" | "D" | "E" | "F" | "G"
           | "H" | "I" | "J" | "K" | "L" | "M" | "N"
           | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
           | "V" | "W" | "X" | "Y" | "Z" ;
Ziffer := "0" | "1" | "2" | "3" | "4" | "5" | "6"
        | "7" | "8" | "9" ;

Beispiel einer Produktion

PROGRAM DEMO1
BEGIN
    A0=3;
    B=45;
    H=-100023;
    C=A;
    D123=B34A;
    ESEL=GIRAFFE;
    TEXTZEILE="HALLO WELT";
END

Formale Definition einer Grammatik

Die Grammatik einer Sprache L(G) ist ein 4-Tupel mit:

G = { N, T, Σ, P }

• N = Menge der nicht-terminalen Symbole
• T = Menge der terminalen Symbole
• Σ = Startsymbol
• P = Menge der Produktionen
  • (die sich aus den Regeln der Syntax und der Semantik ergeben)

Formale Definition einer Grammatik

Anmerkungen

• Die Menge der terminalen und nicht-terminalen Symbole ist disjunkt
• Es gibt nur endlich viele Produktionsregeln
• Das Startsymbol verhindert die Bildung nicht gewollter „Teil-“Produktionen
• Σ = {Satz} garantiert z.B. vollständige Sätze in der Produktion
• Man sagt eine Grammatik „erzeugt“ die zugehörige Sprache
  • Das bedeutet, dass alle Produktionen der Sprache der Grammatik gehorchen

Übung

Welche Sprache L erzeugt folgende Grammatik ?

G = { N, T, Σ, P }

• N = { X }
• T = { a , b }
• Σ = { X }
• P = { X = ab , X = aXb }

L = <span class=‘fragment '

{ aⁿ bⁿ | n є N }

Lessons Learned

In diesem Kapitel geht es darum folgende Dinge zu verstehen und zu können

• Bezug zu formalen Sprachen
• Ablauf der Erstellung von Programmen

Wozu das Ganze?

Als Compiler wird ein Programm bezeichnet, das Quellcode in ein lauffähiges Programm überführt

• Ein Compiler übersetzt nach Bytecode oder Maschinensprache
• Es gibt verschiedene Arten von Compilern
  • Ahead-Of-Time Compiler
    • „normaler Compiler“
  • Just-in-Time Compiler
    • wird erst aktiv, wenn ein bestimmter Teil des Programm gebraucht wird
  • [ Interpreter ]
    • Führt Quellcode direkt und Schritt für Schritt aus
    • Kein Compiler im eigentlichen Sinne

Ablauf der Kompilierung

Die Kompilierung besteht aus zwei Phasen

• Analysephase – Der Code wird analysiert und auf Fehler überprüft
  • Lexikalische Analyse
  • Syntaktische Analyse
  • Semantische Analyse
• Synthesephase – Der Programmcode wird erzeugt
  • Zwischencode-Erzeugung
  • Programmoptimierung
  • Codegenerierung

Ablauf der Kompilierung

Analysephase – Lexikalische Analyse

Die lexikalische Analyse wird vom lexikalischen Scanner (kurz: Lexer) ausgeführt

Analysephase – Syntaktische Analyse

Die syntaktische Analyse wird vom Parser ausgeführt

• Die einzelnen Tokens, die der Lexer erzeugt hat, werden in einen Syntaxbaum (AST) umgesetzt
• Der Sourcecode wird auf syntaktische Fehler überprüft
• Beispiel: y = 3 + x;

Analysephase – Semantische Analyse

Bei der semantischen Analyse werden die einzelnen Anweisungen überprüft

• Überprüfung semantischer Eigenschaften
  • Sind alle Variablen vor dem ersten Zugriff deklariert worden?
  • Stimmen Quell- und Zieltyp einer Zuweisung überein?
  • Sind alle aufgerufenen Funktionen deklariert?
  • …
• Erweiterung des AST um Attribute

Analysephase - Fehlerbeispi

• Fehler 1: Fehlendes Semikolon

<span class=‘fragment fr mh-2’

Syntax-Fehler

x = 3
x = 5;

• Fehler 2: Ungültiger Variablenname

<span class=‘fragment fr’

->Ungültiger Bezeichner (kein Token für 3d) Lexer-Fehler

3d = true;

• Fehler 3: Division durch Null

<span class=‘fragment fr color-red’

Laufzeitfehler, wird beim Kompilieren nicht erkannt!

x = 10/0

Synthesephase

Die Synthesephase besteht aus …

• … Zwischencode-Erzeugung
  • Generiert einen (plattformunabhängigen) Zwischencode
    • Portabilität, Optimierung einfacher, …
• … Programmoptimierung
  • Anpassung an Zielplattform und –hardware
  • Optimierung der Befehlsstruktur
• … Codegenerierung
  • Aus dem (optimierten) Zwischencode wird der Programmcode erzeugt
    • Entweder lauffähiges Programm …
    • … oder Objektdatei ( Linker)

Synthesephase – Programmoptimierung

Viele verschiedene Optimierungen möglich

• Einsparung von Maschinenbefehlen
• Umsetzung statischer Formeln
• Elimination von „Dead Code“
• Entfernung unbenutzter Variablen
• Integration von Funktionsaufrufen
• …

Umsetzung statischer Formeln

Als statische Formeln werden Formeln bezeichnet, welche (mehrere) Konstanten enthalten

• Alle zur Kompilierungszeit bekannten Konstanten werden zusammengefasst, um Operationen zur Laufzeit einzusparen
• „constant folding“

Beispiel

Vorher

pi = 3.141592653; u = 2 * pi * r;

Nachher

pi = 3.141592653; u = 6.28318531 \* r;

Elimination von „Dead Code“ …

… und unbenutzten Variablen

• Nicht verwendeter Code kann beim Kompilieren entfernt werden
• Beispiel

Vorher

int addiere(int a, int b) {
    int c;
    return (a + b);
    c = a + b;
    return c;
}

Nachher

int addiere(int a, int b) {
    return (a + b);
}

Integration von Funktionsaufrufen

Bei kleinen Funktionen ist der Aufwand der Adressumsetzung und des Sprungbefehls oft größer, als der Nutzen des strukturierten Codes

• Beispiel

Vorher

int addiere(int a, int b) {
                return a + b;
}
int c = addiere(3, 4);

Nachher

int c = 7; //Constant folding von 3+4;

Expertenmeinung

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil" Donald Knuth

The First Rule of Program Optimization: Don’t do it. The Second Rule of Program Optimization (for experts only!): Don’t do it yet.” Michael A. Jackson:

Generelle Informationen

Ein Linker erstellt aus verschiedenen Programmodulen (Objektdateien) ein lauffähiges Programm

• Die Dateien werden „zusammengebunden“ (gelinkt)
  • Eigene Objektdateien
  • Programmbibliotheken
• Umsetzung symbolischer Adressen (Funktionen, Variablen) der verschiedenen Module in Speicheradressen
• Unterscheidung zwischen …
  • Statischem Linken
  • Dynamischem Linken

Statisches Linken

Alle verfügbaren Objektdateien werden zu einer einzigen, ausführbaren Programmdatei gelinkt

• Einfacher Austausch von Programmteilen nicht möglich
  • Bei Änderungen am Programm muss der Linkvorgang jeweils wiederholt werden
• Wird heute nur noch in Mischform mit dynamischem Linken betrieben

Dynamisches Linken

Funktions- und Variablenadressen werden erst zur Laufzeit des Programms aufgelöst

• Einfacher Austausch von Programmteilen möglich
• DLL (Dynamically Linked Library), Shared Library
• Vorteile
  • Von mehreren Programmen verwendete DLLs müssen nur einmal im System verfügbar sein
  • Die fertigen Programm werden kleiner
• Nachteile
  • Es muss sichergestellt sein, dass die richtige DLL in der richtigen Version vorliegt

Programmbibliotheken

Als Programmbibliothek wird eine Sammlung von Funktionen bezeichnet

• Oft thematisch zusammenhängend
  • z.B. Grafikbibliotheken, Mathematikbibliotheken, …
  • Programmbibliotheken sind keine eigenständigen Programme, sondern nur Hilfsmodule
• Unterscheidung zwischen …
  • Statischen Bibliotheken (statisches Linken)
  • Dynamischen Bibliotheken (dynamisches Linken)

Allgemeines

Quellcode wird nicht kompiliert, sondern bei der Programmausführung eingelesen und Schritt für Schritt ausgeführt

• z.B. in Webabwendungen verwendet (PHP, JavaScript, …)
• Nachteile gegenüber Compilersprachen
  • Geringere Ausführungsgeschwindigkeit
• Vorteile gegenüber Compilersprachen
  • Quellcode ist einfach portabel, sofern für die Zielplattform eine Interpreter-Implementierung vorhanden ist
  • Bei Änderungen des Quellcodes muss nicht das ganze Programm aufwändig neukompiliert werden

Ablauf eines Interpreters

Allgemeines

Einfacher Interpreter

• Keine semantische Analyse
  • Überprüfung ob Variablen bereits gesetzt wurden entfällt (Beispiel)
• Keine Optimierung
  • Code läuft oft nur einmal „durch“
  • Idee: Einfache Ausführung ist schneller als Optimierung und Ausführung
• Code von Skriptsprachen ungeeignet für Ahead-of-time-Kompilierung
  • Dynamische Typisierung erschwert Optimierung

Interpreter

Wichtige Unterschiede in Hinblick auf die Optimierung

• Funktionen, Variablen und Klassen werden nur unter Ihrem Namen abgelegt
  • Verknüpfung von Name -> Funktion muss schnell sein
• Objekte können beliebige Eigenschaften speichern (a.b)
  • Dictionary-Implementierung muss schnell sein

Duck-Typing

When I see a bird that walks like a duck and swims like a duck and quacks like a duck, I call that bird a duck. James Whitcomb Riley

• Merkmale eines Objektes sind vor der Ausführung unbekannt
• Wenn 2 Objekte die gleichen Merkmale und Methoden haben, kann man sie auch gelich verwenden