
I was trying to make a minor change today to the gram.y file to make
PostgreSQL recognize "DOUBLE" as a data type the way DB2 does.  I ran into
reduce / reduce conflicts using both of the methods I tried.  

Having fought extensively with  Bison before on a SQL oriented language
translation project, I am amazed that you were able to get a grammar as
complex as PostgreSQL to work without major difficulty.

I was wondering about what the sense of the list would be to someday accepting
a rewrite using a hand-coded LL(k) recursive descent parser.  Anyone?

 - Mark Butler

Wed, 11 Apr 2001 19:38:26 -0600
Mark Butler <butlerm@middle.net>
Yacc / Bison difficulties
> 
> I was trying to make a minor change today to the gram.y file to make
> PostgreSQL recognize "DOUBLE" as a data type the way DB2 does.  I ran into
> reduce / reduce conflicts using both of the methods I tried.  
> 
> Having fought extensively with  Bison before on a SQL oriented language
> translation project, I am amazed that you were able to get a grammar as
> complex as PostgreSQL to work without major difficulty.
> 
> I was wondering about what the sense of the list would be to someday accepting
> a rewrite using a hand-coded LL(k) recursive descent parser.  Anyone?

Interesting.  What advantages would there be?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Wed, 11 Apr 2001 23:30:51 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Yacc / Bison difficulties
Bruce Momjian wrote:

> Interesting.  What advantages would there be?

As any one who has ever attempted to build a C++ parser using Yacc or Bison
can attest, it is very difficult to get an LALR based parser to correctly
parse a sophisticated grammar.  The advantages of using a hand written
recursive descent parser lie in four areas:

1) ease of implementing grammar changes 
2) ease of debugging
3) ability to handle unusual cases
4) ability to support context sensitive grammars

Context sensitivity is useful for handling things like embedded programming
languages without having to escape whole procedures as string literals, for
example.  We could support procedural language plugins without the current
limitations on syntax.

Another nice capability is the ability to enable and disable grammar rules at
run time - you could add run time options to disable all non SQL-92 grammar
rules for application portability testing or emulate Oracle's outer join
syntax, as a couple of examples.

 - Mark Butler

Wed, 11 Apr 2001 22:37:56 -0600
Mark Butler <butlerm@middle.net>
Re: Hand written parsers
Mark Butler <butlerm@middle.net> writes:

> Bruce Momjian wrote:
> 
> > Interesting.  What advantages would there be?
> 
> As any one who has ever attempted to build a C++ parser using Yacc or Bison
> can attest, it is very difficult to get an LALR based parser to correctly
> parse a sophisticated grammar.  The advantages of using a hand written
> recursive descent parser lie in four areas:
> 
> 1) ease of implementing grammar changes 
> 2) ease of debugging
> 3) ability to handle unusual cases
> 4) ability to support context sensitive grammars
> 
> Context sensitivity is useful for handling things like embedded programming
> languages without having to escape whole procedures as string literals, for
> example.  We could support procedural language plugins without the current
> limitations on syntax.
> 
> Another nice capability is the ability to enable and disable grammar rules at
> run time - you could add run time options to disable all non SQL-92 grammar
> rules for application portability testing or emulate Oracle's outer join
> syntax, as a couple of examples.

On the other hand, recursive descent parsers tend to be more ad hoc,
they tend to be harder to maintain, and they tend to be less
efficient.

I believe that yacc based parsers support context sensitivity just as
well as recursive descent parsers.

I'm not sure that C++ is a fair example.  The problem with parsing C++
is the result of a convoluted declaration syntax, so much so that some
constructs are completely syntactically ambiguous no matter how you
look at them and must be decided by semantic rules.  It's true that in
such a case recursive descent is easier, because it is easier to mix
semantic rules and syntax rules.  But the SQL syntax is much simpler;
is this really a problem with SQL?  And I note that despite the
difficulties, the g++ parser is yacc based.

Ian

---------------------------(end of broadcast)---------------------------
TIP 462: A mushroom cloud has no silver lining.

11 Apr 2001 22:44:59 -0700
Ian Lance Taylor <ian@airs.com>
Re: Re: Hand written parsers
On Wed, Apr 11, 2001 at 10:44:59PM -0700, Ian Lance Taylor wrote:
> Mark Butler <butlerm@middle.net> writes:
> > ...
> > The advantages of using a hand written recursive descent parser lie in
> > 1) ease of implementing grammar changes 
> > 2) ease of debugging
> > 3) ability to handle unusual cases
> > 4) ability to support context sensitive grammars
> > ...
> > Another nice capability is the ability to enable and disable grammar
> > rules at run time ...
>
> On the other hand, recursive descent parsers tend to be more ad hoc,
> they tend to be harder to maintain, and they tend to be less
> efficient.  ...  And I note that despite the
> difficulties, the g++ parser is yacc based.

Yacc and yacc-like programs are most useful when the target grammar (or 
your understanding of it) is not very stable.  With Yacc you can make 
sweeping changes much more easily; big changes can be a lot of work in 
a hand-coded parser.  Once your grammar stabilizes, though, hand coding 
can provide flexibility that is inconceivable in a parser generator, 
albeit at some cost in speed and compact description.  (I doubt parser 
speed is an issue for PG.)

G++ has flirted seriously with switching to a recursive-descent parser,
largely to be able to offer meaningful error messages and to recover
better from errors, as well as to be able to parse some problematic
but conformant (if unlikely) programs.

Note that the choice is not just between Yacc and a hand-coded parser.
Since Yacc, many more powerful parser generators have been released,
one of which might be just right for PG.

