[antlr-interest] does ANTLR have syntax for negation of syntactic predicates?

Jim Idle jimi at temporal-wave.com
Sun Apr 1 15:20:03 PDT 2012


In order, this:

1) Left factor all those prefixes so that they have a common path until
they disambiguate (this is the fastest and neatest, but you have to work
at it)
2) Re order the alts - you should be able to put the alt that DOES have
that prefix before the ones that don't. If you cannot, then you will have
to work on 1) above at least to some extent.
3) Change to a semantic predicate and call the syntactic predicate
yourself

Things like this usually mean that your grammar is not 'right' though, so
I strongly advise that you start with 1. If you think of say C function
prototypes vs functions, you can see what to do:

stat: func_leadin  ( SEMI /* proto */ | func_body) ;


Just group all the common stuff together and don't even worry if the rules
allow slightly incorrect syntax - just detect that with a semantic check
either in the code or within your tree walk if you have once.


Jim


> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> bounces at antlr.org] On Behalf Of Nikolay Ognyanov
> Sent: Sunday, April 01, 2012 3:10 PM
> To: antlr-interest at antlr.org
> Subject: [antlr-interest] does ANTLR have syntax for negation of
> syntactic predicates?
>
> Can somebody please advise whether it is possible to negate a syntactic
> predicate in an ANTLR grammar? This is something fairly easy to do in
> the generated code but I am not able to find ANTLR syntax for it. I
> googled a couple of threads on the issue but found no definitive
> answer.
>
> I am not asking for help with my specific problem because I have a
> (kludgey) solution but but will describe it below FYI and in a hope to
> motivate implementation of the feature if it is not available.
>
> The problem is with a rule
>
> like this:
>
> rule
>      : alt1
>      | alt2
>        // ... more alternatives
>      | altm
>      | altn
>      ;
>
> where altm and altn can have (among many others) prefixes prefm and
> prefn respectively such that:
>
>    1/ No alternative other than altm and altm can have prefix
>       prefm or prefn.
>    2/ LL(*) analysis can not distinguish between prefm and prefn
>    2/ If the alternatve between prefm and prefm is resolved
>       then what remains from altm and altn is resolvable by LL(*)
>
> Now I can not say something like:
>
> rule
>      : alt1
>      | alt2
>        // ... more alternatives
>      | (prefm) =>  altm
>      | altn
>      ;
>
> because prefm is not the only possible start of altm.
> It is possible in priciple to say something like this:
>
> rule
>      : alt1
>      | alt2
>        // ... more alternatives
>      | (prefm) =>  prefm altmRest
>      | altmRest
>      | altn
>      ;
>
> but prefm and prefn are two of the core nonterminals in the grammar
> with so many rules, dependences, appearances and recursions that the
> breakdown to prefix and reminder is not practically feasible.
>
> Moreover I do not want to enable general backtracking for the rule
> because it would be quite a bit more expensive than backtracking over
> prefn only.
>
> So what I would like to say is something like this:
>
> rule
>      : alt1
>      | alt2
>        // ... more alternatives
>      | !(prefn) =>  altm
>      | altn
>      ;
>
>
> My kludgey solution is to subclass the parser and to override the
> syntactic predicate method to negate its result. It is somewhat better
> than directly patching the generated parser code but there is still the
> problem with the need to watch out for change of predicate method name
> if/when I add more predicates and the nasty side effects if/when I fail
> to do that.
>
> Thank you in advance
> Nikolay
>
>
>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-
> email-address


More information about the antlr-interest mailing list