Re: Bison Parser negate production rules

Chris F Clark <cfc@shell01.TheWorld.com>
2 Apr 2007 17:30:32 -0400

          From comp.compilers

Related articles
[2 earlier articles]
Re: Bison Parser negate production rules cfc@shell01.TheWorld.com (Chris F Clark) (2007-03-26)
Re: Bison Parser negate production rules mco333@sympatico.ca (mco333) (2007-03-27)
Re: Bison Parser negate production rules gneuner2@comcast.net (George Neuner) (2007-03-27)
Re: Bison Parser negate production rules cfc@shell01.TheWorld.com (Chris F Clark) (2007-03-29)
Re: Bison Parser negate production rules Meyer-Eltz@t-online.de (Detlef Meyer-Eltz) (2007-03-29)
Re: Bison Parser negate production rules gneuner2@comcast.net (George Neuner) (2007-03-29)
Re: Bison Parser negate production rules cfc@shell01.TheWorld.com (Chris F Clark) (2007-04-02)
| List of all articles for this month |

From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: 2 Apr 2007 17:30:32 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 07-03-084 07-03-090 07-03-094 07-03-097 07-03-100 07-03-109
Keywords: parse

George Neuner <gneuner2@comcast.net> writes:


> I still think set complement is a blunt instrument. I can't recall
> ever really missing it and I can't easily think of a good use for it.
> I can't imagine ever wanting to specify a parser rule in the negative
> as in the ANTLR example
>
> expr: T1 (~(T1|T2|T3))* (T1|T2|T3);
>
> because it's so very unlikely that I would ever want to accept every
> other valid language token in the hole.


Yes, one rarely needs the complement (alone), although set difference
is fairly useful when trying to express things like C++ rule of "its
an expression if it isn't a declaration". And, even then, one
generally wants the removed complement to be parsed as something else
legal.


And, again, that's what the original poster appeared to want, a
catch-all for things that weren't otherwised matched. For those
situations, the ordering of predicates alone is generally perfectly
sufficient without boolean operators. Still, once one has the ability
to order rules, adding in the boolean operators isn't that difficult.


If one looks closely, one finds that's the reason why there are more
predicated LL parsers (and PEGs which are almost the same thing) than
predicated LR parsers. It's easier to add ordering to the LL
technology. Of course, I hold Yacc++ as a proof point that it isn't
impossible to add ordering and predicates to LR parsing.


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.