Re: Bison Parser negate production rules

Chris F Clark <cfc@shell01.TheWorld.com>
26 Mar 2007 14:26:17 -0400

          From comp.compilers

Related articles
Bison Parser negate production rules royzlife@gmail.com (2007-03-23)
Re: Bison Parser negate production rules gneuner2@comcast.net (George Neuner) (2007-03-26)
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: 26 Mar 2007 14:26:17 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 07-03-084 07-03-090
Keywords: parse, yacc
Posted-Date: 26 Mar 2007 14:26:17 EDT

George Neuner <gneuner2@comcast.net> writes:


> On 23 Mar 2007 22:16:22 -0400, royzlife@gmail.com wrote:
>
>>Can any one help in explaining how to negate a production rule in
>>Bison parser?
>>e.g A:B
>> B: C
>> |D
>> |E
>> (here i want to write a block of statements or rules which will be
>>executed if B doesnt match to C/D/E.)
>>
>>[Basically, you can't other than by enumerating all of the other
>>possibilities. What do you really want to do here? -John]
>
> There is no way to specify the complement of a rule because it isn't a
> terribly useful thing to do. Context free languages are drawn from an
> infinite set of strings, the complement of any particular subset of a
> language is also an infinite set of strings. Not very practical to
> match.


Perhaps equally importantly the set of deterministic context free
languages is not closed under complement. That is a NOT rule means
your grammar is no longer parsable using the same basic machinery, as
one without a NOT rule. In other words, if you have an LL or LR
grammar and add a NOT rule it may cease to be an LL or LR grammar.


Now, the "modern" parsing methodologies like GLR, PEGs, and predicated
grammars are closed under complement, so if you use a technique like
that, you can add a NOT rule and still create a parser.


In fact, Yacc++ can be thought of as taking Yacc/Bison and adding in
regular expressions and predicates (then cleaning up the syntax a
little). In it we have a not predicate that allows exactly what you
are asking for. You will find similar functionality in PCCTS/ANTLR
although the underlying technology is LL not LR for them, so you
cannot use left recursion (or precedence rules).


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.