Bison conflict ?

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

Return to the comp.compilers page.
Search the comp.compilers archives again.