[antlr-interest] Re: Bounded Left Recursion

[Brian Smith]

Hello Terence and Loring,

The template idea has been around for years. I think it the 
distinguishing feature of "two level grammars," although my reference 
for two level grammars does not use template-like syntax.

I think that templates are more general than precedence parsing, 
especially if it is possible to add semantic actions and/or 
tree-building annotations to templates. Precedence rules only handle 
issues related to precedence and associativity. It seems that the syntax 
for handing precedence/associativity via templates is not too 
unreadable. Also, a template-based grammar can always be deconstructed 
down to a "normal" ANTLR grammar, which means that the core analysis and 
runtime code could not have to change at all if it was implemented as a 
preprocessor. So, my (naive) inclination is that templates are a better 
option than explicit precedence rules when performance issues are not 
taken into account.

Probably, dedicated precedence parsing is more efficient. However, with 
a template-based approach, you could have predefined left_infix, 
right_infix, prefix, postfix, etc. templates that would be specially 
optimized during the analysis in the same way. In other words, it seems 
like somebody could implement the templates first via a preprocessor for 
a proof of concept, and then later integrate the template processing 
into the LL analysis phase for optimization purposes.

- Brian



> On Friday, March 21, 2003, at 03:40  PM, lgcraymer wrote:
>>The template idea is interesting and might be worth pursuing.
>>
>>Ter--what do you think?

Terence Parr wrote:
> 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?





 

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