In den Übungsräumen in der Argentinierstraße 8, Erdgeschoß stehen Ihnen ca. 25 X-Terminals als Arbeitsplätze zur Verfügung. Die offiziellen Öffnungszeiten des Labors sind Montag bis Freitag 9h-17h, jedoch sind die Übungsräume normalerweise wochentags bis 22h und samstags bis 17h zugänglich (es kommt aber vor, dass die Eingangstür schon früher versperrt wird). Die Übungsrechner sind rund um die Uhr in Betrieb, sodass Sie sich von auswärts (z.B. von den Benutzerräumen des ZID) auch zu anderen Zeiten einloggen können. Sollte es allerdings außerhalb der offiziellen Öffnungszeiten zu einem technischen Problem (z.B. Absturz) kommen, wird das Problem erst am nächsten Arbeitstag behoben.
Auf den X-Terminals können Sie Verbindungen zu verschiedenen Computern auswählen. Die Übungsmaschine ist die b1; sollte sie längerfristig ausfallen, steht als Ersatzmaschinen die b2 zur Verfügung (Sie können vorerst aber nicht auf den Ersatzmaschine einloggen). Sie können sich von auswärts mit ssh b1.complang.tuwien.ac.at einloggen.
Vor dem Einloggen sollten Sie einen Doppelklick auf das Ende-Icon machen oder zweimal <Ctrl><Alt><Backspace> drücken (X-server reset, verbessert die Stabilität). Nach dem Einloggen erscheint ein Emacs-Fenster und einige andere. Sie können die Session beenden, indem Sie einen X-Server-Reset auslösen (z.B. per Doppelklick auf das Ende-Icon).
Auf allen Arbeitsplätzen liegt die Meta-Taste auf <Alt>.
Wir haben keine Möglichkeit, Dateien von oder auf Diskette o.ä. zu überspielen. Falls Sie zuhause arbeiten wollen, müssen Sie Ihre Dateien mit scp (eine ssh-Anwendung) auf unsere Rechner übertragen.
Die in der Übung verwendeten Werkzeuge sind für verschiedene Platformen auf http://www.complang.tuwien.ac.at/ublu/tools/ erhältlich.
Wenn Sie selbst ein .forward-File einrichten oder ändern, 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 freie 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 tuwien.lva.uebersetzerbau-lu; derzeit ist sie nur auf wenigen Newsservern vorhanden; auf http://www.complang.tuwien.ac.at/ublu/newsgroup.html werden verschiedene Zugriffsmöglichkeiten erläutert. Stellen Sie Fragen, deren Antwort vermutlich auch 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>
Im WWW finden Sie unter http://www.complang.tuwien.ac.at/ublu/ Informationen zur Übung.
Während der Übung stehen zu gewissen Zeiten in den Übungsräumen Tutoren bereit (siehe http://www.complang.tuwien.ac.at/ublu/stundenplan.txt). 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 Anton Ertl 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.
Die Beispiele finden Sie weiter hinten im Skriptum. Beachten Sie, daß die ersten Beispiele erfahrungsgemäß wesentlich leichter sind als die Beispiele ,,Attributierte Grammatik'', ,,Befehlsauswahl'' und ,,Gesamtbeispiel''. Versuchen Sie, mit den ersten Beispielen möglichst rasch fertig zu werden, um genügend Zeit für die schwierigeren 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 Abgabeterminen zwischen 14h und 15h 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.
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 | info as | Assembler |
| 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 | |
| burg, iburg | man iburg, man burg | Baumparser-Generator |
| bfe | Skriptum | Präprozessor für burg |
| gdb | info gdb | Debugger |
| objdump | info objdump | Disassembler etc. |
| elm, mutt, | man elm, man mutt, man mail | |
| xrn | man xrn | Newsreader |
| lynx, w3, | WWW-Browser | |
| mosaic, | ||
| mozilla, | ||
| netscape |
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).
mail ist ein primitives Email-Werkzeug, elm und mutt sind etwas bequemer1.
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.
Abgabe spätestens am 17. März 2004, 14 Uhr.
Gegeben ist folgende C-Funktion:
unsigned long count0s(unsigned long a)
{
unsigned long i, r;
for (i=0, r=0; i<64; i++)
r += (a&(1L<<i))==0;
return r;
}
Schreiben Sie diese Funktion in Assembler unter Verwendung von ctpop (viel mehr ist übrigens auch nicht nötig, insbesondere keine Schleife).
Am einfachsten tun Sie sich dabei wahrscheinlich, wenn Sie eine einfache C-Funktion wie
unsigned long count0s(unsigned long a)
{
return a;
}
mit z.B. gcc -O -S in Assembler übersetzen und sie dann erweitern. Dann stimmt schon das ganze Drumherum. Die Originalfunktion auf diese Weise zu übersetzen ist auch recht lehrreich, aber vor allem, um zu sehen, wie man es nicht machen soll. Um ctpop zu assemblieren, muss der Prozessortyp mit .arch ev6 deklariert werden.
Beachten Sie, dass Sie nur dann Punkte bekommen, wenn Ihre Version korrekt ist, also bei gleicher (zulässiger) Eingabe das gleiche Resultat liefert wie das Original.
Zum Assemblieren und Linken verwendet man am besten gcc, der Compiler-Treiber kümmert sich dann um die richtigen Optionen für as und ld.
Zum angegebenen Termin stehen im Verzeichnis ~/abgabe/asma die maßgeblichen Dateien. Mittels make clean soll man alle von Werkzeugen erzeugten Dateien löschen können und make soll eine Datei count0s.o erzeugen. Diese Datei soll nur die Funktion count0s enthalten, keinesfalls main. Diese Funktion soll den Alpha-Aufrufkonventionen gehorchen und wird bei der Prüfung der abgegebenen Programme mit C-Code zusammengebunden.
Abgabe spätestens am 24. März 2004, 14 Uhr.
Gegeben ist folgende C-Funktion:
unsigned long mem0s(unsigned char *s, unsigned long l)
{
unsigned long r=0, i,j;
for (i=0; i<l; i++)
for (j=0; j<8; j++)
r += (s[i]&(1L<<j))==0;
return r;
}
Sie zählt die 0-Bits im Speicherblock.
Schreiben Sie diese Funktion in Assembler unter Verwendung von ctpop. Sie dürfen dabei annehmen, dass hinter dem letzten Zeichen von s noch 8 Zeichen zugreifbar sind.
Für besonders effiziente Lösungen (gemessen an der Anzahl der ausgeführten Maschinenbefehle) gibt es Bonuspunkte. Allerdings dürfen dabei keine Alignment-Fehler auftreten (die Korrektur solcher Fehler durch Linux wird bei den Testläufen ausgeschaltet). uldq wird in mehrere Maschinenbefehle übersetzt; die tatsächlichen Maschinenbefehle sehen Sie mit objdump -d.
Beachten Sie, dass Sie nur dann Punkte bekommen, wenn Ihre Version korrekt ist, also bei jeder zulässigen Eingabe das gleiche Resultat liefert wie das Original. Dadurch können Sie viel mehr verlieren als Sie durch Optimierung gewinnen können, also optimieren Sie im Zweifelsfall lieber nicht.
Die Vertrautheit mit dem Assembler müssen Sie beim Gespräch am Ende des Semesters beweisen, indem Sie Fragen zum abgegebenen Code beantworten.
Zum angegebenen Termin stehen im Verzeichnis ~/abgabe/asmb die maßgeblichen Dateien. Mittels make clean soll man alle von Werkzeugen erzeugten Dateien löschen können und make soll eine Datei mem0s.o erzeugen. Diese Datei soll nur die Funktion mem0s enthalten, keinesfalls main. Diese Funktion soll den Alpha-Aufrufkonventionen gehorchen und wird bei der Prüfung der abgegebenen Programme mit C-Code zusammengebunden.
Abgabe spätestens am 31. März 2004, 14 Uhr.
Schreiben Sie mit flex einen Scanner, der Identifier, Zahlen, und folgende Schlüsselwörter unterscheiden kann: func where end if then else not hd tl islist and; weiters soll er auch noch folgende Lexeme erkennen: : ; , = - + * < ( ).
Identifier bestehen aus Buchstaben und Ziffern, dürfen aber nicht mit Ziffern beginnen. Zahlen bestehen entweder ausschließlich aus Dezimalziffern oder aus 0x gefolgt von Hexadezimalziffern. Leerzeichen, Tabs und Newlines zwischen den Lexemen sind erlaubt und werden ignoriert, ebenso Kommentare, die mit (* anfangen und bis zum nächsten *) gehen. Alles andere sind lexikalische Fehler; auch ein unbeendeter Kommentar ist ein lexikalischer 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 Lexeme aus Sonderzeichen soll das Lexem ausgegeben werden, für Identifier ,,ident '' und der String des Identifiers, für Zahlen ,,num '' und die Zahl (in Hexadezimaldarstellung ohne führende Nullen, aber mit davorgehängten 0x). Für Leerzeichen, Tabs, Newlines 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 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 darf der Scanner Beliebiges ausgeben (eine sinnvolle Fehlermeldung hilft bei der Fehlersuche).
Abgabe spätestens am 21. April 2004, 14 Uhr.
Gegeben ist die Grammatik (in yacc/bison-artiger EBNF):
Program: { Funcdef ';' }
;
Funcdef: func ident /* Funktionsdefinition */
{ ident ',' } ident /* Parameterdefinition */
'=' Expr
;
Expr: Term where Defs end /* where-Ausdruck */
| if Expr then Expr else Term
| Term
| { not | '-' | hd | tl | islist } Term
| Term { '+' Term }
| Term { '*' Term }
| Term { and Term }
| Term ('<'|'='|':') Term
| ident { Term ',' } Term /* Funktionsaufruf */
;
Term: '(' Expr ')'
| ident /* Variablenverwendung */
| num
;
Defs: { Def ';' } /* Definitionsfolge */
;
Def: ident '=' Expr /* Variablendefinition */
;
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 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). Konflikte in der Grammatik sollten Sie durch Umformen der Grammatik beseitigen; yacc löst den Konflikt zwar irgendwie, aber nicht unbedingt in der gewünschten Art.
Abgabe spätestens am 12. Mai 2004, 14 Uhr.
Erweitern Sie den Parser aus dem letzten Beispiel mit Hilfe von ox um eine Symboltabelle und eine statische Analyse.
Die hervorgehobenen Begriffe beziehen sich auf Kommentare in der Grammatik.
6.5.2.1 Namen.
Die folgenden Dinge haben Namen: Funktionen und Variablen.
Eine Funktion wird im Funktionsaufruf verwendet und in der Funktionsdefinition definiert. Verwendete Funktionen müssen nicht definiert werden und können nicht deklariert werden. Funktionen dürfen, soweit es den Compiler betrifft, doppelt definiert werden und dürfen den gleichen Namen wie Variablen oder Felder haben; daher muss der Compiler Funktionsnamen nicht in einer Symboltabelle verwalten. Auch die Anzahl der Argumente soll (und kann) der Compiler nicht überprüfen.
Durch eine Variablendefinition oder eine Parameterdefinition wird eine Variable definiert. Variablen, die durch Parameterdefinitionen definiert werden, sind in der ganzen Funktion sichtbar; eine Variable, die in einer Variablendefinition definiert wird, ist sichtbar im Term vor der where-Klausel, die die Variablendefinition enthält, und sonst nirgends.
In einer Definitionsfolge darf ein Name nur einmal direkt definiert werden; die Definition des gleichen Namens in einer verschachtelten where-Klausel ist dagegen möglich. Dabei gilt, dass jeweils der Name sichtbar ist, der in der Ableitungsreihenfolge zuinnerst definiert wurde; z.B. ist bei
(x where x=1; end) where x=2; end
im Ausdruck x die Definition x=1 sichtbar.
6.5.2.2 Überprüfungen.
Zu überprüfen ist also:
Offenbar übersehen viele Leute, dass attributierte Grammatiken Information auch von rechts nach links (im Ableitungsbaum) weitergeben können. Sie denken sich dann recht komplizierte Lösungen aus. Dabei reichen die von Ox zur Verfügung gestellten Möglichkeiten vollkommen aus, um zu einer relativ einfachen Lösung zu kommen.
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ß, dass 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 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. Verwendung eines nicht sichtbaren Namens) der Fehlerstatus 3. Die Ausgabe kann beliebig sein.
Abgabe spätestens am 26. Mai 2004, 14 Uhr.
Gegeben ist die Grammatik (in yacc-artiger EBNF):
Expr: Term
| { not| '-' | 'hd' | 'tl' | 'islist'} Term
| Term { '+' Term }
| Term { '*' Term }
| Term { and Term }
| Term ('<'|'='|':') Term
;
Term: '(' Expr ')'
| Register
| num
;
Register: '$' num
;
Das Startsymbol ist Expr. Schreiben Sie mit den bisher verwendeten Werkzeugen und burg oder iburg einen Compiler, der solche Ausdrücke in Alpha-Assemblercode übersetzt. Die Lexeme sind die gleichen wie im Scannerbeispiel, zusätzlich gibt es noch das Lexem $.
6.6.2.1 Datendarstellung.
Es gibt zwei Typen, die durch dynamische Typüberprüfung unterschieden werden: ganze Zahlen und Listenzellen. Listenzellen bestehen aus zwei Feldern: den Kopf (head) und den Rest (tail); in beiden Feldern können beliebige Daten gespeichert werden.
Für die dynamische Typüberprüfung müssen die Daten mit tags versehen werden, die den Typ angeben. Wir verwenden das niedrigste Bit des Wortes als tag:
Wenn das tag 0 ist, ist das Datum eine vorzeichenbehaftete 63-Bit-Zahl; den Wert der Zahl erhält man durch bitweises arithmetisches Verschieben nach rechts um ein Bit.
Ist das tag 1, ist das Datum ein Zeiger auf eine Listenzelle; den tag-losen Zeiger erhält man, indem man vom Datum eins subtrahiert. Das Kopffeld der Listenzelle ist auf Offset 0 vom tag-losen Zeiger, das Restfeld ist auf Offset 8. Eine Listenzelle ist 16 Bytes groß.
In Listen und bei der Parameterübergabe sind die Daten immer mit tags versehen, bei der Bearbeitung können sie dargestellt werden, wie es gerade paßt. Im folgenden wird bei Integern der Zahlenwert genannt, nicht die Darstellung mit tag.
6.6.2.2 Bedeutung der Operatoren.
+, - und * haben ihre übliche Bedeutung (ein etwaiger Überlauf soll ignoriert werden).
x:y baut eine Listenzelle, und zwar mit x als Kopf und y als Rest. hd l produziert den Kopf von l, tl l produziert den Rest von l.
< und = vergleichen ihre Operanden und liefern 1 für ``wahr'' und 0 für ``falsch''. < funktioniert dabei nur für ganze Zahen, = für beliebige Kombinationen von Zahlen und Listen. = vergleicht dabei nur die beiden Maschinenwörter (Quadwords in DEC-Terminologie), die die Daten repräsentieren, es macht keinen Tiefenvergleich von Listen; bei zwei Listen mit gleichem Inhalt, die nicht in der selben Operation gebaut wurden, wird = also 0 liefern (z.B. (0:0)=(0:0) liefert 0). islist liefert 1, wenn sein Operand eine Liste ist, sonst 0.
and und not arbeiten bitweise auf ganzen Zahlen.
'$' num steht für das Register num.
6.6.2.3 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.
In Register dürfen nur die Register $16-$21 stehen (muss Ihr Compiler nicht überprüfen), für Zwischenergebnisse können Sie die Register $0-$8 und $22-$25 verwenden; das Ergebnis soll in Register $0 stehen. Die Ausdrücke haben maximal 12 Operatoren (muss Ihr Compiler nicht überprüfen; das Laden einer Konstanten zählt dabei als Operator), 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 Listenzellen können Sie auf dem Heap anlegen. Der Heap-Zeiger befindet sich im Register $9; der Heap wächst nach oben. Um die Freigabe der Elemente brauchen Sie sich nicht kümmern, es ist genug Platz für die Listenelemente, die in dem Ausdruck vorkommen.
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).
Im Fall eines Typfehlers soll ein Signal erzeugt werden, das den Prozess beendet. Bei den Operatoren, die Listen erwarten (head und tail), erledigen die normalen Load-Befehle das von selbst, da sie bei einem nicht ausgerichtetem (unaligned) Zugriff eine Exception erzeugen, die das Betriebssystem in ein Signal übersetzt2. Bei den Operatoren, die ganze Zahlen erwarten (not - + * and <), müssen Sie das selbst abfragen (z.B. mit blbs). Ihr Programm kann ein Signal erzeugen, indem es zum Label raisesig springt.
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 (Metrik wieder: ausgeführte Maschinenbefehle) 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 Operatorionen (z.B. tagging und untagging) 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, dass 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.
Einige Beispiele für weitere Optimierungen mit burg/iburg sind in
http://www.complang.tuwien.ac.at/papers/ertl00dagstuhl.ps.gz zu
finden.
Beachten Sie allerdings, dass es leicht ist, durch eine falsche Optimierungsregel mehr Punkte zu verlieren als man durch Optimierung überhaupt gewinnen kann. Testen Sie daher ihre Optimierungen besonders gut. Überlegen Sie sich, welche Optimierungen es wohl wirklich bringen (welche Fälle also tatsächlich vorkommen), und lassen Sie die anderen weg (im Zweifelsfall alle).
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 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 16. Juni 2004, 14 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:
In einer Variablendefinition wird ein Ausdruck ausgewertet und mit einem Namen assoziiert. Die Verwendung des Namens produziert das Ergebnis des Ausdrucks. Ein where-Ausdruck berechnet den Term unter Berücksichtigung der in der where-Klausel gebundenen Namen und liefert als Ergebnis das Ergebnis des Terms.
Bei einem if-Ausdruck wird zunächst der Ausdruck zwischen if und then ausgerechnet, und überprüft, ob der Wert eine ganze Zahl ist (sonst muss das Programm eine Exception verursachen). Ist die (getagte) ganze Zahl ungerade, wird der Ausdruck zwischen then und else ausgewertet; das Ergebnis wird zum Ergebnis des gesamten if-Ausdrucks. Ansonsten wird der Ausdruck nach dem else ausgewertet und wird zum Ergebnis des if-Ausdrucks.
Der Funktionsaufruf wertet alle Parameterterme aus, ruft eine Funktion mit diesen Parametern gemäß der Alpha-Aufrufkonvention (mit Ausnahme des Heap-Pointers) auf, und liefert das Resultat der Funktion als Ergebnis.
Jede Funktion im Programm verhält sich gemäß der Alpha-Aufrufkonvention, nur der Heap-Pointer wird etwas anders behandelt: Der Heap-Pointer in $9 zeigt unmittelbar hinter den benutzten Bereich des Heap, und die Funktionen Ihres Compilers sollen diese Invariante erhalten. Das Ergebnis des Ausdrucks in der Funktion ist der Rückgabewert der Funktion.
Ihr Compiler soll Alpha-Assemblercode ausgeben. Der erzeugte Code 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. Der Funktionsname soll als Label am Anfang des erzeugten Code verwendet werden und als externes Symbol definiert werden. In der Quellsprache verwendete Funktionsnamen sind externe Symbole. Diesmal müssen Sie selbst für raisesig sorgen; ein geeigneter Befehl ist stq $31,0($31). Nicht ausgerichtete Zugriffe produzieren auch in der Testumgebung für dieses Beispiel ein Signal.
Der Name einer Funktion soll als Label am Anfang des erzeugten Codes verwendet werden und das Symbol soll exportiert werden; andere Symbole soll Ihr Code nicht exportieren.
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 5 Parameter. Die Anzahl der gleichzeitig sichtbaren Variablen einer Funktion ist maximal 5. Die maximale Tiefe eines Ausdrucks ist 5 (Tiefe eines Ausdrucks: Anzahl der Ableitungen von Expr zwischen einem Blatt des Syntaxbaums und dem nächsten Def, bzw. der Wurzel). Die im Quellprogramm vorkommenden Zahlen sind kleiner als 256.
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 ein.
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 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.
2zumindest in der Einstellung, in der wir Ihren Code aufrufen; die entsprechende Funktion zum Einschalten dieses Features finden Sie in \~{}ftp/pub/ublu/uac\_sigbus.c.