Code Vorlesung 1.06.

Dateiinhalt

module Expr where

import Prelude hiding (lex)
import Data.Char
import Data.Maybe

data Expr = Const Integer 
          | Plus  Expr Expr
          | Times Expr Expr
  deriving (Eq)

instance Show Expr where
  show (Const i)     = show i
  show (Plus  e1 e2) = "("++ show e1 ++ "+" ++ show e2 ++")"
  show (Times e1 e2) = "("++ show e1 ++ "*" ++ show e2 ++")"

instance Read Expr where
  readsPrec _ s = let (e,t) = parseExpr $ lex s in [(e,concatMap show t)]

-- Beispiel:
a2 = Times (Plus (Const 5) (Const 3)) (Const 2)

eval :: Expr -> Integer
eval (Const     n)  = n
eval (Plus  l r)    = eval l + eval r
eval (Times l r)    = eval l * eval r        

data Token 
  = CONST Integer
  | LPAREN | RPAREN | PLUS | TIMES 

instance Show Token where
  show (CONST i) = show i
  show LPAREN  = "("
  show RPAREN  = ")"
  show PLUS    = "+"
  show TIMES   = "*"


-- Beispiel:
s1 = [CONST 3, TIMES, LPAREN, CONST 8, PLUS, CONST 3, RPAREN, PLUS, CONST 5, TIMES, CONST 4]


-- Lexikalische Analyse
lex :: String -> [Token]
lex = undefined -- TODO


lexInt :: String -> Maybe (Integer, String)
lexInt s | null num  = Nothing
         | otherwise = Just (read num, rest)
  where
    (num,rest) = span (`elem` '-':['0'..'9']) s

-- Variante
lexInt1 :: String -> Maybe (Integer, String)
lexInt1 = listToMaybe . reads

-- Natürlich könnte man das auch komplett zu Fuss implementieren:
-- lexInt2 ('0':s) = ...
-- lexInt2 ('1':s) = ...
--  ...



-- Syntaxanalyse
parseExpr   :: [Token] -> (Expr,[Token])
parseProd   :: [Token] -> (Expr,[Token])
parseFactor :: [Token] -> (Expr,[Token])

parseExpr l  = let (summand1,rest1) = parseProd l in 
    case rest1 of
      PLUS:rest2 -> let (summand2,rest3) = parseExpr rest2
                    in  (Plus summand1 summand2, rest3)
      _other     -> (summand1,rest1)


parseProd = undefined -- TODO


parseFactor = undefined -- TODO


test :: Expr -- query GHCI for "test" to test your solution
test = read "1 * (2 + 3 * 4) + 5 * 6 + 7 + 8 * 9"