Search code examples
parsingyaccfsyacc

Why 1*2+3 is parsed as 1*(2+3) even though operator precedence or associativity is not declared?

I use fsyacc (yacc for fsharp) to write a small parser. The grammar is something like

Expr:=
  | INT                              { Cst $1           }  
  | Expr PLUS  Expr                     { Op("+", $1, $3) }  
  | Expr TIMES Expr                     { Op("*", $1, $3) }

Then, without declaring precedence or associativity, I got "1*2+3" parsed as

Op ("*",Cst 1,Op ("+",Cst 2,Cst 3)

Why?

Solution

  • If you don't declare a precedence and associativity for your tokens in an ambiguous grammar such as you describe, by default yacc will resolve the resulting shift/reduce conflict in favor if the shift. This has the effect of making the rule right recursive, so the operators will appear to group right to left.

    If you do define precedence rules, what they do is to resolve shift/reduce conflicts in favor of the higher precedence (token or rule) or, if the same precedence, in favor of shift for %right and reduce for %left. That's basically all that the precedence settings do, so they can sometimes be used to resolve conflicts in a way that has nothing really to do with "precedence" if that is what you want to do. But for a simple infix expression grammar, they basically do exactly what you want.