www.jammni.de

Gepostet:
20.05.2010 09:01

Konstanten in Haskell

Hallo,
habe soweit die Funktion First erstellt. Habe nun leider ein Problem für die leere Produktion. Ich möchte gerne eine Konstante für die leere Produktion erstellen. zb: epsilon = "eps".
in diesem Code möchte ich dann:


first'::[Production]->[Symbol]->[Symbol]->[Symbol]
first' prod _ [] = []
first' prod a (x:z)| isTerminal x = [x]
first' prod a (x:z)| x `elem` a = first' prod a z --NonTerminal already checked
                  ....

für den ersten Pattern [] statt der leeren liste eps übergeben, aber das kann halt so nicht funktionieren, obwoh "eps" ja eigentlich schon ein String wäre, und Symbol ist ja laut Def String oder Char. Vielleicht kannst Du mir ja nochmals helfen, danke
arnold

Zum Seitenanfang

Siracusa

Gepostet:
20.05.2010 17:49

Hallo,

du könntest einen neuen Datenkonstruktor einführen, dass ein Symbol auch Eps sein kann, also data Symbol = ... | Eps. Oder aber direkt für Produktionen einen neuen Datenkonstruktor, der eine leere Regel darstellt. Das macht aber an anderer Stelle vermutlich Umstände, weil du diesen zusätzlichen Fall in Patterns u.U. abfangen musst. eps = [] wird nicht funktionieren, weil du dann in einem Pattern nicht gegen eps matchen kannst. Ich würd's einfach lassen wie es ist :-)

Viele Grüße,

Siracusa

Zum Seitenanfang

arnold74

Gepostet:
21.05.2010 12:59

Hallo,
danke für deine schnelle Antwort. Nun leider gibt es aber mit dieser Funktion ein Problem:


first'::[Production]->[Symbol]->[Symbol]->[Symbol]
first' prod _ [] = []
first' prod a (x:z)| isTerminal x = [x]
                   | x `elem` a = first' prod a z --NonTerminal already checked
                   | nullable'' prod  x = (first' prod (x:a) z)++ concat( map (first' prod (x:a)) (find2 (symtoVar x) prod)) 
                   | otherwise = concat $ map (first' prod (x:a)) (find2 (symtoVar x) prod)

denn wenn ich nun Produktionen folgender Art habe muss ich ja auch Epsilon (leere Projektion) [] irgendwie zur Ergebnismenge hinzufügen
A-> AB
B->
B-> Bc
...
dann muss ich ja zu first(B) auch Epsilon hinzufügen, dh ich muss auch die leere Menge hinzufügen aber mit ++ wird doch die leere Menge nicht hinzugfügt ich meine [Terminalsymbole]++[]=[Terminalsymbole]. Irgendwie muss ich das Resultat so hinbekommen dass auch die leere Menge dort enthalten ist. Vielleicht kannst Du mir ja auch diesmal weiterhelfen.

danke
arnold

Zum Seitenanfang

arnold74

Gepostet:
21.05.2010 17:22

Leider befindet sich in der Funktion zur Berechnung von first noch ein Fehler, den ich leider nicht finde:
bei dieser Ausgabe der Produktionen
S {
S : A B
A :
A : a A
B :
B : b B
}
sollte ja first(S)={a,b,epsilon}, wobei ich das Problem mit Epsilon noch zu lösen habe
leider bekomme ich bei First diese Ausgabe
("S",[a])
dh: nullable scheint richtig implementiert zu sein, denn das Programm sucht richtigerweise die Produktionen von A, leider jedoch nicht mehr diese von B. Dies sollte jedoch laut drittem Guard (siehe Listing oben) doch passieren. Komme einfach nicht dahinter wo der Fehler liegt. Hier wäre ein Debugger Step by Step sicherlich hilfreich. Vielleicht siehst Du ja den Fehler Siracusa.

danke
arnold

Zum Seitenanfang

Siracusa

Gepostet:
21.05.2010 18:11

> aber mit ++ wird doch die leere Menge nicht hinzugfügt

So wie du es gemacht hast nicht, denn die Vereinigung mit einer leeren Menge ist wieder die Ausgangsmenge selbst. Du kannst aber mit der Menge vereinigen, die nur eine leere Menge enthält: menge ++ [ [] ]. Das funktioniert aber nur, wenn menge selbst wieder Listen enthält. [Symbol] ++ [[]] würde nicht gehen, weil ein Symbol keine Menge/Liste ist. Da bliebe dann die Möglichkeit, ein spezielles Symbol für eps einzuführen.

> Hier wäre ein Debugger Step by Step sicherlich hilfreich

Der GHCi hat einen eingebauten Debugger. Die Benutzung ist allerdings gewöhnungsbedürftig, genauso wie die Auswertung der Resultate. Näheres dazu ist in der GHC-Dokumentation zu finden. Oder halt die gute alte Methode - mit Zettel und Stift selbst auswerten :-)

