CODEWITHSUNDEEP
parsingyacclex
user3386378
user3386378

Reputation: 3

Parser shift/reduce reduce/reduce conflicts

I'm given a parser written in Lex and Yacc which happens to be ambiguous and incomplete. When compiling, I get several shift/reduce and reduce/reduce conflicts. I cannot seem to find anything online that helps me understand what this really means and what needs to be done to fix it. I'm hoping someone here can help clear things up for me.

The parser:

%{
  #include <stdio.h>
  int yylex();
%}

%token ID INT_CONST REAL_CONST LPAREN RPAREN INT REAL VOID COMMA LCBRAC RCBRAC ASSIGN      SEMICOLON IF ELSE ADD RETURN SUBT MULT DIV FOR UNTIL 

%%                   /* beginning of rules section */

program : functionDeclarationS; 
functionDeclarationS : functionDeclaration | functionDeclaration functionDeclarationS;
functionDeclaration : typeSpecifier ID  LPAREN params RPAREN functionBody;
typeSpecifier : INT | VOID;
params : paramList | VOID;
paramList : param COMMA paramList | param;
param : typeSpecifier ID;
functionBody : LCBRAC localDeclarations statementS RCBRAC;
localDeclarations : varDeclarations SEMICOLON localDeclarations | ;
varDeclarations : INT varList;
varList : ID | ID COMMA varList;
statementS : statement statementS | ;
statement : assignment SEMICOLON | expression  SEMICOLON | ifStmt | return SEMICOLON;
assignment : ID ASSIGN expression;
expression : expression ADD expression | LPAREN expression RPAREN | expression;
expression : integer | real | ID | functionCall;
integer : sign INT_CONST;
real : sign REAL_CONST;
sign : ADD | SUBT| ;
functionCall : ID LPAREN argumentsList RPAREN;
argumentsList : expression | expression COMMA argumentsList | ;
ifStmt : IF LPAREN expression RPAREN block;
block : LCBRAC statementS RCBRAC;
return : RETURN expression ;

%%
int main()
{
  return(yyparse());
}

yyerror(s)
char *s;
{
  fprintf(stderr, "%s\n",s);
}

int yywrap()
{
  return(1);
}

The conflicts and warning messages:

conflicts: 11 shift/reduce, 7 reduce/reduce parser.y:30.17-26: warning: rule useless in parser due to conflicts: argumentsList: expression **parser.y:33.10-26:** warning: rule useless in parser due to conflicts: return: RETURN expression

Upvotes: 0

Views: 453

Answers (1)

Chris Dodd
Chris Dodd

Reputation: 126130

The rule expression: expression is meaningingless and makes the grammar ambiguous, and also results in a parser with an infinite loop, since an argumentList will try to expand it infinitely (this is why you get the message about argumentsList: expression being useless -- it is superceded by expression: expression so can never be reduced.)

Upvotes: 1

Related Questions