Mini-HowTo für BFE


BURG ist ein Übersetzerbau-Werkzeug für die Code-Generierung, das die Befehlsauswahl durchführt. D.h., es wird versucht eine bestmögliche Sequenz von Befehlen in der Zielsprache zu generieren.

Die Code-Generierung wird als Baumgrammatik-Problem formuliert. Ein Baum, der die Programm-Semantik darstellt, wird mit Hilfe einer mehrdeutigen Baum-Grammatik geparst. Unterschiedliche Ableitungsregelen entsprechen unterschiedlichen Varianten der Code-Erzeugung. Der Baum-Parser von BURG findet aber die Baum-Ableitung mit minimalen Kosten.

Beispiel: Wir haben eine Summe zu berechnen, die aus Konstanten und Variablen besteht. Die Zielmaschine besitzt eine beliebige Anzahl von Registern (r0,r1,...) und folgende Befehle:

  1. Laden einer Variable in ein Register r<k> = var <var>
  2. Laden einer Konstante in ein Register r<k>= cons <value>
  3. Addieren von zwei Registern r<x>=r<y>+r<z>
  4. Addieren von einem Register und einer Konstante r<x>=r<y> + cons <value>
  5. Einen Return-Befehl return r<k>, der den Summenwert bekannt  gibt.

Die Summe 3 + 5 + a würde folgende Befehlssequenz berechnen:
     r0 = cons 3
     r1 = cons 5
     r2 = var a
     r3 = r0 + r1
     r4 = r3 + r2
     return r4
Leider ist obige Befehlssequenz nicht optimal. Eine kürzere Sequenz wäre wünschenswert.

Um Burg verwenden zu können, müssen wir die Summe als Baum darstellen. Die Knoten des Baums haben drei unterschiedliche Typen:
Konstante, Variablen oder Additionsoperationen mit jeweils zwei Nachfolgern. NB: Der Typ eines Knotens wird in der Baum-Grammatik als Terminal bezeichnet.

Beispiel: Unsere Summe 3 + 5 + a können wir als Baum darstellen. Als Terminale haben wir Konstante(CONS), Variablen(VAR) und Additionsoperationen(ADD). Der Baum für das Beispiel 3 + 5 + a sieht folgendermaßen aus:

 
Im nächsten Schritt entwickeln wir eine Baum-Grammatik. Eine Baum-Grammatik besteht aus Terminale, Nonterminale, Produktionen und
einem Start-Symbol. Ein Nonterminal beschreibt einen Teilbaum und besitzt eine oder mehrere Produktionen. Die rechte Seite der
Produktion ist entweder ein Terminal (i.e. Knoten mit konkretem Typ) oder ein Nonterminal. Falls es ein Terminal ist, werden die Nachfolgeknoten auch noch spezifiziert.

Zusätzlich werden für Produktionen Kosten und Aktionen angegeben. Die Kosten werden benötigt, um die minimale Ableitung des Baums zu finden. In der Aktion wird der Code für die Zielsprache generiert.

Wir definieren nun ein Nonterminal "register", das den Wert eines Knotens in einem Register berechnet, und ein Startsymbol für unsere Baumgrammatik.
start: register
register: CONS
register: VAR
register: ADD(register, register)
Obige Produktionen reichen aus, um für jede beliebige Summe eine Code-Sequenz zu generieren. Jeder mögliche Eingabe-Baum ist
abgedeckt. Die Baum-Grammatik ist noch nicht mehrdeutig. D.h., es gibt für das Beispiel nur eine Baum-Ableitung:

