[antlr-interest] Re: Bounded Left Recursion
Terence Parr
parrt at jguru.com
Sat Mar 22 07:19:16 PST 2003
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/
More information about the antlr-interest
mailing list