◐ static  ·  no trackers  ·  built to be lightweight
Theo Charalambous

The Precedence Parser

Parser Combinators · 05 12 min read haskell · pratt

Introduction

Today we reach our final boss: the precedence parser. This is going to hopefully bring together all of the knowledge we have gathered so far and combine all of our expression parsers so that we can parse expressions with a variety of operations.

Here is a copy of our grammar and its Haskell encoding.

  SimpleExp := Num | '(' Exp ')'
  Exp       := SimpleExp | UnOpExpr | BinOpExpr | FuncApp
  UnOpExpr  := '-' SimpleExp
             | 'sin' SimpleExp 
             | 'cos' SimpleExp 
             | 'tan' SimpleExp
  BinOpExpr := Exp + Exp  -- lowest precedence
             | Exp - Exp 
             | Exp * Exp 
             | Exp / Exp
             | Exp ^ Exp  -- highest precedence
  FuncDef   := Ident '(' [Var {', ' Var}] ')' '=' Exp
  Var       := Ident
  FuncApp   := Ident '(' [Exp {, Exp}] ')'
  Ident     := String
  data Expr    = Num Float 
               | Var String
               | UnOpExpr UnOp Expr 
               | BinOpExpr BinOp Expr Expr 
               | FuncApp String [Expr]
  data UnOp    = Negate | Sin | Cos | Tan
  data BinOp   = Add    | Sub | Mul | Div | Exp
  data FuncDef = FuncDef String [String] Expr

Motivation

Consider the following expression

  1 * 2 + 3 ^ 4 / 5

It raises the question of how should we evaluate it? There are many options, for example:

  1 * (2 + (3 ^ (4 / 5)))
  (((1 * 2) + 3) ^ 4) / 5
  1 * (((2 + 3) ^ 4) / 5)

to name a few, but I propose that the correct version is:

  (1 * 2) + ((3 ^ 4) / 5)

As addition has the lowest precedence in this and exponention has the highest precedence. Another example is the expression

  - 1 + sin 0.5 + 3

which should be evaluated as

  ((- 1) + (sin 0.5)) + 3

as unary operations should have the highest precedence.

The precedence of operators vastly changes how the AST will be constructed when we parse a given string, so we need some way to encode the precedence. The idea is that we will keep a list of all of the unary and binary operations and the higher in the list an operation is, the higher its precedence. For example, all of the unary operations will be first, then exponentiation, then division and multiplication, then subtractions and addition.

Another important thing is the associativity of a binary operation, for example,

  1 + 2 + 3 - 4

should be evaluated as

  ((1 + 2) + 3) - 4

There isn’t any difference in the precedence of addition and subtraction, they are just evaluated so that they are left associative operations, hence, in our precedence list, they should be at the same level (the same is true for multiplcation and division). So this leads us to change our precedence list to be a 2D list that contains levels of operators with the same associativity and the level of a group of operators represents their precedence so that all operators in a group have the same precedence.

I think this is enough describing. Let’s actually try and write some code of our ideas. First let’s begin with the groups of operators with the same precedence. We’ve already seen how this can be the case with binary operations with the same associativity (i.e. + and -), but another case is unary operators (they should all have the same highest precedence). So we can form the following type:

  data Level a
    = BinOpL [Parser (a -> a -> a)]
    | BinOpR [Parser (a -> a -> a)]
    | Unary  [Parser (a -> a)]

Here we have encoded the concept of a level of precedence, now we can actually create our precedence list:

  precedenceTable :: [Level Expr]
  precedenceTable 
    = [ Unary  [ pNegate 
               , pSin 
               , pCos 
               , pTan    ]
      , BinOpR [ pExp    ]
      , BinOpL [ pMul               
               , pDiv    ]
      , BinOpL [ pAdd               
               , pSub    ] ]

Now that we have this, we need some parser that can actually utilise this information and parse an expression with the correct precedence and associativity.

The Level Parsers

