[antlr-interest] Left recursion

Benji Smith benji at benjismith.net
Thu Jul 26 11:20:37 PDT 2007


Nesting of blocks is done through *right* recursion, not left recursion.

Left-recursion looks like this:

A : ( A )* B ;

Whereas right-recursion looks more like this:

A : B ( A )* ;

Since every statement block must begin and end with a curly brace, its
definition avoids left-recursion.

--benji


On 7/26/07, Thomas Brandon <tbrandonau at gmail.com> wrote:
> On 7/27/07, mitchellch <mitchellch at comcast.net> wrote:
> > I feel like there must be an obvious answer for this one, but I can't find
> > it in the book or on the site.
> >
> > Given that ANTLR doesn't support left-recursion, how do I specify a grammar
> > for arbitrarily nested blocks?
> Modified from cminus example:
> block
>     :  '{'
>        ( stat )*
>        '}'
>     ;
>
> stat
>     : forStat
>     | expr ';'
>     | block
>     | assignStat ';'
>     | ';'
>     ;
>
> Tom.
> >
> >
> >
> > For example,
> >
> >
> >
> > void method() {
> >
> >             { /* nested block */
> >
> >                         { /* nested block */
> >
> >
> > double-nested-statement;
> >
> >                         }
> >
> >                         nested-statement;
> >
> >             }
> >
> >             unnested-statement;
> >
> > }
> >
> >
> >
> > -Mitch Christensen
>


More information about the antlr-interest mailing list