Re: Bison Parser negate production rules

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)

Return to the comp.compilers page.
Search the comp.compilers archives again.