Hier finden Sie allgemeine Fragen und deren Antworten zur Lehrveranstaltung Übersetzerbau.
Aus Sicherheitsgründen können sie sich auf dem Übungsrechner nur über die ssh einloggen und mit scp Dateien uploaden. Alle anderen Zugriffsmöglichkeiten (telnet, ftp) sind deaktiviert.
Die ssh für verschiedene Betriebssysteme gibt es auf SSH
Da bei den beiden oben erwähnten Programmen leider kein scp dabei ist, machen Sie noch folgendes:
set HOME=c:\home
ausführen (oder
ein beliebiges, anderes Verzeichnis angeben; das Verzeichnis muss
existieren)scp »datei« u???????@g0.complang.tuwien.ac.at:~
eine Datei ins Home-Verzeichnis auf der Übunsmaschine schaufelnInsbesondere mag Ox keine CRLF-Zeilenumbrüche (sondern nur LF).
Bei technischen Problemen (z.B. Maschine abgestürzt) wenden Sie sich an den Techniker (58801/18525).
Die Testprogramme finden Sie im Verzeichnis
/usr/ftp/pub/ubvl/
. Aufruf einfach mit
/usr/ftp/pub/ubvl/test/asma/test
/usr/ftp/pub/ubvl/test/asmb/test
/usr/ftp/pub/ubvl/test/scanner/test
/usr/ftp/pub/ubvl/test/parser/test
/usr/ftp/pub/ubvl/test/ag/test
/usr/ftp/pub/ubvl/test/codea/test
/usr/ftp/pub/ubvl/test/codeb/test
/usr/ftp/pub/ubvl/test/gesamt/test
Beachten Sie, dass diese Testscripts nur dazu gedacht sind, Formalfehler zu entdecken und zu verhindern (wie z.B. falsche Namen o.ä.), die sonst katastrophale Konsequenzen hätten. FüR eingehendere Tests (vor allem bei späteren Beispielen) sind Sie selbst zuständig, und wir empfehlen, sie ernsthaft durchzuführen.
Sie können allerdings für die Beispiele scanner, parser, und ag selbst Testdaten anlegen, und zwar in
~/test/scanner/
~/test/parser/
~/test/ag/
Beim Scanner-Beispiel legen Sie für korrekte Eingaben Dateien mit Namen der Form *.0 an, und für die zugehoerigen Ausgaben Dateien mit Namen der Form *.out; für Eingabendateien mit lexikalischen Fehlern legen Sie Dateien mit Namen der Form *.1 an.
FüR das parser- und ag-Beispiel legen Sie Dateien der Form *.[012] bzw. $[0123] an, wobei die Extension angibt, welchen exit-Status parser bzw. ag bei dieser Eingabe liefern sollen. Wenn Sie also eine Datei mit einem Syntax-Fehler anlegen, sollte sie z.B. "test.2" heißen.
Falls sie das Skript für eigene Modifikationen kopieren, beachten Sie, dass sie es nicht mit "test" aufrufen koennen, aber z.B. mit "./test" geht es; in der Shell gibt es einen eingebauten Befehl "test".
Auch wenn Sie Ihr Programm zu Hause schon getestet haben, sollten Sie die Tests auf jeden Fall auf unseren Übungsservern wiederholen, um Fehler bei der Übertragung abzufangen.
Man kann zu Hause arbeiten. Unix (Linux) ist emfehlenswert, aber nicht Voraussetzung; worauf es beim Betriebssystem ankommt, ist , dass die Werkzeuge vorhanden sind. Zum Testen der letzten drei Beispiele ist ein AMD64-kompatibler Prozessor im 64-bit-Modus nötig.
Relativ alte Versionen von bison, flex, gcc, etc. für MS-DOS finden Sie hier. Ox finden Sie hier als Quellcode und als Linux-a.out-Binärversion. Burg, iburg, und bfe finden Sie hier als Quellcode.
Bitte verwenden Sie die ssh wenn Sie sich von »auswärts« einloggen.
Da bei Linux kein lex dabei ist, macht wohl auch libl.a keinen Sinn. Wenn man ein Programm namens lex unter Linux hat, ist es höchstwahrscheinlich flex, und dann sollte es mit libfl.a linken.
liby.a muss man nicht verwenden, es enthält nur "main" und "yyerror", und die schreibt man sich normalerweise selbst, und zwar maßgeschneidert für den eigenen Zweck.
Ja, man kann das Passwort ändern. Bitte verwenden Sie ein Passwort mit acht Zeichen Länge, Klein- und Großbuchstaben und Sonderzeichen. Die Passwörter werden periodisch durch ein Crackprogramm überprüft. Bei der Rechenleistung unserer Maschine (Stand März 2000) braucht das Programm ungefähr 30 Minuten, um alle Kombination aus Kleinbuchstaben mit sechs Zeichen Länge durchzurechnen.
test
nicht, was es soll?
Ich kann keinen Fehler finden.
test
ist ein Shell-Kommando. Starten Sie Ihr Programm mit
./test
!
Unmittelbar nach der Ausführung eines Programms zeigt ihnen
echo $?
den exit-code an.
Genau zum Abgabezeitpunkt (siehe Skriptum) kopiert ein Programm die Daten aus dem jeweiligen Abgabeverzeichnis der Übungsteilnehmer an eine andere Stelle. Es wird damit ein Snapshot der Daten erzeugt. Aus diesem Grund darf zum Abgabezeitpunkt keine Veränderung des Abgabeverzeichnisses stattfinden!
Dann werden für jeden Übungsteilnehmer folgende Befehle durchgeführt:
make clean
make
make clean
make clean
richtig funktioniert hatWenn die Email nicht auf dem Account ankommt, auf den sie weitergeleitet haben (z.B. weil die Quota ueberschritten sind), finden Sie das Ergebnis immer noch in Ihrem Account auf der g0 (wenn Sie diesen Teil des .forward-Files nicht kaputt gemacht haben).
Beim Unterschied zwischen erwarteter und tatsächlicher Ausgabe erhalten Sie ein context-diff, das schaut z.B. so aus:
*** ../../testscanner/test11.de Fri Mar 21 11:59:13 1997 --- - Sat Mar 22 16:28:03 1997 *************** *** 1 **** ! Dschovanni \ No newline at end of file --- 1 ---- ! Giovanni \ No newline at end of file
diff zeigt die Stellen in erwarteter und tatsächlicher Eingabe, die unterschiedlich sind. Und zwar wird jede dieser Stellen mit einem "!" gekennzeichnet. Zusätzlich zeigt diff noch jeweils drei Zeilen drüber und drunter, wenn vorhanden. Das "\ No newline at end of file" ist keine Fehlermeldung, sondern rein informativ. Da in beiden Dateien die letzte Zeile kein Newline hat, ist das getestete Programm diesbezüglich korrekt. Der Fehler ist also nur, dass das "Gi" nicht durch "dsch" (oder "Dsch") ersetzt wurde.
Für die Gesamtbeurteilung werden die einzelnen Bespiele verschieden gewichtet. Für 100% einer Abgabe erhalten sie folgende Punkteanzahlen:
10 asma 10 asmb 10 scanner 10 parser 20 ag 20 codea 20 codeb 20 gesamt
Für jedes Beispiel zählt das Maximum der erreichten Punkte der drei möglichen Abgaben.
5 [0,60) 4 [60,75) 3 [75,90) 2 [90,105) 1 ab 105
Beachten Sie, dass Sie nur nach einem bestandenen Abschlussgespräch eine positive Note erhalten.
Lex und yacc bzw. flex und bison werden in der Praxis häufig eingesetzt.
Ox ist nicht so populär (wohl u.a. weil es verwaist ist). Für unsere Übung hat es allerdings den Vorteil, dass es einfach ist und mit lex und yacc zusammenarbeitet.
Warum Ox und nicht nur yacc? In manchen Jahren kann man das Beispiele mit einer L-attributierten Grammatik lösen, sodass man sie theoretisch mit yacc allein ohne Aufbau eines Syntaxbaums lösen kann. Im allgemeinen kommt man allerdings mit L-Attributierung nicht durch, und wenn man es versucht und erst spät draufkommt, dass es nicht geht, hat man ein großes Problem. Ausserdem zeigt die Erfahrung, dass es die meisten Übungsteilnehmer nicht fertigbringen, mit yacc/bison alleine einen Compiler zu schreiben, der verschachtelte Konstrukte korrekt behandelt.
Tree parsing ist eine der populärsten Code-Erzeugungsmethoden und wird z.B. im Java Hotspot-Compiler, in lcc, in SML/NJ eingesetzt. Allerdings werden dabei statt iburg gerne erweiterte Varianten des gleichen Algorithmus eingesetzt wie BEG oder lburg. Der zusätzliche Lernaufwand für diese Werkzeuge überträfe die Zeitersparnis bei unserer Übung allerdings bei weitem.
... vpcmpleub zs, %zmm0, %k3 ... .data zs: .ascii ...Hier wird
zs
absolut addressiert, der Linker kann diesen
Befehl nicht in ein position-independent executable (PIE) einbauen,
und liefert daher einen Fehler. Das Problem kann behoben werden,
indem zs
RIP-relativ addressiert wird:
... vpcmpleub zs(%rip), %zmm0, %k3 ... .data zs: .ascii ...
Im Endeffekt soll ein Compiler für einen AMD64-Prozessor geschrieben werden. Der Wertebereich für Integerzahlen ist demnach [0, 2^63).
Als Ausgaberoutine in Ihrem Scanner verwenden Sie deshalb so etwas ähnliches wie
printf("%ld",atol(yytext));
In Lex/Flex kann EOL mit dem Sonderzeichen $ bzw. mit "\n" gekennzeichnet werden. Dabei ist zu beachten, dass eine Eingabe ohne EOL das Dateiende erreicht (also kein EOL bevor EOF).
Reguläre Ausdrücke der Form,
"--".*$
funktionieren nur für Eingaben, die mit EOL enden; jedoch nicht für Eingaben, die mit EOF enden. Daher sollte obiger Ausdruck umgewandelt werden:
"--".*
Durch das Weglassen von $ wird entweder bis zum EOL oder EOF gelesen.
Das ist eine kurze Erklärung der EBNF an einem Beispiel.
S: x A; A: z | y A;
Aus dem Startsymbol lassen sich die folgenden Sätze herleiten:
xz, xyz, xyyz, xyyyz, xyyyyz, xyyyyyz, ....
Das Beispiel zeigt also, wie durch Anwendung einer rekursiven Produktion beliebige Repetitionen erzeugt werden koennen. Allerdings ist die Rekursivität nicht unmittelbar ersichtlich.
Die EBNF verwendet daher eine zusätzliche Notation,
{ s }
wobei die Folge s von Terminal- bzw. Nichtterminal-Symbolen beliebig oft (inklusive 0-mal) repetiert werden kann. Das vorige Beispiel lässt sich wie folgt zusammenfassen,
S: x { y } z;
wobei die Notwendigkeit für das Symbol A entfällt. Ebenfalls im Sinne einer Vereinfachung führen wir die Notation
[ s ]
ein. [ s ] sei gleichbedeutend mit s wird 0 mal oder einmal genommen. Das Beispiel
S: x [ y ] z;
erzeugt die Sprache mit den Sätzen xz und xyz. Weiters verwenden wir Klammerungen. Das Beispiel:
S: x y z | x w z;
kann mit Hilfe der Klammern auf
S: x (y | w) z;
zusammengefasst werden. In der EBNF können auch Kommentare verwendet werden. Kommentare beginnen mit /* und enden mit */. Das Beispiel:
/* Funktionsdefinition */
Kommentare verändern die EBNF nicht.
%token MYTOKEN
wird in ein
#define MYTOKEN wert
umgewandelt. (einzelne zeichen wie '(' oder ')' sind »Standard«-Token und müssen nicht definiert werden. ihr Token-Wert entspricht einfach dem ascii-code des Zeichens)
Die erzeugten defines befinden sich default-mäßig im file
y.tab.c
. Mit der option -d können diese defines jedoch in
das file y.tab.h
geschrieben werden.
yacc erwartet eine funktion yylex(), die genau ein token einliest und dessen token-code retourniert.
Im Skriptum (yacc-beschreibung) sind Beispiele abgedruckt, welche die funktion yylex() »zu Fuß« implementiert haben.
Aber: in Beispiel 1 haben sie mit flex im wesentlichen eine c-funktion yylex() erzeugt, die ein ganzes file einliest, und bei jedem token eine Operation (printf-Ausgabe) ausführt. (einfach einmal lex.yy.c anschauen!)
Wenn sie nun anstatt des printf
ein return
implementieren, so liest die neue yylex()-funktion nur noch genau ein
token, also genau das was yacc erwartet!
#include
"y.tab.h"
die token-codes inkludiert werden.
Holzhammermethode ohne option -d: das ganze c-file y.tab.c
inkludieren.
Eine Möglichkeit ist, dem c-compiler mitzuteilen, dass es die funktion
yylex()
extern gibt (um warnings/errors zu vermeiden). dann
mit gcc y.tab.c lex.yy.c
die files zusammenlinken.
oder »Holzhammer«: einfach ganze funktion als c-code inkludieren.
yyparse()
auf? oder nimmt
ihre (vermutlich vom scanner kopierte) version immer noch
yylex()
als einstieg-funktion?
in die main-funktion einfuegen
int main(){ #ifdef YYDEBUG yydebug = 1; #endif /* ...und ihr weiterer code... */ }
und dann zb. im makefile:
debug: ... gcc -DYYDEBUG ... -odebug_parser
(... entspricht ihren files, die sie auch beim "normalen" parser
compilieren; -DYYDEBUG definiert nur YYDEBUG und hat den gleichen effekt,
als ob sie #define YYDEBUG
in den c-code geschrieben haetten)
mittels "make debug" koennen sie sich dann die debug version "debug_parser" erzeugen sie koennen dann mitschauen, welche regeln der grammatik angewendet werden und welche token eingelesen werden
Nein, man muss sich die Konflikte genau ansehen; in den meisten Faellen muss man dann die Grammatik aendern, um den Konflikt zu vermeiden, in manchen Faellen loest der Parser-Generator den Konflikt so, wie man es will (aber eher bei shift/reduce als bei reduce/reduce-Konflikten).
Konflikte sind oft das Resultat von mehrdeutigen Grammatiken, manchmal aber auch ein Artefakt der LALR(1)-Methode. Um Shift/reduce- und Reduce/reduce-Konflikte zu eliminieren, muss die BNF-Grammatik modifiziert werden.
Bei einem Reduce/Reduce-Konflikt weiss der Parser-Generator nicht, welche von mehreren moeglichen Regeln er für die Reduktion in einer bestimmten Situation wählen soll, und wählt willkuehrlich eine davon. Wenn das nicht die ist, die man in der Situation haben wollte, dann wird der Parser wohl das falsche machen. Wenn yacc und bison dabei verschiedene Regeln wählen, wuerde das die Unterschiede in der Fehlermeldung erklaeren.
Jedenfalls sollte man sich die Ausgabe von z.B. bison
-v
ansehen (verbose mode). Um die Ausgabe verstehen zu
können, sollte man auch die Grundlagen für
LR-Parser-Generator beherrschen.
Beispiel: Ein Progamm enthaelt einen lexikalischen Fehler und einen syntaktischen Fehler. Welchen Fehler soll man in so einem Fall ausgeben? Theoretisch kann je nach Implementierung der eine oder andere Fehler zuerst entdeckt werden.
Es soll entweder der erste erkennbare Fehler oder der Fehler mit dem niedrigsten Exit-Code gemeldet werden. Es wird keine Testfaelle geben, in denen es einen Unterschied macht, welche dieser beiden Moeglichkeiten man wählt.
Für die Erstellung der Attributierten Grammatik kann ein von Studenten entwickeltes Java Programm zur Hilfe genommen werden. Es ermöglicht die Attributierung in einer Baumansicht vorzunehmen und kann Ox Files generieren. Die Homepage dieses Tools finden sie unter http://www.complang.tuwien.ac.at/torero/ .
Überlegen sie sich bevor sie loslegen, welche Datenstrukturen sie verwenden wollen, um die Symboltabelle zu speichern.
Achten sie bei ihren Attributen auf die korrekte Anwendung von synthetisiert und vererbt/inherited. Ein Attribut kann entweder immer nur synthetisiert oder vererbt werden!
Bei Attributauswertungen ist die Reihenfolge der Ausführung nicht vollständig festgelegt. Bei einem Parse-tree Traversal ist sie zwar festgelegt, aber wenn Sie nur Traversals verwenden, verlieren Sie die meisten Vorteile einer attributierten Grammatik: Regel-lokale Variablen (Attribute), automatisches Auflösen von Abhängigkeiten.
Im Jahr 1993 wurde bei der Übung noch kein Ox verwendet, sondern nur yacc, sodass überall globale Variablen verwendet werden mussten. Die abgegebenen Compiler waren praktisch alle sehr fehlerhaft, insbesondere haben die Compiler Verschachtelungen nicht verkraftet. Eine Gruppe hat den Zeitaufwand gemessen: Nachdem sie das Programm das erste Mal hergezeigt hatten (im Prinzip die erste Abgabe), brauchten sie noch einmal soviel Zeit, um es zu reparieren.
Beachten Sie bitte, daß Regeln in der lexikalischen Analyse in einer Zeile geschrieben werden müssen. Statt
{BLABLA} return (TOKEN); @{ @TOKEN.synth1@ = f(yytext); @}
müssen Sie
{BLABLA} return (TOKEN); @{ @TOKEN.synth1@ = f(yytext); @}
verwenden.
Das Startsymbol darf kein vererbtes Attribut besitzen, da dieses nie initialisiert werden kann. Die Fehlermeldung ist allerdings höchst verwirrend:
%start programm %% progamm: programm ... @{ @i @programm.1.vererbt@=@programm.0.vererbt@ @} ... ;
führt dazu, dass Ox behauptet, in der Regel in der Nähe von zeile X ist das Attribut vererbt, aber in derselben Regel in derselben Zeile synthetisiert (nicht zu verwechseln mit der »normalen« Fehlermeldung, bei denen verschiedene Zeilennummern/Regeln in der Fehlermeldung vorkommen!!).
Am besten führt man ein Hilfs-Startsymbol ohne vererbte Attribute ein:
%start Start %% Start: programm @{ @i @programm.vererbt@ = /*initialisierung*/; @} programm: programm ...
Der Fehler sollte dann verschwinden.
Beispiel: Ein Progamm enthaelt einen lexikalischen Fehler, einen syntaktischen Fehler und einen Semantik-Fehler. Welchen Fehler soll man in so einem Fall ausgeben? Theoretisch kann je nach Implementierung der eine oder andere Fehler zuerst entdeckt werden.
Es soll entweder der erste erkennbare Fehler oder der Fehler mit dem niedrigsten Exit-Code gemeldet werden. Es wird keine Testfaelle geben, in denen es einen Unterschied macht, welche dieser beiden Moeglichkeiten man wählt.
Ein Beispiel, wie die Werkzeuge zusammenarbeiten, finden Sie unter /usr/ftp/pub/ubvl/beispiel1.tgz. Die Datei beispiel1.tgz enthaelt ein Beispiel, das zeigt, wie die Werkzeuge flex,bison,ox und burg zusammenarbeiten. Mit tar xvzf /usr/ftp/pub/ubvl/beispiel1.tgz wird die Datei entpackt. Enthalten ist auch ein ausführliches README, das weitere Erläuterungen zu dem Beispiel enthält.
Weiters steht ein Mini-Howto zu burg (bzw. BFE) hier zur Verfügung.
Rufen Sie ihn mit burg -c 10 auf. Dann bricht er ab und liefert eine Meldung
Das ist ein Fehler, der laut Original-Burg-Manual bei Grammatiken für die Befehlsauswahl nicht vorkommt. Offenbar kommt er doch vor.
Man kann dieses Problem eliminieren, indem man zusätzliche Regeln zur Konversion zwischen den Nonterminalen einbaut, insbesondere zwischen den Nonterminalen, die in der Meldung von Burg erwähnt werden. Bei einer Meldung wie
... Relative Costs: const(0), nreg(7) ...
hat z.B. die zusätzliche Regel
nreg: const # 1 #
geholfen.
Wenn auch das nichts hilft, kann man noch an den Kosten der Regeln drehen oder Regeln entfernen.
burg -c
Beispiel:
ERROR: The grammar appears to diverge Relative Costs: const(0), nreg(7) Offending Operator: MUL Offending Tree: MUL(MUL(MUL(NEG(INT)(INT,),INT),INT),INT)
Burg versucht im Prinzip, alle Bäume aus allen Nonterminalen
abzuleiten. In diesem Fall hat er u.a. versucht, den Offending
Tree (MUL(MUL(MUL(NEG(INT)(INT,),INT),INT),INT))
abzuleiten. Und zwar konnte er das aus dem nonterminal const
zu Kosten 0 und aus dem Nonterminal nreg
zu Kosten 7 (die
Kosten sind hierbei relativ zum Nonterminal mit der billigsten Ableitung
des Baums, entsprechen also nicht unbedingt den wahren Kosten der
Ableitung).
Wegen der Option "-c 5" war ihm dieser Unterschied zu groß und er hat abgebrochen. Ohne "-c" kam er in eine Endlosschleife.
Durch Einfügen der Regel nreg: const #1 ...
erkennt burg,
dass es billiger ist nreg
über const
zu
Kosten 1 abzuleiten statt über die andere Ableitung zu Kosten 7,
betrachtet daher diesen Baum und seine grösseren Verwandten nicht, und
erspart sich die Endlosschleife.
Über TUWEL. Termin und Link siehe Übungshomepage.
Über TUWIS. Der letztmögliche Termin ist dort ersichtlich.