Capstone B: the parser

A parser with precedence

The parser is a recursive descent over the token list: term reads a factor and then any number of times or divides. A factor is a number or a parenthesised expression. That three-level grammar is what makes Each function returns parseAll does at the end.

The program

module Main (main) where import Data.Char (isDigit) data Token = TNum Int | TPlus | TMinus | TStar | TSlash | TLParen | TRParen deriving (Show, Eq) data Expr = Num Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr deriving (Show, Eq) lexer :: String -> [Token] lexer [] = [] lexer (c : cs) | c == ' ' = lexer cs | c `elem` "+-*/()" = symbol c : lexer cs | isDigit c = let (digits, rest) = span isDigit (c : cs) in TNum (read digits) : lexer rest | otherwise = error ("bad character: " ++ [c]) where symbol '+' = TPlus symbol '-' = TMinus symbol '*' = TStar symbol '/' = TSlash symbol '(' = TLParen symbol ')' = TRParen symbol other = error ("bad symbol: " ++ [other]) parseExpr :: [Token] -> Either String (Expr, [Token]) parseExpr tokens = do (left, rest) <- parseTerm tokens restExpr left rest where restExpr left (TPlus : rest) = do (right, rest') <- parseTerm rest restExpr (Add left right) rest' restExpr left (TMinus : rest) = do (right, rest') <- parseTerm rest restExpr (Sub left right) rest' restExpr left rest = Right (left, rest) parseTerm :: [Token] -> Either String (Expr, [Token]) parseTerm tokens = do (left, rest) <- parseFactor tokens restTerm left rest where restTerm left (TStar : rest) = do (right, rest') <- parseFactor rest restTerm (Mul left right) rest' restTerm left (TSlash : rest) = do (right, rest') <- parseFactor rest restTerm (Div left right) rest' restTerm left rest = Right (left, rest) parseFactor :: [Token] -> Either String (Expr, [Token]) parseFactor (TNum n : rest) = Right (Num n, rest) parseFactor (TLParen : rest) = do (expr, rest') <- parseExpr rest case rest' of TRParen : rest'' -> Right (expr, rest'') _ -> Left "expected )" parseFactor [] = Left "unexpected end of input" parseFactor (token : _) = Left ("unexpected token " ++ show token) parseAll :: String -> Either String Expr parseAll input = do (expr, rest) <- parseExpr (lexer input) case rest of [] -> Right expr _ -> Left "unexpected input after the expression" main :: IO () main = do print (parseAll "1+2*3") print (parseAll "(1+2)*3") print (parseAll "1+")

ghc -Wall -O1 -o parser parser.hs
./parser

Right (Add (Num 1) (Mul (Num 2) (Num 3)))
Right (Mul (Add (Num 1) (Num 2)) (Num 3))
Left "unexpected end of input"

Reading the three lines