You can keep reading here or jump to my blog to get the full experience, including the wonderful pink, blue and white palette.
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.
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.
sub) on integers. In particular, we will use as an input the following code:
add 1 sub 6 add 3 2.
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
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
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)
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
Get the latest content via email from me personally. Reply with your thoughts. Let's learn from each other. Subscribe to my PinkLetter!