Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Skuld

Erfahrener Schreiberling

  • "Skuld" is male
  • "Skuld" started this thread

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

1

Monday, June 14th 2010, 1:00pm

PSÜ 7. Übungsblatt, Aufgabe 2

Hallo!

Ich war nicht bei der Übung, daher sind mir ein paar Sachen beim Konflikte lösen in der action- und goto-Tabelle in bisschen unklar.

Aufgabe 2.1, der erste Konflikt wäre ja im Zustand 9 beim + Zeichen zwischen shift5 und reduce1. Auf dem Stack wäre da S+S, wenn ich das richtig sehe. Nun sind Prioritäten und Assoziativitäten gegeben. Mir ist nicht ganz klar, wonach ich jetzt entscheiden soll, ob shift5 oder reduce1 angewendet wird, hauptsächlich deswegen, weil ich nicht ganz nachvollziehen kann, was das shift5 bewirkt. Kann mir da jemand auf die Sprünge helfen?
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

derSmutje

Alter Hase

  • "derSmutje" is male

Posts: 295

Date of registration: Dec 7th 2004

2

Monday, June 14th 2010, 3:01pm

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.
/join #inf

This post has been edited 1 times, last edit by "derSmutje" (Jun 14th 2010, 3:02pm)


hamena314

Zerschmetterling

  • "hamena314" is male

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

3

Monday, June 14th 2010, 5:30pm

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!
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)

This post has been edited 1 times, last edit by "hamena314" (Jun 14th 2010, 5:31pm)


derSmutje

Alter Hase

  • "derSmutje" is male

Posts: 295

Date of registration: Dec 7th 2004

4

Monday, June 14th 2010, 6:14pm

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.
/join #inf

Skuld

Erfahrener Schreiberling

  • "Skuld" is male
  • "Skuld" started this thread

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

5

Monday, June 21st 2010, 10:37am

Danke für die Aufklärung.

Noch eine Frage zum aktuellen Übungsblatt Nr. 8 (wollte nicht schon wieder einen neuen Thread eröffnen).

Ich komme am Ende auf die Konfigurationen:

-> (7) [0S1B5C11, $]
-> (1) [0S1, $]

In der Tabelle unter dem Eintrag (1, $) steht nun ein shift 2 und nicht, wie erhofft, accept. Hab ich mich vorher irgendwo vertan oder ist das Wort tatsächlich nicht in der Grammatik?

A propos vertan: Bei den Epsilon-Produktionen bin ich mir nicht sicher, kann sein dass da mein Fehler liegt: Ersetzt man, wie bei anderen Produktionen auch 2*x Zeichen bei einem reduce, wenn auf der rechten Seite der Produktion ein Epsilon steht? Habe nämlich angenommen, dass die Länge des leeren Wortes 0 ist und man daher kein Zeichen ersetzt sondern nur hinten anhängt.
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

This post has been edited 1 times, last edit by "Skuld" (Jun 21st 2010, 10:38am)


SunshineSunny

Sonnenscheinchen auf'm Campus

6

Monday, June 21st 2010, 10:46am

Bis dahin alles richtig. :)

In der Vorlesung wurde gesagt was dann passiert. Sollte auch irgendwo im Skript zu finden sein.
Manche Männer bemühen sich lebenslang, das Wesen einer Frau zu verstehen.
Andere befassen sich mit weniger schwierigen Dingen z.B. der Relativitätstheorie.

Salz

Opa

  • "Salz" is male

Posts: 144

Date of registration: Dec 3rd 2009

7

Monday, June 21st 2010, 10:49am

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.
Damals…

Skuld

Erfahrener Schreiberling

  • "Skuld" is male
  • "Skuld" started this thread

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

8

Monday, June 21st 2010, 11:00am

Ah, alles klar :D Dankeschön!
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?