Fachrat Informatik - Forum

Wenn ich das richtig verstehe, dann liegt auf dem Stack gerade S+S und der Lookahead zeigt gerade ein +-Zeichen. D.h., es folgen zwei Additionen (S+S+...) aufeinander. Nun stellt sich die Frage der korrekten Klammerung, also ob das Ergebnis der Ausführung nachher (S+S)+... oder S+(S+...) sein soll.

Wendest du in dem von dir beschriebenen Zustand nun eine reduce-Operation an, so wird die bereits auf dem Stack befindliche Addition auf dem Stack durch das entsprechende Nicht-Terminal einer umgekehrten Ableitungsregel ersetzt. Hierdurch wird also der Fall (S+S)+.... erzeugt.

Führst du in dem von dir beschriebenen Zustand eine shift-Operation aus, so wird das +-Zeichen auch noch auf den Stack getan. Werden im weiteren Verlauf reduce-Operationen angewendet, so läuft das ganze auf den Fall S+(S+....) hinaus.

Ich denke das ist genau das Problem.
Man hat 2 Möglichkeiten (eben den Shift oder Reduce Konflikt) und weiss nicht was man anwenden soll.
Natürlich geht hier beides
(S+S)+... oder (S+(S+...) aber die Frage ist was davon genommen werden soll.

Wenn ich das nicht ganz falsch verstehe, so zeigt das reduce an was auf dem Stack liegt:


In der Übung hat Torben 2 Bäume aufgemalt und meinte dass shift dem rechten Baum entspräche und reduce dem linken Baum. Daher würde ich in der ersten Zeile der Tabelle für s5 plädieren, da das + rechtsassoziativ ist.
Aber wie Skuld hab ich nicht so den Durchblick wie man die weiteren Konflikte korrekt lösen könnte...

HAVE PHUN!

wenn das +-Zeichen rechtassoziativ sein soll, so stimme ich hamena zu, dass an der stelle geshiftet werden muss.

Für die Multiplikation und Potenz hängt es nun von den Prioritäten der Operatoren ab, welche Klammerung und damit welche Aktion zu wähle ist.

Bis dahin alles richtig.

In der Vorlesung wurde gesagt was dann passiert. Sollte auch irgendwo im Skript zu finden sein.

Das ist ein "Fehler" in der Aufgabenstellung, Torben hatte in meiner Übungsgruppe schon darauf hingewiesen. Die Parsingtabellen auf den Übungsblättern wurden nicht per Hand generiert, sondern mit yacc. Und yacc fasst im letzte Schritt alle accept-Zustände zu einem zusammen, indem es ein EOF ($) shiftet und in den accept-Zustand springt. Da man in C am Ende der Datei mit fgetc() immer ein EOF bekommt, kann yacc das EOF einfach auf den Keller shiften, in der Eingabe erscheint dann ein neues EOF ($). Der neue Zustand wäre also
[0S1$2,$]

Bei den anderen Übungsblättern wurde dieser letzte Zustand, der ein $ shiftet, per Hand entfernt, es wurde auf diesem Aufgabenblatt einfach vergessen.