D.h., jeder Knoten wird mit der Regel für register abgeleitet. Jetzt erweitern wir die Grammatik mit Kosten und Aktionen.
start: register # 1 # gen(return <reg>) 
register: CONS  # 1 # <reg>=newreg; gen(r<reg> = cons <value>) 
register: VAR   # 1 # <reg>=newreg; gen(r<reg> = var <variable>)
register: ADD(register, register) # 1 # <reg>=newreg; r<reg> = r<left-reg> + r<right->reg>
Nach einer Grammatik-Regel folgen die Kosten (getrennt mit Symbol #). Für unsere Architektur nehmen wir an, dass jeder erzeugte Befehl
einen Zyklus benötigt. Nach den Kosten folgt der Aktionsteil, der die Code-Generierung durchführt. Ähnlich den attributierten Grammatiken
haben auch Baum-Grammatiken (synthetisierte) Attribute. In unserem Beispiel werden neue Register für Knoten im Baum erzeugt. Diese Register werden über das Nonterminal register nach oben gereicht.

Mit obiger Ableitung wird folgende Sequenz erzeugt.
  r0 = cons 3
  r1 = cons 5
  r2 = r0 + r1
  r3 = var a
  r4 = r2 + r3
  return r4
Die Sequenz ist noch immer nicht optimal. Durch das Hinzufügen von weiteren Produktionen können wir die Addition der zwei Konstanten
bereits zur Laufzeit ausführen. Wir führen daher ein weiteres Nonterminal constant ein. Dieses Nonterminal behandelt konstante Werte in Teilausdrücken:
register: constant # 1 # <reg>=newreg; gen(r<reg> = <c-value>) 
constant: CONS # 0 # <c-value>=cons <value>
constant: ADD(constant,constant) # 0 # <c-value> = <left-c-value> + <right-c-value>
Die letzte Produktion führt eine Addition zur Laufzeit durch. Der Wert der Addition wird in <c-value> gespeichert. Wenn die Konstante <c-value> in ein Register geladen wird, benötigen wir wieder einen Kopierbefehl (siehe erste Produktion der Erweiterung).

Mit obiger Erweiterung erzeugen wir bereits besseren Code:
  r0 = cons 8
  r1 = var a
  r2 = r0 + r1
  return r2
Jedoch ist der Code noch immer nicht optimal. Erst durch die Berücksichtigung der Regeln:
register: ADD(constant,register) # 1 # ...
register: ADD(register,constant) # 1 # ...
können wir für unser Beispiel wirklich optimalen Code erzeugen:

   r0 = var a
   r1 = r0 + cons 8
   return r1

Leider ist obige Grammatik mit den angeführten Erweiterungen noch immer nicht optimal. Da mehrere Konstante in unterschiedlichen Teil-Ausdrücken vorkommen können. Erst durch das Einführen eines Nonterminals "reg_const", das einen Registerwert mit einer Konstante beschreibt können wir  wirklich für alle Summen optimalen Code generieren.

Die Baumgrammatik können Sie mit Hilfe von bfe in ein C-Programm übersetzen. Eine genaue Spezifikation der Baumgrammatik finden Sie im Skriptum. Folgende Schritte Sind für die Erstellung einer Baumgrammatik notwendig:
  1. Definieren sie eine Datenstruktur, die den Eingabe-Baum für die Baum-Grammatik beschreibt. Dabei müssen die Terminale und einige
  2. Zugriffs-Funktionen definiert werden (e.g. OP_LABEL, STATE_LABEL, LEFT_CHILD, RIGHT_CHILD, etc...)
  3. Aufbauen der Datenstruktur für ein Eingabeprogramm
  4. Entwickeln sie eine Baum-Grammatik, die Kosten und die jeweiligen Aktionen für die Code-Generierung enthält.
Das obige Summenbeispiel finden Sie bereits ausprogrammiert unter folgender URL: http://www.complang.tuwien.ac.at/ublu/summe3.tgz

Im Makefile finden Sie alle Schritte, um die Baumgrammatik (matcher.bfe) in ein C-Programm (matcher.c) umzuwandeln. Die
Datenstruktur sowie deren Zugriffsfunktionen für BURG wurden in tree.h definiert. Der Eingabebaum wird in parser.y aufgebaut und die Funktion burm_label und burm_reduce rufen den Baum-Parser für die Code-Generierung auf.


Hinweis: Es gibt einen kleinen Bug im script "bfe". Es dürfen keine Leerzeilen zwischen den einzelnen Produktionen sein! 


Zurück zur UBLU-Homepage.