This project has moved and is read-only. For the latest updates, please go here.

Shift-reduce conflict

Apr 30, 2012 at 3:58 AM


This should a very simple one, but I couldn't figure out how.

What I am trying to achieve is a custom SQL parser, I started from the SQL sample from the kit. I added support for LIMIT and OFFSET in the select statement. However, the LIMIT option and OFFSET option can appear before GROUP BY or after GROUP BY.

Currently I have the following rule, which reports "Shift-reduce conflict" error.

selectStmt.Rule = SELECT + columnItemList + FROM + fromItem + whereClauseOpt +
                              limitOpt + offsetOpt +
                              groupClauseOpt + havingClauseOpt + orderClauseOpt +
                              limitOpt + offsetOpt;

As you can see, my rule has limitOpt and offsetOpt twice, which would be the cause of compilation error.

How should I fix this error?

Thanks in advance!

Apr 30, 2012 at 4:12 AM

create an extra non-terminal ExtraClause and ExtraClauseList - as a general term for clauses that might appear after WHERE

ExtraClauseList.Rule = MakeStarList(ExtraClauseList, ExtraClause);

ExtraClause.Rule = GroupClause | HavingClause | OrderByClause | LimitClause | Offset;

selectStmt.Rule = SELECT + columnItemList + FROM  + fromItem + whereClauseOpt + ExtraClauseList;

Note that all elements in ExtraClause are NOT optional; you get optionality by using StarList

Restrictions on order of clauses, and one-only restriction - should be checked after parsing by traversing the parse tree. Alternatively you can do it immediately when SelectStmt is reduced - hook to Reduced event on non-terminal

Apr 30, 2012 at 4:36 AM
Edited Apr 30, 2012 at 4:37 AM

That was quick. It's much appreciated.

I am getting the following two errors after making the changes.

  • Shift-reduce conflict. State S86, lookaheads [LIMIT OFFSET GROUP HAVING ORDER]. Selected shift as preferred action. (S86)
  • Reduce-reduce conflict. State S86, lookaheads: EOF ). Selected reduce on first production in conflict set. (S86)

Here is my latest code.

var extraClause = new NonTerminal("extraClause");
var extraClauseList = new NonTerminal("extraClauseList");

extraClauseList.Rule = MakeStarRule(extraClauseList, extraClause);
extraClause.Rule = limitOpt | offsetOpt | groupClauseOpt | havingClauseOpt | orderClauseOpt;

//Select stmt
selectStmt.Rule = SELECT + columnItemList + FROM + fromItem + whereClauseOpt + extraClauseList;

Did I do something wrong?


Apr 30, 2012 at 4:47 AM

Read my post again - these clauses must NOT be optional, you should remove "opt" suffix and "|Empty" from their rules

Apr 30, 2012 at 5:55 AM

Sorry for picking it up slowly.

Problem solved after following your instructions.

Much appreciated.