Let’s start small with this though and begin by making a parser that can parse a specific precedence level. Specifically, we want to create a parser

  pLevel :: Parser a -> Level a -> Parser a
  pLevel atom level = ???

The first thing to note is that the way we parse will depend on what we are parsing, so let’s pattern match on level . First we will try and parse a group of left associative operators,

  pLevel atom (BinOpL ops) = ???

So ops :: [Parser (a -> a -> a)] , and the intention is that we will successively parse atoms (which in our case is a number) seperated by a op in ops and combine the expression such that the resulting AST is left associative. So for example, we should get

  > runParser (pNum (BinOpL [pAdd, pSub])) "1+2-3+4" 
  ((1 + 2) - 3) + 4

You might notice now that this seems suspiciously like chainl1 , so let’s use that to our advantage. Before though, we were only able to parse a single left associative binary operator, we need some way to combine all of the possible operators into one parser that represents choice between them.

Our choice parser should take a list of parsers and combine into one parser where we successively try each parser until we find one that works. This sounds quite ripe for using alternatives, specifically p1 <|> p2 <|> p3 will try p1 first, then if that fails, it will try p2 , then if that fails, p3 . This is the choice between p1 , p2 and p3 . This can be implemented either via recursion or as a fold, but I will leave this as an exercise.

So with this new combinator, we can write

  pLevel atom (BinOpL ops) = chainl1 atom (choice ops)

The exact same logic holds for right associative operations, and we get

          pLevel atom (BinOpR ops) = chainr1 atom (choice ops)

The final thing we need to do is

  pLevel atom (Unary ops) = ???

This one requires slightly more work, because it doesnt follow the same logic as the other two, instead of atoms seperated by operators, what we are expecting is a chain of operators proceeding an atom, for example

  sin cos sin - 5 ==> sin (cos (sin (-5)))

This time we need a parser that will parse a chain of operators that is followed by an atom, which we will call chainPre :: Parser (a -> a) -> Parser a -> Parser a , so let’s take a quick detour and implement it.

chainPre

Succintly put, chainPre op p returns zero or more instances of op followed by one instance of p . First, we will begin with a bit of a naive recursive, monadic solution.

Essentially the idea is that we can parse one op and then recursively call chainPre op p to parse the rest of the expression, and then compose the operator with the expression, i.e.

  chainPre :: Parser (a -> a) -> Parser a
  chainPre op p = rest <|> p 
    where 
      rest = do 
        f   <- op 
        exp <- chainPre op p
        return (f exp)

Hopefully it’s clear how this works, if not, I advise you to step through it with a simple example, I extract the rest function just for the sake of clarity, and the <|> p deals with the base case when there are no more unary operators.

However, this is a bit clunky and we can definitely do better using combinators, specifically many where many op will return to us a list of the unary operators it was able to parse and then we must parse an atom, so our idea is:

  chainPre = do 
    fs <- many op
    x  <- p 
    return ???

The question now is how do we combine the list of functions with the term. Let’s consider a concrete example:

  String: "sin cos sin - 5"
  fs:     [Sin, Cos, Sin, Negate]
  x:      Num 5

What we want to produce is

          Sin (Cos (Sin (Negate (Num 5))))

It is possible to write the desired function as an explicit recursion, ie

  chainPreHelper :: a -> [a -> a] -> a
  chainPreHelper atom []       = atom 
  chainPreHelper atom (f : fs) = f $ chainPreHelper atom fs

However, we can do a bit better than this. This looks suspiciously like a fold, with

  chainPreHelper atom fs = foldr ??? atom fs

The question is what is the the function we are folding with. Well if we look at our original implementation of chainPreHelper , we use ($) to combine a function with a value, so this leads us to write

  chainPreHelper atom fs = foldr ($) atom fs

So finally we get our slightly improved version of chainPre :

  chainPre = do 
    fs <- many op
    x  <- p 
    return $ foldr ($) x fs

