shift/reduce conflicts yacc

Question

see the following code for yacc. if i remove the production factor : '!' expr, the parsing conflict disappears. what is happening here?

%{
#include <stdio.h>
#include <ctype.h>

%}


%token TRUE
%token FALSE


%%
line    : line expr '\n' { printf("%d\n", $2); }
    | line '\n'
|
;
expr    : expr "or" term { printf("expr : expr or term\n"); $$ = $1 | $3; }
| term  { printf("expr : term\n");  }
;
term    : term "and" factor { printf("term : term and factor\n"); $$ = $1 & $3; }
| factor  { printf("term : factor\n"); }
;
factor  : '(' expr ')' { printf("factor : (expr)\n"); $$ = $2; }
| '!' expr { printf("factor : !expr\n"); $$ = !$2; }
| TRUE  { printf("factor : TRUE\n"); }
| FALSE  { printf("factor : FALSE\n"); }
;
%%

#include "lex.yy.c"

int main(int argc, char** argv)
{
while (yyparse() == 0) {
    }

    return 0;
}

Answer 1

It looks to me like the conflict probably arises because when the parser sees a '!', it's running into problems with your rewrites for 'expr'. Ignoring the other productions for 'factor', specifically look at these two productions:

expr    : expr "or" term  { printf("expr : expr or term\n"); $$ = $1 | $3; }
        | term            { printf("expr : term\n"); }
        ;

factor  : '!' expr        { printf("factor : !expr\n"); $$ = !$2; }

Since expr is recursive, when the parser sees a '!', it knows that negation applies to the following expr, but if you write "! TRUE OR TRUE", does that negation apply only to the first true, or to the entire disjunction?

EDIT: In other words, it can't decide if it needs to shift the "or" or reduce "expr".

Setting the -v command line option in yacc will produce a .output file that's got all kinds of goodies in it, including diagnostic information for shift/reduce conflicts. It'll show you all the states of the DFA and where conflicts occur, and sometimes show you exactly why.

Putting negations in their own production logically "between" 'term' and 'factor' should do the trick.

Answer 2

If you change factor: ! expr to factor: ! factor the conflicts will go away.

Analyzing just the first conflict, the problem is that a term can reduce to expr or become a more complex term. Without !, this decision can be made with only one symbol of lookahead.

Note that shift/reduce conflicts are not necessarily errors. The conflict is resolved by doing the shift, which may well be what you want. Most real production grammars contain a number of shift/reduce conflicts.