Zerlegungsregeln

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Zerlegungsregeln

Beitrag von Stefan1992 » 12. Nov 2014 16:47

Hallo,

ich stehe vor folgender Frage:

Ich habe eine Grammatik mit den Produktionen
S ::= aXb | bXb
X ::= a | \epsilon

Nun möchte ich über die Zerlegungsregeln überprüfen, ob ich eine LL(1)-Grammatik habe.
In G ist die Produktion X | Y enthalten und zwar einmal aXb | bXb und einmal a | \epsilon.

Für mich würde der erste Fall auch unter den ersten Punkt der Folie 50 (2. Satz) fallen, dass sich also weder aXb noch bXb zu \epsilon ableiten lassen. Somit hätte ich dann also starters[[aXb]] \cup starters[[bXb]] = {a} \cup {b} = \emptyset.

Der zweite Fall würde meiner Meinung nach unter Punkt 2 fallen, dass sich \epsilon trivialerweise zu \epsilon ableiten lässt.
Damit habe ich dann starters[[a]] \cup (starters[[\epsilon]] \cap follow[[a | \epsilon]]) = {a} \cup ({} \cap {a, b}) = {a} \cup {a, b} = {a} != \empty.

Dementsprechend wäre die Grammatik nicht LL(1).


Ist das so richtig?

Grüße

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

Re: Zerlegungsregeln

Beitrag von Jens Huthmann » 16. Nov 2014 15:52

Ja, das ist richtig so. Am besten auch mal mit einer Produktion üben die auf der rechten Seite mehr als zwei Alternativen hat.

Antworten

Zurück zu „Archiv“