In den Übungsräumen in der Argentinierstraße 8, 5. Stock stehen Ihnen ca. 20 X-Terminals als Arbeitsplätze zur Verfügung. Die offiziellen Öffnungszeiten des Labors sind Montag bis Freitag 9h-17h. Die Maschinen sind normalerweise rund um die Uhr in Betrieb, sie können also auch zu anderen Zeiten arbeiten: normalerweise sollten sie bis 22h und am Samstag bis 17h Zutritt zu den Übungsräumen haben (es kommt aber vor, dass die Eingangstür schon früher versperrt wird); über Zugriff von woanders (z.B. Benutzerräume des ZID) können Sie auch arbeiten, wenn die Übungsräume geschlossen sind. Sollte es allerdings außerhalb der offiziellen Öffnungszeiten zu einem technischen Problem (z.B. Absturz) kommen, wird das normalerweise erst am nächsten Arbeitstag behoben.
Auf den X-Terminals können Sie Verbindungen zu verschiedenen
Computern auswählen. Die Übungsmaschine ist die a6; sollte sie
längerfristig ausfallen, steht als Ersatzmaschine die a3 zur
Verfügung (Sie können sich erst dann auf der a3 einloggen). Sie
können sich von auswärts mit ssh a6.complang.tuwien.ac.at
einloggen. Ssh-clients finden Sie z.B. über
http://www.rhic.bnl.gov/RCF/Software/Commercial/SSH/SSHSources.html.
Nach dem Einloggen erscheint ein Emacs-Fenster und einige andere. Sie können sich ausloggen, indem Sie Emacs verlassen (mit <Ctrl><x> <Ctrl><c> <Space>). Auf den X-Terminals müssen Sie das dann noch bestätigen. Vergessen Sie das nicht! Wenn Sie voraussichtlich der letzte Benutzer des Terminals vor dem Wochenende sind, schalten Sie es aus.
Auf allen Arbeitsplätzen liegt die Escape-Taste auf <F11> und die Meta-Taste auf <Alt>.
Wir haben keine Möglichkeit, Disketten zu überspielen. Falls Sie zuhause arbeiten wollen, müssen Sie Ihre Dateien mit scp (eine ssh-Anwendung) auf unsere Rechner übertragen, z.B. von den Benutzerräumen des ZID aus. Die Werkzeuge sind auf http://www.complang.tuwien.ac.at/ublu/tools/ erhältlich. Dort findet man auch ein Paket mit Binärversionen von gcc, flex und bison für 386-Rechner (und bessere) unter MS-DOS.
Wenn Sie ein .forward-File einrichten, testen Sie es unbedingt! Wenn es nicht funktioniert, haben wir keine Möglichkeit, Sie zu erreichen (z.B. um Ihnen die Ergebnisse der Abgabe mitzuteilen).
Mit Ihrer Anmeldung zur Übung haben Sie sich gleichzeitig zwei Stunden Zeit pro Woche an einem Arbeitsplatz reserviert. Während dieser Zeit können Sie jeden, der zu diesem Zeitpunkt nicht reserviert hat, aufforden, Ihnen Platz zu machen. Zu welchem Zeitpunkt jemand reserviert hat, können Sie am Account-Namen im Shell-Prompt ablesen (Bei Prolog-Übungsteilnehmern steht unten im Emacs-Fenster ,,reserviert'' oder ,,nicht reserviert''). Der mittlere Buchstabe gibt die reservierte Zeit an. Sie können also zu Ihrer reservierten Zeit jeden, dessen Accountnamen einen anderen mittleren Buchstaben hat als Ihr Accountname, auffordern, Ihnen den Arbeitsplatz zu überlassen. Sie können aber auch zu jedem anderen Zeitpunkt kommen und arbeiten, wenn es Plätze gibt. Auf Aufforderung müssen Sie dann Platz machen.
Nach den Erfahrungen der letzten Jahre kommt es allerdings nur kurz vor den Abgabeterminen zu großem Andrang in den Übungsräumen. Zu anderen Zeiten sollten Sie also keine Platzprobleme haben, und Ihre Anwesenheit vielleicht eher nach den Tutorenzeiten als nach Ihrer reservierten Zeit ausrichten.
Verlautbarungen zur Übung (z.B. Klarstellungen zur Angabe) gibt es in der Newsgroup at.tuwien.lva.uebersetzerbau-lu. Stellen Sie Fragen, deren Antwort vermutlich andere Übungsteilnehmer interessiert, bitte dort. Wir bemühen uns, Fragen innerhalb eines Arbeitstages zu beantworten. Bitte schauen Sie zuerst, ob die Frage nicht schon gestellt und beantwortet wurde. Wenn Ihre Frage schon früher beantwortet wurde, wird die Antwort auf ihre Frage meist die Message-Id der alten Antwort sein. Mit der Message-Id kommen sie auf folgende Weise an den Artikel, wenn Ihr Newsreader diese Funktion nicht bietet:
telnet news.tuwien.ac.at nntp article <Message-Id>Oder sie verwenden http://www.deja.com/forms/mid.shtml.
Im WWW finden Sie unter http://www.complang.tuwien.ac.at/ublu/ Informationen zur Übung.
Während der Übung stehen zu gewissen Zeiten (siehe WWW) in den Übungsräumen Tutoren bereit. Wenn die Tutoren Ihre Frage nicht beantworten können, erreichen Sie unter ublu@mips.complang.tuwien.ac.at die betreuenden Assistenten; Email zu Übungsthemen an andere Accounts wird von den Empfängern möglicherweise ignoriert. Wenn Sie Ihre Fragen gerne persönlich stellen, kommen Sie am Montag von 10h-11h zu Alexander Forst-Rakoczy in die Sprechstunde.
Technische Probleme wie Computerabstürze, Druckerprobleme, falsche Permissions sind eine Sache für den Techniker. Wenden Sie sich direkt an ihn: email an Herbert Pohlai (root@mips.complang.tuwien.ac.at), Tel. 18525.
Folgende Assistenten sind für folgende Teile der Übung verantwortlich:
Die Beispiele finden Sie weiter hinten im Skriptum. Beachten Sie, daß die ersten beiden Beispiele erfahrungsgemäß wesentlich leichter sind als die Beispiele ,,Attributierte Grammatik'', ,,Befehlsauswahl'' und ,,Gesamtbeispiel''. Versuchen Sie, mit den ersten beiden Beispielen möglichst rasch fertig zu werden, um genügend Zeit für das dritte zu haben.
Ihre Note wird aufgrund der Qualität der von Ihnen abgegebenen Programme ermittelt. Das Hauptkriterium ist dabei die Korrektheit. Sie wird mechanisch überprüft, Sie erhalten per Email das Ergebnis der Prüfung. Wenn Sie meinen, daß sich das Prüfprogramm geirrt hat, wenden Sie sich an einen Tutor.
Die Prüfprogramme sind relativ einfach, dumm und kaum fehlertolerant. Damit Sie prüfen können, ob Ihr Programm im richtigen Format ausgibt und ähnliche wichtige Kleinigkeiten, stehen Ihnen die Testprogramme und einige einfache Testeingaben und -resultate zur Verfügung; Sie können die Testprogramme auch benutzen, um Ihre Programme mit eigenen Testfällen zu prüfen (siehe http://www.complang.tuwien.ac.at/ublu/).
Beachten Sie, daß bei der Abgabe die Überprüfung mit wesentlich komplizierteren Testfällen erfolgt als denen, die wir Ihnen vorher zur Verfügung stellen. Ein erfolgreiches Absolvieren der Ihnen vorher zur Verfügung stehenden Tests heißt also noch lange nicht, daß Ihr Programm korrekt ist. Sie müssen sich selbst weitere Testfälle überlegen (wie auch im Berufsleben).
Ihre Programme werden zu den angegebenen Terminen kopiert und später überprüft. Ändern Sie zu den Abgebeterminen zwischen 17h und 18h nichts im Abgabeverzeichnis, damit es nicht zu inkonsistenten Abgaben kommt.
Ein paar Tage nach der Abgabe erhalten Sie das Ergebnis per Email. Das Ausschicken der Ergebnisse wird auch in at.tuwien.lva.uebersetzerbau-lu verkündet, Sie brauchen also nicht nachfragen, wenn Sie dort noch nichts gesehen haben. Eine Arbeitswoche nach der ersten Abgabe werden Ihre (eventuell von Ihnen verbesserten) Programme erneut kopiert und überprüft. Diese Version wird mit 70% der Punkte eines rechtzeitig abgegebenen Programms gewertet. Das ganze wiederholt sich zwei Arbeitswochen nach dem ersten Abgabetermin (30% der Punkte). Sie erhalten für das Beispiel das Maximum der drei Ergebnisse. Für das letzte Beispiel gibt es nur einen Nachtermin.
Sollten Sie versuchen, durch Kopieren oder Abschreiben von Programmen eine Leistung vorzutäuschen, die Sie nicht erbracht haben, erhalten Sie keine Note. Die Kontrolle erfolgt in einem Gespräch am Ende des Semesters, in dem überprüft wird, ob Sie auch verstehen, was Sie abgegeben haben. Weitere Maßnahmen behalten wir uns vor.
Ihr Account ist nur für Sie lesbar. Bringen Sie andere nicht durch Ändern der Permissions in Versuchung, zu schummeln.
Es stehen folgende Werkzeuge zur Verfügung:
| Name | online Doku | Bemerkung |
| emacs, vi | info emacs, man vi | Editor |
| gcc, ccc | info gcc, man ccc | C-Compiler |
| make | info make | baut Programme |
| flex | man flex | Scanner-Generator |
| yacc, bison | man yacc, info bison | Parser-Generator |
| ox | man ox | AG-basierter |
| xdvi /usr/ftp/pub/ublu/oxURM.dvi | Compilergenerator | |
| gcc | info as | Assembler |
| burg, iburg | man iburg, man burg | Baumparser-Generator |
| bfe | Skriptum | Präprozessor für burg |
| gdb | info gdb | Debugger |
| objdump | info binutils | Disassembler etc. |
| elm, mutt, | man elm, man mutt, man mailx | |
| mailx | ||
| xrn | man xrn | Newsreader |
| lynx, w3, | WWW-Browser | |
| mosaic |
Die mit ,,man'' gekennzeichnete Dokumentation können Sie lesen, indem sie auf der Kommandozeile man ... eintippen. Die mit ,,info'' gekennzeichnete Dokumentation können Sie lesen, indem sie in Emacs C-h i tippen. In der Dokumentation für Emacs bedeutet C-x <Ctrl>x und M-x <Meta> x (auf den Übungsgeräten also <Alt>x).
Sie können w3 aufrufen, indem Sie in Emacs M-x w3 tippen. Alle anderen Werkzeuge werden von der Shell-Kommandozeile aus aufgerufen, indem man ihren Namen tippt.
Mit flex erzeugte Scanner müssen normalerweise mit -lfl gelinkt werden.
Das auf den Übungsgeräten unter yacc aufrufbare Programm ist Berkeley yacc und ist näher mit Bison verwandt als mit AT&T yacc (für den Fall, daß Sie Diskrepanzen zwischen diesem yacc und dem auf kommerziellen Unices bemerken).
mailx ist ein primitives Email-Werkzeug, elm und mutt sind etwas bequemer1.
Netscape ist für den Multiuserbetrieb, die verwendeten X-Terminals, und Linux-Alpha ungeeignet und steht daher nicht zur Verfügung.
Das Ox User Reference Manual ist nicht in diesem Skriptum abgedruckt, sondern steht nur on-line zur Verfügung, da es relativ umfangreich ist und nur ein Teil der enthaltenen Information in dieser Übung nützlich ist. Sollten Sie dagegen meinen, daß wir diese Handbuch doch abdrucken hätten sollen (bei einem entsprechend höheren Preis des Skriptums), lassen Sie es uns wissen.
Abgabe spätestens am 16. März 2000, 17 Uhr.
Schreiben Sie mit flex einen Scanner, der Identifier, Zahlen, und
folgende Schlüsselwörter unterscheiden kann: extern
interface end func class implements var return let in if then else
loop exit new not and
or; weiters soll er auch noch
folgende Lexeme erkennen: ; ( , ) := - + * < =.
Identifier bestehen aus Buchstaben und Ziffern, dürfen aber nicht mit Ziffern beginnen. Zahlen bestehen ausschließlich aus Ziffern. Leerzeichen, Tabs und Newlines zwischen den Lexemen sind erlaubt und werden ignoriert, ebenso Kommentare, die mit /* anfangen und mit dem nächstfolgenden */ aufhören. Alles andere sind lexikalische Fehler. Es soll jeweils das längste mögliche Lexem erkannt werden, if39 ist also ein Identifier (longest input match).
Der Scanner soll für jedes Lexem eine Zeile ausgeben: für Schlüsselwörter und die Sonderzeichen soll das Schlüsselwort bzw. Sonderzeichen ausgegeben werden, für Identifier ident und der String des Identifiers, für Zahlen num und die Zahl in der Basis 16. Für Leerzeichen und Kommentare soll nichts ausgegeben werden (auch keine Leerzeile).
Der Scanner soll zwischen Groß- und Kleinbuchstaben unterscheiden, If ist also kein Schlüsselwort.
Legen Sie ein Verzeichnis ~/abgabe/scanner an, in das sie die maßgeblichen Dateien stellen. Mittels make clean soll man alle von Werkzeugen erzeugten Dateien löschen können (auch den ausführbaren Scanner) und mittels make all ein Programm namens scanner erzeugen, das von der Standardeingabe liest und auf die Standardausgabe ausgibt. Korrekte Eingaben sollen akzeptiert werden (Ausstieg mit Status 0, z.B. mit exit(0)), bei einem lexikalischen Fehler soll der Fehlerstatus 1 erzeugt werden. Bei einem lexikalischen Fehler können sie Beliebiges ausgeben.
Abgabe spätestens am 23. März 2000, 17 Uhr.
Gegeben ist die Grammatik (in yacc/bison-artiger EBNF):
Program: { ( Type | Implementation | Funcdef | Funcdecl extern ) ';' }
;
Type: interface ident { Funcdecl ';' } end interface
;
Funcdecl: func ident '(' { ident ',' } [ ident ] ')'
;
Implementation: class ident implements ident { Def ';' } end class
;
Def: var ident
| Funcdef
;
Funcdef: Funcdecl Statseq end func
;
Statseq: { Statement ';' }
;
Statement: ident ':=' Expr
| Expr
| return Expr
| let { ident ':=' Expr ';' } in Statseq end let
| if Expr then Statseq else Statseq end if
| loop Statseq end loop
| exit
;
Expr: [ not | '-' ] Term
| Term { '+' Term }
| Term { '*' Term }
| Term { and Term }
| Term { or Term }
| Term ('-'|'<'|'=') Term
;
Term: '(' Expr ')'
| ident
| num
| new ident
| ident '(' { Expr ',' } [ Expr ] ')'
;
Schreiben Sie einen Parser für diese Sprache mit flex und yacc/bison. Die Lexeme sind die gleichen wie im Scanner-Beispiel (ident steht für einen Identifier, num für eine Zahl). Das Startsymbol ist Program.
Zum angegebenen Termin stehen im Verzeichnis ~/abgabe/parser die maßgeblichen Dateien. Mittels make clean soll man alle von Werkzeugen erzeugten Dateien löschen können und mittels make all ein Programm namens parser erzeugen, das von der Standardeingabe liest. Korrekte Programme sollen akzeptiert werden (Ausstieg mit Status 0, z.B. mit exit(0)), bei einem lexikalischen Fehler soll der Fehlerstatus 1 erzeugt werden, bei Syntaxfehlern der Fehlerstatus 2. Das Programm darf auch etwas ausgeben, z.B. damit Sie sich beim Debugging leichter tun.
Die Verwendung von Präzedenzdeklarationen von yacc kann leicht zu Fehlern führen, die man nicht so schnell bemerkt (bei dieser Grammatik sind sie sowieso sinnlos).
Abgabe spätestens am 13. April 2000, 17 Uhr.
Erweitern Sie den Parser aus dem letzten Beispiel mit Hilfe von ox um eine Symboltabelle und eine statische Analyse.
6.3.2.1 Namen.
Die folgenden Dinge haben Namen: Interfaces, Klassen, Instanzvariablen (deklariert mit var), Funktionen, Funktionsparameter, lokale Variablen (deklariert mit let).
Interfacenamen, Klassennamen, und Funktionsnamen sind von ihrer Deklaration/Definition bis zum Ende des Programms sichtbar, Instanzvariablen von ihrer Definition bis zum Ende der Klasse, Funktionsparameter in der gesamten Funktion, und lokale Variablen im let-Statement zwischen in und end let.
Alle Namen teilen sich einen Namensraum. Wenn der gleiche Name für zwei Dinge verwendet wird, dürfen sich die Sichtbarkeitsbereiche des Namens nicht überlappen. Allerdings zählt die Definition einer Funktion in einer Klasse als Verwendung des Namens und nicht als Deklaration (siehe nächster Abschnitt: ``Funktionen'').
Die Namen werden in folgenden Kontexten verwendet:
Eine Funktionsdefinition oder -deklaration außerhalb einer Klassen/Interface-definition definiert bzw. deklariert eine normale Funktion. Eine Funktionsdeklaration in einem Interface deklariert eine virtuelle Funktion. Eine Funktionsdefinition in einer Klasse definiert die Implementation einer virtuellen Funktion. Dabei dürfen nur Funktionen definiert werden, die im Interface, das die Klasse implementiert, deklariert wurden (die Definition einer Funktion in einer Klasse zählt also nicht als Deklaration des Namens und führt zu keinem Konflikt mit der Deklaration im Interface); die Anzahl der Parameter in der Deklaration und der Definition muss gleich sein. Eine Funktion darf nur einmal in einer Klasse definiert werden.
6.3.2.3 Schleifen. exit darf nur innerhalb eines loop... end loop-Konstrukts verwendet werden.
6.3.2.4 Überprüfungen.
Zu überprüfen ist also:
Verwenden Sie keine globalen Variablen oder Funktionen mit Seiteneffekten bei der Attributberechnung! ox macht globale Variablen einerseits unnötig, andererseits auch fast unbenutzbar, da die Ausführungsreihenfolge nicht vollständig festgelegt ist.
Sie brauchen angeforderten Speicher (z.B. für Symboltabellen-Einträge oder Typinformation) nicht freigeben, die Testprogramme sind nicht so groß, daß der Speicher ausgeht (zumindest wenn Sie's nicht übertreiben).
Zum angegebenen Termin stehen die maßgeblichen Dateien im Verzeichnis ~/abgabe/ag. Mittels make clean soll man alle von Werkzeugen erzeugten Dateien löschen können und mittels make all ein Programm namens ag erzeugen, das von der Standardeingabe liest. Korrekte Programme sollen akzeptiert werden, bei einem lexikalischen Fehler soll der Fehlerstatus 1 erzeugt werden, bei Syntaxfehlern der Fehlerstatus 2, bei anderen Fehlern (z.B. Mehrfachdeklaration) der Fehlerstatus 3. Die Ausgabe kann beliebig sein.
Der Sinn dieses Beispiels ist, daß Sie sich mit der Alpha-Assemblersprache vertraut machen und lernen, was die Optimierer heutiger Compiler können und was nicht.
Abgabe spätestens am 4. Mai 2000, 17 Uhr.
Gegeben sind folgende C-Funktionen (zu finden in ftp/pub/ublu/countbits.c und .../search_combination.c):
#include <assert.h>
#define COLOURS 8
#define MAX_COMBINATIONS 2048
typedef unsigned long Uint;
int combination_number[MAX_COMBINATIONS][COLOURS];
int p_colours[COLOURS];
Uint search_combination(Uint max_cn, Uint colours)
{
Uint i,j;
assert(colours<=COLOURS);
assert(max_cn<=MAX_COMBINATIONS);
for (i = 0; i<max_cn; i++) {
for (j=0; j<colours; j++)
if (p_colours[j] != combination_number[i][j])
break;
if (j==colours)
break;
}
return i;
}
Uint countbits(Uint x)
{
Uint count=0;
for (; x > 0; x >>= 1)
count += x&1;
return count;
}
Schauen Sie sich den Assembler-Code an, den der Compiler erzeugt (mit der Compiler-Option -S), und auch den Maschinencode (compilieren mit -c, dann mit objdump -d oder dem gdb-Befehl disas disassemblieren). Optimieren Sie die Funktionen sowohl auf der Ebene des C-Quellcodes als auch über die Auswahl des Compilers und der Optimierungsoptionen, sodaß eine möglichst geringe Anzahl an Maschinenbefehlen ausgeführt wird (entspricht nicht unbedingt der kleinsten Ausführungszeit); nops, fnops, und unops werden dabei nicht gezählt. Führen Sie aber nur Änderungen im Quellcode durch, die tatsächlich zu einer Verbesserung führen.
Es gibt für die Alpha-Architektur einige Befehlssatzerweiterungen (z.B. die Byte-Word-Extension (BWX)). Weder in diesem noch in den folgenden Beispielen dürfen sie diese Befehle verwenden. Die erzeugten Programme werden möglicherweise auf der a3 getestet, die diese Erweiterungen nicht unterstützt. Beachten Sie, dass manche Compileroptionen (z.B. -mcpu=21164a beim gcc) die Benutzung dieser Befehle freigeben, die dürfen sie also nicht verwenden.
Sie können davon ausgehen, daß die Zusicherungen (assert) stimmen. Ihre optimierte Version braucht die Assertions nicht überprüfen, aber sie darf sich trotzdem darauf verlassen, daß sie gelten. Mit anderen Worten, wenn die Assertions nicht gelten, darf Ihre optimierte Version ein beliebiges Resultat (inkl. Absturz) liefern; wenn sie gelten, muß Ihre optimierte Version das gleiche Resultat liefern wie das Original.
In der Eingabe von countbits werden durchschnittlich ca. die Hälfte der Bits gesetzt sein. Die Parameter von search_combination werden wir wahrscheinlich so gestalten, dass Optimierungen wie Loop Peeling und Loop Unrolling nicht zu stark belohnt werden.
Viele Assemblerbefehle entsprechen mehreren Maschinenbefehlen. Mit gdb und objdump -d können Sie sich den tatsächlich erzeugten Maschinencode ansehen. Für einige Befehle werden Prozeduren aufgerufen, die zur Laufzeit dutzende oder hunderte Befehle ausführen können.
Beachten Sie, daß Sie nur dann Punkte bekommen, wenn Ihre optimierte Version korrekt ist, also bei gleicher Eingabe das gleiche Resultat liefert wie das Original. Jedes Jahr bringt es eine erstaunlich große Anzahl von Übungsteilnehmern fertig, ein funktionierendes Programm kaputtzuoptimieren.
To begin, let us state the obvious. If a program is not correct, it matters little how fast it runs. Kernighan und Plauger, The Elements of Programming Style
Die Vertrautheit mit dem Assembler müssen Sie beim Gespräch am Ende des Semesters beweisen, indem Sie Fragen zum erzeugten Assemblercode beantworten.
Zum angegebenen Termin stehen im Verzeichnis ~/abgabe/asm ein Makefile und die Dateien search_combination.c und countbits.c, aus denen mit make search_combination.o bzw. make countbits.o (nicht (nur) mit make all!) optimierte Object-Dateien erzeugt werden sollen. Diese Dateien sollen nur die Funktion search_combination bzw. countbits enthalten, keinesfalls main. Sie können für jede Objekt-Datei andere Optimierungsoptionen verwenden.
Abgabe spätestens am 18. Mai 2000, 17 Uhr.
Gegeben ist die Grammatik (in yacc-artiger EBNF):
Statement: variable ':=' Expr
;
Expr: [ not | '-' ] Term
| Term { '+' Term }
| Term { '*' Term }
| Term { and Term }
| Term { or Term }
| Term ('-'|'<'|'=') Term
;
Term: '(' Expr ')'
| variable
| num
;
variable: '$' num
| num '(' '$' num ')'
;
Das Startsymbol ist Statement. Schreiben Sie mit den bisher verwendeten Werkzeugen und burg oder iburg einen Compiler, der solche Ausdrücke in Alpha-Assemblercode übersetzt.
Alle Operationen arbeiten auf vorzeichenbehafteten 64-Bit-Zahlen und liefern solche Zahlen als Ergebnis. +, - und * haben ihre übliche Bedeutung (ein etwaiger Überlauf soll ignoriert werden). and, or und not führen die Operation bitweise auf ihren Operanden durch. < und = vergleichen ihre Operanden und liefern -1 (alle Bits gesetzt) für wahr und 0 für falsch.
$n bezeichnet das Register n, d($n) ist die Speicherstelle an der Adresse d+$n. In Term: variable wird von dem Register bzw. von der Speicherstelle gelesen, in Statement: variable ':=' ... wird dorthin geschrieben.
6.5.2.1 Erzeugter Code
Der von Ihrem Compiler erzeugte Code wird in eine Funktion inkludiert, Ihr Compiler braucht sich also nicht um das Drumherum einer Funktion zu kümmern.
Die Eingaben des Ausdrucks (inkl. des Registers, das zur Berechnung der Adresse der linken Seite der Zuweisung verwendet wird) stehen in den Registern $16-$21 (muss Ihr Compiler nicht überprüfen), für Zwischenergebnisse können Sie die Register $0-$8 und $22-$25 verwenden. Die Ausdrücke haben maximal 12 Operatoren (muss ihr Compiler nicht überprüfen), was die Registerbelegung trivial macht: Sie können das Ergebnis jedes Maschinenbefehls in ein neues Register schreiben und brauchen sich nicht um das Auslagern kümmern. Die Eingabe-Register können im Ausdruck in beliebiger Reihenfolge und auch mehrfach verwendet werden; am Ende können alle hier erwähnten Register beliebige Werte haben, ausgenommen die linke Seite der Zuweisung (wenn sie ein Register ist).
Die im Quellprogramm als Konstanten vorkommenden nums sind kleiner als 256 (muss ihr Compiler nicht überprüfen). Das sollte es ihnen erleichtern, eine gute Codeauswahl durchzuführen. Allerdings geben wir für konstante Ausdrücke keine solche Garantie (z.B. kann folgendes vorkommen: 255*255*$16).
Der erzeugte Code soll korrekt sein und möglichst wenige Befehle ausführen (da es hier keine Verzweigungen gibt, ist das gleichbedeutend mit ,,wenig Befehle enthalten''). Dabei ist nicht an eine zusätzliche Optimierung (wie z.B. common subexpression elimination) gedacht, sondern vor allem an die Dinge, die Sie mit burg tun können, also eine gute Codeauswahl und einige algebraische Optimierungen (siehe Hinweis). Für besonders schnellen erzeugten Code gibt es Sonderpunkte.
Sie werden burg/iburg in diesem Beispiel wohl vor allem dazu verwenden, um Befehle mit konstanten Operanden auszuwählen, und eventuell einige spezielle Befehle wie s4subq.
Sie können allerdings mit Hilfe von burg/iburg auch Optimierungen durchführen, insbesondere solche, die auf algebraischen Gesetzen wie x+0 = x beruhen.
Insbesondere lassen sich unäre Operatoren gut optimieren: Wenn wir z.B. den Negationsoperator (unäres -) optimieren wollen und wir Werte in Registern mit dem Nonterminal reg repräsentieren, brauchen wir nur ein Nonterminal negreg einführen, das den Fall repräsentiert, daß das Register den negierten Wert enthält. Wenn wir nun die folgenden drei Regeln hinzufügen:
negreg: Neg(reg) reg: Neg(negreg) negreg: Mul(negreg, reg) #1#.../* generate multiply */
kann die Befehlsauswahl z.B. in -(-(x)), -((-(x))*y), -(((-(x))*y)*z) etc. die - wegoptimieren.
Zum angegebenen Termin stehen die maßgeblichen Dateien im Verzeichnis ~/abgabe/code. Mittels make clean soll man alle von Werkzeugen erzeugten Dateien löschen können und mittels make all ein Programm namens code erzeugen, das von der Standardeingabe liest und auf die Standardausgabe ausgibt. Bei lexikalischen Fehlern soll code mit dem Fehlerstatus 1 aussteigen, bei Syntaxfehlern mit dem Status 2. Im Fall eines Fehlers kann die Ausgabe beliebig sein. Sonderpunkte gibt es, wenn der erzeugte Code besonders schnell ist, also unterdurchschnittlich viele Befehle ausführt. Der ausgegebene Code wird in ein Assemblerprogramm inkludiert und muß vom Assembler verarbeitet werden können.
Abgabe spätestens am 8. Juni 2000, 17 Uhr. Achtung, bei diesem Beispiel gibt es nur einen Nachtermin!
Schreiben Sie einen Compiler für die Sprache aus dem Beispiel ,,Attributierte Grammatik''. Der Großteil der Sprache wurde schon in den Beispielen ,,Attributierte Grammatik'' und ,,Codeerzeugung'' erklärt, hier der Rest:
Es handelt sich um eine einfache objektorientierte Sprache. In einer Klassendefinition definieren sie u.a. Felder eines Objekts (mit var). new ident erzeugt ein Objekt der Klasse ident, wobei alle Felder mit 0 initialisiert sind.
Ein Aufruf einer virtuellen Funktion muss zur Laufzeit als ersten Parameter (eine Referenz auf) ein Objekt einer Klasse enthalten, in der die Funktion definiert ist. Diese Funktion wird dann aufgerufen. Erfolgt in dieser Funktion ein Feldzugriff, dann bezieht sich das auf das entsprechende Feld des Objekts, das im ersten Parameter übergeben wurde.
Abgesehen von diesen Spezialitäten virtueller Funktionsaufrufe funktionieren Funktionsaufrufe wie üblich.
Weder der Compiler noch das Laufzeitsystem müssen eine Typüberprüfung durchführen. Wenn eine Operation auf dem falschen Typ ausgeführt wird (z.B. wenn der erste Parameter einer virtuellen Funktion eine Zahl ist, oder ein Objekt einer Klasse, in der die Funktion nicht definiert ist), ist das Ergebnis undefiniert (das Programm darf dann beliebiges machen).
Objekte werden immer über Referenzen angesprochen; nach Ausführen des Codefragments
a := new x; b := a;
enthalten a und b Referenzen auf das selbe Objekt; wird das Objekt geändert, hat das Auswirkungen auf a und b.
Statement: ident ':=' Expr ist die übliche Zuweisung. Statement: Expr wertet den Ausdruck aus und ignoriert das Ergebnis.
return Expr beendet eine Funktion und liefert Expr als Ergebnis; Es ist nicht definiert, was passiert, wenn die Ausführung einer Funktion bis zum Ende durchfällt (wenn also kein return ausgeführt wurde).
Das let-Statement definiert lokale Variablen und initialisiert sie mit den entsprechenden Ausdrücken; diese lokalen Variablen können dann zwischen in und end let beliebig verwendet werden.
Das if-Statement wertet Expr aus; ist das Ergebnis ungleich 0, werden die Statements zwischen then und else ausgeführt, sonst die zwischen else und end if.
Das loop-Statement führt die enthaltenen Statements unbegrenzt oft aus. exit verlässt die statisch innerste umgebende Schleife.
Term: ident '(' { Expr ',' } [ Expr ] ')' ist ein Funktionsaufruf. Er wertet alle Ausdrücke aus und ruft dann die entsprechende Funktion auf, mit den Ergebnissen der Ausdrücke als Parameter. Das Ergebnis des Ausdrucks in der Funktion ist der Rückgabewert der Funktion.
Ihr Compiler soll Alpha-Assemblercode ausgeben. Normale Funktionen verhalten sich gemäß der Alpha-Aufrufkonvention, mit einer Ausnahme: es gibt einen Heap-Pointer in $9, der von new verwendet werden sollte; er zeigt unmittelbar hinter den benutzten Bereich des Heap, und die Funktionen Ihres Compilers sollen diese Invariante erhalten.
Der erzeugte Code für normale Funktionen wird nach dem Assemblieren und Linken von C-Funktionen oder Funktionen, die Ihr Compiler compiliert hat, aufgerufen. Und Ihr Code ruft wiederum C-Funktionen auf oder Funktionen, die Ihr Compiler compiliert hat. Virtuelle Funktionen werden nur von Code aufgerufen, den ihr Compiler produziert hat, dabei könenen Sie also eine beliebige Aufrufkonvention verwenden. Auch Zugriffe auf die Felder von Objekten erfolgen nur von Ihren virtuellen Funktionen aus, Sie können also ein beliebiges Objektlayout verwenden.
Der Name einer normalen Funktion soll als Label am Anfang des erzeugten Codes verwendet werden und das Symbol soll exportiert werden; andere Symbole soll Ihr Code nicht exportieren. Als extern deklarierte Funktionen werden in einem anderen File definiert und mit dem von ihrem Compiler produzierten Code zusammengelinkt.
Folgende Einschränkungen sind dazu gedacht, Ihnen gewisse Probleme zu ersparen, die reale Compiler bei der Codeauswahl und Registerbelegung haben. Sie brauchen sie nicht überprüfen (es könnte ihnen allerdings beim Debuggen ihrer Testprogramme helfen): Funktionen haben maximal 6 Parameter. Die Anzahl der gleichzeitig sichtbaren Parameter und lokalen Variablen zusammen ist maximal 6. Die maximale Tiefe eines Ausdrucks ist 5 (Tiefe eines Ausdrucks: Anzahl der Ableitungen von Expr zwischen der Wurzel und einem Blatt des Syntaxbaums). Die im Quellprogramm vorkommenden Zahlen sind kleiner als 256. Eine Klasse hat maximal 4094 Felder, ein Interface maximal 4095 virtuelle Funktionen.
Weiters muss sich ihr Compiler nicht um die Freigabe von auf dem Heap allozierten Speicher kümmern; solange er nicht exzessiv viel Platz für Objekte reserviert, wird der Speicher in der Testumgebung für die Testprogramme ausreichen. Wir rechnen mit folgendem Speicherverbrauch (pro Objekt): (Anzahl der Felder+1)×8 bytes. Der Heap ist mit Nullen initialisiert. Der Heap-pointer ist anfangs aligned.
Wichtigstes Kriterium ist wie immer die Korrektheit, für gute Codeerzeugung gibt es aber wieder Sonderpunkte. Belassen Sie es dabei aber bei Optimierungen, die mit den verwendeten Werkzeugen einfach möglich sind, bauen Sie keine nachträgliche Optimierung.
Für den Einsatz der Assembleranweisungen orientieren Sie sich am C-Compiler. Übersetzen Sie ein C-Programm mit gcc -O -S und schauen Sie sich das Ergebnis an.
Sie können sich das Objektlayout und die Aufrufkonvention für virtuelle Funktionen aussuchen. Eine Möglichkeit ist: Objekte haben als erstes Feld einen Zeiger auf eine Tabelle der virtuellen Funktionen (vtable; Klassendesktiptor im Vorlesungsskriptum), danach folgen die anderen Felder. Pro Klasse gibt es eine vtable, wobei die vtables aller Klassen mit dem gleichen Interface das gleiche Layout haben (das sinnvollerweise während der Interfacedefinition festgelegt wird). Die vtables enthalten Zeiger auf den Anfang der Funktionen. Virtuelle Funktionen haben die normale Aufrufkonvention, allerdings funktioniert der Aufruf etwas anders: Zunächst greift das Programm über den ersten Parameter auf den Zeiger auf die vtable zu, von dort holt es den Zeiger auf die Funktion, und ruft schließlich die Funktion auf. Zugriffe auf Felder erfolgen per Offset über den ersten Parameter.
Die in den Hinweisen zur Codeerzeugung erläuterte Technik ist besonders praktisch, um Vergleiche und Boolesche Ausdrücke in dieser Programmiersprache zu optimieren: In der Sprache erzeugen Vergleiche entweder 0 oder -1, die Alpha-Architektur hat aber dafür nur Befehle, die 0 oder 1 erzeugen, und im if-Statement kommt es nur auf = 0 oder ¹ 0 an (und die Alpha-Architektur hat auch Befehle dafür). Das kann man z.B. optimieren, indem man zusätzliche Nonterminale für negierte Werte und/oder für Werte einführt, für die man nur weiß, ob sie = 0 sind.
Ich empfehle, Parameter der aktuellen Funktion nicht in den Argumentregistern zu lassen, sondern sie z.B. in gesicherte Register zu kopieren, damit man beim Berechnen der Parameter einer anderen Funktion problemlos auf sie zugreifen kann.
Zum angegebenen Termin stehen die maßgeblichen Dateien im Verzeichnis ~/abgabe/gesamt. Mittels make clean soll man alle von Werkzeugen erzeugten Dateien löschen können und mittels make all ein Programm namens gesamt erzeugen, das von der Standardeingabe liest und auf die Standardausgabe ausgibt. Bei einem lexikalischen Fehler soll der Fehlerstatus 1 erzeugt werden, bei einem Syntaxfehler Fehlerstatus 2, bei anderen Fehlern der Fehlerstatus 3. Im Fall eines Fehlers kann die Ausgabe beliebig sein. Verwenden Sie keine globalen Variablen.
1elm und xrn sind so vor-eingestellt, daß der schon laufende Emacs als Editor verwendet wird. Wenn Sie mit dem Editieren des Buffers fertig sind, tippen Sie C-x # und elm wird weitermachen.