Fachrat Informatik - Forum

Hallo, weiss einer von euch wie der o.g. Parser arbeitet, wenn er einen reduce -Operation auf einen Stack mit folgendem Inhalt : [0,...$] anwenden soll? // [0,...$] sei die Konfigurationsschreibweise des Parsers

//[momentaner Stackinhalt, restliche Eingabe$] vgl. S.57

Laut Skript wäre dann folgender Arbeitsschritt durchzuführen:

Quoted

Ist action [z,a] = reduce A -> alpha, dann lösche die obersten 2 * |alpha| Einträge vom Stack. (Dann) Sei z´ der dann oberste Zustand auf dem Stack. Schreibe A und danach den Zustand goto [z',A] auf den Stack. Gebe die Produktion A -> alpha aus. vgl. Seite 71 , (C) Prof. Dr. R. Parchmann

===> Jetzt das Problem: wir haben keine 2 obersten Einträge im Stack...lediglich ein einziges Symbol für den Startzustand...eine 0...was tun?

Zur Anwendbarkeit der reduce-Operation sei noch folgendes erwähnt:

Quoted

Eine reduce-Operation ist nur dann anwendbar, wenn zum momentanen Zeitpunkt die obersten Symbole auf dem Stack die rechte Seite einer Produktion bilden. Diese Symbole werden gelöscht und durch das Symbol auf der linken Seite der Produktion ersetzt. vgl. Seite 70 , (C) Prof. Dr. R. Parchmann

im konkreten Anwendungsfall bildet das oberste Symbol auf dem Stack...also die 0...die rechte Seite einer Produktion, daher ist die reduce Operation anwendbar und muss durchgeführt werden.

Ist die Aufgabe nicht lösbar - was meint ihr? Oder würdet ihr die "0" 2x löschen, dann ist z`=0 oder vll. sogar leer, wir würden A schreiben...in konkreter Aufgabe wäre das S (wegen einer r2-Operation: (2) S -> epsilon ) und goto [z`=0,S]=1 ...??und dann wieder eine "0" hinschreiben?

Es könnte sich ergeben [S1,...$] oder [0S1,...§]...als nächstes folgt eine r6-Operation laut gegebener Tabelle: wir löschen wiederum die beiden obersten Elemente des Stacks [leer oder 0,...$] oder [0,...$] und wenden die Produktion 6 an:

(6) B-> epsilon beim Zustand 0 an: [leer oder 0B??,...$] -> goto [z`=0,B]= nicht definiert! ->error!

- >oder: [0B??,...$] --> goto [z`=0,B]= nicht definiert! ->error!

Oder die reduce-Operation überspringen?

Quoted

Ist action [z,a]=error (LEERER EINTRAG IN DER ACTION-TABELLE], dann beende das Parsing mit einer Fehlermeldung. Das Eingabewort gehört nicht zu einer Sprache. vgl. Seite 71, (C) Prof. Dr. R. Parchmann

Quoted from "SunshineSunny"

Denn nichts mal 2 bleibt nichts!

Das heisst also, dass der Startzustand 0 nicht gelöscht werden kann.

P: (2) S-->epsilon

[0,....$] --> [0S1,...$]

#################################################################

Fortsetzung des Problems

###############################################################

Im folgenden wird einer Tabelle eine r6-Operation entnommen - die dazugehörige Produktion ist: (6) B -> epsilon; die r6-Operation wird auf den Stack [0S1,....$] angewendet.

( Nebeninformation: im Zustand 0 existiert nur goto(z=0,S)=1; im Zustand 1 existiert nur goto(z=1,A)=4 und goto(z=1,B)=5 )

Auf dem Stack befindet sich die Einträge S und 1, die gelöscht werden, z` wird 0 gesetzt, A=B wird auf den Stack geschrieben und danach wird versucht goto[z´=0,B] auf den Stack zu schreiben...ABER wie erwähnt existiert im Zustand 0 nur goto(z=0,S)...wird dann das Parsing beendet?Oder springen wir zu Zustand 1? - Das steht ausdrücklich nicht im Skript...eventuell fehlt ein Eintrag in der goto-Tabelle im Zustand 1 - und zwar in der Spalte B.

[0S1,...$] ---(6)---> [0Bgoto[z´=0,B],...$] ---> ???

Quoted from "SunshineSunny"

Das ist doch das gleiche... du reduzierst genauso...

wenn du nach Produkionen reduzierst, die ein Epsilon enthalten, dann schreibst du die linke Seite der Produktion hin.... Und entfernst Nichts!

das heisst also, es ist generell gar nicht erforderlich nur die obersten 2 Stack-Einträge zu löschen wie im Skript beschrieben...für den Spezialfall epsilon wird gar nix entfernt - ansonsten werden wie in Beispiel 2.52 die jeweils rechten Seiten der Produktionen bei reduce gelöscht z.B.

[0(4E8+6T9,)*a$] --(1)--> [0(4E8,)*a$] //angewendete Operation: reduce1 (vgl. Tabelle) ; Produktion (1) E -> E+T

// E8+6T9 wurde durch E ersetzt, z´=4, goto(z´=4,E)=8 wurde darauf auf den Stack geschrieben

Quoted

Ist action [z,a] = reduce A -> alpha, dann lösche die obersten 2 * |alpha| Einträge vom Stack. (Dann) Sei z´ der oberste Zustand auf dem Stack. Schreibe A und danach den Zustand goto [z',A] auf den Stack. Gebe die Produktion A -> alpha aus. vgl. Seite 71 , (C) Prof. Dr. R. Parchmann

Alles klar - danke für deine Hilfe!