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

[Jim Idle]

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/a566eac2/attachment-0001.html