Re: Oracle grammar ambiguities and conflicts

Chris F Clark <cfc@shell01.TheWorld.com>
12 Jan 2006 12:12:18 -0500

          From comp.compilers

Related articles
SQL grammar problem with Visual Parse++ junk@junk.com (John) (2001-07-23)
Oracle grammar ambiguities and conflicts mattblackmon@hotmail.com (matt blackmon) (2006-01-09)
Re: Oracle grammar ambiguities and conflicts grosch@cocolab.de (Josef Grosch) (2006-01-12)
Re: Oracle grammar ambiguities and conflicts derek@knosof.co.uk (Derek M. Jones) (2006-01-12)
Re: Oracle grammar ambiguities and conflicts cfc@shell01.TheWorld.com (Chris F Clark) (2006-01-12)
Re: Oracle grammar ambiguities and conflicts DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-01-12)
Re: Oracle grammar ambiguities and conflicts drikosv@otenet.gr (Evangelos Drikos) (2006-01-12)
Oracle grammar ambiguities and conflicts mark.thiehatten@bibit.com (Mark Thiehatten) (2006-01-12)
Re: Oracle grammar ambiguities and conflicts cfc@shell01.TheWorld.com (Chris F Clark) (2006-01-17)
Re: Oracle grammar ambiguities and conflicts mattblackmon@hotmail.com (Matt Blackmon) (2006-01-17)
Re: Oracle grammar ambiguities and conflicts david@tribble.com (David R Tribble) (2006-01-17)
[3 later articles]
| List of all articles for this month |

From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: 12 Jan 2006 12:12:18 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 01-07-118 06-01-029
Keywords: parse, SQL

Matt Blackmon reasked:
>I am attempting to write a parser for Oracle 7.3.4 SQL/PLSQL using
>Visual Parse++ 4.0. I have run into a problem where non-reserved
>keywords must be included as identifiers, causing millions of conflicts
>in the grammar. Does anyone have experience with either using VP++
>or with writing grammars for SQL?


Generally the cleanest solution is:


create a non-terminal id which accepts all the keywords (you may have
done this) and use it in place of your token ID.


e.g.


id: ID | KW1 | KW2 | KW3 | ... | FROM | ... | SELECT | ... ;


select: SELECT id FROM table;


Now, this will give you conflicts at several (many) points in the grammar.


For each such point in the grammar, look at the tables and conflict messages.


e.g.
conflict between shifting "FROM" and reducing id at state 3.
conflict between shifting "KW3" and reducing id at state 3.


That conflict means you need another id non-terminal, say id_1 which
does not allow FROM or KW3, as in:


id_1: ID | KW1 | KW2 | ... | SELECT | ... ;


You then have to use that in the proper spot(s) in the grammar. That
is not the rule which is shifting the grammar, but the rule that has
the id reference. Generally, when I am looking for such conflicts I
back-up in the grammar and find the state which shifted to this state
and in that state one of the items (dotted rules) will have a dot (I
think bison and byacc use _ for dot, Yacc++ uses ., other tools could
use other characters) before the id nonterminal that needs to be
changed to id_1. Fix that rule.


Repeat this process until it converges (i.e. you get no more
conflicts).


Alternately, if all you conflicts are shift-reduce conflicts between
keywords and the id non-terminal, you can simply ignore the conflicts
as the default rule of preferring to shift over reducing has exactly
the right semantics to resolve this problem. Of course, that can
leave you with a huge pile of warnings which you want to ignore. You
can improve on that with associativity and precedence directives, so
that the shifts are prefered to reduces of "id" by default and with no
warning.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------


Post a followup to this message

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