Shift reduce conflicts in happy grammar

Question

Hello good programmers,

I have built following grammar in happy (haskell):

P  :  program  C             {Prog $2}


E  :  int            {Num $1}
   |  ident           {Id $1}
   |  true           {BoolConst True}
   |  false          {BoolConst False}
   |  read           {ReadInput}
   |  '(' E ')'              {Parens $2}
   |  E '+' E                { Add $1 $3 }
   |  E '-' E                { Sub $1 $3 }
   |  E '*' E                { Mult $1 $3 }
   |  E '/' E                { Div $1 $3 }
   |  E '=' E                { Eq $1 $3 }
   |  E '>' E                { Gt $1 $3 }
   |  E '<' E                { Lt $1 $3 }


C  :   '(' C ')'             {$2}
   |  ident assign E         {Assign $1 $3}
   |  if E then C else C     {Cond $2 $4 $6}  
   |  output E               {OutputComm $2}
   |  while E do C           {While $2 $4 }
   |  begin D ';' C end      {Declare $2 $4}
   |  C ';' C                {Seq $1 $3 }


D  :  D ';' D                {DSeq $1 $3 } 
   |  '(' D ')'              {$2}
   |  var ident assign E     {Var $2 $4} 

Now, While loop includes all the commands that follow after 'do'. How to change this behavior? I've already tried %left, %right... :(

Answer 1

Invent two kinds of C, one that allows sequencing, and one that doesn't. Something like this, perhaps:

Cnoseq : '(' Cseq ')'
       | ident assign E
       | while E do Cnoseq

Cseq : Cnoseq ';' Cseq
     | Cnoseq

Answer 2

Consider this code fragment:

while True do output 1 ; output 2

This could be parsed as either

(while True do output 1) ; (output 2)

or

while True do (output 1 ; output 2)

This sort of ambiguity is the source of the conflict.

If you don't want to change the grammar as @DanielWagner suggested, you can use precedence rules to resolve the ambiguity. Exactly how depends on what the precedence should be, however it's probably something like this:

%right do
%right then else
%right ';'

Precedences are listed from low to high, so in this case the above example would be parsed in the latter manner. Just add the precedence rules below the tokens but before the %% line.