Reduce-reduce conflict. State S67, lookaheads: id_simple. Selected reduce on first production in conflict set.

Dec 10, 2014 at 10:56 AM
Hi Roman,

I am newbie to Irony. I have created my personal sql parser by commenting what is not required. See code below. While parsing the text like (SeriesId in (1,2,3) and State = 'TX') OR (State = 'CO' and SeriesId in (2,3,4))

i get the error "Reduce-reduce conflict. State S67, lookaheads: id_simple. Selected reduce on first production in conflict set." . Please advise what change i need to make so while parsing i don't get error.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Irony.Parsing;

namespace Irony.Samples.SQL {
// Loosely based on SQL89 grammar from Gold parser. Supports some extra TSQL constructs.

public class WhereGrammar : Grammar {
  public WhereGrammar()
      : base(false)
  { //SQL is case insensitive
  //Terminals
  var number = new NumberLiteral("number");
  var string_literal = new StringLiteral("string", "'", StringOptions.AllowsDoubledQuote);
  var Id_simple = TerminalFactory.CreateSqlExtIdentifier(this, "id_simple"); //covers normal identifiers (abc) and quoted id's ([abc d], "abc d")
  var comma = ToTerm(",");
  var dot = ToTerm(".");
  var CREATE = ToTerm("CREATE"); 
  var NULL = ToTerm("NULL");
  var NOT = ToTerm("NOT");
  var UNIQUE = ToTerm("UNIQUE"); 
  var WITH = ToTerm("WITH");
  var TABLE = ToTerm("TABLE"); 
  var ALTER = ToTerm("ALTER"); 
  var ADD = ToTerm("ADD"); 
  var COLUMN = ToTerm("COLUMN"); 
  var DROP = ToTerm("DROP"); 
  var CONSTRAINT = ToTerm("CONSTRAINT");
  var INDEX = ToTerm("INDEX"); 
  var ON = ToTerm("ON");
  var KEY = ToTerm("KEY");
  var PRIMARY = ToTerm("PRIMARY"); 
  var INSERT = ToTerm("INSERT");
  var INTO = ToTerm("INTO");
  var UPDATE = ToTerm("UPDATE");
  var SET = ToTerm("SET"); 
  var VALUES = ToTerm("VALUES");
  var DELETE = ToTerm("DELETE");
  var SELECT = ToTerm("SELECT"); 
  var FROM = ToTerm("FROM");
  var AS = ToTerm("AS");
  var COUNT = ToTerm("COUNT");
  var JOIN = ToTerm("JOIN");
  var BY = ToTerm("BY");

  //Non-terminals
  var Id = new NonTerminal("Id");
  var stmt = new NonTerminal("stmt");
  var createTableStmt = new NonTerminal("createTableStmt");
  var createIndexStmt = new NonTerminal("createIndexStmt");
  var alterStmt = new NonTerminal("alterStmt");
  var dropTableStmt = new NonTerminal("dropTableStmt");
  var dropIndexStmt = new NonTerminal("dropIndexStmt");
  var selectStmt = new NonTerminal("selectStmt");
  var insertStmt = new NonTerminal("insertStmt");
  var updateStmt = new NonTerminal("updateStmt");
  var deleteStmt = new NonTerminal("deleteStmt");
  var fieldDef = new NonTerminal("fieldDef");
  var fieldDefList = new NonTerminal("fieldDefList");
  var nullSpecOpt = new NonTerminal("nullSpecOpt");
  var typeName = new NonTerminal("typeName"); 
  var typeSpec = new NonTerminal("typeSpec");
  var typeParamsOpt = new NonTerminal("typeParams");
  var constraintDef = new NonTerminal("constraintDef");
  var constraintListOpt = new NonTerminal("constraintListOpt");
  var constraintTypeOpt = new NonTerminal("constraintTypeOpt");
  var idlist = new NonTerminal("idlist"); 
  var idlistPar = new NonTerminal("idlistPar"); 
  var uniqueOpt = new NonTerminal("uniqueOpt");
  var orderList = new NonTerminal("orderList");
  var orderMember = new NonTerminal("orderMember"); 
  var orderDirOpt = new NonTerminal("orderDirOpt");
  var withClauseOpt = new NonTerminal("withClauseOpt");
  var alterCmd = new NonTerminal("alterCmd");
  var insertData = new NonTerminal("insertData"); 
  var intoOpt = new NonTerminal("intoOpt");
  var assignList = new NonTerminal("assignList");
  var whereClauseOpt = new NonTerminal("whereClauseOpt");
  var assignment = new NonTerminal("assignment");
  var expression = new NonTerminal("expression");
  var exprList = new NonTerminal("exprList");
  var selRestrOpt = new NonTerminal("selRestrOpt");
  var selList = new NonTerminal("selList");
  var intoClauseOpt = new NonTerminal("intoClauseOpt");
  var fromClauseOpt = new NonTerminal("fromClauseOpt");
  var columnItemList = new NonTerminal("columnItemList");
  var columnItem = new NonTerminal("columnItem");
  var columnSource = new NonTerminal("columnSource");
  var asOpt = new NonTerminal("asOpt");
  var aliasOpt = new NonTerminal("aliasOpt");
  var aggregate = new NonTerminal("aggregate");
  var aggregateArg = new NonTerminal("aggregateArg");
  var aggregateName = new NonTerminal("aggregateName");
  var tuple = new NonTerminal("tuple");
  var joinChainOpt = new NonTerminal("joinChainOpt");
  var joinKindOpt = new NonTerminal("joinKindOpt");
  var term = new NonTerminal("term");
  var unExpr = new NonTerminal("unExpr");
  var unOp = new NonTerminal("unOp");
  var binExpr = new NonTerminal("binExpr");
  var binOp = new NonTerminal("binOp");
  var betweenExpr = new NonTerminal("betweenExpr");
  var inExpr = new NonTerminal("inExpr");
  var parSelectStmt = new NonTerminal("parSelectStmt");
  var notOpt = new NonTerminal("notOpt");
  var funCall = new NonTerminal("funCall");
  var stmtLine = new NonTerminal("stmtLine");
  var semiOpt = new NonTerminal("semiOpt");
  var stmtList = new NonTerminal("stmtList");
  var funArgs = new NonTerminal("funArgs");
  var inStmt = new NonTerminal("inStmt");

  //BNF Rules
  this.Root = expression;
  stmtLine.Rule = stmt + semiOpt;
  semiOpt.Rule = Empty | ";";
  stmtList.Rule = MakePlusRule(stmtList, stmtLine);

  //ID
  Id.Rule = MakePlusRule(Id, dot, Id_simple);

  //stmt.Rule = createTableStmt | createIndexStmt | alterStmt 
  //          | dropTableStmt | dropIndexStmt 
  //          | selectStmt | insertStmt | updateStmt | deleteStmt
  //          | "GO" ;

  stmt.Rule = whereClauseOpt;

  //Create table
  createTableStmt.Rule = CREATE + TABLE + Id + "(" + fieldDefList + ")" + constraintListOpt;
  fieldDefList.Rule = MakePlusRule(fieldDefList, comma, fieldDef);
  fieldDef.Rule = Id + typeName + typeParamsOpt + nullSpecOpt;
  nullSpecOpt.Rule = NULL | NOT + NULL | Empty;
  typeName.Rule = ToTerm("BIT") | "DATE" | "TIME" | "TIMESTAMP" | "DECIMAL" | "REAL" | "FLOAT" | "SMALLINT" | "INTEGER"
                               | "INTERVAL" | "CHARACTER"
                               // MS SQL types:  
                               | "DATETIME" | "INT" | "DOUBLE" | "CHAR" | "NCHAR" | "VARCHAR" | "NVARCHAR"
                               | "IMAGE" | "TEXT" | "NTEXT";
  typeParamsOpt.Rule = "(" + number + ")" | "(" + number + comma + number + ")" | Empty;
  constraintDef.Rule = CONSTRAINT + Id + constraintTypeOpt;
  constraintListOpt.Rule = MakeStarRule(constraintListOpt, constraintDef );
  constraintTypeOpt.Rule = PRIMARY + KEY + idlistPar | UNIQUE + idlistPar | NOT + NULL + idlistPar
                         | "Foreign" + KEY + idlistPar + "References" + Id + idlistPar;
  idlistPar.Rule = "(" + idlist + ")";
  idlist.Rule = MakePlusRule(idlist, comma, Id); 

  //Create Index
  createIndexStmt.Rule = CREATE + uniqueOpt + INDEX + Id + ON + Id + orderList + withClauseOpt;
  uniqueOpt.Rule = Empty | UNIQUE;
  orderList.Rule = MakePlusRule(orderList, comma, orderMember);
  orderMember.Rule = Id + orderDirOpt;
  orderDirOpt.Rule = Empty | "ASC" | "DESC";
  withClauseOpt.Rule = Empty | WITH + PRIMARY | WITH + "Disallow" + NULL | WITH + "Ignore" + NULL;

  //Alter 
  alterStmt.Rule = ALTER + TABLE + Id + alterCmd;
  alterCmd.Rule = ADD + COLUMN  + fieldDefList + constraintListOpt 
                | ADD + constraintDef
                | DROP + COLUMN + Id
                | DROP + CONSTRAINT + Id;

  //Drop stmts
  dropTableStmt.Rule = DROP + TABLE + Id;
  dropIndexStmt.Rule = DROP + INDEX + Id + ON + Id; 

  //Insert stmt
  insertStmt.Rule = INSERT + intoOpt + Id + idlistPar + insertData;
  insertData.Rule = selectStmt | VALUES + "(" + exprList + ")"; 
  intoOpt.Rule = Empty | INTO; //Into is optional in MSSQL

  //Update stmt
  updateStmt.Rule = UPDATE + Id + SET + assignList + whereClauseOpt;
  assignList.Rule = MakePlusRule(assignList, comma, assignment);
  assignment.Rule = Id + "=" + expression;

  //Delete stmt
  deleteStmt.Rule = DELETE + FROM + Id + whereClauseOpt;

  //Select stmt
  selectStmt.Rule = SELECT + selRestrOpt + selList + intoClauseOpt + fromClauseOpt + whereClauseOpt;

  selRestrOpt.Rule = Empty | "ALL" | "DISTINCT";
  selList.Rule = columnItemList | "*";
  columnItemList.Rule = MakePlusRule(columnItemList, comma, columnItem);
  columnItem.Rule = columnSource + aliasOpt;
  aliasOpt.Rule = Empty | asOpt + Id; 
  asOpt.Rule = Empty | AS;
  columnSource.Rule = aggregate | Id;
  aggregate.Rule = aggregateName + "(" + aggregateArg + ")";
  aggregateArg.Rule = expression | "*"; 
  aggregateName.Rule = COUNT | "Avg" | "Min" | "Max" | "StDev" | "StDevP" | "Sum" | "Var" | "VarP";
  intoClauseOpt.Rule = Empty | INTO + Id;
  fromClauseOpt.Rule = Empty | FROM + idlist + joinChainOpt; 
  joinChainOpt.Rule = Empty | joinKindOpt + JOIN + idlist + ON + Id + "=" + Id;
  joinKindOpt.Rule = Empty | "INNER" | "LEFT" | "RIGHT";
  whereClauseOpt.Rule = Empty | expression;


Coordinator
Dec 10, 2014 at 7:06 PM
you have to understand how LALR works and how to fix the conflicts. Read about LALR parsing, there's plenty of info out there.
Sorry, no easy way. Irony makes it easier to build parser, but you have to know what parser is and how it works.
Dec 18, 2014 at 11:28 AM
Hi Roman,

Thanks for your reply and sorry for replying late. I would me to help your provide some specific pointers as to what is missing and what to refer to LALR parsing since i am very new to these.

Thanks Again
Piyush
Coordinator
Dec 18, 2014 at 10:33 PM
Hi

A little bit of explanation of conflicts, 'dangling else' and how to solve them:
http://eli-project.sourceforge.net/elionline/syntax_3.html

For deeper reading, my #1 recommendation is always Parsing Techniques, 2 ed
http://www.amazon.com/Parsing-Techniques-Practical-Monographs-Computer/dp/038720248X
Focus on LR/LALR algorithms; it is not very difficult reading, but requires quite a time and concentration to go through (very clear!) explanations and examples
Reserve a whole weekend for this, at minimum
Have a nice weekend :) !
Roman