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

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.

  1. What is a lexer?

    Answer

    A function from characters to tokens

    The lexer groups characters into the words of the language.

  2. 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.

  3. What does span isDigit do?

    Answer

    Takes the longest run of digits and leaves the rest

    span returns the prefix that satisfies the test and the remainder.

  4. 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.

  5. 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.

  6. What does this program print? module Main (main) where main :: IO () main = print (length "+-*/")

    Answer

    4

    The string has four characters.

  7. 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.

  8. 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.

  9. 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.

  10. 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