## Parser **Ex 1.** Implement `term`. This is the grammar rule: ``` Term <- Factor [*/] Term | Factor ``` Assume that the function `factor` is already implemented. ``` active haskell import Data.Char data Operator = Plus | Minus | Times | Div deriving (Show, Eq) data Token = TokOp Operator | TokAssign | TokLParen | TokRParen | TokIdent String | TokNum Double | TokEnd deriving (Show, Eq) operator :: Char -> Operator operator c | c == '+' = Plus | c == '-' = Minus | c == '*' = Times | c == '/' = Div tokenize :: String -> [Token] tokenize [] = [] tokenize (c : cs) | elem c "+-*/" = TokOp (operator c) : tokenize cs | c == '=' = TokAssign : tokenize cs | c == '(' = TokLParen : tokenize cs | c == ')' = TokRParen : tokenize cs | isDigit c = number c cs | isAlpha c = identifier c cs | isSpace c = tokenize cs | otherwise = error $ "Cannot tokenize " ++ [c] identifier :: Char -> String -> [Token] identifier c cs = let (name, cs') = span isAlphaNum cs in TokIdent (c:name) : tokenize cs' number :: Char -> String -> [Token] number c cs = let (digs, cs') = span isDigit cs in TokNum (read (c : digs)) : tokenize cs' ---- parser ---- data Tree = SumNode Operator Tree Tree | ProdNode Operator Tree Tree | AssignNode String Tree | UnaryNode Operator Tree | NumNode Double | VarNode String deriving Show lookAhead :: [Token] -> Token lookAhead [] = TokEnd lookAhead (t:ts) = t accept :: [Token] -> [Token] accept [] = error "Nothing to accept" accept (t:ts) = ts expression :: [Token] -> (Tree, [Token]) expression toks = let (termTree, toks') = term toks in case lookAhead toks' of (TokOp op) | elem op [Plus, Minus] -> let (exTree, toks'') = expression (accept toks') in (SumNode op termTree exTree, toks'') TokAssign -> case termTree of VarNode str -> let (exTree, toks'') = expression (accept toks') in (AssignNode str exTree, toks'') _ -> error "Only variables can be assigned to" _ -> (termTree, toks') -- show term :: [Token] -> (Tree, [Token]) term toks = undefined factor :: [Token] -> (Tree, [Token]) --/show factor toks = case lookAhead toks of (TokNum x) -> (NumNode x, accept toks) (TokIdent str) -> (VarNode str, accept toks) (TokOp op) | elem op [Plus, Minus] -> let (facTree, toks') = factor (accept toks) in (UnaryNode op facTree, toks') TokLParen -> let (expTree, toks') = expression (accept toks) in if lookAhead toks' /= TokRParen then error "Missing right parenthesis" else (expTree, accept toks') _ -> error $ "Parse error on token: " ++ show toks parse :: [Token] -> Tree parse toks = let (tree, toks') = expression toks in if null toks' then tree else error $ "Leftover tokens: " ++ show toks' -- show main = (print . parse . tokenize) "x1 = -15 / (2 + x2)" ``` @@@ Show solution ``` haskell term :: [Token] -> (Tree, [Token]) term toks = let (facTree, toks') = factor toks in case lookAhead toks' of (TokOp op) | elem op [Times, Div] -> let (termTree, toks'') = term (accept toks') in (ProdNode op facTree termTree, toks'') _ -> (facTree, toks') ``` @@@