Compilerbau/Aufarbeitung Komplett

Aus Halloserv Wiki

Einführung

Inhalt

Ein Compiler ist ein Übersetzer von einer Quellsprache in eine Zielsprache. Die Quellsprache ist meistens eine höhere Programmiersprache (Java, C, Ocaml), die Zielsprache eine maschinennahe Programmiersprache (Assembler, ObjectCode, Maschienencode). Es gibt verschiedene Arten von Compilern: Batch-Compiler, integrierte Compiler (z.B. in Eclipse) und just-in-time Compiler (auf Bytecode-Ebene). Wir werden im Folgenden einen Batch-Compiler mit klassischer Pipeline-Architektur behandeln.

- Quellsprache Frontend -Zwischensprache Backend -Zielsprache [IMAGE]

Warum benutzt man eine Zwischensprache? Schreibt man einen Compiler für m Quellsprachen und n Zielsprachen, dann hat der minimale Compiler mit Zwischensprache m + n Programme. Frontend und Backend sind jeweils für eine Reihe von Funktionen zuständig:

Frontend

• lexikalische Analyse
• syntaktische Analyse
• semantische Analyse
• Übersetzung in Zwischensprache

Backend

• Transformation/Optimierung

von hier an plattformabhängig:

• Generierung von Assemblercode (abstrakt) / Auswahl der Instruktionen
• Scheduling
• Datenflussanalyse
• Registerallokation
• Codeausgabe

Im Folgenden werden die einzelnen Funktionen näher erläutert:

lexikalische Analyse

Die lexikalische Analyse enthält Lexer und Scanner und verwendet endlicher Automaten. Ihre Aufgabe ist die Aufteilung des Quellprogramms in Sinneinheiten (Symbole).

new Segment ( pi / 2 )

Keyword(new)
Identifier("Segment")
Lparen
Identifier("pi")
Slash
Integer(2)
Rparen

syntaktische Analyse

Die syntaktische Analyse enthält den Parser, sie ermittelt die Struktur des Quellprogramms. Die syntaktische Struktur wird durch kontextfreie Grammatiken spezifiziert.

<expr> ::= Keyword("new") <ident> Lparen <param-list> rparen
	| <expr> Slash <expr>
	| <ident>
	| <integer-literal>
<param-list> ::= <expr> <rest-list>
<rest-list> ::= Comma <expr> <rest-list>

Ergebnis: konstruiert Syntaxbaum (Ableitungsbaum) zu Liste von Symbolen, abtstrakter Syntaxbaum (AST). [IMAGE]

semantische Analyse

Die semantische Analyse behandelt folgende Fragen:

• Welche Definition gehört zu einem Vorkommen eines Bezeichner ?
• Welchen Typ hat ein Ausdruck?
• Wird eine Variable vor ihrer Initialisierung verwendet? (auch: Datenflussanalyse)
• Welche Exceptions werden von einem Methodenrumpf geworfen? (Pattern: Baumdurchlauf mit annotierten Knoten)

Datenflussanalyse

Eine Datenflussanalyse ist notwendig, da manche Optimierungen nur dann korrekt sind, wenn ein Programmen gewisse Eigenschaften erfüllt. Ein Beispiel hierfür ist die Lebendigkeitsanalyse.

Registerallokation

Bei der Registerallokation werden Zwischenergebnissen Maschinenregister zugeordnet. Bildet man diese Zuordnung auf ein Problem aus der Graphentheorie ab, kann man sie mittels einer Heuristik lösen.

Übersetzung in Zwischensprache

Dieses Kapitel ist auch als m/n Problem bekannt.

Lexikalische Analyse

Die lexikalische Analyse bildet den ersten Schritt des Compilers und wandelt den Quellcode eines Programmes in eine Liste von Token-Attribut Paaren um. Dabei werden zum Beispiel Whitespaces ignoriert, Schlüsselwörter erkannt und Formatierungszeichen gefiltert. Die lexikalische Analyse wird von einem Lexer durchgeführt, der aus einem Scanner und einem Tokenizer besteht.

Lexeme und Token

Der Quellcode eines Programmes ist aus Lexemen zusammengesetzt, der Scanner erkennt diese und wandelt sie in Token-Attribut Paare um.

new Segment(pi/2)

Scanner

Konstruktion von Scannern

Es gibt zur Konstruktion von Scannern folgende Möglichkeiten:

1. von Hand
2. benutze Bibliothek (in der Vorlesung)
3. Scannergenerator (Beispiele: lex, flex für C; jlex, jflex für Java; ocamllex für OCaml)

Bei Ansatz b) und c) werden die Lexeme durch eine reguläre Sprache definiert. Dafür gibt es einige Möglickeiten, namentlich die reguläre Grammatik, einen endlicher Automaten (DFA / NFA / ε-NFA) oder regulärer Ausdrücke. Es wird eine Repräsentation der Lexeme benötigt, die eine abstrakte und prägnante Spezifikation sowie eine effiziente Erkennung bereitstellt. Als optimale Lösung ergibt sich, dass Lexeme durch regulärer Ausdrücke spezifiziert werden und die Erkennung mit Hilfe von DFAs implementiert wird. Die folgenden beiden Abschnitte spezifizieren diese Beschreibungen.

DFA

reguläre Ausdrücke

Um Literale reguläre Ausdrücke von Symbolen zu unterscheiden, werden sie in diesem Text unterstrichen dargestellt, also statt (a | ε).

Vom regulären Ausdruck zum DFA

Wie oben beschrieben, werden Lexeme in regulären Ausdrücken spezifiziert, ihre Erkennung aber mit Hilfe eines DFA durchgeführt. Traditionell erhält man den DFA folgendermaßen:

Hier wählen wir ein anderes Verfahren, wir übersetzen direkt vom regulären Ausdruck in einen DFA (nach Brzozowski, Derivations of Regular Expressions, 1964). Die Idee besteht darin, reguläre Ausdrücke als Zustände des DFA zu nutzen. Da jeder Zustand eines Automaten eine Sprache erkennt (nämlich die Wörter, die von hier aus zu einem Endzustand führen), kann diese Sprache durch einen regulären Ausdruck beschrieben werden, der dann die Beschreibung des Zustands liefert.

• Falls , dann erkennt der reguläre Ausdruck q die Wörter "ab q", d.h. die Wörter, die q in einen Endzustand überführen (hierbei ist q sowohl Zustandsname als auch regulärer Ausdruck).
• q₀ ist der zu übersetzende reguläre Ausdruck
• falls L(q) = ε

Man muss nun aus dem gegebenen regulären Ausdruck einen Automaten konstruieren, der ihn erkennt. Hierzu definiert man die Ableitung eines regulären Ausdrucks als Funktion mit . Bevor wir eine Beschreibung von D geben können, benötigen wir noch die Hilfsfunktion , die auf ε testet, d.h. zurückgibt, wenn der reguläre Ausdruck nach aufgelöst werden kann und sonst.

Nun können wir an die Konstruktion des Automaten M gehen:

Der echte Scanner

Mit Hilfe von regulären Ausdrücken, genauer dem matcher, können wir feststellen, ob ein Wort von einem regulären Ausdruck akzeptiert wird, oder formal, ob gilt: . Ein Scanner aber muss eine ganze Reihe von Lexemen erkennen und sie in Token-Attribut Paare wandeln. Er beantwortet also die Frage: und dann . Genauer heisst das, dass der Scanner für die Eingabe u ein w,v bestimmt, so dass gilt u = wv und . Leider ist diese Bestimmung nicht eindeutig, da matches überlappen können:

Rule of the Longest Match

formel1 -> Bezeichner
for     -> Schlüsselwort

Eindeutigkeit erzielt man mit Hilfe der Rule of the longest Match, d.h. der längste passende Abschnitt wird gewählt, in obigem Beispiel also formel1. Sind beide matches gleich lang, wird die als erstes kommende Spezifikation bevorzugt.

Implementation

Im Folgenden wird der Code eines in OCaml geschriebenen echten Scanners vorgestellt, der auf den vorausgegangenen Überlegungen basiert.

Der Typ lex-action beschreibt Aktionen um Lexeme in Token-Attribut Paare zu wandeln.

type ('a, 'token, 'attrib) lex_action =
  'a list * 'a list -> 'token * 'attrib * 'a list
     a)        b)                            c)

</div> Dabei stehen die Listen für diese Symbole:

1. erkanntes Lexem
2. Rest der Eingabe
3. Rest der Eingabe, ist meistens identisch mit b) (d.h. wird durchgeschleift, es gibt aber Ausnahmen: z.B. werden Kommentare entfernt)

Eine Regel der Scannerspezifikation, lex_rule kombiniert einen regulären Ausdruck (zum Erkennen des Lexems) mit einer Aktion (zur Umwandlung in Token-Attribut Paare).

type ('a, 'token, 'attrib) lex_rule =
  'a Regexp.regexp * ('a, 'token, 'attrib) lex_action

</div>

Während des Durchlaufens des Inputstrings, merkt sich der Scanner den aktuellen Zustand in einer Struktur lex_state:

