Übersetzerbau: Fragen und Antworten

Hier finden Sie allgemeine Fragen und deren Antworten zur Lehrveranstaltung Übersetzerbau.


Allgemeine Fragen

Login

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

scp unter Windows gibt es nicht?

Da bei den beiden oben erwähnten Programmen leider kein scp dabei ist, machen Sie noch folgendes:

  1. Downloaden von ssh-1.2.14-win32bin.zip (dort ist ein secure copy enthalten)
  2. Unter DOS den Befehl set HOME=c:\home ausführen (oder ein beliebiges, anderes Verzeichnis angeben; das Verzeichnis muss existieren)
  3. Mit scp »datei« u???????@g0.complang.tuwien.ac.at:~ eine Datei ins Home-Verzeichnis auf der Übunsmaschine schaufeln
Uns wurde von einigen schwer durchschaubaren Fehlern berichtet, die offenbar auf die (fehlende?) Umkodierung bei der Übertragung von Windows-Maschinen auf unsere Übungsserver entstehen. Testen Sie Ihre Abgaben also auf jeden Fall noch einmal vor der Abgabe auf unserem Übungsserver.

Insbesondere mag Ox keine CRLF-Zeilenumbrüche (sondern nur LF).

Hilfe! Ich kenne mich nicht mehr aus, was soll ich tun?

  1. Lesen Sie das Übungsskriptum sorgfältig durch.
  2. Verwenden Sie die online-Dokumentation (WWW,Info-Manuals, manpages).
  3. Sind Sie der Meinung, daß zur Lösung der Beispiele notwendige Informationen nicht verfügbar sind, oder daß die Ihnen zur Verfügung stehenden Informationen widersprüchlich sind, oder helfen Ihnen einfach nicht weiter, dann wenden Sie sich an einen Tutor.
  4. Ist gerade kein Tutor anwesend, oder weiß dieser auch nicht weiter, so wenden Sie sich per e-mail an die Betreuer unter anton@complang.tuwien.ac.at.

Bei technischen Problemen (z.B. Maschine abgestürzt) wenden Sie sich an den Techniker (58801/18525).

Wo sind die Testprogramme?

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.

Kann man zu Hause arbeiten? Welches Betriebssystem wird empfohlen? Wo gibt es Software?

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.

Wo sind libl.a, liby.a für Linux?

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.

Kann man das Passwort ändern?

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.

Warum tut mein Programm test nicht, was es soll? Ich kann keinen Fehler finden.

test ist ein Shell-Kommando. Starten Sie Ihr Programm mit ./test!

Wie kann ich den exit-code kontrollieren?

Unmittelbar nach der Ausführung eines Programms zeigt ihnen echo $? den exit-code an.

Was geschieht bei der Abgabe?

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:

An welche Email-Adressen wurde das Ergebnis verschickt?

An Ihren Account auf der g0. Bei Einrichtung Ihres Accounts wurde auch ein .forward-File eingerichtet, das dafür sorgt, dass eine Kopie auf der g0 bleibt und eine an e.....@student.tuwien.ac.at weitergeschickt wird. Wenn Sie die Weiterleitung woanders hin haben wollen, editieren Sie die .forward-Datei, und testen Sie, dass sie richtig funktioniert!

Wenn 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).

Was bedeutet die Ausgabe des Abgabeprogramms?

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.

Wieviele Punkte gibt es pro Beispiel?

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.

Wie ist der Notenschlüssel für den Laborübungsteil?

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.

Wie wird die Note für die Lehrveranstaltung ermittelt?

Laborübungsteil und Vorlesungsteil werden im Verhältnis 2:1 gewichtet. Beide Teile müssen positiv absolviert werden. Sie erhalen für Laborübungsteil und Vorlesungsteil jeweils eine Note. Die Gesamtnote für die Lehrveranstaltung ergibt sich aus dem gewichteten Durchschnitt der beiden Teile. Die Note für den Vorlesungsteil erhalten Sie durch eine mündliche Prüfung.

Warum verwenden wir diese Werkzeuge? Werden sie in der Praxis verwendet?

Die verwendeten Werkzeuge sind einfach im Vergleich zu anderen (z.B. Cocktail), und benötigen daher weniger Lernaufwand. Es ist mit ihnen möglich, die gestellten Aufgaben zu bewältigen, und die Übungsteilnehmer lernen dabei Konzepte praktisch kennen, die auch bei Verwendung anderer Werkzeuge von Nutzen sind (z.B. attributierte Grammatiken, Baum-Parser).

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.

Assembler A, B

Fehlermeldung: relocation R_X86_64_32S ... can not be used when making a PIE object; recompile with -fPIE

Hier regt sich der Linker mit einer wenig verständlichen Fehlermeldung darüber auf, dass es in der .o-Datei eine oder mehrere absolute Adressen gibt. Verwenden Sie stattdessen RIP-relative Addressierung. Beispiel:
...
      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 ...

Scanner

Wertebereich von Integerzahlen

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));

End-of-file(EOF) ist nicht End-of-line (EOL)

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.

Parser

Was ist eine EBNF?

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.

Wie arbeiten (f)lex und yacc/bison zusammen?

Eine yacc-grammatik ist Token-basiert. Ein Token ist auf c-Ebene im wesentlichen ein Integerwert.
%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!

woher kennt (f)lex nun die token-werte (sind nur im yacc-file als %token implementiert), die er retournieren muss?

im falle der yacc-option -d koennen ganz einfach mit #include "y.tab.h" die token-codes inkludiert werden.

Holzhammermethode ohne option -d: das ganze c-file y.tab.c inkludieren.

woher kennt yacc die funktion yylex(), die im file lex.yy.c liegt?

viele varianten möglich. ist aber im wesentlichen nur ein c-problem.

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.

mein parser erkennt zwar lexikalische fehler korrekt, aber scheint einfach nicht die grammatik zu verwenden!?

ruft ihre main-funktion auch wirklich yyparse() auf? oder nimmt ihre (vermutlich vom scanner kopierte) version immer noch yylex() als einstieg-funktion?

gibt es einen debugging-switch vom yacc?

ja. sie koennen sich eine debug-version ihres parsers so erzeugen:

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

Sind Shift/reduce- und Reduce/reduce-Konflikte egal?

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.

Wie soll eigentlich der Rückgabewert sein, wenn mehrere Fehlertypen in einer Datei auftreten?

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.

Attributierte Grammatik

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!

Warum wird von der Verwendung von globalen Variablen abgeraten?

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.

Ox beschwert sich, daß ein synthetisiertes Attribut in einer Regel im Scanner nicht definiert würde; das Attribut ist aber sicher synthetisiert und ich weise ihm auch einen Wert zu. Was mache ich falsch?

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.

Warum vererbte Attribute im Startsymbol nicht funktionieren?

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.

Wie soll eigentlich der Rückgabewert sein, wenn mehrere Fehlertypen in einer Datei auftreten?

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.

Befehlsauswahl

Gibt es ein Beispiel, wie die Werkzeuge zusammenarbeiten?

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.

Burg hängt

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.

Was bedeutet die Ausgabe von 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.

Abgabegespräch

Wie melde ich mich für das Abschlusspräch (die Prüfung) an?

Über TUWEL. Termin und Link siehe Übungshomepage.

Abmeldung

Wie melde ich mich ab?

Über TUWIS. Der letztmögliche Termin ist dort ersichtlich.