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

Hans-Martin Adorf dradorf at googlemail.com
Sat Dec 12 13:06:06 PST 2009


I found the solution in "Automata and Computability" by Dexter C. Kozen on
page 140. One has to use the Greibach normal form (GNF) of the grammar:

S => (B | (SB | (BS | (SBS
B => )

In ANTLR the grammar reads:

grammar ParenGreibach;

tokens {
    L = '(' ;
    R = ')' ;
}

s    : p NEWLINE? EOF! ;

p    : L ( R ( | p ) | p R ( | p ) )  ;

NEWLINE    : '\r'? '\n' ;

I have left-factored the grammar as much as I could in order to pacify
ANTLR.

Regards
Hans-Martin


On Sat, Dec 12, 2009 at 7:45 PM, Jim Idle <jimi at temporal-wave.com> wrote:

>  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
>
>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe:
> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20091212/5a0e9048/attachment.html 


More information about the antlr-interest mailing list