However, as always, we want to try and avoid monadic functions in favour for applicative ones, but the reason we rewrote chainPre is that it’s much more ripe to create an applicative function with this logic. We first parse many op and then p like before, but now we need to be a bit more intelligent with how we apply the foldr ($) :: a -> [a] -> a . As we are parsing many op first, it makes sense to consider flip (foldr ($)) :: [a] -> a -> a . So now, we can just do

          chainPre op p = flip (foldr ($)) <$> many op <*> p

and that is all there is to it! So we can now do

  > runParser (chainPre pSin pNum) "sin sin sin 4"
  Just (UnOpExpr Sin (UnOpExpr Sin (UnOpExpr Sin (Num 4.0))),"")

So now we are ready to finish up pLevel

Back to pLevel

Now that we have chainPre , we can do the case of when the level is a group of unary operators, and in a similar way to the binary operator cases, we end up with

  pLevel :: Parser a -> Level a -> Parser a 
  pLevel atom (BinOpL ops) = chainl1 atom (choice ops)
  pLevel atom (BinOpR ops) = chainr1 atom (choice ops)
  pLevel atom (Unary  ops) = chainPre (choice ops) atom

and now we can test this with our example from before!

  >runParser (pLevel pNum (BinOpL [pAdd, pSub])) "1+2-3+4"
  Just (BinOpExpr Add (BinOpExpr Sub (BinOpExpr Add (Num 1.0) 
                                                    (Num 2.0)) 
                                      (Num 3.0)) 
                      (Num 4.0),"")

It works! So now all there is left to do is to incorporate this with our precedence table.

The Precedence Table

We are ready to tackle our final parser!

  precedence :: [Level s a] -> Parser a -> Parser a
  precedence levels atom = ???

Let’s now think about how to approach this. We will use a similar trick to encoding precedence with EBNF, ie:

          exp    := exp + exp | term 
          term   := term * term | factor
          factor := ( exp ) | number

So basically this ensures that multiplication has a higher precedence than addition. In a similar way we will use high precedence operations as the atom for lower precedence operations. For example, we will

  pUnary  = pLevel pNum    (Unary [pNegate, pSin, pCos, pTan])
  pExp'   = pLevel pUnary  (BinaryOpR [pExp])
  pMulDiv = pLevel pExp'   (BinaryOpL [pMul, pDiv])
  pAddSub = pLevel pMulDiv (BinaryOpL [pAdd, pSub])
  pExpr   = pAddSub

Now you might notice that this is secretly a fold over our precedence table, so we end up with the parser

  precedence :: [Level a] -> Parser a -> Parser a
  precedence levels atom = foldl pLevel atom levels

Note that we could change the foldl into a foldl' for performance benefits, but this is a bit beyond the scope of what we want to do - but I recommend reading about foldl' nonetheless.

We’re actually almost completely finished with all the parsers we need to parse the grammar one thing from the grammar that we are missing is pSimpleExpr , so let’s do that very quickly - it’s quite straightforward, we just define it by following the grammar.

  pSimpleExpr :: Parser Expr
  pSimpleExpr = ws *> (betweenBrackets pExpr <|> pNum <|> pFuncApp) <* ws

We don’t actually have pExpr defined yet, but we define it to be mutually recursive with pSimpleExpr (which is the smallest atom in expressions), so we end up with

  pExpr = precedence precedenceTable pSimpleExpr

and finally, we are done! Let’s run some complex examples: (note that I wrote some show instances for the expressions just so that they are easier to read).

  > runParser pExpr "1 + (2 + 3) + g(4) + f(2, 3)"
  Just ((((1.0 + (2.0 + 3.0)) + g(4.0)) + f(2.0, 3.0)),"")

  > runParser pExpr "5 + sin (5 * 3) + 3 * -7"
  Just (((5.0 + (sin(5.0 * 3.0))) + (3.0 * (-7.0))),"")

So it looks like it all works well!

Finishing notes

This is probably the most complex combination of parsers we’re going to come across for the time being. We’ve successfully made parsers that can parse all parts of our grammar, namely pExpr , pFuncDef . Currently we do not have the ability to combine these two parsers into one parser, and in the next tutorial I will explain why, and various ways to fix it.