Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Systemanalyse

Compilerbaupraktikum - Aufgabenblatt 4

Generelles

Abgabetermin

So, 22.06.2014 23:59 Uhr

Allgemeine Hinweise

Für alle Praktikumsaufgaben gilt, dass Einsendungen, die nicht in der jeweils mitgegebenen Testumgebung laufen, mit null Punkten bewertet werden! Das beinhaltet insbesondere alle Programme, die sich nicht fehlerfrei kompilieren lassen. Als Testsystem werden wir dabei star mit den dort installierten Compilern und Compilerwerkzeugen benutzen. Prüfen Sie bitte rechtzeitig vor der Abgabe, ob ihr Programm auch dort lauffähig ist. Die Aussage „aber bei mir zuhause hat es funktioniert“ führt entgegen mancher Erwartungen nicht zur Punktevergabe.

Ebenfalls mit null Punkten werden alle Abgaben bewertet, die sich nicht exakt an die vorgegebenen Formate halten. Hier sollen insbesondere falsch gepackte Archive erwähnt werden (die nicht alle nötigen/die falschen/zu viele Dateien enthalten, eine falsche Verzeichnisstruktur besitzen, …). Kleiner Tipp (der bisher jedes Jahr von mindestens fünf Studenten ignoriert wurde): Vor der Abgabe einfach mal selbst das Archiv auspacken und nachsehen was drin ist.

Bei Fragen wenden Sie sich bitte an Ihren Praktikumsbetreuer während des Praktikums.


Sollten wir beim persönlichen Beantworten von Fragen feststellen, dass unsere Aufgabenstellung nicht präzise genug war, so werden wir einen konkretisierenden Eintrag in der Newsgroup erstellen. Zur Bewertung wird die Aufgabenstellung inklusive aller von uns erstellten Nachrichten in der Newsgroup herangezogen. Schauen Sie daher bitte ab und zu ebendort nach, ob sich die Aufgabenstellung inzwischen eventuell leicht geändert hat und ob ihre bereits fertige Lösung nochmal bearbeitet werden muss.

Abgabemodus

Die Abgabe erfolgt digital über das Goya-System. Die Dateien sind in einer Datei loesung.tar.gz verpackt abzugeben. In dieser tar.gz-Datei soll ausschließlich die Datei minako-syntax.y (ohne irgendwelche Unterverzeichnisse!) enthalten sein.

Zur Lösung der Aufgaben steht für Sie eine Datei aufgabenblatt-4.tar.gz mit einem vorgegeben makefile, dem Scanner minako-lexic.l sowie einem Codefragment minako-syntax.y und einer Testeingabe demorgan.c0 zur Verfügung.

Aufgabe 4 (100 Punkte)

Kurzbeschreibung

Implementieren Sie unter Verwendung des Werkzeugs Bison einen Parser für die Sprache C0. Erweitern Sie dazu das von uns vorgegebene Gerüst in der Datei minako-syntax.y.

Aufgabenstellung

Ihre Aufgabe besteht darin, einen Parser für die Sprache C0 zu erstellen. Dazu bekommen Sie von uns einen Scanner. (Sie können theoretisch auch Ihren Scanner vom Aufgabenblatt 3 benutzen – zur Korrektur werden wir jedoch den von uns gegebenen verwenden!)

Gegeben ist die Grammatik von C0 in EBNF. Da Bison leider keine EBNF, sondern nur BNF versteht, werden Sie die Grammatik zwangsläufig umbauen müssen. Dabei ist im Prinzip fast alles erlaubt, nur die Sprache darf sich dabei natürlich nicht ändern!

Folgende Anforderungen werden Ihre Lösung gestellt:

  • wenn man den Parser ohne Kommandozeilenparameter aufruft, soll er von stdin lesen, ansonsten aus der auf der Kommandozeile angegebenen Datei (dabei sollen eventuell auftauchende Dateizugriffsfehler wie üblich abgefangen werden)
  • die Implementation hat in einer Datei namens minako-syntax.y zu erfolgen
  • der Parser gibt im erfolgreichen Fall nichts aus und beendet sich mit dem Rückgabewert 0
  • bei einem Parserfehler wird eine Fehlermeldung ausgegeben und das Programm mit einem Rückgabewert ungleich 0 beendet
  • wenn Sie den Parser auf das mitgelieferte C0-Programm demorgan.c0 ansetzen, sollte er entsprechend nichts ausgeben und sich mit Rückgabewert 0 beenden – sehen Sie bitte diesen Test als Mindestvoraussetzung für eine Abgabe an.
  • die Verwendung von %expect ist untersagt

Zur Hilfestellung seien noch folgende Hinweise gegeben:

  • Gehen Sie am Anfang alle EBNF-Konstrukte durch und überlegen Sie sich, wie man diese jeweils generisch in BNF umwandeln kann.
  • In dieser Grammatik ist eine Mehrdeutigkeit enthalten, die einem spätestens bei der Implementierung auf‌fällt. Da es sich um eine „berühmte“ Mehrdeutigkeit handelt, werden Sie (so Sie nicht selbst auf eine Lösung kommen) im Netz bzw. in der Compilerbauliteratur Hilfe finden.
  • Sehen Sie sich nochmal die Bedeutung von %left, %right und %nonassoc an, bevor Sie die Grammatik unnötig verkomplizieren.