SQL grammar

Hello All:

First off, I would like to apologize in case this post does
not belong to
this
forum. If that is the case, please let me know if there is
another forum
where I
can post my question. 

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 diffrent 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
            ;

search_condition:   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




-- 
View this message in context: http://www.nabble.com/SQL-grammar-tp17127516p17127516.
html
Sent from the Gnu - Bison - Help mailing list archive at
Nabble.com.



_______________________________________________
help-bisongnu.org http
://lists.gnu.org/mailman/listinfo/help-bison

Hi. Also, here is a simplified version of my bison file. You
can just copy
and paste it in a file and compile it with:

bison -y -v -d  file_name.y




%token  NOT IN UNION ICONST SELECT FROM SCONST

%left UNION
%left '+' '-'
%left '*' '/'


%%


search_cond:    NOT IN '(' exp_list ')'
                | NOT IN '(' query_list ')'
                ;


exp_list:   exp_list ',' expression
            | expression
            ;

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


expression: ICONST
            | expression '+' expression
            | expression '-' expression
            | expression '/' expression
            | expression '*' expression
            | '(' expression ')'
            | '(' query_specification ')'
            ;

query_specification:    SELECT '*' FROM table
                        ;

table:  SCONST
        ;


%%




-- 
View this message in context: http://www.nabble.com/SQL-grammar-tp17127516p17127524.
html
Sent from the Gnu - Bison - Help mailing list archive at
Nabble.com.



_______________________________________________
help-bisongnu.org http
://lists.gnu.org/mailman/listinfo/help-bison

On 8 May 2008, at 17:49, RichardT wrote:

> please let me know if there is another forum
> where I
> can post my question.

The Usenet newsgroup comp.compilers.

> I am writing a parser to parse SQL (actually T-SQL for
MS Sql Server).

Or netsearch for links like
   http://savage.net.au/SQL/

> I am
> getting a shift/reduce conflict that I don't know how
to solve.

Look in the .output file, for the conflicting state and in
its  
conflicting rule, the tokens immediately before and after
the parsing  
position ".". The token precedences %left, etc.,
order these.

   Hans Aberg

  


_______________________________________________
help-bisongnu.org http
://lists.gnu.org/mailman/listinfo/help-bison

Check the logs, as Hans suggests. For starters, though,
what's this:

NOT IN ((SELECT '*' FROM SCONST))

What sort of 'search_cond' is it? First branch, second
branch, or both? 
It can't be both; that's a conflict.

Evan


_______________________________________________
help-bisongnu.org http
://lists.gnu.org/mailman/listinfo/help-bison

Evan Lavelle wrote:
> Check the logs, as Hans suggests. For starters, though,
what's this:
> 
> NOT IN ((SELECT '*' FROM SCONST))
> 
> What sort of 'search_cond' is it? First branch,
second branch, or both? 
> It can't be both; that's a conflict.

Sorry, didn't read your first post; seems you already knew
this.

There's no general fix. You need a detailed understanding
of your 
language, and you have to formulate the grammar in a way
that doesn't 
have these overlaps. There are a lot of SQL parsers on the
net, so that 
would be a good place to start.

In this simple case, your problem is that a
query_specification can be 
both a query and an expression. This might make sense to a
human, but 
not to a parser. You appear to be trying to fix this by the
use of 
brackets, but this won't work, since a bracketed expression
is still an 
expression. There are various things you can try, but which
one you 
should use depends on the language itself, which I know
nothing about:

1 - completely subsume queries into expressions

2 - completely exclude queries from expressions

3 - allow both query_lists and expressions to include 
query_specifications, but make sure that you never write a
production 
that actually uses both a query_list and an expression

Evan


_______________________________________________
help-bisongnu.org http
://lists.gnu.org/mailman/listinfo/help-bison