[antlr-interest] eliminating left-recursion in the PAREN grammar
Hans-Martin Adorf
dradorf at googlemail.com
Sat Dec 12 09:14:19 PST 2009
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/4d93a77b/attachment.html
More information about the antlr-interest
mailing list