[antlr-interest] eliminating left-recursion in the PAREN grammar

[Jim Idle]

Sorry – pressed send too quickly ;-)
 
I meant to say that while the theory states this, I don’t believe that it is possible to construct a practical grammar in ANTLR that would do it. ANTLR uses LL(1) for this. It may be possible to hack this, but otherwise the construct I have (and you have now I look at it more closely J, is what you would do in ANTLR. There may be options for this in the future though as there are two methodologies for parsing expressions without recursion that are contemplated, mostly for avoiding lots of recursive method calls for expression parsing in the Java target. These work by keeping state as they go basically. 
 
Jim
 
 
 
From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Jim Idle
Sent: Saturday, December 12, 2009 10:38 AM
To: antlr-interest at antlr.org
Subject: Re: [antlr-interest] eliminating left-recursion in the PAREN grammar
 
grammar T;
 
program
       : LPAREN program? RPAREN
       ;
 
LPAREN : '(';
RPAREN : ')';
WS     : (' '|'\t'|'\n'|'\r')+ { skip(); } ;
 
Jim
 
From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Hans-Martin Adorf
Sent: Saturday, December 12, 2009 9:14 AM
To: antlr-interest at antlr.org
Subject: [antlr-interest] eliminating left-recursion in the PAREN grammar
 
Folks,

I am working with a toy grammar as a stepping stone for more complicated grammars. It is a grammar for the well-known PAREN language consisting only of matched nested parantheses. In other words the language consists of non-empty strings of the form "()", "(())", "()()", etc.

The grammar I am toying with reads
grammar PAREN;
tokens {
     L     = '(' ;
     R     = ')' ;
}
s : L R | L s R | s s;

ANTLR has the foreseeable problem with left-recursion. I was able to fix the grammar for use with ANTLR by using an EBNF-notation

grammar ParenEBNF;
tokens {
    L    = '(' ;
    R    = ')' ;
}
s : L s? R s? ;

However, I would still be interested in a purely recursive grammar that avoids left-recursion. Theory states that it should be possible to rewrite the grammar such that it avoids left-recursion (and iterations). But I am lacking the skills to achieve this, despite the apparent simplicity of the language above. 

Any hints are welcome.

Regards
Hans-Martin Adorf




-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20091212/54566f97/attachment.html