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
- The first tree is an addition whose right side is a product, which is the precedence.
- The parentheses made an addition a factor, so the product is on the outside.
-
The trailing plus has no factor after it, and the error is the
The next lesson gives the tree a show of its own, so a value can be printed
as an expression and read back.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why does
termsit belowexprin the grammar?Answer
So multiplication binds tighter than addition
The deeper level is parsed first, which gives it the higher precedence.
-
What does a parse function return?
Answer
Either an error or the tree and the unused tokens
The unused tokens let the caller decide whether they are an error.
-
What is the tree of
1+2*3?Answer
Add (Num 1) (Mul (Num 2) (Num 3))
The product is the right operand of the addition.
-
What does this program print?
module Main (main) where main :: IO () main = print (2 + 3 * 4 :: Int)Answer
14
The product is 12 and the sum is 14.
-
Why are parentheses a factor?
Answer
A parenthesised expression is one operand
The brackets group an expression into a single factor.
-
What does this program print?
module Main (main) where main :: IO () main = print ((2 + 3) * 4 :: Int)Answer
20
The sum is 5 and the product is 20.
-
What does
parseAlldo with leftover tokens?Answer
Returns an error about unexpected input
Only an empty remainder is a complete parse.
-
What does this program print? ``
module Main (main) where main :: IO () main = print (10div2 :: Int)``Answer
5
Ten divided by two is five.
-
Which function parses a number or a parenthesised expression?
Answer
parseFactorThe factor is the smallest unit and handles the brackets.
-
What does this program print?
module Main (main) where main :: IO () main = print (length "1+2*3")Answer
5
The string has five characters.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev
-