You can keep reading here or jump to my blog to get the full experience, including the wonderful pink, blue and white palette.
Intro
This week I've decided to write some code in PureScript that resembles a compiler. As for the last few posts, I've limited the scope to the smallest possible unit.
That means, I haven't had much time to learn about compilers myself. Hopefully, this will prove useful foundation when I'll decide to dive deeper.
Let's roll
As long as I understand, a compiler consists of a series of steps that take some input code and transforms it into the target language.
As an input we will use a language that supports two operations (i.e. add and sub) on integers. In particular, we will use as an input the following code: add 1 sub 6 add 3 2.
Parsing
The first thing we want to do is to parse the code into an Abstract Syntax Tree (AST). In other words, a structure that enables us to work easily with the code. The AST for the example code provided above would look like
add
/ \
1 sub
/ \
6 add
/ \
3 2
The code to do that is the following
data Ast
= Node Op Ast Ast
| Value Int
instance showAst :: Show Ast where
show (Node op ast1 ast2) = "(" <> show op <> " " <> show ast1 <> " " <> show ast2 <> ")"
show (Value i) = show i
data Op
= Add
| Sub
instance showOp :: Show Op where
show Add = "Add"
show Sub = "Sub"
astParser :: Parser Ast
astParser = do
skipSpaces
op <- opParser
skipSpaces
ast1 <- valueParser <|> astParser
skipSpaces
ast2 <- valueParser <|> astParser
pure $ Node op ast1 ast2
opParser :: Parser Op
opParser =
addParser <|> subParser
addParser :: Parser Op
addParser = do
_ <- string "add"
pure Add
subParser :: Parser Op
subParser = do
_ <- string "sub"
pure Sub
intParser :: Parser Int
intParser = do
ds <- many1 anyDigit
case fromString $ fromChars ds of
Just i -> pure i
Nothing -> fail "I was expecting an int!"
valueParser :: Parser Ast
valueParser = do
i <- intParser
pure $ Value i
Generation / Evaluation
With the AST at our disposal we can either compile to some other language or evaluate the code:
generate :: Ast -> String
generate (Value i) = show i
generate (Node Add ast1 ast2) =
"(" <> generate ast1 <> " + " <> generate ast2 <> ")"
generate (Node Sub ast1 ast2) =
"(" <> generate ast1 <> " - " <> generate ast2 <> ")"
evaluate :: Ast -> Int
evaluate (Value i) = i
evaluate (Node Add ast1 ast2) =
evaluate ast1 + evaluate ast2
evaluate (Node Sub ast1 ast2) =
evaluate ast1 - evaluate ast2
Test Drive
input :: String
input =
"add 1 sub 6 add 3 2"
main :: Effect Unit
main = do
logShow $ runParser astParser input
-- (Right (Add 1 (Sub 6 (Add 3 2))))
logShow $ map generate $ runParser astParser input
-- (Right "(1 + (6 - (3 + 2)))")
logShow $ map evaluate $ runParser astParser input
-- (Right 2)
Outro
If you want to read more, this is what inspired me to take a few steps into the compilers world:
- The Super Tiny Compiler
- Tiny Interepter and Compiler
- How to be a compiler — make a compiler with JavaScript
Get the latest content via email from me personally. Reply with your thoughts. Let's learn from each other. Subscribe to my PinkLetter!
Top comments (0)