www.jammni.de

Gepostet:
13.05.2010 16:16

Komplette Liste übergeben bei Pattern Matching

Hallo,
versuche gerade eine Funktion für Nullable für meine Grammatik zu erstellen (siehe vorige Postings).
Aber ich bleibe beim Implementieren von Nullable hängen. Eine Grammatik ist nullable, wenn:
A->[] also Epsilon, somit ist A nullable
B-> CD , B ist auch nullable wenn sowohl C als auch D nullable sind.
Hier mein Code:


nullable1 :: [Production]->Variable->Bool
nullable1 ((Production x []):rest) s |((x)==s) = True
                                    |((x)/=s) = nullable rest s
                                    |otherwise= False            

nullable :: [Production]->Variable->Bool
nullable ((Production x (T t:z)):_) _ = False
nullable ((Production x (V v:[])):_)y = ??

Bei der Funktion nullable1 teste ich ob es Produktionen gibt die direkt nullable sind, also (A->[]) für alle Produktionen, wenn eine übergebene Variable eine solche Produktion ergibt ist nullable1 True.
In einer weiteren Funktion teste ich die anderen Fälle:
wenn eine Produktion mit einem Terminal anfängt (T..) dann false
und hier nun mein Problem ich möchte nun die Variable und mit den Produktionen nullable1 übergeben, wie mache ich das? Kann ich das überhaupt, ich stehe irgendwie auf der Leitung! Mir ist klar dass ich bei
einem Patternmatching der Art nullable pliste v = nullable1 pliste v aufrufen kann!
Oder wie würdet Ihr das Problem lösen, danke Arnold

Zum Seitenanfang

arnold74

Gepostet:
13.05.2010 17:45

Verschachtelte Liste von leeren Listen befreien

Hallo,
bin nun schon ein bißchen weiter, aber nun habe ich leider das Problem von verschachtelten Listen:
Die Ausgabe sieht folgendermaßen aus:
A {
A :
A : a A
A : B
B :
B : b B
}
hier meine Ausgabe bei der Suche nach allen Produktionen von A
[]
[a,A]
[B]
[]
[]
Hier meine beiden entsprechenden Funktionen (2 Varianten), bei Variante 1 würde zwar die Ausgabe passen, aber ich würde gerne direkt auf der Grammatik arbeiten!


find ::  Variable -> [(Variable,[Symbol])] ->[Symbol]
find k t =concat$ [vs|(k',vs)<-t, k ==k']

find2 :: Variable -> [Production] -> [[Symbol]]
find2 k ((Production x xs):[]) =[[vs | vs <- xs, x==k]]
find2 k ((Production x []):rest) =[[vs | vs <- [], x==k]]++ find2 k rest
find2 k ((Production x xs):rest) = [[vs | vs <- xs, x==k]]++ find2 k rest

Ich benötige eine Ausgabe der Art [[a,A],[B]], denn dann könnte ich ein map und and auf die einzelen Elemente der Liste anwenden, denn dort müssen ja alle Variablen nullable sein und ein or auf die gesamten Listen. Ich hoffe mir kann jemand einen Tipp geben wie ich das berwerkstellige.
danke

Zum Seitenanfang

Siracusa

Gepostet:
14.05.2010 17:55

Hallo,

zu nullable: Die Liste mit den Produktionen und die Variable ist ja gegeben, also kannst du die auch an nullable1 übergeben. Das Problem ist u.U. nur, dass die Liste dann nicht mehr komplett ist. Ich würde bei nullable erstmal alle Produktionen herausfiltern, die auf der linken Seite die Variable haben und dann für jede dieser gefilterten Produktionen testen ob sie nullable1 ist. nullable1 würde also für eine Produktion prüfen, ob sie entweder leer ist oder nur aus Variablen besteht, die wiederum nullable sind.

Zu find: Offenbar musst du dein Ergebnis nochmal "nachfiltern", und zwar könnte da filter (not . null) hilfreich sein, also alle nichtleeren Listen.

Viele Grüße,

Siracusa

Zum Seitenanfang

arnold74

Gepostet:
16.05.2010 10:35

Hallo,
zuerst nochmals Danke, bin jetzt ein Stück weiter: Habe die Funktionen für Nullable implementiert. Nun möchte ich das mal mit GHCI überprüfen. Ich möchte über GHCI einfach die Funktion nullable testen. Wenn ich deinen Code vom vorigen Posting (danke) in die Haskell-Datei eintrage, wie kann ich dann testen ob Nullable korrekt ist. :l FirstFollow.hs wird korrekt geladen :-) ... nach Tagen des Testens und nicht zuletzt deiner Hilfe. Ich suche einen Weg wie ich einfach und schnell Testen und das Ergebnis angezeigt bekomme! Mir ist leider nicht klar wie ich wenn ich deine Definition von gram1 in meine hs-Datei einfüge, diese Funktion von nullabel aufrufen kann.

Hier der Code von Nullable


nullable :: [Production]->[Symbol]->Bool
nullable prod [] = True
nullable prod (T t:z) = False
nullable prod (V v:[])= nullable' prod v
nullable prod (V v:vx)= (nullable' prod v) && (nullable prod vx)

In nullable' werden alle Produktionen von v durch das aufrufen von find2 ermittelt und auf nullable überprüft. Ich würde gerne nullable testen, dh: im GHCI einfach nullable eingeben und irgendwie die Parameter übergeben oder eben schon im hs-File definieren.

danke
Arnold

Zum Seitenanfang

arnold74

Gepostet:
16.05.2010 18:32

Casting von Variablen in Haskell

Bin beim Implementieren von First:
Hier mein Code


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 x prod)))

find2 erwartet als ersten Parameter eine Variable. Wie kann ich einen Cast von Symbol (Variable=String|Terminal=Char) zu Variable machen. find2 soll ja eigentlich nur nach den Produktionen einer Variablen suchen. Ich bekommen klarerweise die Fehlermeldung, dass find2 einen Wert vom Typ Variable und nicht Symbol erwartet.

danke
arnold

Zum Seitenanfang

arnold74

Gepostet:
17.05.2010 19:13

Hallo,
scheitere jetzt schon seit Stunden am Versuch zu überprüfen ob eine Variable in einer der Produktionen ([Symbol]) vorkommt. Dies hängt ja direkt mit meinem geschilderten Problem vom Cast zusammen. Deshalb habe ich eine Funktion iselem eingeführt die überprüfen soll ob eine Variable in der Produktion vorkommt. Das Problem beim Patternmatching liegt bei der letzten Stelle von Symbol.
Hier der Code


iselem:: Variable -> [Symbol]-> Bool
iselem x (V y:[]) = ??
iselem x (T y: ys) = iselem x ys
iselem x (V y: ys) = (x==y) || (iselem x ys)

Ich kann doch nicht (V y:[]) = x==y setzen denn dann hängt der Wert der Funktion nur von dem letzten Buchstaben ab.

danke
arnold

Zum Seitenanfang

Siracusa

Gepostet:
19.05.2010 00:00

Hallo,

also Casts (implizite Typumwandlungen) gibt es bei Haskell nicht. Du kannst dir aber eine Funktion schreiben, die eine Konvertierung vornimmt. Von Variable zu Symbol kommst du, indem du den Datenkonstruktor V auf deine Variable anwendest. Von Symbol zu Variable durch ein Patternmatching (V var) wobei var dann die Variable ist.

Viele Grüße,

Siracusa

Zum Seitenanfang

Haskell-Forum