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: [email protected]
[mailto:[email protected]] On Behalf Of Jim Idle
Sent: Saturday, December 12, 2009 10:38 AM
To: [email protected]
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: [email protected]
[mailto:[email protected]] On Behalf Of Hans-Martin Adorf
Sent: Saturday, December 12, 2009 9:14 AM
To: [email protected]
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
--
You received this message because you are subscribed to the Google Groups
"il-antlr-interest" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/il-antlr-interest?hl=en.
List: http://www.antlr.org/mailman/listinfo/antlr-interest
Unsubscribe:
http://www.antlr.org/mailman/options/antlr-interest/your-email-address
