The Parser

The AST for a program captures its behavior in such a way that it is easy for later stages of the compiler (e.g. code generation) to interpret. We basically want one object for each construct in the language, and the AST should closely model the language. In Kaleidoscope, we have expressions, and a function object. When parsing with Parsec we will unpack tokens straight into our AST which we define as the Expr algebraic data type:

  1. module Syntax where
  3. type Name = String
  5. data Expr
  6.   = Float Double
  7.   | BinOp Op Expr Expr
  8.   | Var String
  9.   | Call Name [Expr]
  10.   | Function Name [Expr] Expr
  11.   | Extern Name [Expr]
  12.   deriving (Eq, Ord, Show)
  14. data Op
  15.   = Plus
  16.   | Minus
  17.   | Times
  18.   | Divide
  19.   deriving (Eq, Ord, Show)

This is all (intentionally) rather straight-forward: variables capture the variable name, binary operators capture their operation (e.g. Plus, Minus, …), and calls capture a function name as well as a list of any argument expressions.

We create Parsec parser which will scan an input source and unpack it into our Expr type. The code composes within the Parser to generate the resulting parser which is then executed using the parse function.

  1. module Parser where
  3. import Text.Parsec
  4. import Text.Parsec.String (Parser)
  6. import qualified Text.Parsec.Expr as Ex
  7. import qualified Text.Parsec.Token as Tok
  9. import Lexer
  10. import Syntax
  12. binary s f assoc = Ex.Infix (reservedOp s >> return (BinOp f)) assoc
  14. table = [[binary "*" Times Ex.AssocLeft,
  15.           binary "/" Divide Ex.AssocLeft]
  16.         ,[binary "+" Plus Ex.AssocLeft,
  17.           binary "-" Minus Ex.AssocLeft]]
  19. int :: Parser Expr
  20. int = do
  21.   n <- integer
  22.   return $ Float (fromInteger n)
  24. floating :: Parser Expr
  25. floating = do
  26.   n <- float
  27.   return $ Float n
  29. expr :: Parser Expr
  30. expr = Ex.buildExpressionParser table factor
  32. variable :: Parser Expr
  33. variable = do
  34.   var <- identifier
  35.   return $ Var var
  37. function :: Parser Expr
  38. function = do
  39.   reserved "def"
  40.   name <- identifier
  41.   args <- parens $ many variable
  42.   body <- expr
  43.   return $ Function name args body
  45. extern :: Parser Expr
  46. extern = do
  47.   reserved "extern"
  48.   name <- identifier
  49.   args <- parens $ many variable
  50.   return $ Extern name args
  52. call :: Parser Expr
  53. call = do
  54.   name <- identifier
  55.   args <- parens $ commaSep expr
  56.   return $ Call name args
  58. factor :: Parser Expr
  59. factor = try floating
  60.       <|> try int
  61.       <|> try extern
  62.       <|> try function
  63.       <|> try call
  64.       <|> variable
  65.       <|> parens expr
  67. defn :: Parser Expr
  68. defn = try extern
  69.     <|> try function
  70.     <|> expr
  72. contents :: Parser a -> Parser a
  73. contents p = do
  74.   Tok.whiteSpace lexer
  75.   r <- p
  76.   eof
  77.   return r
  79. toplevel :: Parser [Expr]
  80. toplevel = many $ do
  81.     def <- defn
  82.     reservedOp ";"
  83.     return def
  85. parseExpr :: String -> Either ParseError Expr
  86. parseExpr s = parse (contents expr) "<stdin>" s
  88. parseToplevel :: String -> Either ParseError [Expr]
  89. parseToplevel s = parse (contents toplevel) "<stdin>" s