Parsing function application with Happy

Question

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)

Answer 1

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 }

Answer 2

The accepted answer is not satisfactory.

The correct way of solving this problem is:

%nonassoc VAR LPAREN -- etc...
%nonassoc APP

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

That is:

• Adding a ghost precedence token called APP, and no need to make it left or right since it won't be relevant, so you can keep it nonassoc to not get the wrong intuition that it matters

• Marking your Expr rule with %prec APP like you did

• and most importantly and often forgotten, you need to give all tokens that may appear as the first token of an Expr production a precedence lower than that of APP, usually achieved by listing them somewhere above, either with left, right, or nonassoc for the ones that don't associate

The reason why your trial failed is probably that you missed the last step.

The reason why the last step is needed is that the algorithm, in deciding whether to shift the next token or to reduce the APP rule, will compare the precedence of the APP rule with the precedence of the incoming token. And by default, tokens that you don't mention have high precedence. So when faced with:

Expr Expr . LPAREN VAR RPAREN

for instance, it would compare the precedence of the APP rule (to reduce), with the precedence of LPAREN (to shift), and unless you set it up correctly, it will shift, and do the wrong thing.

---

Staging your grammar is just ugly and unpleasant.