[antlr-interest] Refactoring (was Re: Nondeterminism problem)

lgcraymer lgc at mail1.jpl.nasa.gov
Fri Dec 19 11:36:35 PST 2003


Actually PCCTS did full LL at one method per rule, and ANTLR 3 should as well.  ANTLR 2 did not implement some important features 
of PCCTS--most notably full LL analysis/code generation and semantic predicate hoisting.  ANTLR 2 was a "rush to market" job while 
Ter was busy starting up jGuru.  At the time, Sriram Srinivasan had started work on JavaCC and was basing the design on PCCTS, 
albeit with some more "conservative" features like parse trees instead of ANTLR-style syntax trees.  Ter had just decided on Java as 
an implementation language after playing around with Sather and some others--by that time, he had developed a passionate dislike of 
C++.

That said, multiple methods per rule would be an internal refactoring of a grammar.  I've given some (not nearly enough) thought to 
grammar refactoring and can identify a few cases.  My bias is to think of tree grammar refactorings, but the current set of possible 
refactorings that I have identified includes (paired, for symmetry):

iteration to recursion (often necessary when using synpreds to determine exits from ()* loops)
recursion to iteration

left factoring
syntactic predication

subrule hoisting (pushing dangling alternatives "upwards")
subrule internment (converse)

rule/subrule replication (often necessary to insert different action sets)
rule/subrule consolidation (a good design of tree grammars often leads to simplification by consolidation--requires care in annotating 
the parser or preceding tree grammars)

inlining of rules (demotion of rule to subrule)
promotion of subrule to rule.

I'd like to build up a reasonably comprehensive list of these--automation assistance for refactoring is an obvious feature to incorporate 
into a workbench.  Anyone have any additions to suggest?

--Loring


--- In antlr-interest at yahoogroups.com, mzukowski at y... wrote:
> I can't think of any reason an LL grammar couldn't be one method per rule.
> Do you have a counter example?
> 
> My understanding of LALL is that it "simply" collapses the search space for
> lookahead tests at the expense of some accuracy.  I don't see any reason why
> doing that would be related to the one method per rule question.  
> 
> Monty
> 
> -----Original Message-----
> From: Oliver Zeigermann [mailto:oliver at z...] 
> Sent: Friday, December 19, 2003 8:48 AM
> To: antlr-interest at yahoogroups.com
> Subject: OT: [antlr-interest] Re: Nondeterminism problem
> 
> Terence Parr wrote:
> > I think you'll find that LALL(k) done by PCCTS is a proper *superset*.  
> > I don't understand "only one that does practical SLL(k) near 
> > computation".  Can you rephrase?  Again, PCCTS does full LALL(k); my 
> > dissertation was how approximate lookahead can be used to attenuate the 
> > complexity of computation and storage of lookahead.  This includes 
> > weaker parser as well as helping to build full LALL(k) parsers.
> 
> All this makes me wonder if there is any way to have a recursive descent 
> compiler generator handling all LL grammars that still has a single 
> method per grammar rule? If not is this one of the reasons ANTLR does 
> LALL instead of LL?
> 
> Oliver
> 
> 
> 
>  
> 
> Yahoo! Groups Links
> 
> To visit your group on the web, go to:
>  http://groups.yahoo.com/group/antlr-interest/
> 
> To unsubscribe from this group, send an email to:
>  antlr-interest-unsubscribe at yahoogroups.com
> 
> Your use of Yahoo! Groups is subject to:
>  http://docs.yahoo.com/info/terms/


 

Yahoo! Groups Links

To visit your group on the web, go to:
 http://groups.yahoo.com/group/antlr-interest/

To unsubscribe from this group, send an email to:
 antlr-interest-unsubscribe at yahoogroups.com

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




More information about the antlr-interest mailing list