[antlr-interest] Left-factoring and recursion

[Loring Craymer]

> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> bounces at antlr.org] On Behalf Of Nigel Sheridan-Smith
> Sent: Sunday, January 09, 2005 2:38 PM
> To: antlr-interest at antlr.org
> Subject: [antlr-interest] Left-factoring and recursion
> 
> 
> Hi everyone,
> 
> I was wondering if there are any tools out there that help with
> left-factoring, or converting from LALR/LR to LL(k)?
> 
> I am trying to do a Structure of Management Information (SMI) grammar for
> networking devices. I tried the ANTLR ASN.1 grammar that already exists,
> but
> it had a few non-determinisms and the like, so I started to do my own
> since
> it looked pretty messy to fix up. However, now I have even more
> non-determinisms because the X.680-683 standards seem to favour
> left-recursion (like just about everyone else). So I'm faced with the huge
> and complicated left-factoring task, or I can switch back to the existing
> ASN.1 grammar and try and extend that.
> 
> Any ideas?
> 
> I found a few links from ANTLR/PCCTS users:
> 
> http://www.zenspider.com/Languages/PCCTS/LR2LL.html
> http://www.javadude.com/articles/lalrtoll.html
> 
> But these are just very high-level. What I really need is a tool that
> either
> helps in clarifying what the non-determinisms are given a particular ANTLR
> grammar, or even attempts to left-factor on its own.
> 
> Cheers
> 
> Nigel
> 
> --
> Nigel Sheridan-Smith
> PhD research student
> 
> Faculty of Engineering
> University of Technology, Sydney
> Phone: 02 9514 7946
> Fax: 02 9514 2435

Nigel--

Use syntactic predicates as a first step for removing non-determinisms.
Some of the ANTLR 2 reported non-determinisms are not real, and result from
the approximate LLk algorithm.  Once you have a working grammar, left-factor
if you need the added performance.  I note that ANTLR 3 does/will do
automatic left-factoring and will remove predicates where they are unneeded;
does it make sense to spend a lot of effort manually left-factoring when the
tool will do it for you within a year?

--Loring