[antlr-interest] Re: Bounded Left Recursion

[Terence Parr]

On Friday, March 21, 2003, at 03:40  PM, lgcraymer wrote:

> Brian--
>
> The template idea is interesting and might be worth pursuing.
>
> Ter--what do you think?

Interesting...i'm wondering if we don't want to try some kind of 
precedence parser instead. Perhaps mark a rule (and all others invoked 
from it) as a special rule that gets implemented differently.  I have 
to look back at my precedence parsing notes from 10 years ago to see 
what way would be better.

Yes, i've been annoyed by the cumbersome multi-level grammar for 
expressions for years.  Further, you have like 20 levels to go down 
just to parse "34".  Very inefficient compared to a state-machine based 
approach.  Can we blend the approaches for this particular problem?

Ter

>
> --Loring
>
>
>
> --- In antlr-interest at yahoogroups.com, Brian Smith
> <brian-l-smith at u...> wrote:
>> I will reply to both of you at once:
>>
>> lgcraymer wrote:
>>> Brian--
>>>
>>> I would suggest taking a look at some of the ANTLR example
> grammars,
>>> particularly the one for the exprAST example and java.g (or
> Monty's C
>>> grammar).  ANTLR handles operator precedence in the same way that
> you
>>
>> Thanks. I already know this standard way of doings things. I was
> just
>> tired of seeing dozens of lines of (essentially) the same rule
> repeated.
>> Since I do not use ANTLR's AST's representation, I also have to to
>> duplicate the embedded code that constructs my AST.
>>
>>> --- In antlr-interest at yahoogroups.com, mzukowski at y... wrote:
>>>> Very interesting post.  Two main problems:
>>>> 1. PCCTS hoisted those sem preds.  ANTLR doesn't.  So if you have
>>
>> Ah, I see what is meant now by hoisted semantic predicates. Of
> course
>> this technique cannot work without that
>>
>>>> 2. It is infinite recursion there, and antlr's analysis won't
> allow
>>>> You're stuck with that one, I think.
>>
>> I'm not sure what you meant by this.
>>
>>>> I agree it would be nice to have such a compact representation of
>>> expression rules.  I can't think of an easy way to do that in
> antlr
>>> currently, and it's really not too difficult
>>> to do it the standard LL way.
>>
>> How about supporting two-level grammars (i.e. grammars with
>> meta-rules/templates)? For example, you could define a rule like
> this:
>>
>> // meta-rule
>> infix<ops, nextLevel>
>>         :: nextLevel (^ops infix<ops, nextLevel>)?
>>         ;
>>
>> and then use it like this:
>>
>> expression:
>> 	infix<IMPLIES,
>>                infix<(AND|OR|XOR),
>>                      infix<(EQUALS|NOT_EQUALS),
>>                            infix<(LT|LE|GT|GE),
>>                                  infix<(PLUS|MINUS),
>>                                        infix<STAR|SLASH,
>>                                              prefix<NOT, INTEGER>
>>>
>>>
>>>
>>>
>>>
>>
>> prefixExp<ops, nextLevel>: OPS prefixExp<ops, nextLevel>
>>                           | nextLevel
>>                           ;
>>
>> Maybe, you want to convert this grammar to construct AST's for
> binary
>> expressions with a different shape. Then you could do it by changing
> one
>> line in the grammar:
>>
>>    infit<ops, nextLevel>
>> -	:: nextLevel (^ops infix<ops, nextLevel>)?
>> + 	:: nextLevel (^ops nextLevel)*
>>          ;
>>
>> Just a thought...
>>
>> Regards,
>> Brian
>
>
>
>
> Your use of Yahoo! Groups is subject to 
> http://docs.yahoo.com/info/terms/
>
>
--
Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org
Lecturer in Comp. Sci., University of San Francisco


 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/