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:
- Laden einer Variable in ein Register
r<k> = var
<var>
- Laden einer Konstante in ein Register
r<k>= cons
<value>
- Addieren von zwei Registern
r<x>=r<y>+r<z>
- Addieren von einem Register und einer Konstante
r<x>=r<y>
+ cons <value>
- 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:
- Definieren sie eine Datenstruktur, die den Eingabe-Baum für
die Baum-Grammatik beschreibt. Dabei müssen die Terminale und
einige
- Zugriffs-Funktionen definiert werden (e.g. OP_LABEL,
STATE_LABEL, LEFT_CHILD, RIGHT_CHILD, etc...)
- Aufbauen der Datenstruktur für ein Eingabeprogramm
- 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.