Gepostet: |
kontexfreie Grammatik, lexer, Token . | ||||||||||
Hallo zusammen, ich habe da eine Aufgabe, wobei ich gar nicht weiss, womit ich anfangen soll :s und für irgendwelche Hilfe würde mich sehr freuen, es sieht folgendermaßen aus : Eine Sprache für arithmetische Ausdrücke sei durch KFG gegeben : Expr ::= Expr + Expr | Expr - Expr | Expr * Expr | Expr / Expr | (Expr) | Int ich soll in Haskell eine Funktion lexer :: String -> [Token]die einen String erwartet und diesen der lexikalischen Analyse unterzieht, dabei Leerzeichen und Zeilenumbüche entfernt, und eine Liste von Token (vom Typen Token) als Ergebnis liefert. Der Datentyp für Token sei in Haskell definiert als : data Token = TokenPlus -- + Sollten im String Zeichen enthalten sein, die nicht der Sprache entsprechen, so soll ein Fehler vom Lexer erzeugt werden. Zum Erzeugen von Fehlern können Sie die vordefinierte Funktion error :: String-> a verwenden und zum Konvertieren von Strings in Zahlen können Sie die vordefinierte Funktion read verwenden. Vielen Dank im Voraus . |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Na der Lexer ist ja noch der einfachere Teil. Eine mögliche Implementierung wäre (in Pseudocode):
Das ließe sich noch ein wenig straffen, wenn du eine Map von Char zu Token anlegst, und alle Fälle in lex, in denen ein einzelnes Zeichen gesucht ist, also +-*/(), damit in einen zusammenfasst. Aber das ist die Kür, mach erst mal die Pflicht... |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Hallo Landei , danke für die schnelle Antwort , aber seit gestern bemühe ich mich dein Pseaudocode in Haskellquellcode zu umwandeln aber vergeblich, bitte was ist mit der variable \" tokens \",die du definiert hast gemeint ? soll ich für sie auch einen signatur definieren oder wie ? ( sorry bin total Anfänger aber bin motiviert :)) in der 4. Zeile deines Pseaudocodes hast du geschrieben : string started mit Leerzeichen ... ich denke so viel ich die Aufgabenstellung verstanden habe muss die Leerzeichen nicht nur am Anfang des Strings entfernt werden, sondern in dem ganzen string, falls sie irgendwo auftretten . oder irre ich mich :) danke |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Ich hab mal was zusammengeschrieben:
tokenTable gibt an, welche Token hinzugefügt werden sollen, wenn ein bestimmtes Zeichen gefunden wird. Dabei verwende ich eine Liste, da man ja für \' \' und \'\\n\' nichts hinzufügen will. lexer übergibt die Arbeit an lexi, wobei eine leere Liste als Akkumulator für die Tokens mitgegeben wird. lexi verwendet die eingebaute Funktion lookup, um die richtigen Token zu finden. Allerdings kann es sein, dass wir in tokenTable unser Zeichen gar nicht finden. Deshalb führen wir eine zusätzliche Funktion consume ein, die pattern matching auf dem zurückgelieferten Maybe [Token] von lookup machen kann. Finden wir Token, fügen wir sie dem Akkumulator hinzu und rufen lexi rekursiv mit den restlichen Zeichen chars auf. Finden wir keine Token, kann es sich noch um eine Zahl handeln. Mit elementIndex (aus Data.List) überprüfen wir, ob es sich um eine Ziffer handelt. Wieder führen wir eine Funktion ein, um pattern matchen zu können. Falls wir keine Ziffer finden, ist das ein Fehler. Falls wir eine finden, müssen wir unterscheiden, ob es die erste Ziffer einer Zahl ist (dann machen wir ein neues TokenInt auf) oder nicht (dann nehmen wir das letzte TokenInt auseinander und addieren die neue Stelle \"hinten dran\"). Ist unser String auf diese Weise abgearbeitet, drehen wir die Tokenliste um und sind fertig. Das ist jetzt ein wenig komplizierter als ich vorher beschrieben hatte, dafür aber ziemlich kompakt. Ich hoffe, das hilft dir weiter. |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Hallo Landei, danke für die ausführliche Erklärung, ich habe versucht der Quelltext im GHCi zu laden, aber ich bekomme eine Fehlermeldung der Art : lexer.hs:4:8: lexical error in string/character literal at character \'\\\\\' irgendwelche Vorschläge ? :) |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Die Backslaslashes sind zu viel, das ist ein Bug im Forum: Es fügt vor jedem Quote oder Anführungszeichen automatisch einen Backslash ein. Lösche in meinem Beispiel alle Backslashes außer in tokenTable vor dem n (da muss einer davorstehen), dann sollte es gehen. |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
habe es gemacht und da bekomme ich eine neue Fehlermeldung und zwar dass die variablen TokenPlus..etc + TokenInt not in scope sind . Grüße |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Deine data-Definition von weiter oben brauchst du natürlich auch noch, die habe mal vorausgesetzt... | |||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Hier noch eine ganz einfache Version:
Zuerst werden mit translate einfach alle einzelnen Zeichen in ihre Tokens übersetzt, wobei TokenInts hier nur für einzelne Ziffern stehen. Erst im zweiten Schritt werden in unifyNumbers aus den TokenInts für Ziffern die TokenInts für ganzen Zahlen zusammengerechnet, während der Rest der Token-Liste unverändert bleibt. Einzige Schwierigkeit in diesem Code ist >>= (\"bind\"), eine Operation auf Monaden. Für Listen (die auch Monaden sind) ist es aber nicht weiter kompliziert. Es ähnelt ein bisschen der map-Funktion, der Unterschied ist aber, dass jedes Element einer Liste auf eine Ergebnisliste (und nicht wieder auf ein einzelnes Element wie bei map) abgebildet wird. Am Ende werden alle Ergebnislisten zu einer zusammengefügt. Will man z.B. alle Elemente einer Liste verdoppeln, kann man [1,2,3,4] >>= (\\x -> [x,x]) schreiben, was [1,1,2,2,3,3,4,4] ergibt. Natürlich geht es auch ohne bind, z.B. unter Verwendung von Maybe, wobei die Funtion catMaybes aus Data.Maybe aus einer Liste die (Just x)-Werte herausfiltert und die x in eine Liste packt
|
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
vielen Dank LANDEI es hat geklappt und ich habe vieles davon gelernt !!! danke :) | |||||||||||
Zum Seitenanfang | |||||||||||