Nathan Myers
ncm@zembu.com

Thu, 12 Apr 2001 00:53:56 -0700
ncm@zembu.com (Nathan Myers)
Re: Re: Hand written parsers
set nomail

Thu, 12 Apr 2001 11:19:12 -0700
"Howard Williams" <howieshouse@home.com>
Mark Butler writes:

> I was trying to make a minor change today to the gram.y file to make
> PostgreSQL recognize "DOUBLE" as a data type the way DB2 does.  I ran into
> reduce / reduce conflicts using both of the methods I tried.

See attached patch.

-- 
Peter Eisentraut      peter_e@gmx.net       http://yi.org/peter-e/
Thu, 12 Apr 2001 20:22:24 +0200 (CEST)
Peter Eisentraut <peter_e@gmx.net>
Re: Yacc / Bison difficulties
Thanks. I didn't realize the need to move the DOUBLE token from the TokenId to
the ColId production.  Will this patch be integrated into the head branch?

 - Mark Butler

Peter Eisentraut wrote:
> 
> Mark Butler writes:
> 
> > I was trying to make a minor change today to the gram.y file to make
> > PostgreSQL recognize "DOUBLE" as a data type the way DB2 does.  I ran into
> > reduce / reduce conflicts using both of the methods I tried.
> 
> See attached patch.

Thu, 12 Apr 2001 12:57:46 -0600
Mark Butler <butlerm@middle.net>
Re: Yacc / Bison difficulties
Mark Butler writes:

> Thanks. I didn't realize the need to move the DOUBLE token from the TokenId to
> the ColId production.  Will this patch be integrated into the head branch?

Not sure.  It's not a standard type, but at least two other RDBMS have it
and the name does make sense.  Any comments?

>
>  - Mark Butler
>
> Peter Eisentraut wrote:
> >
> > Mark Butler writes:
> >
> > > I was trying to make a minor change today to the gram.y file to make
> > > PostgreSQL recognize "DOUBLE" as a data type the way DB2 does.  I ran into
> > > reduce / reduce conflicts using both of the methods I tried.
> >
> > See attached patch.
>
>

-- 
Peter Eisentraut      peter_e@gmx.net       http://yi.org/peter-e/


Fri, 13 Apr 2001 00:30:48 +0200 (CEST)
Peter Eisentraut <peter_e@gmx.net>
Re: Yacc / Bison difficulties
> Mark Butler writes:
> 
> > Thanks. I didn't realize the need to move the DOUBLE token from the TokenId to
> > the ColId production.  Will this patch be integrated into the head branch?
> 
> Not sure.  It's not a standard type, but at least two other RDBMS have it
> and the name does make sense.  Any comments?

That's a tough call.  We already have some duplicate type symbols, but
this is not a standard SQL type.  I would see if we can get others to
say it is a good idea.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Thu, 12 Apr 2001 21:18:47 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Yacc / Bison difficulties
Bruce Momjian wrote:

> That's a tough call.  We already have some duplicate type symbols, but
> this is not a standard SQL type.  I would see if we can get others to
> say it is a good idea.

But the DOUBLE keyword is already reserved by ANSI for use in the "DOUBLE
PRECISION" type, so a "DOUBLE" synonym for it shouldn't make much of a
difference. Right?

 - Mark Butler

Thu, 12 Apr 2001 23:21:16 -0600
Mark Butler <butlerm@middle.net>
Re: DOUBLE synonym for DOUBLE PRECISION
Peter Eisentraut <peter_e@gmx.net> writes:
> Mark Butler writes:
>> Thanks. I didn't realize the need to move the DOUBLE token from the TokenId to
>> the ColId production.  Will this patch be integrated into the head branch?

> Not sure.  It's not a standard type, but at least two other RDBMS have it
> and the name does make sense.  Any comments?

Seems like a reasonable change (for 7.2, not now).

			regards, tom lane

Fri, 13 Apr 2001 02:35:07 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Yacc / Bison difficulties 
ncm@zembu.com (Nathan Myers) writes:
> Yacc and yacc-like programs are most useful when the target grammar (or 
> your understanding of it) is not very stable.  With Yacc you can make 
> sweeping changes much more easily; big changes can be a lot of work in 
> a hand-coded parser.

And, in fact, this is precisely the killer reason why we will not switch
to a handwritten parser anytime in the foreseeable future.  Postgres'
grammar is NOT stable.  Compare the gram.y files for any two recent
releases.  I foresee changes at least as large in upcoming releases,
btw, as we implement more of SQL92/99 and drop ancient PostQuel-isms.

I have some interest in proposals to switch to a better parser-generator
tool than yacc ...  but yacc has the advantages of being widely
available and widely understood.  You'd need a pretty significant
improvement over yacc to make it worth switching.

			regards, tom lane

Fri, 13 Apr 2001 03:12:57 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Re: Hand written parsers 
On Fri, Apr 13, 2001 at 03:12:57AM -0400, Tom Lane wrote:
> I have some interest in proposals to switch to a better parser-generator
> tool than yacc ...

There are tools to produce efficient top-down parsers as well.  Those
doing such parsers "by hand" may be interested in looking at PCCTS
(http://www.polhode.com/pccts.html) or ANTLR (http://www.antlr.org/).
-- 
Bruce Guenter <bruceg@em.ca>                       http://em.ca/~bruceg/
Sun, 15 Apr 2001 07:35:44 -0600
Bruce Guenter <bruceg@em.ca>
Re: Re: Hand written parsers