Re: Bison Parser negate production rules

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


>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.


I'd appreciate some references.


It seems to me that the complement of a rule can't be concretely
defined without limiting the universe to those token strings which
would be legal in the language defined by the complete set of rules.


It also seems that with such limitation, the complemented rule should
be parsable using the same model given sufficient lookahead. That is,
the restriction means the complement subset is just the language minus
the subset which is the rule.




>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).


I'm not familiar with Yacc++, but I do use ANTLR and I was unaware
that it has this capability and I don't see any (obvious) syntax for
it in the manual. Do you have a cite or an example?


George
--

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