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
-v
flag to yacc to produce a y.output file detailing all the states and the conflicts... – Chris Dodd