Re: Interesting problem with PostgreSQL grammar ...

[Hans Aberg]

One problem is that in a parser generator, different empty rules may have
different actions attached to them. Therefore, the parser generator cannot
zip them out, even though it make no difference in a formal grammar, which
does not worry about those semantic actions.

For example, let A[B]C be a shorthand for AC | ABC. Then A[B][C]D expands to
AD | ABD | ACD | ABCD, which is what one should choose as an implementation.
By contrast, if one implements A(empty | B)C, then A[B][C]D expands to
  A(empty | B)(empty | C)D
then the parser may not be able to resolve this (perhaps due to a limited
lookahead). In other words, first factor
    (empty | B)(empty | C) = empty | B | C | BC
and the use this expansion in the implementation.

On 2004/11/22 10:44, Laurence Finston at address@hidden wrote:

>> You do not say what shift/reduce conflicts you get, so it is hard to follow.
>> Please make sure to always include pertinent info.
>> 
>> But a casual look suggests that you may get a conflicts between two empty
>> rules. If that is so, you need to rewrite your grammar.
>> 
> 
> My experience bears this out.  One of the advantages of using the approach
> I described in my last posting is that it reduces the number of empty
> rules.  It also makes it possible to have use options in any order in the
> input, and to use options multiple times.  I won't claim that it's not
> possible to do this in the normal way, but I don't know off the top of my
> head how to do it.  My approach does involve some overhead, so I don't
> always use it.  I'm past the point of worrying about shift-reduce
> conflicts;  if resolving them by shifting works, I don't care.
> 
> Laurence