1. 20
  1.  

  2. 6

    Meh, for the precedence thing to work nicely you need extra-grammar things like %left anyway; usually when operator precedence shows up in a grammar not augmented by this feature it looks something like this:

    Exp   : let var '=' Exp in Exp  { \p -> $6 (($2,$4 p):p) }
          | Exp1                    { $1 }
    
    Exp1  : Exp1 '+' Term           { \p -> $1 p + $3 p }
          | Exp1 '-' Term           { \p -> $1 p - $3 p }
          | Term                    { $1 }
    
    Term  : Term '*' Factor         { \p -> $1 p * $3 p }
          | Term '/' Factor         { \p -> $1 p `div` $3 p }
          | Factor                  { $1 }
    
    Factor			  
          : int                     { \p -> $1 }
          | var                     { \p -> case lookup $1 p of
    	                                    Nothing -> error "no var"
    					    Just i  -> i }
          | '(' Exp ')'             { $2 }
    

    (taken from the happy manual).

    This ends up dealing with precedence in a roundabout way that’s much lower level than how we “want” to think about it. Just adding a feature for this is fine, but the fact that this can just be implemented as a library function with parser combinators is a nice thing to recommend them:

    expr = makeExprParser term table <?> "expression"
    
    term = parens expr <|> integer <?> "term"
    
    table = [ [ prefix  "-"  negate
              , prefix  "+"  id ]
            , [ postfix "++" (+1) ]
            , [ binary  "*"  (*)
              , binary  "/"  div  ]
            , [ binary  "+"  (+)
              , binary  "-"  (-)  ] ]
    
    binary  name f = InfixL  (f <$ symbol name)
    prefix  name f = Prefix  (f <$ symbol name)
    postfix name f = Postfix (f <$ symbol name)
    

    (from the megaparsec docs, linked from the blog post). I’d dare say that’s easier to follow than even the version using %left.

    Also, In my experience operator precedence is like 95% of the use cases for left recursion; once that’s taken care of it rarely comes up.

    There are some theoretical advantages to parser generators, but in my experience not very many practical ones vs. parser combinators.

    1. 2

      You make a good point that Megaparsec has abstractions for handling operator precedence. You also make a good point that my final parser didn’t address precedence. Thanks for calling me out.

      Here is a correct version of my production rules:

      expr
        : expr '+' expr1 { Add $1 $3 }
        | expr1 { $1 }
      
      expr1
        : expr1 '*' expr2 { Multiply $1  $3 }
        | expr2 { $1 }
      
      expr2
        : int { Num $1 }
        | '-' expr2 { Negate $2 }
        | '(' expr ')' { $2 }
      

      I’ll add section to the article including this.

      1. 1

        This whole “grammar stratification” trick (splitting expr into expr1 and expr2 and so on; is there a better word for it?) pops up a lot in writing grammars, so much so that I would imagine Happy has some kind of built-in functionality for setting the precedence of its production rules. I’m pretty sure Bison has this, for example.

    2. 2

      I must say I find the pun in the title very pleasing.

      1. 2

        Maybe even better would be “LALR parser combinators”! Have a Parser a type that’s backed by an explicit set of grammar rules. Then you can write helper functions for common things like sepBy or sepEndBy. But then use LALR instead of recursive descent, to get nice things like left recursion and ambiguity warnings.