Viele Grüße,

Siracusa

Zum Seitenanfang

arnold74

Gepostet:
22.05.2010 16:33

Danke,
habe den Fehler in der Zwischenzeit gefunden.
Leider hänge ich immer noch beim Problem mit dem Hinzufügen der leeren menge oder eben Eps. Habe leider nicht ganz verstanden wie Du das lösen würdest. Ich müsste auf jeden Fall für Produktionen, die direkt auf der leeren Menge abgebildet werden ein Eps oder eben die leere Menge hinzufügen.
Mir ist nicht klar wieso ich nicht einfach beim Pattern für die leere Menge


first'::[Production]->[Symbol]->[Symbol]->[Symbol]
first' prod _ [] = [] --wieso kann ich hier nicht einfach "Eps" hinschreiben
first' prod a (x:z)| isTerminal x = [x]
                   | x `elem` a = first' prod a z --NonTerminal already checked
                   | nullable'' prod  x = (first' prod (x:a) z)++ concat( map (first' prod (x:a)) (find2 (symtoVar x) prod)) 
                   | otherwise = concat $ map (first' prod (x:a)) (find2 (symtoVar x) prod)

ich möcht doch einfach für leere Menge "Eps" hinschreiben. Dies ist doch ein String und Symbol ist ja laut Definition String(=Variable) oder Char(=Terminal).

Wenn ich dich zuvor richtig verstanden habe würdest Du folgendes machen Data Symbol = Symbol | Eps
aber wie würdest Du dann Eps einfüge oder wo deklarierst Du den Wert für Eps. Muss sagen das mit den Declaring Types ist mir noch nicht so ganz klar. Vielleicht kannst Du mir ja sagen wie ich es machen sollte!
Das mit [[]] kann ja nicht funktionieren da als Rückgabewert [Symbol] erwartet wird.
danke
arnold

Zum Seitenanfang

Siracusa

Gepostet:
22.05.2010 18:14

> wieso kann ich hier nicht einfach "Eps" hinschreiben

Wenn Eps ein Symbol ist dann, kannst du dort zumindest [Eps] hinschreiben

> aber wie würdest Du dann Eps einfüge oder wo deklarierst Du den Wert für Eps

Also wenn du einen Typ definierst data X = A | B, dann gibt es zwei Werte vom Typ X, nämlich A und B. Mehr braucht es nicht bei einer Datentypdefinition. Um einen Wert zu erzeugen benutzt du dann einfach A, oder verwendest A in einem Patternmatching. data Y = C Int | D String ist das gleiche, nur jetzt können in den Werten C und D jeweils noch ein Int bzw. ein String gespeichert werden; C 10 oder D "Hallo" wären dann legale Werte vom Typ Y. In diesem Fall konstuiert C aus einem Int einen Wert vom Typ Y.

Gleiches gilt nun auch für data Symbol = V Variable | T Terminal, wenn du also eine Variable oder ein Terminal in ein Symbol umwandeln willst, musst du ein V bzw. ein T "darumwrappen". Fügst du Symbol noch einen dritten Konstruktor Eps hinzu, dann benutzt du den einfach so: Eps, ohne noch irgendwo irgendwas zu deklarieren oder definieren.

Zum Seitenanfang

arnold74

Gepostet:
24.05.2010 14:17

danke!

Zum Seitenanfang

Haskell-Forum