Bison conflict ?

[judic...@gmail.com]

Hello All:

I am writing a parser to parse SQL (actually T-SQL for MS Sql Server).
I am getting a shift/reduce conflict that I don't know how to solve. I
know the reason of the conflict and I can give you 2 valid SQL
statements that can be parsed in two different ways. I just don't know
how to solve that in my grammar.

Consider the following two valid SQL statements:

Statement #1:
select b from s where b not in ( (select a from t where a = 1), 8, 9 );

Statement #2:
select b from s where b not in ( (select a from t where a = 1)
union (select a from t where a = 2) );

In stmt#1, the search condition inside the "not in" is a list of
expressions. In stmt#2, the search condition inside the "not in" is
another query combined with UNION.

Here is a simplified version of my bison grammar:
=========================================================================
expression: ICONST
| expression '+' expression
| expression '-' expression
| expression '*' expression
| expression '/' expression
| expression '%' expression
...
...
| '(' expression ')'
| '(' query_specification ')'
...
...
;

exp_list: exp_list ',' expression
| expression
;

predicate: expression '>' expression
| expression '<' expression
| expression LIKE expression
...
...
| expression IN '(' exp_list ')'
| expression NOT IN '(' exp_list ')'
| expression IN '(' query_list ')'
| expression NOT IN '(' query_list ')'
...
...
;

query_list: query_list UNION query_list
| '(' query_list ')'
| query_specification
;

/*
* This is the grammar for a select statement
*/
query_specification: SELECT select_list into_clause from_clause
where_clause group_by_clause having_clause

=========================================================================

The ambiguity arise when I give a statement like this:

Statement #3:
select b from s where b not in ( (select a from t where a = 1) );

The parser can treat the search condition as an exp_list or a
query_list.

Can someone point me out how to formulate my grammar.

Thanks
Richard

[Yunzhong]

Richard,
Consider changing these rules:
exp_list => expression;
expression => '(' query_specification ')';
query_list => '(' query_list ')';
query_list => query_specification;

Whether the query_spec in your statement #3 should reduce to exp_list
or query_list will depend on the particular SQL dialect you are
working with, especially the treatment of redundant parentheses. You
may also consider creating an extra nonterminal such as
exp_or_query_list.

Hope it helps.
Y.