Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
26.06.2009, 16:00 Uhr
KFC Embryo
Ein Huhn

Hallo,

ich bin irgendwie völlig ratlos im Moment. Kennt sich einer mit der"Item-Menge" aus?

Ich hab zum Beispiel eine vorgegebene Grammatik:

Code:

I ->  a
I  -> aR
R ->  I
R ->  b
R ->  bR

Daraus soll jetzt diese angesprochene Menge gebildet werden. Da wandert irgendwie immer so ein Punkt. Das Schema verstehe ich nicht. Wisst ihr was ich meine?

Das erste sieht dann z.B. so aus:

Code:

I0={

I' -> .I
I -> .a
I -> .aR
}

Und dann geht das immer so weiter. Bei dieser Grammatik bis I6.
Aber wie gesagt ich versteh das Schema nicht.

Weiß jemand weiter?
Oder weiß jemand wo man das nachlesen kann?

Vielen Dank.

Gruß
KFC
--
An nescis, mi fili, quantilla prudentia mundus regatur?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
26.06.2009, 19:04 Uhr
FloSoft
Medialer Over-Flow
(Administrator)

meinst du evtl die äquivalenzklassen?
sonst weiß ich etz auch nicht was du meinst
--
class God : public ChuckNorris { };

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
27.06.2009, 02:38 Uhr
Blubber2063

So wie das mit dem I' aussieht erinnert mich das an das entfernen der Linksrekursion aus der Grammatik damit man den recursive decent parser schreiben kann. Meinst du sowas vielleicht ? Der Begriff ist mir jedenfalls noch nicht untergekommen.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
28.06.2009, 11:21 Uhr
KFC Embryo
Ein Huhn

Hi,

ich werde euch mal ein komplettes Beispiel posten:

Code:

E → E + T
E →  T
T → T * F
T → F
F →  ( E )
F →  id

I0 = { E→ . E
         E → . E + T
         E → . T
         T → . T * F
         T → . F
         F → . ( E )
         F → . id }

I1 = GOTO(I0, E) : { E → E .
                             E → E . + T}

I2 = GOTO(I0, T) : { E → T
                            T → T . * F}

I3 = GOTO(I0, F) : { T → F . }

I4 = GOTO(I0, ( ) : {F → ( . E )
                           E → . E + T
                           E → . T
                           T → . T * F
                           T → . F
                           F → . ( E )
                           F → . id }

I5 = GOTO(I0, id) : { F → id . }

I6 = GOTO(I1, + ) : {E → E + . T
                            T → . T * F
                            T → . F
                            F → . ( E )
                            F → . id }

I7 = GOTO(I2, * ) : {T → T * . F
                             F → . ( E )
                             F → . id }

I8 = GOTO(I4, E) : {F → ( E . )
                           E → E . + T}

I9 = GOTO(I6, T) : { E → E + T .
                            T → T . * F}

I10 = GOTO(I7, F) : {T → T * F . }

I11 = GOTO(I8, ) ) : {F → ( E ) . }

So hoffe jetzt ist ein bisschen verständlicher. Ich versteh nicht wie das abläuft im ganzen.

Danke.
--
An nescis, mi fili, quantilla prudentia mundus regatur?

Dieser Post wurde am 28.06.2009 um 11:22 Uhr von KFC Embryo editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
28.06.2009, 14:00 Uhr
0xdeadbeef
Gott
(Operator)

Das sieht mir nach der Aktionstabelle eines LR-Parsers aus, allerdings etwas anders aufgeschrieben, als ich das damals gelernt habe.

Wenn ich das richtig lese, bedeutet

Code:

I5 = GOTO(I0, id) : { F → id . }

so viel wie "wenn Zustand 0 auf dem Stack liegt und du id als Eingabe hast, lege Zustand 5 auf den Stack." Wobei I0 Zustand 0 und I5 Zustand 5 ist.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 28.06.2009 um 14:01 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ Allgemeines (OffTopic) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: