YACC reduce/reduce conflict

[leverin4]

I understand, vaguely, what a reduce/reduce conflict is, but I don't understand why I'm getting one in my Yacc Parser. Can anyone help me out?

Prog			:	START StmtSeq END			{ };
StmtSeq 		:	Stmt StmtSeq			        { };
StmtSeq			:						{ };
Stmt			:	Id  ASSIGNOP Expr SEMICOLON		{ *$1 = $3;};
Expr			: 	LEFTPAR Expr RIGHTPAR			{ };
Expr			:	Expr PLUSOP Term			{ $$ = $1 + $3;};
Expr			:	Expr SUBOP Term				{ $$ = $1 - $3;};
Expr			:	Term					{ $$ = $1;};
Term			: 	LEFTPAR Expr RIGHTPAR			{ };
Term			:	Term MULTOP Factor			{ $$ = $1 * $3;};
Term			:	Term DIVOP Factor			{ $$ = $1 / $3;};
Term			:	Term MODOP Factor			{ $$ = $1 % $3;};
Term			:	Factor					{ $$ = $1;};
Factor			:	LEFTPAR Expr RIGHTPAR			{ };
Factor			: 	End					{ $$ = $1;};
Factor 			:	End EXPOP Factor		        { $$ = (int)pow($1, $3);};			
End			:	LEFTPAR Expr RIGHTPAR	                { };
End			:	INTLIT					{ $$ = atoi(yytext);};
End			:	SUBOP End				{ $$ = -$2;};
End			:	Id					{ $$ = *$1;};
Id			: 	IDENT					{ $$ = &vars[yytext[0]-'A'];};

[nezachem]

I understand, vaguely, what a reduce/reduce conflict is, but I don't understand why I'm getting one in my Yacc Parser. Can anyone help me out?

Expr			: 	LEFTPAR Expr RIGHTPAR			{ };
Term			: 	LEFTPAR Expr RIGHTPAR			{ };
Factor		:	LEFTPAR Expr RIGHTPAR			{ };
End			:	LEFTPAR Expr RIGHTPAR	                { };

How LEFTPAR Expr RIGHTPAR should be reduced? You give 4 ways to do it, and yacc cannot decide.

[leverin4]

How LEFTPAR Expr RIGHTPAR should be reduced? You give 4 ways to do it, and yacc cannot decide.

I thought that the right side was what it was getting reduced to. A Term can be reduced to LEFTPAR Expr RIGHTPAR .

It'll eventually be an infix mathematical expression evaluator. How else can I handle parentheses?

[nezachem]

Usually it is handled with primary expression, for example,

Expression
    : AdditiveExpression
    | PrimaryExpression
;
AdditiveExpression
    : Term
    | Term '+' Expression
;
PrimaryExpression
    : IDENTIFIER
    | NUMERIC_LITERAL
    | '(' Expression ')'
;

[leverin4]

Usually it is handled with primary expression, for example,

Expression
    : AdditiveExpression
    | PrimaryExpression
;
AdditiveExpression
    : Term
    | Term '+' Expression
;
PrimaryExpression
    : IDENTIFIER
    | NUMERIC_LITERAL
    | '(' Expression ')'
;

I still don't fully understand. At some point, when reading in a paren, I'll need to start over, right? Which means I'll need to recursively go back to the top level and create a new "sub-tree".

[nezachem]

I do not quite understand what do you mean by "back to the top level". You'd rather go recursively down, building the same tree. And yes, an expression grammar is inherently recursive.

[leverin4]

I do not quite understand what do you mean by "back to the top level". You'd rather go recursively down, building the same tree. And yes, an expression grammar is inherently recursive.

Yes, I didn't actually mean start over, I meant continue down the tree, but I'd need to have the sub-tree begin with a top level non-terminal. I guess I'm confused about how to write the grammer so at these different places I can have this "start over" with the highest level non-terminal.

EDIT: Wait, studying your AdditiveExpression example above again, I think I understand. I don't have a chance to test it until this afternoon, but I'll give it a shot then and let you know how it goes. Thanks a lot.

[leverin4]

Yes, I didn't actually mean start over, I meant continue down the tree, but I'd need to have the sub-tree begin with a top level non-terminal. I guess I'm confused about how to write the grammer so at these different places I can have this "start over" with the highest level non-terminal.

EDIT: Wait, studying your AdditiveExpression example above again, I think I understand. I don't have a chance to test it until this afternoon, but I'll give it a shot then and let you know how it goes. Thanks a lot.

I've changed it to what I think should work, but now I'm getting a shift-reduce conflict. I don't understand why what I had originally doesn't work. Reading my original code, it appears, to me, that if a '(' is seen at any time, then the parser needs to have the sub-tree begin with the top-level non-terminal.

Why don't either of these work? And how can I fix them?

Program			:	START StmtSeq END			{ };
StmtSeq 		:	Stmt StmtSeq				{ };
StmtSeq			:						{ };
Stmt			:	Id  ASSIGNOP Expression SEMICOLON	{ *$1 = $3; };
PrimaryExpression	:	LEFTPAR Expression RIGHTPAR		{ $$ = $2; };
Expression		: 	PrimaryExpression			{ $$ = $1; };
Expression		:	Expression PLUSOP Expression		{ $$ = $1 + $3; };
Expression		:	Expression SUBOP Expression		{ $$ = $1 - $3; };
Expression		:	Term					{ $$ = $1; };
Term			:	Term MULTOP Expression			{ $$ = $1 * $3; };
Term			:	Term DIVOP Expression			{ $$ = $1 / $3; };
Term			:	Term MODOP Expression			{ $$ = $1 % $3; };
Term			:	Factor					{ $$ = $1; };
Factor			:	End EXPOP Expression			{ $$ = (int)pow($1, $3); };
Factor			: 	End					{ $$ = $1; };		
End			:	INTLIT					{ $$ = atoi(yytext); };
End			:	SUBOP End				{ $$ = -$2; };
End			:	Id					{ $$ = *$1; };
Id			: 	IDENT					{ $$ = &vars[yytext[0]-'A']; };

[leverin4]

I got it working.

[nezachem]

First of all, congratulations. Yacc can recover from shift-reduce, whereas reduce-reduce is lethal.

Now, let's look why it happens. One of the sources of the conflict is

Expression		:	Expression PLUSOP Expression

Consider an expression a + b + c. There are 2 ways to parse it:
1. a + Expression
2. Expression + c
The first path would be shift (accept a as Term, and shift to the rest. The second path is reduce (accept a+b, and reduce it to Expression). Again, you didn't tell it which is correct.

There are 2 ways to overcome such shift-reduces. First, you can use %left and %right directives. Second, introduce more non-terminals, like I did with AdditiveExpression.

Reading my original code, it appears, to me, that if a '(' is seen at any time, then the parser needs to have the sub-tree begin with the top-level non-terminal.

It may even do so. The question, unanswered, is what to do when a ')' is encountered.

PS: You are going to have misterious problems with lines 16 and 19. Better start using %union right away.