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

Nikolay Ognyanov nikolay.ognyanov at travelstoremaker.com
Sun Apr 1 15:51:01 PDT 2012


Thank you, Jim.

Apparently your implicit answer is that there is no syntax
in ANTR for negation of syntactic predicates. If so - please
take this as a humble feature request.

To your specific suggestions:

Left-factoring the prefixes is not practically feasible
because they come from different rules and joining them
would ripple through too big part of the grammar. Ordering
would not help because LL(*) does not distinguish between
the 2 prefixes. The idea of using semantic predicate sounds
helpful to me. The way I am inclined to use this hint is
to subclass the parser and implement in the derived
class the syntactic predicate I need with all the backtracking
logic and then use a semantic predicate (which can not have
backtracking logic inlined) to call the sytactic predicate.
This way I will avoid problems with eventual change of sytactic
predicate method name. Of course this all is still a kludge
but it is considerably better than the one I described earlier.

Regards
Nikolay

On 04/02/2012 01:20 AM, Jim Idle wrote:
> 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
>>      
> 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