Shift Reduce Conflict in YACC

Question

I m trying the following yacc code and m receiving shift/reduce errors. I m pretty new to this

The Purpose of the code is to prepare the syntax for if - else with logical operators also incorporated

           %{
               #include<stdio.h>
               #include"lex.yy.c"
               int syntax_status=0;
           %}
           %token IF ELS id EE LE GE closep openp num openb closeb SP logicop 
           %start S
           %%
           S : S SP IF SP openp SP EXP SP closep SP openb SP closeb SP ELS SP openb SP closeb SP {syntax_status=1;}
             | S SP IF SP openp SP EXP SP closep SP openb SP closeb SP {syntax_status = 1;}
             | 
             ;
         EXP : EXP CMP logicop CMP
             | EXP CMP
             |
             ;
         CMP : CMP id EE id 
             | CMP id LE id
             | CMP id GE id
             | CMP id EE num
             | CMP id GE num
             | CMP id LE num
             | CMP num EE id
             | CMP num GE id
             | CMP num LE id
             | 
             ;
         %%
         int main()
         {
              printf("\n\n\n Enter the Syntax :  ");
              yyparse();
              if(syntax_status==1)
              {
                     printf("\n\n\n The Syntax is Correct ");
              }
              else
              {
                     printf("\n\n\n The Syntax is Imcorrect");
              }
              return 0;
          }
          yyerror(char *s)
          {
              syntax_status=0;
          }

The Lex Program for this corresponding yacc code is as follows :

           %{
              #include<stdio.h>
              #include"y.tab.h"
           %}
           IF (if)
           ELS (else)
           iden [a-zA-Z][a-zA-Z0-9]*
           num [0-9]+
           space [ ]* 
           %%
           {IF} { return IF; }
           {ELS} {return ELSE;}
           {iden} {return id;}
           (==) {return EE;}
           (<=) { return LE;}
           (>=) { return GE;}
           ")" { return closep;}
           "(" { return openp;}
          {num} { return num;}
          {space} { return SP; }
          "{" { return openb;}
          "}" { return closeb;}
          "||"|"&&"|"!=" {return logicop;}

%%

Answer 1

The CMP and EXP rules both look very problematic. Take this rightmost derivation, for example:

 EXP ==> (by EXP -> CMP)
 EXP CMP ==>  (by CMP -> CMP id EE id)
 EXP CMP id EE id ==> (by CMP -> CMP id EE id)
 EXP CMP id EE id id EE id ==> (by CMP -> epsilon)
 EXP id EE id id EE id ==> (by EXP -> epsilon )
 id EE id id EE id ==>
 id == id id == id

I'm pretty sure this isn't what you want. It also introduces ambiguity into the grammar: the same string of terminals can be derived by this different rightmost derivation:

 EXP ==> (by EXP -> CMP)
 EXP CMP ==> (by CMP -> CMP id EE id)
 EXP CMP id EE id ==> (by CMP -> epsilon)
 EXP id EE id ==> (by EXP -> CMP)
 EXP CMP id EE id ==> (by CMP -> CMP id EE id)
 EXP CMP id EE id id EE id ==> (by CMP -> epsilon)
 EXP id EE id  id EE id ==> (by EXP-> epsilon)
 id EE id  id EE id ==>
 id == id id == id

You see, yacc will have no way of knowing if id == id id == id is really exp exp or exp. Also, the exp->epsilon rule allows for expressions like if(){}, which isn't very nice.

Now, consider the following grammar:

 exp -> exp logicop cmp | cmp
 cmp -> rvalue < rvalue | rvalue > rvalue ...
 rvalue -> id | num

But it could also be done like this:

exp -> exp op exp | rvalue
op -> "||" | "&&" | "<" | ">" ...

The latter is the traditional way of doing it, but you'd need semantic checks to ensure that the operands are of the right types, while the previous grammar ensures that on a syntactic level. On the long run (once you introduce boolean variables), the second approach is much preferable, since type safety is a matter of semantics, not syntactics.

On another note: spaces don't seem relevant in your language, but lex is handing them up to yacc. You could make lex discard the spaces on the lexical level by saying

{space} //nothing after a pattern discards the matched characters

This would save you the headache of writing out all those SPs in yacc.

Answer 2

you need to specify the precedence and associativity of your operators: see here for example. I cite from sect. 6

As an example of the behavior of these declarations, the description

    %right  '='
    %left  '+'  '-'
    %left  '*'  '/'

    %%

    expr    :       expr  '='  expr
            |       expr  '+'  expr
            |       expr  '-'  expr
            |       expr  '*'  expr
            |       expr  '/'  expr
            |       NAME
            ;

might be used to structure the input

    a  =  b  =  c*d  -  e  -  f*g

as follows:

    a = ( b = ( ((c*d)-e) - (f*g) ) )

Your CMP operators must be defined in similar way, and your logicop should be divided. To get the usual reading in boolean expressions, usually NOT behaves like unary minus, AND like *, OR like +.

HTH