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

Compilerbaupraktikum - Aufgabenblatt 5

Generelles

Abgabetermin

So, 13.07.2013 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 oder per E-Mail.

Sollten wir beim persönlichen Beantworten von Fragen feststellen, dass unsere Aufgabenstellung nicht präzise genug war, so werden wir Details per Mail an sie versenden. 

Abgabemodus

Die Abgabe erfolgt digital über das Goya-System. Die Lösung ist in einer Datei loesung.tar.gz verpackt abzugeben. In dieser tar.gz-Datei sollen ausschließlich die Dateien minako-syntax.y und minako.h (ohne irgendwelche Unterverzeichnisse!) enthalten sein:

Zur Lösung der Aufgaben steht für Sie eine Datei aufgabenblatt-5.tar.gz zur Verfügung.

Aufgabe 5 (100 Punkte)

Kurzbeschreibung

Implementieren Sie die semantische Analyse in den gegebenen Parser unter Zuhilfenahme der zur Verfügung gestellten Symboltabelle.

Aufgabenstellung

Nachdem Sie in den vergangenen beiden Praktikumsaufgaben unter Beweis gestellt haben (sollten), dass Sie mit der syntaktischen Analyse vertraut sind, wenden wir uns diesmal der semantischen Analyse zu. Wie Sie aus der Praktikumsveranstaltung bereits wissen, ist diese dafür verantwortlich, diejenigen Aspekte des Quellprogramms zu prüfen, die nicht von der Syntaxanalyse abgedeckt werden.

Die zu überprüfenden Bedingungen beinhalten unter anderem (die Punkte werden detailliert in den Lehrveranstaltungen besprochen):

  • Werden alle Variablen vor ihrer Benutzung deklariert?
  • Werden keine Variablen in einem Namensraum doppelt deklariert?
  • Sind bei allen Operationen die Typen der beteiligten Operanden verträglich?
  • Erfolgen Zuweisungen nur in „zuweisungsfähige“ Strukturen (also z. B. nicht „5=6“)?
  • Stimmen bei Funktions-/Prozeduraufrufen formale und aktuelle Parameter überein?
  • …

Aus der Praktikumsveranstaltung wissen Sie, dass das wichtigste Hilfsmittel der semantischen Analyse die Symboltabelle ist; eine Datenstruktur, in die alle Bezeichner mit den benötigten Attributen eingetragen werden. Um Ihnen die Arbeit etwas zu erleichtern, stellen wir Ihnen eine Symboltabelle zur Verfügung. Versuchen Sie am besten zunächst, deren Funktionsweise zu verstehen.

Studieren Sie dazu Header- und Quelltextfile der Symboltabelle. Des Weiteren ist in der Datei testsymtab.c ein Programm enthalten, das die Symboltabelle unabhängig von Scanner und Parser verwendet. Sie können das Programm beliebig umschreiben, wenn Sie ein bestimmtes Verhalten der Symboltabelle austesten wollen.

Haben Sie die Implementation und die Schnittstelle der Symboltabelle verstanden, so können Sie mit der Implementation der semantischen Analyse in den Parser beginnen. Sie werden dabei nicht umhin kommen, Regeln mit semantischen Aktionen zu belegen. Die ebenfalls notwendige Zuordnung von Typen zu den Terminalsymbolen haben wir bereits für Sie vorgenommen, allerdings fehlt die Zuordnung der Typen der Metasymbole, die Sie geeignet wählen sollten.

In C0 gelten unter anderem folgende semantische Bedingungen (in allen anderen Fällen gelten die Regeln von C):

  • implizite Casts von int nach float sind möglich (d. h. überall wo ein Konstrukt vom Typ float steht, darf auch ein int-Typ stehen), umgekehrt sind impliziere Casts von float nach int nicht erlaubt
  • explizite Casts (z. B. von float nach int) existieren prinzipiell nicht (wie man leicht in der Grammatik sieht)
  • bei for-Schleifen stellt sich die Frage, in welchem Block eine im Kopf deklarierte Variable gültig ist – wir benutzen die am einfachsten umzusetzende Festlegung, nach der es der umgebende Block ist. Folgendes Beispiel soll dies verdeutlichen:
for (int i=0; i<5; i++) {
  int i; // erlaubt, da ein Block tiefer
}
int i; // verboten, da gleicher Block wie das i im for-Kopf
  • das unäre Minus gilt nur für Zahlen, aber nicht für Boolesche Ausdrücke
  • Boolesche Operatoren (AND (&&) und OR (||)) funktionieren ausschließlich mit Booleschen Operanden (d. h. alle anderen Varianten sind semantische Fehler)
  • die Überprüfung, ob eine (Nicht-void-)Funktion immer ein return enthält, müssen Sie nicht implementieren
  • das Doppelleben von Integerwerten als Boolesche Werte (wie in C) existiert in C0 nicht
  • main() darf keine Parameter haben und muss vom Typ void sein
  • Weitere Hinweise/Hilfestellungen:
  • Die Liste der zu überprüfenden semantischen Bedingungen ist von Ihnen selbst zu erstellen (soll heißen: überlegen Sie bei jeder Regel, ob und welche semantische Bedingungen erfüllt sein müssen – klingt schwerer als es ist).
  • Es ist an einigen Stellen nötig, semantische Aktionen innerhalb von Produktionen zu verwenden.
  • Wenn Sie das Bedürfnis verspüren, die Grammatik zu ändern (auch wenn es für die Lösung der Aufgabe unnötig ist!), dürfen Sie das gerne tun – bedenken Sie jedoch potentielle Punktabzüge, falls Sie wider Erwarten doch die Sprache geändert haben sollten (wir prüfen natürlich auch noch einmal die korrekte Syntaxerkennung).
  • Da Sie die Symboltabelle nicht mit abgeben, ist es nicht zu empfehlen, an dieser Änderungen vorzunehmen; dasselbe gilt für alle anderen gegebenen Dateien (mit Ausnahme des Parsers in minako-syntax.y und minako.h).
  • Der Parser soll von stdin lesen (wir glauben Ihnen, dass Sie inzwischen yyin setzen können).
  • Der Parser soll weiterhin im fehlerfreien Fall nichts ausgeben und nur bei Fehlern eine Fehlermeldung nach stderr erzeugen.
  • Geben Sie bitte Ihre Lösung erst ab, wenn mindestens die folgenden semantischen Fehler erkannt werden (Lösungen, die diese Fehler nicht erkennen, werden von uns nicht weiter bearbeitet/bewertet!):
  • nicht deklarierte Bezeichner
  • doppelt deklarierte Bezeichner
  • Sollten Ihnen die Ideen ausgehen, welche semantischen Fehler man noch so abfangen sollte, können Sie einen Blick auf die Testsuite unter http://amor.cms.hu-berlin.de/~kunert/lehre/material/ werfen. Es handelt sich um eine Sammlung von fehlerhaften C0-Programmen, die viele (aber nicht alle) Testfälle abdeckt.