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

[Nikolay Ognyanov]

P.S.: On a second thought, there is no need to subclass the
parser because it is probably possible to implement the
needed syntactic predicate in the @members section.

On 04/02/2012 01:51 AM, Nikolay Ognyanov wrote:

> 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
>>
>>
>>      
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>