type ('a, 'token, 'attrib) lex_state =
  (('a, 'token, 'attrib) lex_rule) list

</div> Eine Scannerspezifikation ist dann nichts weiter als ein solcher Zustand, nämlich eine Liste von lex_rules.

let initial_state spec = spec

</div>

Mit next_state bearbeitet der Scanner ein Symbol und entfernt alle inaktiven Regeln.

let next_state state symbol =
  let after_state =
    List.map 
      (function (regexp, action) -> Regexp.after_symbol symbol regexp, action)
      state
 in
 filter 
   (function (regexp, _) -> not (Regexp.is_null regexp))
   after_state

</div>

Die Methode matched_rules schliesslich ermittelt die Endzustände (jene Regeln, die gerade ein Lexem erkannt haben).

let matched_rules state =
  filter 
    (function (regexp, _) -> Regexp.accepts_empty regexp)
    state

</div>

Sind alle Regeln inaktiv, landen wir bei is_stuck:

let is_stuck state = state = []

</div>

Nun folgt der Scanner Code selbst, scan_one extrahiert das nächste Lexem am Anfang des Inputs und wandelt es mit Hilfe der entsprechenden Aktion in ein Token-Attribut Paar, welches zusammen mit dem Rest des Inputs zurück gegeben wird.

let scan_one spec input =  
  let (action, rev_lexeme, rest) =
    scan_loop (initial_state spec) [] None input
  in
  action (List.rev rev_lexeme, rest)

let rec scan_loop state rev_lexeme last_match input =
    if (is_stuck state) or (input = [])
    then 
      match last_match with
        None -> raise Scan_error
      | Some match -> match
    else
      let symbol::rest = input in
      let new_state = next_state state symbol in
      let new_rev_lexeme = symbol::rev_lexeme in
      let new_match = 
        match (matched_rules new_state) with
            [] -> last_match
          | (regexp, action)::_ -> Some (action, new_rev_lexeme, rest)
      in
      scan_loop new_state new_rev_lexeme new_match rest

Typischerweise benötigt eine Sprache mehrere Lexerspezifikationen (zum Beispiel Normalzustand (Bezeichner, Literale, Schlüsselwörter), Stringliterale (inneres) und reguläre Ausdrücke (z.B. in JavaScript)).

let rec scan_normal input = scan_one <spec_normal> input
    and scan_string input = scan_one <spec_string> input
    and scan_regexp input = scan_one <spec_regexp> input

Zusammen mit der Methode scan_one, welche ein einzelnes Lexem erkennt, kann man mit diesen Spezifikationen nun den kompletten Scanner zusammensetzen:

let make_scanner scan_one input =
  let rec loop result rest =
    if rest = []
    then List.rev result
    else
      let (token, attrib, new_rest) = scan_one rest in
      loop ((token, attrib)::rev_result) rest
  in
  scan [] input

</div>

Pragmatik

Bisher haben wir die Erkennung von Schlüsselwörtern im Scanner durch triviale reguläre Ausdrücke erledigt. Das allerdings führt zu einer großen Zustandsmenge und ist ineffizient. Alternativ kann man aber auch eine effizientere Methode verwenden: Man scannt zunächst alle Schlüsselwörter als Bezeichner und konstruiere vorab eine Hashtabelle mit allen Schlüsselwörtern. Nachträglich klassifizert man dann Bezeichner als Schlüsselwörter. Benutzt man perfektes Hashing, kann diese Klassifizierung in O(1) vorgenommen werden.

Der Compiler verwaltet eine Symboltabelle, die Bezeichner auf zugehörige Informationen (Art, Typ, ...) abbildet, das heisst der Bezeichner dient als Schlüssel. Strings sind als Schlüssel allerdings nicht optimal, weswegen Bezeichner beim Scannen auf eindeutige Zahlen abgebildet werden.

Syntaxanalyse

Nachdem der Lexer den Quellcode in eine Liste von Token-Attribut Paaren aufgespalten hat, geht es nun darum, die syntaktische Struktur des Quellprogrammes zu erkennen. Ziel des zur syntaktischen Analyse eingesetzten Parsers ist es, aus der gegebenen Liste einen Ableitungsbaum (bzw. einen abstrakten Syntaxbaum, AST) zu bauen, der die Struktur des Programmes enkodiert. Um die Struktur zu definieren, und auch zu ihrer Erkennnung, benutzt man kontextfreie Grammatiken (KFG). KFGs haben den Vorteil, dass sie ein einfacher und verständlicher Formalismus sind, für viele Fälle eine Lösung für das Wortproblem in O(n) liegt und es etliche Tools gibt, die Parser aus KFGs konstruieren (z.B. yacc, bison, antlr, javacc).

Arten von Parsern

Es existieren zwei grundsätzliche Arten von Parsern, Top-Down/Predictive Parser und Bottom-Up/Shift-Reduce Parser. Top-Down Parser bauen den Ableitungsbaum von der Wurzel zu den Blättern auf (Tiefensuche), während Bottom-Up Parser den Aufbau bei dem linkesten Blatt beginnen und zur Wurzel fortsetzen.

kontextfreie Grammatiken

So wie der Lexer mit regulären Ausdrücken und DFAs arbeitet, brauchen wir für den Parser die kontextfreie Grammatik. Sie wird in diesem Abschnitt definiert.

Top-Down Parser mit Recursive Descent

Dieser Abschnitt spezifiziert einen Parser formal. Wir beginnen damit, den Parser als nicht-deterministische Funktion zu entwerfen um ihn dann zu transformieren und vereinfachen. Schliesslich werden wir ein Kriterium für Determinismus suchen (dies schränkt die Grammatik ein).

Gegeben: KFG G mit L = L(G)

Gesucht: Ein Parser für L.

Man kann nun aus der Definition und Struktur von α mit konstruktiver Induktion (Fallunterscheidung über α) eine Implementierung für [α] bestimmen:

Diese Spezifikation wäre einfach in ein Programm umzusetzen. Wie man an diesem Beispiel allerdings gut sieht, gibt es zwei Probleme:

1. Die Definition des Parsers ist nicht deterministisch: [A](w) exploriert alle Teile der rechten Seite einer Produktion. Dies kann dazu führen, dass die Implementation exponentiell zum Input-String ist.
2. Parser rufen sich selbst mit dem gleichen Argument auf (siehe z.B. [X](w)), was zu Endlosrekursion führt. Alle Rekursiv-absteigenden Parser, die links-rekursive Regeln enthalten (Regeln, deren linke Seite auch als erstes Symbol der rechten Seite auftaucht), zeigen dieses Verhalten.

Zu beiden Problemen gibt es eine Lösung, die in den kommenden Abschnitten behandelt wird: Auflösen von Links-Rekursion und Lookahead.

Links-Rekursion

Wie vorher bemerkt, führt Links-Rekursion zu einer Endlosschleife im Parser. Hier wird erklärt, wie man sie auflöst.

Um die Linksrekursion zu eliminieren, sind zwei Schritte nötig. Einmal muss die direkte Linksrekursion am Nichtterminal A beseitigt werden, und zum anderen die allgemeine Rekursion, d.h. G muss zykelfrei und frei von ε-Produktionen sein.

Lookahead

Wie vorher bemerkt, ist es ein Problem, dass der Parser nicht weiss, welcher Teil der rechten Seite zum Weitergehen verwendet werden soll. Würde der Parser alle Möglichkeiten ausprobieren, würde das zu einem Rechenaufwand führen, der exponentiell zur Eingabe ist. Um dieses Problem zu lösen, wird der Lookahead eingesetzt. Lookahead bedeutet, dass der Parser einige (k) Symbole im Input vorausschaut, um zu erkennen, welche rechte Regelseite sinnvoll ist und welche nicht. Als Ergebnis erhält man einen Parser, der linear in der Größe der Eingabe arbeitet.

Um den Lookahead zu realisieren, verwenden wir zwei Funktionen, first_k und follow_k.

Man kann diese Funktionen nun verwenden, um die oben gestellte Frage nach der korrekten rechten Seite zu beantworten. Betrachtet man diese Ableitung: , so dass der Parser [A] die Entscheidung für die Regel machen muss, wenn er ξ in der Eingabe (genauer die ersten k Zeichen von ξ) sieht. Wir können nun berechnen, das das k-Präfix von ξ folgende Eigenschaft hat:

Das führt uns zur Definition der Lookahead-Menge einer Produktion und starken LL(K)-Grammatiken (das erste L steht für "von links nach rechts parsbar", das zweite für "generiert Linksableitung").

Definition: LL(k) Lookahead

Der LL(k) Lookahead einer Produktion berechnet sich wie folgt:

Eine Grammatik ist eine starke LL(K)-Grammatik, wenn für alle Regeln gilt: .

Wir können nun eine deterministische Parserfunktion für Nichtterminale konstruieren:

Implementierung des Lookaheads

Die Implementierung von first_k betreiben wir ähnlich wie beim Parser durch Fallunterscheidung über α.

Wie man leicht sieht, hat diese Implementierung noch ein Problem: sie ist rekursiv. Man kann aber die Implementierung von first_k als Gleichungssystem mit der Unbekannten auffassen. Dann ist eine Lösung der Vektor von Mengen von terminalen Strings.

Bottom-Up / Shift Reduce Parser

Der Bottom-Up Parser baut eine Rechtsableitung von den Blättern zur Wurzel auf (d.h. rückwärts). Die Startproduktion ist die letzte Produktion, die der Parser bearbeitet. Man kann sich den Parser als Stackmaschine vorstellen:

Startkonfiguration: , wobei ε den leeren Stack und w das Eingabewort darstellt. Der Parser geht dann wie folgt vor:

In Konfiguration

• Gibt es eine rechte Regelseite auf dem Stack γ = αβ und es existiert eine Regel , dann ist der neue Zustand (reduce)
• Ist die Eingabe nicht leer, kann sie aufgespalten werden in ein Symbol und den Rest: w = aw'. Der neue Zustand ist dann (shift)
• Falls wurde das Eingabewort erkannt

Man wiederholt die einzelnen Schritte bis keine weitere Aktion mehr möglich ist. Dabei kann nichtdeterministisches Verhalten auftreten, weil ein shift fast immer möglich ist, bei der Aufteilung γ = αβ (reduce) und wenn es mehrere Nichtterminale mit gleicher rechter Seite gibt.

Der so beschriebene Parser ist auch bekannt als LR Parser (L für "von links nach rechts", R für "Rechtsableitung"). Die Arbeitsweise dieses Stackparsers wird vollständig durch einen endlichen Automaten bestimmt, der auf dem Stack arbeitet: dem charakteristischen Automaten (CA) einer Grammatik. Generalvoraussetzung ist, dass jede Grammatik startseparierbar ist.

LR(0) Parser

Es gilt nun, das Problem des nicht-Determinismus zu lösen. Als ersten Schritt konstruieren wir eine deterministische Version des charakteristischen Automaten, den LR(0) Parser

Mit dem LR(0) Automaten kann man jetzt einen Parser konstruieren. Allerdings ist dieser nur deterministisch, falls die Grammatik LR(0) ist - ansonsten treten Konflikte in den Zuständen des Automaten auf.

Die auftretenden Konflikte lassen sich in shift-reduce und reduce-reduce Konflikte aufteilen. Im obigen Beispiel enthält der Zustand einen shift-reduce Konflikt, da sowohl ein shift auf dem Symbol * ausgeführt werden kann, wie auch ein reduce auf dem Nichtterminal E.

Parsen mit dem Automaten

Um eine Eingabe mit Hilfe des LR(0) Automatens zu parsen, wenden wir so lange eine parse Funktion auf einen Stack mit Automatenzuständen und den verbleibenden Eingabestring an, bis die Eingabe leer ist und der oberste Zustand auf dem Stack ein Item enthält.

</div>

Kanonisches LR(k) Parsing

Um die im vorherigen Abschnitt beschriebenen Konflikte aufzuheben, greifen wir auf das bereits bekannte Mittel Lookahead zurück. Wir betrachten hier den kanonischen Weg, Lookahead zu implementieren, der aber sehr aufwendig in der Berechnung ist. Die folgenden Abschnitte zeigen dann effizientere Möglichkeiten auf.

LR(k) Grammatiken haben einige interessante Eigenschaften:

• Jede LL(K) Grammatik ist auch eine LR(k) Grammatik.
• Für kann jede LR(k+1) Grammatik zu einer äquivalenten LR(k) Grammatik umgeformt werden. Daraus ergibt sich, dass zu jeder LR(k) Grammatik eine äquivalente LR(1) Grammatik existiert.
• Falls L eine deterministisch erkennbare (mit deterministischem Stackautomaten), kontextfreie Sprache ist, gibt es eine LR(1) Grammatik für L.

Die nun folgende Definition des LR(k) DFA folgt generell der des LR DFA, wobei der grösste Unterschied die hinzugefügten Lookahead Mengen sind.

Lookahead Mengen werden durch predict propagiert:

</div>

Die Definition des LR(k) Automaten ist sehr ähnlich der des LR(0) Automaten:

Auch ein LR(k) Automat kann Konflikte enthalten, die zu einem nicht-Determinismus im Parser führen:

Praktikable Methoden für LR Parsing mit Lookahead

Da die kanonischen Parser häufig zu unhandlich grossen Zustandsautomaten führen, suchen wir einen anderen Weg zum Konstruieren der Parser. Hier bieten sich zwei Methoden an: Simple LR Parsing (SLR) und Lookahead LR Parsing (LALR). Beide arbeiten mit LR(0) Parsern, wie sie weiter oben vorgestellt wurden.

Simple LR

SLR erweitert die Items eines LR(0) Automaten um Lookahead-Informationen in Form der follow_k Mengen, das heisst: .

Lookahead LR

Der Lookahead LR(k) (LALR) wird mit k = 1 in fast allen Parsergeneratoren eingesetzt. Anstelle von follow_k verwendet er Lookahead-Informationen, die von der Ableitung abhängig sind. Diese Informationen werden aus dem LR(0) Automaten gewonnen.

Ausgabe des Parsers

Es gibt zwei Möglichkeiten der Syntaxrepräsentation, einen Ableitungsbaum und die abstrakte Syntax.

Ableitungsbaum

Der Ableitungsbaum enthält auf diese Weise nutzlose Informationen (d.h. der Term hat keine Bedeutung, im Baum eingekreist), nämlich über Kettenproduktionen und Klammerstrukturen. Stattdessen kann man eine andere Methode wählen, die im nächsten Abschnitt behandelt wird.

abstrakte Syntax

Die Grammatik für die abstrakte Syntax enthält nur die wesentlichen Informationen:

Für 2+x*x ergibt sich dann folgende Struktur:

</div>

Diese Struktur entspricht auch Typdefinitionen in OCaml:

type arith = Two | X | Add of arith * arith | Mul of arith * arith

Und der Ausdruck würde dann folgendermassen aussehen:

Add Two (Mul x x)

</div>

Semantische Analyse

Attribuierte Grammatiken

Ein Parser der nur als Erkenner fungiert ist nicht ausreichend für einen Compiler - seine Ausgabe verrät nichts über die Natur der geparsten Eingabe, nur ob sie zu der durch die unterliegenden Grammatik definierten Sprache gehört. Für einen Compiler muss ein Parser den Syntaxbaum, den er intern generiert hat, bereitstellen. Daher führt dieser Abschnitt eine erweiterte Notation der kontextfreien Grammatik ein: die attribuierte Grammatik. Eine attribuierte Grammatik verbindet zusätzliche Werte (die Attributsinstanzen) mit den Knoten eines Syntaxbaum und stellt Regeln bereit, die diese zu einander in Beziehung setzen. Ein Parser in einem Compiler berechnet die Werte der Attributsinstanzen und gibt diese zum Aufrufer zurück.

Attribuierte Grammatiken besitzen eine beträchtliche Menge an verwirrenden Formalismen. Einige Beispiele sollen die zentrale Idee verdeutlichen.

Wir betrachten eine Grammatik für konstante arithmetische Ausrücke. Aus technischen Gründen hat nur eine Zahl ein Literal: 42. Eine attribuierte Grammatik kann nun beschreiben wie man tatsächlich den Wert eines solchen Ausdrucks berechnet.

Notationen

Definition: attribuierte Grammatik

Sei Att eine Menge von Attributen. Eine attribuierte Grammatik ist ein Tupel mit

• G = (N,T,P,S) als kontextfreie Grammatik,
• spezifiziert für jedes Nichtterminal A die Menge Syn(A) der synthetisierten Attribute. Ein Attribut ist ein synthetisiertes Attribut wenn sein Wert an einem Knoten des Ableitungsbaums aus Attributwerten der Kinder des Knotens berechnet werden kann.
• definiert für jedes Nichtterminal A die Menge Inh(A) der geerbten Attribut. Ein Attribut ist ein geerbtes Attribut wenn sein Wert an einem Knoten des Ableitungsbaums durch die Attribute seiner Eltern- oder Geschwisterknoten definiert werden kann.
• ist eine Familie von Attribuierungsregeln
• ist eine Familie von Attribut-Domänen sodass eine Menge von möglichen Werten für ein Attribut a ist.

Für jedes A gilt: und ist die Menge der Attribute von A.

Ein Attributvorkommen ist ein Paar p.a das aus der Position innerhalb einer Produktion und einem Attribut besteht. Attributvorkommen muss entweder die Form mit oder mit haben.

Die Vorkommen einer Produktion fallen in 2 Klassen: Die definierenden Vorkommen und die angewandten Vorkommen .

Jedes definierende Vorkommen hat eine damit verbundene Attribuierungsregel

wobei m irgendeine natürliche Zahl darstellt die mit p.a verbunden ist und alle angewandte Attributvorkommen für die selbe Produktion sind. f_p.a muss eine Funktion sein. ist eine Familie aller solcher Attribuierungsregeln die durch die definierenden Attributsvorkommen indexiert werden.

Die Attributabhängigkeiten einer Grammatik sind nach der obrigen Definition in der Bochmann Normal Form: Vererbte Attribute hängen nur von "über" ihnen im Syntaxbaum ab, synthetisierte nur von denen "unter" ihnen. Eine attribuierte Grammatik verleiht einem Ableitungsbaum durch Vorschriften für seiner Knotenbeschriftung eine Bedeutung.

Definition: Attributsdekoration

Eine Attributsdekoration verbindet mit jedem Knoten v eines Ableitungsbaum, der mit einer Produktion beschriftet ist, eine Attributsinstanz für jedes . Eine Attributsdekoration ist gültig wenn für jeden Knoten v₀, der mit beschriftet ist und als Nachfolger besitzt und für jedes definierende Vorkommen mit einer verbundenen Attribuierungsregel

gilt das

wobei die Position p_j nicht-terminale Vorkommen von und damit Knoten identifiziert.

Einschub (nicht im Mitschrieb):

Daher definiert eine attribuierte Grammatik G mit der Startproduktion eine meaning function . Für initialisiert den Ableitungsbaum mit Attributsinstanzen für die geerbten Attribute von A und erzeugt Instanzen der synthetisierten Attribute von S die aus der Dekoration des Ableitungsbaums stammen.

Ende Einschub

Definition: Zirkularität einer attribuierten Grammatik

Eine attribuierte Grammatik ist zirkulär falls es einen Ableitungsbaum t gibt sodass der Graph Dt(t) zirkulär ist. Dabei ist Dt(t) = (V,E) mit

• V ist die Menge der Attributsinstanzen
• E enthält ,falls

Autoren-Anmerkung(Firefox): Offensichtlich muss hier statt den in irgendein Bezug auf vorhanden sein. Intuitiv gibt es eine Kante von jedem Vorkommen rechts des Gleichheitszeichens auf das Vorkommen links des Gleichheitszeichens wenn beide das gleiche Nichtterminal haben. Genauere Definitionen werden ergänzt.

Das Testen einer attribuierten Grammatik auf Zirkularität ist exponentiell !

Berechnung einer Dekoration

Es gibt viele Techniken die tatsächlich solch eine Dekoration eines Ableitungsbaum produzieren, manche von ihnen sind auch sehr gut. Es ist jedoch augenscheinlich wünschenswert die Dekoration während des Parsens zu generieren. Da die Bedeutungsfunktion nur an den Attributsinstanzen der Startproduktion interessiert ist und der Ableitungsbaum selbst kein Teil davon ist, könnte das Generieren der Dekoration während des Parsens das Speichern des Baums vermeiden. Leider benötigen manche generelle attribuierte Grammatiken den ganzen Baum um Attribute zu evaluieren; die Attribuierungsregeln könnten außerdem Zirkularitäten generieren.
Deshalb ist es notwendig die Klasse der attribuierten Grammatiken so zu beschränken das sie für on-the-fly Attributsevaluation zugänglich werden. 2 separate Wege geeignete Restriktionen für attribuierte Grammatiken zu formulieren sind L-attribuierte und S-attribuierte Grammatiken.

L-attribuierte Grammatiken

Definition: L-attribuierte Grammatik

Eine L-attribuierte Grammatik ist eine attribuierte Grammatik bei der für jede Regel

mit d von der Form (mit )gilt, das jedes a_j entweder die Form (mit ) oder (mit und ) besitzt. Regeln mit einem d der Form haben keine Beschränkungen.

In einer L-attribuierten Grammatik dürfen alle Attributvorkommen nur von ihrem Auftreten auf der linken Seite abhängen (daher auch L-attribuiert). Weil ein rekursiv-absteigender Parser von links nach rechts durch die Grammatikregeln geht, bieten sich L-attribuierte Grammatiken für on-the-fly Attributevaluation durch rekursiv-absteigende Parser an.

S-attribuierte Grammatiken

Trotz alledem stellen L-attribuierte Grammatiken ein Problem für rekursiv-absteigende Parser dar: Während des Laufs eines rekursiv-absteigenden Parsers muss sich dieser mehrere verschiedene Produktion "merken", von denen jede komplett verschiedene Attribuierungsregeln besitzen kann. Er würde daher alle diese Regeln parallel auswerten müssen - und dadurch viel überflüssige Arbeit erledigen. Allerdings beschränken rekrusiv-aufsteigende Parser die Klasse der attribuierten Grammatiken die sie akzeptieren normalerweise noch weiter: Sie erlauben einfach keine vererbten Attribute.

S-attribuierte Grammatiken werden auch von Parser-Generatoren wie z.B. yacc verwendet. Bei einer S-attribuierte Grammatiken verläuft die Attributevaluation von unten nach oben im Ableitungsbaum: Es können keine Zirkularitäten auftreten da alle Abhängigkeiten in die gleiche Richtung zeigen. Aus diesem Grund ist es ausreichend nur ein synthetisiertes Attribut pro Nichtterminal zu haben - verschiedene Attribute können einfach durch Zusammenfassungen wie Rekords simuliert werden. Daher nehmen wir im Rest dieser Sektion an, das Syn(A) = {v} für alle gilt. Außerdem besitzt der vereinfachten Darstellung wegen immer | α | Argumente. Terminalzeichen geben einfach irgendeinen reservierten Wert , der sonst nicht benutzt wird, als ihr Attribut zurück.

statische semantische Eigenschaften

(vgl. Kapitel 8 in Wilhelm / Maurer)

• Werte, die zu jedem Programmpunkt (Knoten im AST) aus dem Programmtext berechnet werden können.
• Wert beschreibt alle während eines Programmlaufs an diesem Programmpunkt eintretenden Werte und Konfigurationen.

Gültigkeit und Sichtbarkeit von Bezeichnern (Scoping)

Problem: Im Allgemeinen gibt es mehrere definierende Vorkommen eines Bezeichners. Auf welches definierende Vorkommen bezieht sich ein angewandtes Vorkommen ?

Die Identifizierung von Bezeichnern

ordnet jedem angewandtem Vorkommen ein definierendes Vorkommen zu. (Bei Überladung kann und soll sich ein angewandtes Vorkommen auf mehrere definierende Vorkommen beziehen; die Auflösung dieser Mehrdeutigkeit wird durch Kontextanalyse und meistens über Typinformationen realisiert). Die Implementierung wird mittels einer Symboltabelle gemacht, d.h. durch eine Abbildung Id Info. Info ist die korrekte Deklaration für dieses angewandte Vorkommen. Um diese Abbildung zu implementieren gibt es drei Möglichkeiten:

• Verweis auf den Knoten der Deklaration, also zum definierenden Vorkommen im AST
• Referenz auf den Symboltabelleneintrag der Deklaration
• direkt die Information aus der Deklaration kopieren.

Operationen der Symboltabelle

• create Erzeugung und Initialisierung der Symboltabelle
• enter_block Betritt einen neuen Gültigkeitsbereich und erzeugt sie falls sie nicht vorhanden ist
• enter_id(id,decl) Erzeuge Eintrag für id
• search-id(id) liefert Verweis auf sichtbares definierendes Vorkommen
• exit_block verlässt den aktuellen Gültigkeitsbereich und wechselt auf die nächsthöhere Ebene.

Implementierung

naiv:

Die Symboltabelle ist ein Stack von Blocktabellen, die Tabelle des aktuellen Blocks ist das erste Element. Eine Blocktabelle enthält Einträge für alle Bezeichner deren definierendes Vorkommen im entsprechenden Block liegt.

besser:

• eine globale Suchtabelle (Hashtable)
• Eintrag zu Bezeichner ist Stack von Deklarationen
• Stack von Mengen von Bezeichnern; eine Menge pro Block
  • outer_block: push
  • exit_block: entferne den oberen Stackeintrag in der Tabelle zu jedem Bezeichner in der Menge auf der Stackspitze (pop).

type (id',decl') Symtab = {
 table : (id',decl') Hashtable.t; 
 stack : 'id list list ref 
}  

let create () = {
 table = Hashtable.create 101;
 Stack = ref left [right]
}  

let enter_block st = 
  st.block := left [right] :: !st.block 

let enter_id st id decl = 
  let_ = Hashtable.add st.table id decl in  (* versteckt unter anderem den alten Eintrag *) 
    let vars :: Stacks = lst,Stack in 
      st.block := (id::vars)::Stacks 

let search_id st id = 
  Hashtable.find st.table id 

let exit_block st = 
  let vars::blocks = !st.block in 
    let_ = st.block := blocks in 
      List.iter(Hashtable.remove st.table) vars 

Auflösung der Überladung

Problem: Zu einem Attribut eines Bezeichners gibt es mehrere sichtbare definierende Vorkommen. Dies entsteht durch "Überladung" von Bezeichnern, meist Methoden- bzw. Funktionsnamen, Infixoperatoren, aber teilweise auch Variablen mit gleichem Namen aber unterschiedlichen Typen. Durch geeignete Auswahl der Identifikationskriterien lässt sich eine Überladung auflösen.

Ein definierendes Vorkommen überdeckt - bei Überladung - nicht alle gültigen sondern nur die äquivalenten definierendes Vorkommen (bezüglich der Auswahl).

Algorithmus zur Auflösung von Überladungen in Ada

Scanner und Parser verbinden

Über all diese Überlegungen zum Parsen haben wir bisher die Frage nach der lexikalischen Analyse gänzlich ignoriert - sie spielt keine Rolle bei den theoretischen Grundlagen des Parsen. Natürlich ist es augenscheinlich notwendig das wir die beiden Aspekte auf irgendeine Art und Weise verbinden müssen. Die Trennung zwischen lexikalischer und syntaktischer Analyse ist kaum mehr als die Trennlinie, die bei Grammatiken die regulären von den nicht-regulären unterscheidet. Das bedeutet jedoch, daß die Terminalzeichen des nicht-regulären Teils (der Teil der von der syntaktischen Analyse behandelt wird), die die Tokens der lexikalischen Analyse darstellen, in Wirklichkeit Nichtterminalzeichen der originären, vollständigen Grammatik sind. Als solche benötigen sie Attribute.
Jetzt wird klar, daß die Attribute aus der Phase der lexikalischen Analyse tatsächlich die selbe Rolle wie die Attributsinstanzen der syntaktischen Analyse spielen. Es sind nun lediglich kleinere Veränderungen des Attribute evaluierenden Parsers notwendig, um die Tatsache zu berücksichtigen, daß seine Eingabe keine Folge aus Terminalzeichen ξ ist, sondern vielmehr eine Folge von Terminalzeichen/Attribut-Paaren w. In der folgenden Spezifiktion entnimmt nur die Terminalzeichen aus einer Sequenz von Terminalzeichen/Attribut-Paaren.

abstrakte Syntax

Es ist möglich den kompletten Kompilierungsprozess durch die Attribuierungsregeln einer attribuierten Grammatik ablaufen zu lassen. Jedoch werden die Attributevaluierungsregeln während der Evaluierung durch den Parser so weit beschränkt das dieser Vorgang sehr schwierig ist: Der Compiler müsste die Konstrukte in der selben Reihenfolge übersetzen in der sie eingelesen werden - das würde viele Optimierungen unmöglich machen. Außerdem benötigen bestimmte Sprachen mehrere Durchläufe durch das Programm um z.B. Bezeichner aufzulösen. Das kann nicht einfach mit einer on-the-fly Attributsevaluierung gemacht werden.

Konsequenterweise ist es besser die Attribuierungsregeln einfach eine Repräsentation eines Ableitungsbaum konstruieren zu lassen. Jedoch ist die direkte Repräsentation eines Ableitungsbaum nicht die geeignetste für die Zwecke des Compilers. Betrachten wir die Syntax einer Teilmenge von Caml namens Mini-Caml:

<exp> ::= <literal>
   | <ident>
   | ( <operator-name> )
   | ( <exp> )
   | <exp> <exp>
   | <prefix-symbol> <exp>
   | <exp> <infix-symbol> <exp>
   | if <exp> then <exp> else <exp>
   | <exp> or <exp>
   | <exp> & <exp>
   | <exp> ; <exp>
   | function <ident> -> <exp>
   | raise <exp>
   | try <exp> with <ident> -> <exp>
   | let rec? <let-binding> <more-bindings>* in <exp>
   | [ <sequence> ]

<literal> ::= ( ) | <integer-literal> | <character-literal> | <string-literal>
<operator-name> ::== <infix-symbol> | <prefix-symbol>
<sequence> ::= <empty> | <exp> <sequence-rest>*
<sequence-rest> ::= ; <exp>
<let-binding> ::= <ident>+ = <exp>
<more-bindings> ::= and <let-binding>
<definition> ::= let rec? <let-binding> <more-bindings>*
<program> ::= <definition>*

Die Syntax beinhaltet viel "Interpunktion": Klammern, Pfeile, Infixseparatoren wie in oder then die in Ableitungsbaum einfach "tote Blätter" werden: Selbst wenn wir sie auslassen könnten sie leicht automatisch wieder hergestellt werden. Außerdem erlaubt die Syntax Infix-Ausdrücke die eigentlich nur ein anderer Weg sind, binäre Funktionen zu schreiben. Außerhalb der Grammatik gibt es keine Notwendigkeit zwischen der Anwendung von Infixen und Präfixen zu unterscheiden.
Daher verwenden Compiler normalerweise eine abstraktere Repräsentation eines Ableitungsbaums die abtstrakter Syntaxbaum (AST) genannt wird.

Diese beinhaltet immer noch alle notwendigen Informationen um die Bedeutung eines Programms herleiten zu können läßt aber alle unnötigen Details aus. Es ist möglich aus der abstrakten Syntax des Originalprogramm ein äquivalentes Programm zu konstruieren. Deswegen hat die abstrakte Syntax ähnliche Eigenschaften wie die Token/Attribut-Paare, die der Scanner herstellt. Als Faustregel kann man sagen das eine Produktion in der Grammatik zu einem Konstrukt in der abstrakten Syntax korrespondiert. Die Einzelheiten hängen jedoch von der jeweiligen Grammatik und der jeweiligen Parser-Methode, die die Struktur der Grammatik beeinflussen kann, ab.

Mit Hilfe der abtstrakten Syntaxbäume kann nun der volle Formalismus der attribuierten Grammatiken hergestellt werden. Die wichtigste Erkenntnis ist, das Attribuierungen nicht auf Ableitungsbäume beschränkt sind sondern für alle Arten von Baumstrukturen angewendet werden können, im speziellen für abtstrakte Syntaxbäume. Daher kann eine attribuierte Grammatik in geeigneter und erklärender (conveniently and declaratively ) Weise alle Arten von semantischen Analysen auf abtstrakten Syntaxbäume spezifizieren. In diesem Fall ist die Beschränkung alle Attributsdekorationen in einem Durchlauf (z.B. während des Parsens) zu erzeugen nicht mehr vorhanden; fortgeschrittene Multi-Pass-Techniken für das Berechnen der Attributsdekoration existieren und können angewandt werden.

Im Falle von Mini-Caml (was schon einige der syntaktischen Frivolitäten der vollen Caml-Sprache ausläßt) kann die abstrakte Syntax sogar noch einfacher als die konkrete Syntax sein. Die nächste Sektion zeigt eine Caml-Typ Deklaration für eine solche abstrakte Syntax:

type 'ident syntax = 
     Nil
   | Int of int
   | String of string
   | Char of char
   | Ident of 'ident
   | Builtin of 'ident
   | Apply of 'ident syntax * 'ident syntax
   | If of 'ident syntax * 'ident syntax * 'ident syntax
   | Sequence of 'ident syntax * 'ident syntax
   | Function of 'ident * 'ident syntax
   | Raise of 'ident syntax
   | Try of 'ident syntax * 'ident * 'ident syntax 
   | Let of 'ident binding * 'ident syntax
   | Letrec of 'ident binding list * 'ident syntax
 and 'ident binding = 'ident * 'ident syntax

type 'ident definition = 'ident binding list

type 'ident program = 'ident definition list 

Natürlich gibt es einige seltsame Konstrukte die nach einer Erklärung verlangen:

• Die Typdeklaration ist mit dem Typ der Bezeichner parametrisiert. Das macht es später einfacher automatisch generierte Bezeichner modulare Systeme und ähnliches zu behandeln.
• Sie unterscheidet zwischen "normalen" (Ident) und eingebauten (Builtin) Bezeichnern, wobei sich die eingebauten auf eingebaute Operationen wie primitive arithemtische Operationen, Speicheralloziierung und ähnliches beziehen. Obwohl der Parser keine Builtin-Knoten produzieren wird, kann eine spätere Analyse herausfinden, welche Ident-Knoten sich tatsächlich auf eingebaute Operationen beziehen.
• Sie unterscheidet zwischen let und letrec. Es wird klarwerden das beide Konstrukte in einer späteren Phase des Kompilierens genügend unterschiedliche Behandlung benötigen um diese Unterscheidung zu rechtfertigen.

Zwischensprachen

Zwischensprachen werden benutzt, um die Ergebnisse des Frontend (lexikalische, syntaktische und semantische Analyse) mit dem Backend (Codeerzeugung- und Optimierung) zu verbinden. Sie werden eingesetzt, weil man hierdurch die Anzahl der zu schreibenden Programme deutlich verringern kann: Hat man m Quell- und n Zielsprachen, so benötigt man mit Zwischensprache lediglich m + n Programme zur Uebersetzung. Wir suchen hierfür eine interne Repräsentation eines Programmes, für die diese Kriterien erfüllt sind:

• einfach zu analysieren
• einfach zu transformieren
• einfache Codeerzeugung (Elemente der Repräsentation sollen wenigen Maschinenbefehlen entsprechen)
• eindeutig festgelegte Bedeutung

Die Vorlesung überspringt hier eine Kapitel aus dem ursprünglichen Skript, den Lambda-Kalkül. Es entsteht dadurch ein bisschen Verwirrung, was den Inhalt angeht, aber im Grunde bezweckt dieses Kapitel die Vereinfachung des Quellcodes nach den oben beschriebenen Kriterien. Zu diesem Zweck entwerfen wir eine Reihe von Interpretern: zuerst einen naiven Interpreter, der dann zu einem Interpreter mit continuation-passing style (CPS) ausgebaut wird, um daraufhin Lambda-Lifting (basierend auf dem Lambda-Kalkül) und weitere Verfahren zu benutzen, die uns schrittweise dem Maschinencode näherbringen.

Naiver Interpreter

Wir beginnen mit einer Struktur zur Buchführung über die Bezeichner, environment und zugehörigen Operationen. Dies werden als Funktionen festgelegt, damit wir die Struktur in Zukunft optimieren können, ohne den restlichen Code ändern zu müssen:

type expr =
    Int of int
  | Builtin of ident * expr list
  | If of expr * expr * expr
  | Ident of ident
  | Let of ident * expr * expr
  | Function of ident * ident list * expr
  | Apply of expr * expr list
  | Raise of expr
  | Try of expr * ident * expr
  | Var of ident * expr * expr
  | Assign of ident * expr

(* environment manipulation - the environment is a list of identifier-value pairs. *)
type 'value env =
  (string * 'value) list
let extend env x v =
  ((x,v)::env)
let rec extends env xs vs =
  match (xs, vs) with
      (x::xs, v::vs) -> extends (extend env x v) xs vs
    | ([], []) -> env
let lookup =
  List.assoc

</div>

Als nächstes folgt der naive Interpreter eval selbst:

(* begin with a few definitions for values and exceptions *)

type value =
    VInt of int
  | VFun of (value list -> value)
  | VRef of value ref
  | VUnit of unit

let exInt (VInt i) = i
let exFun (VFun f) = f
let exRef (VRef r) = r
let exUnit (VUnit u) = u

exception VException of value

(* eval : Syntax.t −> value env −> value *)
let rec eval e env =
  match e with
      Int (i) -> VInt (i)
    | Builtin (f, es) -> (
        match (f, evals es env) with
            ("+", [v1; v2]) -> VInt (exInt v1 + exInt v2))
    | If (e1, e2, e3) -> 
        if exInt (eval e1 env) != 0
        then eval e2 env
        else eval e3 env
    | Ident (x) -> lookup x env
    | Let (x, e1, e2) -> eval e2 (extend env x (eval e1 env))
    | Function (x0, xs, e) -> VFun (function vs -> eval e (extends env xs vs))
    | Apply (e0, es) -> (exFun (eval e0 env)) (evals es env)
    | Raise (e) -> raise (VException (eval e env))
    | Try (e0, x, e1) -> (
        try eval e0 env with
          VException v -> eval e1 (extend env x v))
    | Var (x, e1, e2) -> eval e2 (extend env x (VRef (ref (eval e1 env))))
    | Assign (x, e) -> VUnit ((exRef (lookup x env)) := eval e env)

and evals es env =
  match es with
      [] -> []
    | e :: es -> eval e env :: evals es env

Continuation-Passing Style

Wie man im naiven Interpreter bei Apply(e1, e2) sehen kann, ist die Reihenfolge der Auswertung von Argumenten nicht festgelegt, gegebenenfalls wird e2 gar gar nicht ausgeführt. Das nennt man auch das Sequenzierungsproblem. Damit die Auswertung der Argumente sichergestellt wird, übergeben wir nun nur noch Werte als Parameter. Erreicht wird das durch Transformation des Programms in den Continuation-Passing Style (CPS). Ein Ausdruck in einem CPS Programm liefert kein Ergebnis, sondern übergibt das Ergebnis an eine Continuation, das heisst eine Funktion, die den Kontext des Ausdrucks (den Rest des Programms) repräsentiert.

Als Illustration mag dieser Vergleich der Fakultätsfunktion in "direktem Stil" und CPS dienen:

(* direct style *)
let rec fac n = 
  if n = 0 then 1 else n * fac (n - 1)

(* CPS, unter der Annahme, dass
     =' (x, y) c
     *' (x, y) c
     -' (x, y) c
   die CPS Versionen von =, *, - sind. *)
let rec fac' n c =
  ='(n, 0) (function b ->
    if b then 
      c 1
    else -'(n, 1) (function n' ->
      fac' n' (function r' ->
        *'(n, r') (function r -> c r))))

Wie man sieht, sind alle Argumente Werte, die Reihenfolge der Auswertung ist festgelegt, Funktionsaufrufe werden zu Sprüngen und primitve Argumente können teilweise als Maschieneninstruktionen gelesen werden. Es gibt aber auch ein paar Nachtteile: Eine wirkliche Festlegung auf primitive Operatoren/Maschienenbefehle ist hier zu früh (weil es je nach Architektur unterschiedliche Spezialbefehle gibt, z.B. MULT/ADD bei der Power-Architektur). Auch müssen die Continuations unterschiedlich repräsentiert werden:

• (function n' -> ...) Vorwärtsschalten des Program Counters (PC)
• (function r' -> ...) ? (jedenfalls nicht Vorwärtsschalten des PC)

Für unsere Zwecke reicht deshalb eine schwächere Form, bei der alle Argumente primitiv auswertbar sind:

let rec fac'' n c =
  if n = 0 then 
    c 1
  else
    fac'' (n-1) (function r' -> c (n * r'))

Daraus folgend konstruieren wir jetzt einen naiven Interpreter mit CPS:

(* as before we start with definitions - note the changed line for VFun *)
type value =
    VInt of int
  | VFun of (value list -> (value -> value) -> value)
  | VRef of value ref
  | VUnit of unit

let exInt (VInt i) = i
let exFun (VFun f) = f
let exRef (VRef r) = r
let exUnit (VUnit u) = u

exception VException of value

(* eval : Syntax.t −> value env −> (value −> value) −> value *)
let rec eval e env c =
  match e with
      Int (i) -> c (VInt (i))
    | Builtin (f, es) ->
        evals es env (function vs ->
          (match (f, vs) with
            ("+", [v1; v2]) -> c (VInt (exInt v1 + exInt v2))))
    | If (e1, e2, e3) ->
        eval e1 env (function v1 ->
          if exInt v1 != 0 then 
            eval e2 env c
          else 
            eval e3 env c)
    | Ident (x) -> c (lookup x env)
    | Let (x, e1, e2) ->
        eval e1 env (function v1 ->
          eval e2 (extend env x v1) c)
    | Function (x0, xs, e) ->
        c (VFun (function vs ->
          eval e (extends env xs vs)))
    | Apply (e0, es) ->
        eval e0 env (function v0 ->
          evals es env (function vs -> (exFun v0) vs c))
    | Raise (e) ->
        eval e env (function v -> raise (VException v))
    | Try (e0, x, e1) -> (*not correct*)
       (try eval e0 env c with
         VException v -> eval e1 (extend env x v) c)
    | Var (x, e1, e2) ->
        eval e1 env (function v1 ->
          eval e2 (extend env x (VRef (ref v1))) c)
    | Assign (x, e) ->
        eval e env (function v ->
          (exRef (lookup x env)) := v ; c (VUnit ()))

and evals es env c =
  match es with
      [] -> c []
    | e :: es ->
        eval e env (function v ->
          evals es env (function vs -> c (v :: vs)))

Wie man sieht, haben wir das Sequenzierungsproblem damit gelöst, allerdings mit dem Nachteil, für CPS sehr viele Funktionen definiert zu haben.

Exceptions

Im ursprünglichen Interpreter werden die Exceptions mit Hilfe der interpretierenden Sprache behandelt:

exception VException of value

let rec eval e env =
  match e with
      ...
    | Raise (e) -> raise (VException (eval e env))
    | Try (e0, x, e1) -> (
        try eval e0 env with
          VException v -> eval e1 (extend env x v))

Wie man am folgenden Beispiel sieht, kann man aus der ursprünglichen Version eine Transition nach CPS vornehmen, die keine Exceptions in der interpretierenden Sprache benötigt. Wir sehen uns dazu product, eine optimierte Version mit Exception und dann die CPS Version an:

(* normal product *)
let rec product xs = 
  match xs with
      [] -> 1
    | x::xs' -> x * product xs'

(* optimized *)
let product xs = 
  let rec pr xs = 
    match xs with
        [] -> 1
      | x::xs' -> 
          if x = 0 then 
            raise Null
          else
            x * xs'
  in
  try pr with Null -> 0

(* CPS version *)
let product xs c = 
  let rec pr xs c'
    match xs with
        [] -> c' 1
      | x::xs' -> 
          if x = 0 then 
            c 0
          else 
            pr xs (function r -> c' (x * r))
  in
  pr xs c

</div>

Man beachte, dass CPS hier etwas waghalsig benutzt wird: Die Verwendung von c im then Teil sollte eigentlich nicht vorkommen, da nur die innerste Continuation zur Benutzung gedacht ist. Man kann deshalb eine weitere Version benutzen, die mit einer zusätzlichen Exception-Continuation die Exceptions systematisch behandelt:

let product xs ex c = 
  let rec pr xs ex c = 
    match xs with
        [] -> c 1
      | x::xs' -> 
          if x = 0 then
            ex Null (* = raise *)
          else
            pr xs ex (function r -> c (x * r))
  in
  pr xs (function Null -> c 0) c
        (*      = try       *)

Closures

Während sich der letzte Abschnitt (auch) mit dem Umwandeln von Operationen in maschinennahe Instruktionen beschäftigt hat, geht es hier und im nächsten Abschnitt um die Behandlung der Funktionsaufrufe. Unser Ziel ist es, ein Programm so zu transformieren, dass es leicht in Maschinencode umgewandelt wird. Wenn wir uns noch einmal den naiven Interpreter ins Gedächtnis rufen, sehen wir, dass er zwar funktioniert, aber die Behandlung von Funktionen der interpretierenden Sprache überlässt:

type value =
    VInt of int
  | VFun of (value list -> value)

let exInt (VInt i) = i
let exFun (VFun f) = f
...

let rec eval e env =
  match e with
      ...
    | Function (x0, xs, e) -> VFun (function vs -> eval e (extends env xs vs))
    | Apply (e0, es) -> (exFun (eval e0 env)) (evals es env)

Um die Funktionsbehandlung abstrahieren, führen wir deshalb Closures ein, die die Funktionsumsetzung übernehmen:

type ident = string

type value =
    VInt of int
  | VClosure of ident list * expr * value env

let rec eval e env =
  match e with
      ...
    | Function (x0, xs, e) -> VClosure(xs, e, env) 
    | Apply (e0, es) -> 
        let VClosure (xs', e', env') = eval e0 env in
        let vs = evals es env in
        eval e' (extends env' xs' vs)

Lambda-Lifting

Immer noch ist es unser Ziel, ein Programm so zu transformieren, dass es leicht in Maschinencode umgewandelt werden kann. Geschachtelte Funktionen sind diesem Ziel aber abträglich. Deshalb soll sich dieser Abschnitt mit der Aufhebung von Schachtelung beschäftigen: Wir wollen alle Funktionen zu top-level Funktionen machen. Das Verfahren hierzu nennt sich Lambda-Lifting. Wir beginnen mit einer Illustration des Problems und fahren mit Methoden zur Behebung fort.

let i = 5 in
letrec f = λx. f (i + i) in
f (i * i)

(* naive, errorenous top-level transformation: 
   obviously i would not be defined in the first line *)
letrec f = λx. f (i + i) in
let i = 5 in 
  f (i * i)

(* use i as parameter *)
letrec f = λi. λx. f i (i + i) in
let i = 5 in
  f i (i * i)

(* real transformation: first introduce variables that are free within the function *)
let i = 5 in
letrec f = λi. λx. f i (i + i) in
  f i (i * i)

Diese einfachen Umformungen reichen aber in der Regel nicht aus, um alle Probleme zu beseitigen, da Funktionen und ihre Parameter verschränkt sein können:

let a = ... in
let b = ... in 
letrec f = λx. ... a ... g x
       g = λx. ... b ... f x
in 
f 42

(* transformed once by the previous mechanism this yields: *)
let a = ... in
let b = ... in 
letrec f = λa. λx. ... a ... g b x
       g = λb. λx. ... b ... f a x
in 
f a 42

(* as we can see, this is wrong: the functions have gotten their own free variables 
   as parameters, but at the same time new parameters are introduced for other 
   functions, creating new free variables within the first function. An additional 
   pass of the transformation yields a satisfying result: *)
let a = ... in
let b = ... in 
letrec f = λb. λa. λx. ... a ... g a b x
       g = λa. λb. λx. ... b ... f b a x
in 
f b a 42

Mit dem mehrfachen Transformieren, wie es im obigen Beispiel gezeigt wird, kann man also die Funktionen von freien Variablen befreien. Allerdings hat dieser naive, sukzessive Algorithmus kubische Laufzeit. Tatsächlich verwendet man deshalb folgenden Algorithmus:

Algorithmus

• Vorbereitungsschritt:
  • Benenne alle lokalen Definitionen so um, dass die Bezeichner programmweit eindeutig sind.
  • Alle Ausdrucksfunktionen erhalten einen eindeutigen Namen: function x -> e wird zu letrec f = function x -> e in f.
• Durchlaufe rekursiv das Programm mit Parameter F, der Menge der bereits bekannten, definierten Funktionen (zu Beginn ist F leer, beziehungsweise enthält alle vordefinierten Funktionen):

Nach diesem Durchlauf verarbeitet man dann rekursiv mit F = F'. Ausserdem nimmt man vorher eine Aufspaltung der letrecs in stark verbundene Komponenten vor, da ansonsten zu viele Variablen in sind, was ineffizient ist.

Der Weg zum Maschinencode

In diesem Abschnitt beschäftigen wir uns mit der weiteren Umformung des Codes, so dass er besser in Maschinencode gewandelt werden kann. Dazu werden drei Zwischenschritte vorgenommen:

1. Alle Zwischenergebnisse werden benannt.
2. Die Reihenfolge wird explizit gemacht.
3. Der Kontrollfluss wird explizit gemacht.

Wir beginnen mit der Programmrepräsentation, Programme sind jetzt rekursive Programmschemata:

Wir kommen nun zum ersten Zwischenschritt, dem Benennen der Zwischenergebnisse:

Benennen der Zwischenergebnisse

Unser Ziel beim Benennen der Zwischenergebnisse ist es, allen Werten, die in Registern gespeichert werden müssen, einen Namen zu geben. Wir bedienen uns dabei einer Transformationsfunktion :

Definition:

Der Wert b wird hierbei aus Kontextinformationen gewonnen, die vier Werte annehmen können:

• v - Kontext verlangt Variable
• f - Kontext verlangt Funktion
• l - Kontext ist let-Header
• t - Kontext hat keine Anforderungen

Mit Hilfe dieser Funktion können wir nun gegebene Programmabschnitte transformieren:

Um die Idee zu verdeutlichen, folgt ein Beispiel, in dem die Funktion power aus ihrer Originalfassung bis zu benannten Zwischenschritten umgeformt wird.

Explizite Reihenfolge

In dem Code, der aus dem Benennen der Zwischenergebnisse folgt, finden sich sehr viele verschachtelte let Blöcke. Um die Reihenfolge der Ausführung von Termen explizit zu machen, werden diese "nach oben gezogen", oder "geplättet". Das Verfahren nennt sich let flattening, es verwendet lokale Transformationsregeln, die so lange angewendet werden, bis alle Möglichkeiten der Anwendung erschöpft sind.

Wir betrachten dazu folgende Werte:

Lasse v über die Werte von laufen. Mit diesen Werten können wir nun die Transformationsregeln angeben:

</div>

Expliziter Kontrollfluss

In diesem letzten Zwischenschritt auf dem Weg zum Maschinencode wollen wir den Kontrollfluss explizit machen. Hier geht es um die Kontrolltransitionen, die am Ende von Funktionen ("return") und in Konditionsblöcken ("if-then-else") entstehen. Unser Ziel ist es, diese Kontrolltransitionen im Code explizit zu machen, und insbesondere zu zeigen, wohin wir springen, nachdem ein Block beendet wurde.

Wir beginnen dazu mit der Einführung einer neuen Programmbeschreibung, um die Unterscheidung von Ausdrücken in triviale und komplizierte (serious) zu ermöglichen.

Der Ausdruck dient dazu, eine Zieladresse für den Sprung aus einem Konditionalblock festzulegen. Die Funktion k repräsentiert dieses Ziel und wird mit dem yield Ausdruck ausgeführt. Das Verhalten dieser Transformation (Definition weiter unten) lässt sich am besten an unserem power Beispiel betrachten:

Wie man hier sieht, ist k nichts anderes als eine continuation, wie wir sie schon bei der Benutzung von von Continuation-Passing Style kennen gelernt haben. Um ein Programm in die oben dargestellte Form umzuwandeln, können wir die Funktion benutzen. k ist hier entweder 0, um eine top-level continuation anzuzeigen (also ein "return") oder eine von letcont eingeführte continuation.

Definition:

Nachdem wir diese Definition erhalten haben, können wir noch einmal einen genaueren Blick auf das Beispiel von eben werfen: Man kann sich fragen, warum wir überhaupt die continuation eingeführt haben. Die Ineffizienz, die daruch entsteht, dass wir erst aus dem Konditionalblock und dann aus der Funktion springen, lässt sich durch ein Ersetzen der durch returns erreichen:

</div>

Während sich Funktionen wie power mit bisherigen Methoden gut optimieren lassen, gibt es noch einige Dinge, die man verbessern kann. Folgende Funktion down zeigt ein Optimierungsproblem mit Endrekursion auf, selbst nachdem sie mit den bei power genutzten Methoden verbessert wurde:

down n = if n=0 then 1 else down (n-1)

</div>

Das Auffangen und sofortige Zurückgeben des Aufrufs von down ist nicht besonders effizient. Es ist aber mit gegebenen Mitteln möglich, die Funktion umzuformen, so dass sie korrekte Endrekursion benutzt (hierbei springt die aufgerufene Funktion nicht zum unmittelbaren Aufrufenden zurück, sondern zum letzten Aufrufenden ohne Endrekursion):

</div>

Implementation

Die in den vergangenen Abschnitten behandelten Zwischenschritte auf dem Weg zum Maschinencode können in einem einzigen Durchlauf implementiert werden (one pass transformation). Der entsprechende Algorithmus wird hier in Form von OCaml Code dargestellt.

Zu Beginn stellen wir die Typen vor, die von unseren Funktionen genutzt werden:

(* source calculus *)
type exp =
    Var of ident
  | Const of ident
  | Pure of ident * exp list
  | Oper of ident * exp list
  | Vector of exp list              (* <exp, ..., exp> *)
  | App of exp * exp
  | Let of ident list * exp * exp
  | If of exp * exp * exp
  | Close of exp * exp              (* f$z *)

type definition =
  ident * ident list * ident * exp  (* f = λ^$<exp,...exp>. λx. e *)

type scheme =
  definition list * exp


(* target calculus *)
type trivial =
    TVar of ident
  | TConst of ident
  | TPure of ident * trivial list
  | TClose of ident * ident

type header =
    HTriv of trivial
  | HOper of ident * ident list
  | HApp3 of ident * ident * ident
  | HVect of ident list

type serious =
    SReturn of ident
  | SApp3 of ident * ident * ident         (* tail call to function  f$z (y) *)
  | SLet of ident list * header * serious  (* SLet(...HApp3...) - ordinary call to function *)
  | SIf of ident * serious * serious
  | SLetCont of kident * ident list * ident * serious * serious
  | SYield of kident * ident

type xDefinition =
  ident * ident * ident * serious


(* identifiers, including functions to create fresh names which aren't yet in use *)
type ident =
    StrId of string
  | NumId of string * int

type kident =
  ident

let fresh_counter =
  ref 0

let fresh_int () =
  begin
    fresh_counter := !fresh_counter + 1;
    !fresh_counter
  end

let fresh prefix =
  NumId (prefix, fresh_int ())

let freshL ps =
  List.map fresh ps

type xScheme =
  xDefinition list * serious

Wir kommen nun zu dem Hauptteil der Transformation, der Funktion toSerious, die Ausdrücke vom Typ exp in komplizierte (serious) Ausdrücke übersetzt.

(* toSerious : (string * string) list -> exp -> (ident −> serious) −> serious *)
(* subst is a variable renaming, e an expression to be transformed 
   and c a continuation *)

let rec toSerious subst e c =
  match e with
      Var i ->
        c (rename i subst)
    | Const p ->
        let fr = fresh "t" in
        SLet ([fr], HTriv (TConst p), c fr)
    | Pure (p, es) ->
        toTrivialL subst es
          (fun ts ->
            let fr = fresh "t" in
            SLet ([fr], HTriv (TPure (p, ts)), c fr))
    | Oper (o, es) ->
        let fr = fresh "t" in
        toSeriousL subst es
          (fun is ->
            SLet ([fr], HOper (o, is), c fr))
    | App (Close (e1, e2), e) ->
        toSerious subst e1
          (fun x1 ->
            toSerious subst e2
              (fun x2 ->
                toSerious subst e
                  (fun x3 ->
                    let fr = fresh "t" in
                    SLet ([fr], HApp3 (x1, x2, x3), c fr))))
    | App (f, e) ->
        toSerious subst f
          (fun ff ->
            toSerious subst e
              (fun ee ->
                 let [frf; frc; fr] = freshL ["t"; "t"; "t"] in
                 SLet ([frf; frc], HTriv (TVar ff),
                 SLet ([fr], HApp3 (frf, frc, ee), c fr))))
    | Let ([x], e1, e2) ->
        toSerious subst e1
         (fun xx ->
           toSerious ((x, xx) :: subst) e2 c)
    | Let (xs, e1, e2) ->
        toSerious subst e1
          (fun xx ->
            SLet (xs, HTriv (TVar (xx)), toSerious subst e2 c))
    | If (e1, e2, e3) ->
        toSerious subst e1
          (fun x1 ->
            let [kk; xx] = freshL ["k"; "t"] in
            let body = c xx in
            SLetCont
              (kk, remove xx (free_serious body), xx, body,
               SIf
                 (x1,
                   toSerious subst e2 (fun i ® SYield (kk, i)),
                   toSerious subst e3 (fun i ® SYield (kk, i)))))
    | Close (e1, e2) ->
        toSerious subst e1
          (fun x1 ->
             toSerious subst e2
               (fun x2 ->
                 let fr = fresh "t" in
                 SLet ([fr], HTriv (TClose (x1, x2)), c fr)))
    | Vector (es) ->
        toSeriousL subst es
          (fun xs ->
            let fr = fresh "t" in
            SLet ([fr], HVect( xs), c fr))

</div>

Wir brauchen noch die Funktion toTrivial - sie hat fast die gleiche Signatur wie toSerious, der einzige Unterschied ist das Argument der continuation, die einen trivialen Term anstelle eines Bezeichners erwartet. Die Funktion inspiziert alle Fälle, in denen sie einen trivialen Term konstruieren kann und gibt sonst an toSerious weiter.

(* toTrivial : (string * string) list -> exp -> (trivial −> serious) −> serious *)
and toTrivial subst e c =
  match e with
      Var i ->
        c (TVar (rename i subst))
    | Const p ->
        c (TConst p)
    | Pure (p, es) ->
        toTrivialL subst es
          (fun ts ->
            c (TPure (p, ts)))
    | _ ->
        toSerious subst e
          (fun xx ->
            c (TVar xx))

</div>

Die Implementationen von toTrivialL und toSeriousL sind einfach und finden sich in Trafo.pdf. Des weiteren übernimmt der oben angegebene Algorithmus noch nicht die Auflösung der Endrekursion - dazu benötigen wir eine modifizierte Version der toSerious Funktion, die nur die top-level Funktionen bearbeitet und auf Seite 91/15 in Coco-Lambda-Trans.pdf besprochen wird.

Codeerzeugung

Übersicht

Vorbereitung: Transformation des Codes

Konstantenpropagierung

Zuerst werden triviale Ausdrücke symbolisch ausgewertet.

Bei einer Variablenbindung der Form

let x = c in e

werden die Terme der Form

reduziert.

let x = Vector() in e
let  = x in e'

Danach wird der nutzlose (weil z.B. nicht ausgeführte) Code entfernt. Beispielsweise ist let x = h in e nutzlos, falls h ein trivialer Ausdruck oder ein Vektor mit ist.

Instruktionsauswahl

Abbildung trivialer Ausdrücke, Header und wichtiger Ausdrücke (Serious) auf Assembler-Befehle.

• Serious: Jeder Term entspricht einer Folge von Assembler-Befehlen
• trivialer Ausdruck: zwei verschiedene Verfahren (greedy und optimal)
• -viele Register
• wir ignorieren vorerst das Retten von Registern über Funktionsaufrufe

Konkret für MIPS-Assembler:

• RISE, LOAD/STORE
• 32 GPRs (General Purpose Registers)
• Sonderregister: PC, ..., HI, LO
• Koprozesor: FPU

siehe Instruktionsauswahl durch Patternmatching

Lebendigkeitsanalyse

siehe Lebendigkeitsanalyse

Registerzuteilung

siehe Registerallokation

Instruktionsauswahl durch Patternmatching

Idee:

• beschreibe Instruktionen durch Fragmente von trivialen Ausdrücken
• jede Instruktion / jedes Fragment ist mit Kosten assoziiert, beispielsweise die Anzahl der Maschinenzyklen für die Ausführung
• bestimme dann die Abdeckung eines trivialen Ausdrucks aus Fragmenten mit minimalen Kosten.

2 grundliegende Algorithmen:

• greedy
  • top-down-Patternmatching der Fragmente auf den Eingabeausdruck
  • Pattern dürfen überlappen
  • Pattern aufsteigend nach Kosten geordnet
    einfach (durch Ocaml-Patternmatching, findet aber nicht die Abdeckung mit minimalen Kosten
  • Appell: "optimal cover" (2 aufeinandertreffende Fragmente können nicht durch ein Fragment mit geringeren Kosten ersetzt werden

• dynamische Programmierung
  • verwende Baumgrammatik mit Attributen ( Verallgemeinerung von kontextfreien Grammatiken)
    • Menge von nichtterminalen Symbolen können Attribute mit sich führen
    • Produktionen der Form , wobei Blätter auch Nichtterminale sein können.

<div> ::= VAR(id)
        | ADD (<div>,<div>)
        | CONST(id)

ADD(VAR "x", CONST "1")

Auf der rechten Seite der Grammatikregel ist auch ADD(τ, CONST(1))ADD(VAR(id),CONST(1)) erlaubt, mit τ als Nichtterminal und VAR(id)

Jede Regel hat außerdem Kosten mit sich assoziiert.

Nichtterminale können folgende Attribute besitzen:

• Liste der Instruktionen
• simulierte Kosten
• Wert von Konstanten
• Registernamen

Aufgabenstellung Vorliegender Term/Ausdruck/Baum soll auf sein Startsymbol reduziert werden Parsen des Terms !

Verfahren:

• Bottom-Up Durchlauf durch den Baum
• lege an jedem Knoten die Liste der matchenden Nichtterminale ab
• für jedes Nichtterminal ist nur das mit minimalen Kosten interessant
  Autoren-Anmerkung(Firefox): Vielleicht sollte das eigentlich "für jede Liste ist nur das NT mit den geringsten Kosten..." bedeuten. In beiden Quellen allerdings identisch so formuliert
• Matchen (am Knoten)
  • Knotennamen müssen gleich sein
  • falls rechte Seite suche in den Kinderknoten
  • falls erfolgreich:
    • berechne Kosten
    • verkette Codesequenzen
    • hänge attribuiertes Nichtterminal an den Knoten des Subjektterms an.
      Autoren-Anmerkung(Firefox): Was ist ein Subjektterm ?

Lebendigkeitsanalyse

siehe Appel: Modern Compiler Implementation in ML, Kapitel 10

Zustand des übersetzten Programs

• Folge von Instruktionen über Pseudoregister
• Annahme: Maschine mit unendlich vielen Registern
• Reale Maschine: endlich viele Register

Gesucht: Abbildung Pseudoregister reale Register, sodass 2 unterschiedliche Pseudoregister nur dann auf ein reales Register abgebildet werden, wenn sie nicht gleichzeitig benutzt werden.

• Lebendigkeit formuliert diese Eigenschaft
• Analyse der Lebendigkeit ist ein Beispiel für statische und semantische Analyse.

Die Analyse wird auf einem Kontrollflußgraphen (KFG) durchgeführt:

entry I 1 a: = 0 II 2 b: = a + 1 III 3 c: = c + b IV 4 V 5 a < N VII VI 6

Kante a b c I 0 0 x II x 0 x III 0 x x IV 0 x x V x 0 x VI 0 0 x VII x 0 x

Kontrollflußgraphen

Definition

Ein Kontrollflußgraph ist ein markierter gerichteter Graph. Die Markierungen sind entry, exit, return c, a <rel_op> b, a: = e. Jede Instruktion liefert einen Knoten.

Kanten

Über die eingehende Kanten werden mit pred(n) die Nachfolgerknoten erreicht; über die ausgehenden Kanten erhält man mit succ(n) die Vorgängerknoten.

Verhalten bei Konstruktion

• use[n]: Menge der Pseudoregister die von Knoten n verwendet werden.
• def[n]: Pseudoregister die von Knoten n definiert (und überschrieben) werden.

Instruktion	use[n]	def[n]
return c	{c}
a <rel_op> b	{a,b}
a:=e	Regs(e)	{a}
entry,exit

Lebendigkeit

Definition

Daraus ergeben sich die Datenflussgleichungen für die Lebendigkeit:

Die Lösung der Gleichungen erhalten wir durch Fixpunktiteration

Für die Rückwärtsanalyse müssen wir einfach die Zeilen 8 und 9 vertauschen.

Beispiel

	1		2		3
	in	out	in	out	in	out	...
1				a		a	...
2	a		a	c,b	a,c	c,b	...
3	c,b		c,b	b	c,b	b	...
4	b		b	a	b	a	...
5	a	a	a	c,a	a,c	c,a	...
6	c		c		c		...

Rückwärtsanalyse: Information wird gegen den Kontrollflußgraph propagiert.

	1		2
1	a	a,c	c	a,c	...
2	a,c	c,b	a,c	b,c	...
3	c,b	b,c	b,c	b,c	...
4	b,c	a,c	b,c	a,c	...
5	a,c	c	a,c	a,c	...
6	c		c		...

Komplexität

Grundoperationen Mengenrepräsentation

N: = Größe des Programms (Anzahl an Instruktionen), W: = Wortbreite

Operation	Bitvektor	geordnete Liste (ohne Wiederholungen)
Platzbedarf		N
Kopieren	O(N)	O(N)
	xor: O(N)	O(N)
	and/neg: O(N)	O(N)
	Vorteilhaft bei nichtbesetzten Mengen	Vorteilhaft bei sparsam besetzten Mengen ( Elemente)

Anzahl an Variablen

• erste Schleife: O(N²)
• innere Schleife: O(N²)
• repeat Schleife: O(N^N)

Die Datenflussgleichungen haben eine kleinste Lösung (wegen der Monotonie). Jede Lösung kann durch eine Variable, die nirgends definiert wird vergrößert werden. Es existiert keine eindeutige Lösung, aber aus der Monotonie kann eine eindeutige, kleinste Lösung gefolgert werden.

Für jede tatsächliche Lösung L1/L0 der Datenflussgleichungen gilt folgende Invariante der repeat-Schleife:

(informeller) Beweis:

• bei Betreten der Schleife: ok
• 
• 

Der Algorithmus findet also die kleinste Lösung, da beim Verlassen der repeat-Schleife die Datenflussgleichungen erfüllt sind.

Registerallokation

Interferenzgraph

Bemerkung: Weitere Constraints können durch den Interferenzgraph ausgedrückt werden:

• falls eine Instruktion ist, deren Ergebnis nicht im Register z erzeugt werden kann, dann
  • verwende Pseudoregister dem z direkt zugeordnet ist
  • 
• Caller-Save-Register werden als Def[Call-Instruktionen] betrachtet
  Interferenz zwischen den Caller-Save-Registern und den lebendigen Registern
  Lebendige Register Caller-Save-Register oder Speicher

Zurückführung auf Graphfärbung des Interferenzgraphen.
Farbe Maschinenregister
Färbung ist Abbildung von Knoten(IG) auf Menge der Farben, sodass benachbarte Knoten unterschiedliche Farben erhalten

k Maschinenregister k-Färbung gesucht.

Probleme:

• k-Färbung zu finden ist NP-Vollständig.
• falls eine k-Färbung nicht möglich ist müssen Pseudoregister im Speicher abgelegt werden. (Spilling)

Algorithmus

Build

• Erstelle den Interferenzgraphen.
• Erzeuge einen Stack

Simplify

• wähle Knoten v mit Grad(v) < k
• entferne v und push v (alle Kanten zu v werden ebenfalls entfernt und reduzieren dadurch den Grad anderer Knoten)
• wiederhole solange wie möglich. Danach gibt es nur noch Knoten v mit (oder gar keine)

Spill

• wähle Knoten v mit
• markiere v als "potential spill"
• entferne v und push v (alle Kanten zu v werden ebenfalls entfernt und reduzieren dadurch den Grad anderer Knoten)
• zurück zu Simplify und solange wiederholen bis der Interferenzgraph leer ist.

Select

• let v = pop
• falls v durch Simplify entfernt wurde (also keine Markierung trägt) wähle eine Farbe für v
• falls v durch Spill entfernt wurde (also mit "potential spill" markiert ist) und färbbar ist , färbe v
• ansonsten wird v als "actual spill" markiert und eine Speicherzelle dafür alloziiert. Außerdem wird der Code geändert:
  • STORE nach jeder Definition von v
  • LOAD vor jeder Benutzung von v
• wiederhole bis der Stack leer ist.

End

Entweder ist der Stack nun leer und kein "actual spill" ist aufgetreten, oder der Code des Programms wurde geändert und der Algorithmus muss nochmal von Anfang an ausgeführt werden.

Vorgefärbte Register

• Pseudoregister, die von vornherein bestimmten Registern zugeordnet sind (Argumentregister, Multiplikationsergebnis, etc.)
• jedes vorgefärbte Register interferiert mit jedem anderen
• dürfen nicht gespillt werden ( Lebensbereiche klein halten mit MOVE) und werden von Simplify zuletzt gewählt damit Select ihnen zuerst die gewünschten Farben zuordnen kann.

Behandlung von MOVE / Coalescing (Verschmelzen)

• Die Instruktion r:=s kann eliminiert werden falls
• die zugehörigen Kanten im Interferenzgraphen werden verschmolzen Der Grad erhöht sich Die Färbbarkeit wird beeinträchtigt.

Vor Verschmelzung: 2-färbbar

Nach Verschmelzung: 3-färbbar

Also: Konservative Strategie

Verschmelze nur Register mit insgesamt nicht weniger als k Nachbarn mit damit die k-Färbbarkeit erhalten bleibt.

Denn:(hinreichendes Kriterium)

Nach Entfernen der Kanten vom Grad < k (Simplify) verbleiben höchstens Nachbarn mit , also hat der verschmolzene Knoten einen Grad < k und kann somit von Simplify entfernt werden.

Registerallokation mit Verschmelzen

Build

• Erstelle den Interferenzgraphen.
• Erzeuge einen Stack
• markiere v und s als "move-related".

Simplify

• wähle unmarkierten Knoten v mit Grad(v) < k (berücksichtige obrige Bemerkungen zur Verschmelzung)
• entferne v und push v (alle Kanten zu v werden ebenfalls entfernt und reduzieren dadurch den Grad anderer Knoten)

Coalescing

• wähle markierten Knoten und verschmelze ihn mit "MOVE-Partner" (falls der Gesamtgrad < k ist )
• entferne MOVE
• entferne Markierung, falls der verschmolzene Knoten nicht mehr an MOVE beteiligt ist
• gehe zu Simplify und wiederhole

Freeze

• wähle markierten Knoten v mit Grad(v) < k
• MOVE bleibt erhalten, Markierung wird entfernt
• gehe zu Simplify und wiederhole

Spill

• wie im normalen Algorithmus (Spill)
• gehe zu Simplify und wiederhole bis der Graph leer ist

Select

• wie im normalen Algorithmus (Select)

Registerallokation für Ausdrücke (Baumstruktur)

Baumstruktur

Baumstruktur

t₁ braucht m Register

t₂ braucht n Register

if max(m,n+1) > max(m+1,n)

then t₁ zuerst

else t₂ zuerst

Garbage Collection

In einem fertigen Programm ist die Garbage Collection (Müllentsorgung, GC) dafür zuständig, nicht mehr benutzte Objekte aus dem Speicher zu entfernen, um Platz für neue zu schaffen. Sie ist nicht automatisch Teil jeden Programms, sondern eine Optimierung, respektive Automatisierung.

Die Speicherverwaltung kann man in zwei Bereiche unterteilen:

• lokale Variablen, Rücksprungadressen
  • Lebensdauer entspricht Funktionsaufruf
  • Anlegen auf dem Stack, Freigabe ist billig (Zurücksetzen des Stackpointers)
• Closures, Vektoren, Objekte, dynamische Datenstrukturen
  • Lebensdauer unabhängig von Funktionsaufruf
  • Ablage auf Stack nicht möglich
  • Stattdessen Ablage im Heap

Bei der GC werden wir uns deshalb mit den im Heap abgelegten Objekten beschäftigen. Im Gegensatz zur manuellen Heapverwaltung (malloc/free, mit Gefahr von memory leaks, bzw. Fehlerpointern) legt man bei der GC die Objekte lediglich an, und die GC erledigt das Verwerfen automatisch.

Wir beginnen das Kapitel mit einer allgemeinen Einführung in die GC und werden dann einige Algorithmen vorstellen, um sie zu realisieren.

Allgemein

Die Garbage Collection hat zwei Aufgaben:

1. Feststellen, welche Objekte im Heap noch lebendig (werden noch benutzt) sind.
2. Freigeben der toten Obejkte.

Aufgabe 1 ist leider unentscheidbar (nach dem Satz von Rice). Wir können allerdings eine Approximation verwenden: Alle Objekte, die vom Stack und globalen Variablen (zusammen: Wurzeln) erreichbar sind, werden noch verwendet (sind lebendig). Dies ist eine sichere Approximation, da alle anderen Objekte nicht mehr durch eine Zeigerkette von der Wurzel aus erreicht werden können.

Um festzustellen, ob ein Objekt lebendig ist, müssen wir demnach den Zeigern folgen. Allerdings folgt daraus ein Problem: Wir müssen die Zeiger kennen. Das ist ein Problem, weil nicht jede Speicherzelle einen Zeiger enthält und bei manchen Sprachen die Eigenschaft, Zeiger zu sein, nicht statisch vorhersagbar ist (bei polymorphen Funktionen in OCaml beispielsweise).

Die Lösung für das Zeigererkennungsproblem nennt sich Tagging und verwendet 1-2 Bits zur Angabe des Typs:

Mark & Sweep

Mark & Sweep benutzt eine sogenannte Freelist um freie Speicherbereiche zu markieren. Neue Objekte werden in einen freien Speicherbereich eingefügt, Adressen nicht mehr benutzter Objekte bei der Garbage Collection der Freelist hinzugefügt. Mark & Sweep (inklusive nichtrekursiver Tiefensuche) wurde schon in Lisp eingesetzt, es ist eine Technik der 60er Jahre.

Allokation

Wir gehen davon aus, dass alle aktuell freien Speicherbereiche bereits in der Freelist verkettet sind. Wir suchen dann einen passenden Bereich in der Freelist und entfernen ihn aus dieser, nachdem das Objekt dort eingefügt wurde.

Bei der Allokation können zwei Probleme auftauchen, wenn kein passender Speicherbereich vorhanden ist:

• Alle Speicherbereiche sind zu klein, obwohl in der Summe ausreichend Speicher vorhanden ist (externe Fragmentierung). In diesem Fall führt man Garbage Collection mit Verschmelzen von benachbarten Speicherbereichen durch. Dies muss aber nicht zum Ziel führen, da Mark & Sweep nicht kompaktifiziert.
• Alle Speicherbereiche sind zu gross. Tritt dieser Fall ein, muss man einen Speicherbereich aufspalten und nur teilweise verwenden. Es bleibt ein ungenutzter Rest (interne Fragmentierung), die Aufspaltung provoziert auch externe Fragmentierung.

Garbage Collection

Die Garbage Collection läuft in zwei Schritten ab:

1. Tiefendurchlauf beginnend mit den Wurzeln, markiere alle besuchten Objekte (mark).
2. linearer Durchlauf des Heaps (sweep):
   • nichtmarkierte Objekte kommen in die Freelist
   • bei markierten Objekten wird die Markierung entfernt

Ein Nachteil von Mark / Sweep ist die kostspielige rekursive Tiefensuche: sie verbraucht Stackplatz proportional zur Heapgröße - zu einer Zeit, wo der Heap voll ist. Man nutzt deshalb die Technik der nichtrekursiven Tiefensuche (Schorr-Waite). Die nichtrekursive Tiefensuche codiert den Stack in den Objekten durch Zeigerumkehrung mit zwei Zeigern:

Mark & Sweep benötigt mit nichtrekursiver Tiefensuche konstanten Platz und eine lange Laufzeit.

Reference Count

Genau wie beim Mark & Sweep Algorithmus benutzt Reference Count eine Freelist. Beim Reference Count-Algorithmus besitzt jedes Objekt ausserdem einen Zähler, der die Anzahl der Zeiger auf das Objekt nachhält. Bei Operationen auf den Zeigern wird der Zähler angepasst:

• jedes Kopieren eines Zeigers führt zur Inkrementierung des Zählers
• jedes Verwerfen eines Zeigers führt zur Dekrementierung des Zählers

Falls der Zähler eines Objektes auf 0 fällt, wird das Objekt in die Freelist eingehängt.

Diese Verfahren ist langsam, benötigt zusätzlichen Code und Speicherzugriffe. Ein weiteres Problem ist, dass es zyklische Datenstrukturen nicht verarbeiten kann:

Um das Problem der zyklischen Datenstrukturen zu beheben, kann man zusätzliche Läufe von Mark & Sweep einsetzen.

Copying Collection

Die Copying Collection nutzt keine Freelist, sondern teilt den Heap in zwei Hälften gleicher Größe auf: FROMSPACE und TOSPACE. Der Algorithmus läuft dann wie folgt:

• Allokation wird linear fortlaufend im FROMSPACE vorgenommen.
• Ist der FROMSPACE gefüllt, wird die Garbage Collection durchgeführt:
  • Beginnend bei den Wurzeln werden erreichbare Objekte in den TOSPACE kopiert.
  • Danach ist der FROMSPACE leer, die Rollen von FROMSPACE und TOSPACE werden getauscht.

Beim Kopieren der Objekte vom FROMSPACE zum TOSPACE während der Garbage Collection ändern sich alle Adressen, dies wird mit Hilfe von Umleiten gelöst. Der Algorithmus zum Anpassen eines Objektes (verschiebt Kind-Objekte) lässt sich so ausdrücken:

forward(p) =
  if p  TOSPACE then
    return p 
  else
    if p -> f_1  TOSPACE then
      return p -> f_1
    else
      foreach  f_i:
        next -> f_i = p -> f_i
      p -> f_1 = next
      next += size(p)
      return p -> f_1

</div>

Cheneys Algorithmus

Cheneys Algorithmus stellt eine Verbesserung der Copying Collection dar:

Auch mit Cheneys Algorithmus gibt es Nachteile beim Einsatz von Copying Collection. Sie hat doppelten Speicherbedarf und zerstört durch das Kopieren (Breitensuche!) die Lokalität, was das Caching schwierig macht.

Generationed Collection

Generational Collection nutzt ein ähnliches Prinzip wie die Copying Collection, nur werden aufgrund einiger Beobachtungen mehr als zwei Speicherbereiche genutzt:

• die meisten Objekte sind jung
• Objekte, die schon mehrere GC überlebt haben, leben vermutlich noch länger

Damit die Garbage Collection effektiver wird, werden bei Generational Collection die jüngeren Objekte häufiger getestet, und der Heap in eine Reihe von Speicherbereichen aufgeteilt, die dem Alter der Objekte entsprechen.

Neue Objekte werden in G₀ alloziert. Falls G₀ voll ist, führt man eine Copying Collection auf G₀ aus, mit G₁ als TOSPACE. Wurde G₀ häufig genug geleert oder sind G₀ und G₁ voll, führt man die Garbage Collection auf G₀ und G₁ aus: .

Die Größe der G_i wird oft exponentiell größer gesetzt.

Garbage Collection

Wurzeln sind alle Objekte im Stack, globale Variablen sowie alle Objekte, die in "älteren" Generationen (als diejenigen im FROMSPACE) liegen, und "junge" Objekte referenzieren.

Beobachtung zeigt, dass alte Objekte selten auf junge zeigen, da dies nur durch "späte Zuweisung" möglich ist. Um herauszufinden, welche Objekte aus "älteren" Generationen referenziert werden, gibt es verschiedene Methoden:

• Remembered Set: Jedes Update eines alten Objekts trägt die geschriebene Adresse in ein Remembered Set ein.
• Card Marking: Teile die G_i in Blöcke der Größe 2^k ein. Beim Update markiere in einem Bitvektor den betroffenen Block, bei GC betrachte alle Altobjekte des markierten Blocks als Wurzeln.
• Page Marking: Verwende die Blöcke des virtuellen Speichers; markiere Blöcke aus alten Generationen als schreibgeschützt. Wird ein altes Objekt verändert, gibt es einen memory fault: fange diesen ab und markiere Block im Bitvektor.

Inkrementelle Garbage Collection

Alle bisher betrachteten Versionen von Garbage Collection haben das Problem, dass sie bei der Durchführung das laufende Programm anhalten müssen. Dieses Verhalten ist insbesondere in Echtzeitumgebungen unerwünscht. Eine Abhilfe schafft die inkrementelle Garbage Collection. Sie nutzt zwei Teile:

• den Mutator, ein Programm, das die Arbeit macht, Objekte anlegt und verändert und
• den Collector, der den Speicher bereinigt.

Es gibt zwei Varianten der inkrementellen Garbage Collection, die erste heisst einfach inkrementelle Garbage Collection: Hier stößt der Mutator den Collector an, der einen Teil der Garbage Collection erledigt. Die zweite Version ist die nebenläufige Garbage Collection, in der Mutator und Collector gleichzeitig arbeiten.

Grundlage aller inkrementeller Garbage Collection bildet ein 3-Farben Markierungsschema, das den Verarbeitungsstatus eines Objektes aus Sicht des Collectors beschreibt:

• weiß bedeutet, dass das Objekt noch nicht besucht wurde,
• ein graues Objekt wurde besucht, aber noch nicht alle seiner Kinder (bei Mark & Sweep etwa: Objekt befindet sich auf dem Stack, bei Cheney: in j-ter Queue, also zwischen scan und next),
• ein schwarzes Objekt wurde besucht und ebenso alle seine direkten Kinder (d.h diese sind entweder grau oder schwarz).

Allokation

Zur Allokation eines Objektes mit N Worten kann man folgendes Schema nutzen:

Garbage Collection

Es gelten zwei Invarianten für den Mutator und den Collector:

• ein schwarzes Objekt zeigt nie auf ein weißes
• jedes graue Objekt ist in der Datenstruktur des Collectors

Collector

Es gilt: Alle Objekte sind weiß, Wurzeln befinden sich in grauen Wurzelobjekten.

Dann verfolgt der Collector dieses Vorgehen:

Mutator

Für den Mutator gibt es verschiedene Möglichkeiten:

• Jedes Update wird instrumentiert mit einem Test, ob ein weißes Objekt in ein schwarzes Objekt geschrieben wird: wenn dies geschieht, muss man das schwarze Objekt in der Datenstruktur des Collectors grau färben (write barrier: Software oder Hardware).
• Der Collector markiert Seiten, die nur schwarze Objekte enthalten. Bei Schreibzugriff wird die ganze Seite grau gefärbt.
• Wenn der Mutator auf Objekt b zugreift, färbt er es grau und verschiebt es in die Datenstruktur des Collectors, also kann Invariante 1 nie verletzt werden (read barrier).

Bahrers Algorithmus

Der Algorithmus von Bahrer ist eine inkrementelle Version von Cheneys Algorithmus. Er hat eine zusätzliche Invariante zu den beiden inkrementellen Invarianten:

• Der Mutator benutzt nur TOSPACE Zeiger.

Die Garbage Collection läuft dann folgendermassen ab:

Verfahren: Bahrers Algorithmus

Die Allokation findet findet im TOSPACE in einem zusammenhängenden Speicherbereich statt, der durch next und limit begrenzt ist (siehe Illustration).

1. FLIP:
   • vertausche FROMSPACE und TOSPACE
   • leite alle Wurzeln um (in den TOSPACE)
2. bei jeder Allokation:
   • leite einige Zeiger um (inkrementeller Part)
   • lege neues Objekt am Ende des TOSPACE ab
3. bei jedem Feldzugriff könnte ein Zeiger auf ein weißes Objekt benutzt werden - falls der Wert des Feldzugriffs in den FROMSPACE zeigt, wird das Objekt in den TOSPACE umgeleitet.
4. pausiere, falls scan = next (siehe Illustration)

Interface zum Compiler

Die Garbage Collection wird im Compiler vorbereitet. Er kümmert sich um die Anpassung von

• Allokation
• Datenlayout von Heapobjekten (zum Finden/Markieren von Zeigern)
• Wurzeln
• Code für read/write Barrieren

Glossar

Den Glossar findet man auf einer eigenen Seite.

Literatur & externe Links

Literatur

• Wilhelm & Maurer: Übersetzerbau. Theorie, Konstruktion, Generierung deutsch, für Background
• Aho, Sethi & Ullman: Compilers: Principles, Techniques, and Tools "Drachenbuch"
• Appel: Modern Compiler Implementation in ML

externe Links

• Wikipedia:Compilerbau
• Wikipedia:Compiler
• Seite der FH Regensburg über ihre Vorlesung Compilerbau mit einem leicht verständlichen Lehrbuch
• Prof. Dr. Peter Thiemanns Spezialvorlesung Compilerbau am Institut für Informatik der Universität Freiburg aus dem
  • WS 2006/2007
  • WS 2004/2005
  • WS 2001/2002
• Dr. Michael Sperber, Wilhelm-Schickard-Institut
  • Compilerbau WS 2001/2002

nicht aufgelöste Quellen

• Bochmann Normal Form: [Boc78]