Binary Operators

We extend the lexer with two new keywords for “binary” and “unary” toplevel definitions.

lexer :: Tok.TokenParser ()
lexer = Tok.makeTokenParser style
  where
    ops = ["+","*","-","/",";","=",",","<",">","|",":"]
    names = ["def","extern","if","then","else","in","for"
            ,"binary", "unary"]
    style = emptyDef {
               Tok.commentLine = "#"
             , Tok.reservedOpNames = ops
             , Tok.reservedNames = names
             }

Parsec has no default function to parse “any symbolic” string, but it can be added simply by defining an operator new token.

operator :: Parser String
operator = do
  c <- Tok.opStart emptyDef
  cs <- many $ Tok.opLetter emptyDef
  return (c:cs)

Using this we can then parse any binary expression. By default all our operators will be left-associative and have equal precedence, except for the bulletins we provide. A more general system would allow the parser to have internal state about the known precedences of operators before parsing. Without predefined precedence values we’ll need to disambiguate expressions with parentheses.

binop = Ex.Infix (BinaryOp <$> op) Ex.AssocLeft

Using the expression parser we can extend our table of operators with the “binop” class of custom operators. Note that this will match any and all operators even at parse-time, even if there is no corresponding definition.

binops = [[binary "*" Ex.AssocLeft,
          binary "/" Ex.AssocLeft]
        ,[binary "+" Ex.AssocLeft,
          binary "-" Ex.AssocLeft]
        ,[binary "<" Ex.AssocLeft]]
expr :: Parser Expr
expr =  Ex.buildExpressionParser (binops ++ [[binop]]) factor

The extensions to the AST consist of adding new toplevel declarations for the operator definitions.

data Expr =
  ...
  | BinaryOp Name Expr Expr
  | UnaryOp Name Expr
  | BinaryDef Name [Name] Expr
  | UnaryDef Name [Name] Expr

The parser extension is straightforward and essentially a function definition with a few slight changes. Note that we capture the string value of the operator as given to us by the parser.

binarydef :: Parser Expr
binarydef = do
  reserved "def"
  reserved "binary"
  o <- op
  prec <- int
  args <- parens $ many identifier
  body <- expr
  return $ BinaryDef o args body

To generate code we’ll implement two extensions to our existing code generator. At the toplevel we’ll emit the BinaryDef declarations as simply create a normal function with the name “binary” suffixed with the operator.

codegenTop (S.BinaryDef name args body) =
  codegenTop $ S.Function ("binary" ++ name) args body

Now for our binary operator, instead of failing with the presence of a binary operator not declared in our binops list, we instead create a call to a named “binary” function with the operator name.

cgen (S.BinaryOp op a b) = do
  case Map.lookup op binops of
    Just f  -> do
      ca <- cgen a
      cb <- cgen b
      f ca cb
    Nothing -> cgen (S.Call ("binary" ++ op) [a,b])