[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Interesting problem with PostgreSQL grammar ...
From: |
Hans Aberg |
Subject: |
Re: Interesting problem with PostgreSQL grammar ... |
Date: |
Mon, 22 Nov 2004 19:25:49 +0100 |
User-agent: |
Microsoft-Outlook-Express-Macintosh-Edition/5.0.6 |
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