parsinghaskellhappy

Parsing function application with Happy


How would I parse something like

f x y

Into

APPLY (APPLY f x) y

using Happy? Right now I have a rule that says

%left APP
Expr : Expr Expr %prec APP { APPLY $1 $2 }

But that parses the above as

APPLY f (APPLY x y)

Solution

  • You can encode left/right associativity using grammar rules.

    For example, have a look at this basic lambda calculus parser:

    https://github.com/ghulette/haskell-parser-examples/blob/master/src/HappyParser.y

    The operative productions are:

    Expr : let VAR '=' Expr in Expr    { App (Abs $2 $6) $4 }
         | '\\' VAR '->' Expr          { Abs $2 $4 }
         | Form                        { $1 }
    
    Form : Form '+' Form               { Binop Add $1 $3 }
         | Juxt                        { $1 }
    
    Juxt : Juxt Atom                   { App $1 $2 }
         | Atom                        { $1 }
    
    Atom : '(' Expr ')'                { $2 }
         | NUM                         { Num $1 }
         | VAR                         { Var $1 }