yacc: 22 reduce/reduce conflicts

Question

%%

%token IDENTIFIER NUMBER SIZEOF
%token PTR DOT
%token TYPEDEF INT FLOAT VOID STRUCT
%token IF ELSE WHILE RETURN FOR DO SWITCH CASE BREAK DEFAULT CONTINUE
%token PRINTF SCANF
%token STRING
%token PREPROC

%left GT LT LE GE NE EQ
%left AND OR

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

%%
start:  Function
    |   Declaration
    ;

Function:   Type IDENTIFIER '(' ArgList ')' CompoundStmt
    |   Type IDENTIFIER '('')' CompoundStmt
    ;

ArgList:    ArgList ',' Arg
    |   Arg
    ;

Arg:    Type IDENTIFIER
    ;

Type:   INT
    |   FLOAT
    |   VOID
    ;

CompoundStmt:   '{' StmtList '}'
    |   '{''}'
    ;

StmtList:   StmtList Stmt
    | Stmt
    ;

Stmt:   WhileStmt
    |   Declaration
    |   ForStmt
    |   IfStmt
    |   PrintStmt
    |   ScanStmt
    |   ';'
    ;

WhileStmt:  WHILE '(' Expr ')' Stmt
    |   WHILE '(' Expr ')' CompoundStmt
    ;

ForStmt:    FOR '(' Expr ';' Expr ';' Expr ')' Stmt
    |   FOR '(' Expr ';' Expr ';' Expr ')' CompoundStmt
    ;

IfStmt: IF '(' Expr ')' Stmt
    |   IF '(' Expr ')' CompoundStmt
    ;

PrintStmt:  PRINTF '(' Expr ')' ';'
    ;

ScanStmt:   SCANF '(' Expr ')' ';'
    ;

Expr:   Expr LE Expr
    |   Expr GE Expr
    |   Expr GT Expr
    |   Expr LT Expr
    |   Expr NE Expr
    |   Expr EQ Expr
    |   Assignment
    |   ArrayUsage
    ;

ArrayUsage: IDENTIFIER '[' Assignment ']'
    ;

Declaration:    Type Assignment ';'
    |   Assignment ';'
    |   FunctionCall ';'
    |   ArrayUsage ';'
    |   Type ArrayUsage ';'
    |   StructStmt ';'
    ;

StructStmt: STRUCT IDENTIFIER '{' Type Assignment '}'
    ;

FunctionCall:   IDENTIFIER '('')'
    |   IDENTIFIER '(' Assignment ')'
    ;

Assignment: IDENTIFIER '=' Assignment
    |   IDENTIFIER '=' FunctionCall
    |   IDENTIFIER '=' ArrayUsage
    |   ArrayUsage '=' Assignment
    |   IDENTIFIER ',' Assignment
    |   NUMBER ',' Assignment
    |   IDENTIFIER '+' Assignment
    |   IDENTIFIER '-' Assignment
    |   IDENTIFIER '*' Assignment
    |   IDENTIFIER '/' Assignment
    |   NUMBER '+' Assignment
    |   NUMBER '-' Assignment
    |   NUMBER '*' Assignment
    |   NUMBER '/' Assignment
    |   '\'' Assignment '\''
    |   '(' Assignment ')'
    |   '-' Assignment
    |   '-' NUMBER
    |   '-' IDENTIFIER
    |   NUMBER
    |   IDENTIFIER
    ;

%%
include"lex.yy.c"

int main(int argc,char *argv[])
{
    FILE *file;
        file = fopen(argv[1], "r");
        if (!file)
        {
            fprintf(stderr, "Could not open %s
", argv[1]);
            exit(1);
        }
        yyin = file;

    if(!yyparse())
        printf("
Parsing done");
    else
        printf("
Parsing failed");

    fclose(yyin);

        return 0;
    }

While running :

yacc scanner.y          // scanner.y being by yacc code

I get the following error :

yacc: 22 reduce/reduce conflicts.

A reduce/reduce conflict occurs if there are two or more rules that apply to the same sequence of input. This usually indicates a serious error in the grammar.

What is the error here?

Chris Dodd · Accepted Answer

The problem comes from the ambiguity in the rules

Assignment: '-' Assignment
          |   '-' NUMBER
          |   '-' IDENTIFIER
          |   NUMBER
          |   IDENTIFIER

When you have the input - IDENTIFIER or (- NUMBER) you can either reduce it to Assignment in one step (the 2nd or 3rd rule above) or two steps (4th or 5th rule, followed by 1st rule). The easiest fix is to just delete 2nd and 3rd rules above, which will force it to always reduce two steps. You probably also want to give the '-' Assignment rule higher precedence by defining a fake UNARY token (with higher precedence than all binary operators), which the lexer never returns, but allowing you to say

Assignment: '-' Assignment %prec UNARY

to give that rule higher precedence.

yacc: 22 reduce/reduce conflicts

Answers (2)

Related Questions