Capstone B: the tokens
The second capstone
The second capstone is an expression parser and evaluator with a REPL, built over eight lessons: a lexer, a parser with precedence, a syntax tree, an evaluator, readable errors, a REPL, a test table and one extension. Every lesson shows the whole program of that stage.
The first stage is the lexer: a string of characters becomes a list of tokens. The token type is a sum type, which the types part of the course built by hand and the parser reads with a case.
data Token
= TNum Int
| TPlus
| TMinus
| TStar
| TSlash
| TLParen
| TRParen
deriving (Show, Eq)
The lexer
module Main (main) where
import Data.Char (isDigit)
data Token
= TNum Int
| TPlus
| TMinus
| TStar
| TSlash
| TLParen
| TRParen
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])
main :: IO ()
main = do
print (lexer "1 + 2 * (3 - 4)")
print (length (lexer "12/3"))
ghc -Wall -O1 -o lexer lexer.hs
./lexer
[TNum 1,TPlus,TNum 2,TStar,TLParen,TNum 3,TMinus,TNum 4,TRParen]
3
The details of the lexer
- span isDigit reads a run of digits as one number, so 12 is one token and not two.
- The spaces are dropped, which is why the token list has eight entries for a string of fifteen characters.
- An unknown character is an error here; the lesson on readable errors replaces it with a value and a position.
The next lesson reads the token list with a recursive descent parser and gives multiplication a higher precedence than addition.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is a lexer?
Answer
A function from characters to tokens
The lexer groups characters into the words of the language.
-
Why is the token type a sum type?
Answer
Each constructor is one kind of token with its own data
A token is one of several cases, which is what a sum type is.
-
What does
span isDigitdo?Answer
Takes the longest run of digits and leaves the rest
span returns the prefix that satisfies the test and the remainder.
-
What does this program print?
module Main (main) where main :: IO () main = print (span (< 3) [1, 2, 3, 4 :: Int])Answer
([1,2],[3,4])
The prefix 1 and 2 pass and the rest starts at 3.
-
Why does the token list of
1 + 2 * (3 - 4)have eight entries?Answer
The spaces are dropped and each number is one token
Four numbers and two operators and two parentheses make eight.
-
What does this program print?
module Main (main) where main :: IO () main = print (length "+-*/")Answer
4
The string has four characters.
-
What is a character the lexer does not know?
Answer
An error in this version, a value with a position later
The readable-errors lesson replaces the error call with a value.
-
What does this program print?
module Main (main) where main :: IO () main = print (read "12" :: Int)Answer
12
read turns the digits into the number.
-
What does the parser of the next lesson take as input?
Answer
The list of tokens
The lexer has already turned the characters into tokens.
-
What does this program print?
module Main (main) where main :: IO () main = print (filter (> 1) [1, 2, 3 :: Int])Answer
[2,3]
Only 2 and 3 are greater than one.
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