Frage zum Skript S.51

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Frage zum Skript S.51

Beitrag von patrix »

Hallo zusammen,
ich habe eine Frage zu der Anwendbarkeit der Zerlegungsregeln:

Angenommen es gibt folgende Gramatik:
G::= X|Y
X::= (ab|\(\varepsilon\))Z
Y::= (cd|\(\varepsilon\))Q
Z::=ef...
Q::=gh...

nun ist nach meinem Verständnis
starter[[X]]={ab, \(\varepsilon\)}
starter[[Y]]={cd, \(\varepsilon\)}
follow[[X]]={ef}
follow[[Y]]={gh}

Nun sind ja bereits starter[[X]] und starter[[Y]] nicht disjunkt da sie beide \(\varepsilon\) beinhalten also sind die auf Seite 51 definierten Regeln verletzt. Trotzdem kann aber ein eindeutiger AST erzeugt werden. Wo liegt mein denkfehler?

Über eine Antwort würde ich mich freuen.

Danke und Grüße,

Patrick

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Re: Frage zum Skript S.51

Beitrag von JanM »

Ich könnte mir denken, dass du wenn du das Epsilon nimmst, dein X ja mit starters[[Z]] und dein Y mit starters[[Q]] beginnt und da diese disjunkt sind (zumindest so wie du es angegeben hast) sind auch starters[[X]] und starters [[Y]] disjunkt.
Bin mir aber auch nicht sicher.

Jens Huthmann
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 192
Registriert: 10. Nov 2011 19:42

Re: Frage zum Skript S.51

Beitrag von Jens Huthmann »

Ich gehe bei meiner Antwort davon aus das "ab,cd, ef, gh" Tokens sind und nicht als einzelne Buchstaben behandelt werden.

\(starters[[X]]\) bestimmt man mit der Regel \(starters[[XY]] = starters[[X]] \cup starters[[Y]]\) mit \(X = ab|\epsilon\), \(Y = Z\) da aus \(X\) \(\epsilon\) herleitbar ist.

\(starters[[ab|\epsilon]]\) wiederum bestimmt man mit der Regel \(starters[[X|Y]] = starters[[X]] \cup starters[[Y]]\) mit \(X = ab\), \(Y = \epsilon\).

Aus \(starters[[\epsilon]] = \{\}\) folgt \(starters[[ab|\epsilon]]=\{ab\}\).
Offensichtlich ist \(starters[[Z]] = \{ef\}\).

Daraus folgt \(starters[[X]]=\{ab,ef\}\).

Wenn man das nun analog für Y anwendet bekommen wir \(starters[[Y]]=\{cd,gh\}\).

Man sieht nun leicht das die Startermengen disjunkt sind und daher keine der Regeln verletzen. Daher funktioniert die Grammatik auch.

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Re: Frage zum Skript S.51

Beitrag von patrix »

Hallo nochmals,

ich verstehe \(\epsilon\) existiert in der Tokenmenge nicht. Ist jetzt auch irgendwie logisch :D.

Danke und Grüße

Patrick

Antworten

Zurück zu „Archiv“