www.jammni.de

Gepostet:
21.05.2011 17:29

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

Int hier ist nichtterminal und erzeugt beliebige positive Ganzzahlen

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           -- +
            | TokenMinus         -- -
            | TokenMal            -- *
            | TokenGeteilt        -- /
            | TokenKlammerAuf -- (
            | TokenKlammerZu  -- )
            | TokenInt Int
   deriving (Eq,Show)

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

Landei

Gepostet:
21.05.2011 18:39

Na der Lexer ist ja noch der einfachere Teil. Eine mögliche Implementierung wäre (in Pseudocode):


lexer string = lex string [] where
    lex [] tokens = reverse tokens 
    lex string tokens
           | string started mit Leerzeichen oder Zeilenumbruch = lex (string ohne Leerzeichen oder Zeilenumbruch) tokens
           | string started mit \\\'+\\\' = lex (string ohne +) (TokenPlus : tokens)
           | string started mit \\\'-\\\' = lex (string ohne -) (TokenMinus : tokens)
           | ...
           | otherwise = error \\\"WTF!?!\\\"

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

korchix

Gepostet:
22.05.2011 14:40

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

Landei

Gepostet:
22.05.2011 16:08

Ich hab mal was zusammengeschrieben:


import Data.List

tokenTable = 
  [(\' \', [])
  ,(\'\\n\', [])
  ,(\'+\', [TokenPlus])
  ,(\'-\', [TokenMinus])
  ,(\'*\', [TokenMal])
  ,(\'/\', [TokenGeteilt])
  ,(\'(\', [TokenKlammerAuf])
  ,(\')\', [TokenKlammerZu])
  ]

lexer :: String -> [Token]
lexer string = lexi string []

lexi :: String -> [Token] -> [Token]
lexi [] tokens = reverse tokens
lexi (c : chars) tokens = consume $ lookup c tokenTable where
   consume (Just ts) = lexi chars (ts ++ tokens)
   consume Nothing = consumeNumber (elemIndex c [\'0\'..\'9\']) tokens
   consumeNumber Nothing _ = error $ \"Unknown character \" ++ [c]                           
   consumeNumber (Just i) (TokenInt j : rest) = lexi chars (TokenInt (10*j + i) : rest)
   consumeNumber (Just i) _ = lexi chars (TokenInt i : tokens)

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

korchix

Gepostet:
22.05.2011 19:08

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

Landei

Gepostet:
22.05.2011 21:46

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

korchix

Gepostet:
22.05.2011 23:22

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

Landei

Gepostet:
23.05.2011 00:03

Deine data-Definition von weiter oben brauchst du natürlich auch noch, die habe mal vorausgesetzt...

Zum Seitenanfang

Landei

Gepostet:
23.05.2011 09:31

Hier noch eine ganz einfache Version:


lexer :: String -> [Token]
lexer string =  unifyNumbers (string >>= translate) where
  translate \' \' = []
  translate \'\\n\' = []
  translate \'+\' = [TokenPlus]
  translate \'-\' = [TokenMinus]
  translate \'*\' = [TokenMal]
  translate \'/\' = [TokenGeteilt]
  translate \'(\' = [TokenKlammerAuf]
  translate \')\' = [TokenKlammerZu]
  translate \'0\' = [TokenInt 0]
  translate \'1\' = [TokenInt 1]
  translate \'2\' = [TokenInt 2]
  translate \'3\' = [TokenInt 3]
  translate \'4\' = [TokenInt 4]
  translate \'5\' = [TokenInt 5]
  translate \'6\' = [TokenInt 6]
  translate \'7\' = [TokenInt 7]
  translate \'8\' = [TokenInt 8]
  translate \'9\' = [TokenInt 9]
  translate c = error (\"Unknown character \" ++ [c])
  unifyNumbers [] = []
  unifyNumbers (TokenInt i : TokenInt j : xs) = unifyNumbers (TokenInt (10*i + j) : xs)
  unifyNumbers (x:xs) = x : unifyNumbers xs

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


import Data.Maybe

...

lexer :: String -> [Token]
lexer string =  unifyNumbers (catMaybes (map translate string)) where
  translate \' \' = Nothing
  translate \'\\n\' = Nothing
  translate \'+\' = Just TokenPlus
  translate \'-\' = Just TokenMinus
  translate \'*\' = Just TokenMal
  translate \'/\' = Just TokenGeteilt
  translate \'(\' = Just TokenKlammerAuf
  translate \')\' = Just TokenKlammerZu
  translate \'0\' = Just (TokenInt 0)
  translate \'1\' = Just (TokenInt 1)
  translate \'2\' = Just (TokenInt 2)
  translate \'3\' = Just (TokenInt 3)
  translate \'4\' = Just (TokenInt 4)
  translate \'5\' = Just (TokenInt 5)
  translate \'6\' = Just (TokenInt 6)
  translate \'7\' = Just (TokenInt 7)
  translate \'8\' = Just (TokenInt 8)
  translate \'9\' = Just (TokenInt 9)
  translate c = error (\"Unknown character \" ++ [c])
  unifyNumbers [] = []
  unifyNumbers (TokenInt i : TokenInt j : xs) = unifyNumbers (TokenInt (10*i + j) : xs)
  unifyNumbers (x:xs) = x : unifyNumbers xs

Zum Seitenanfang

korchix

Gepostet:
23.05.2011 14:47

vielen Dank LANDEI es hat geklappt und ich habe vieles davon gelernt !!! danke :)

Zum Seitenanfang

Haskell-Forum