Re: eliminating left-recursion

Chris Dodd <cdodd@acm.org>
8 Jan 2006 11:38:39 -0500

          From comp.compilers

Related articles
eliminating left-recursion aegis@mad.scientist.com (aegis) (2006-01-07)
Re: eliminating left-recursion rjshaw@netspace.net.au (Russell Shaw) (2006-01-08)
Re: eliminating left-recursion cdodd@acm.org (Chris Dodd) (2006-01-08)
Re: eliminating left-recursion DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-01-09)
Re: eliminating left-recursion lojiancn@hotmail.com (jackycn) (2006-01-09)
| List of all articles for this month |

From: Chris Dodd <cdodd@acm.org>
Newsgroups: comp.compilers
Date: 8 Jan 2006 11:38:39 -0500
Organization: Compilers Central
References: 06-01-013
Keywords: parse, LL(1)

"aegis" <aegis@mad.scientist.com> wrote
> Given the following production:
>
> d-declarator: ID | d-declarator '[' constant ']' | '(' d-declarator ')'
> ;
>
> How can I eliminate left-recursion here? The method sketched
> out in 'Compilers, Principles, Techniques and Tools' only
> presents a very simple case...


The method in ASU is fully general -- given a production of the form:


        X ::= X A | B


Trnsforiming it into


        X ::= B X'
        X' ::= A X' | epsilon


is equivalent, but right recursive instead of left recursive. The intuition
behind this is that the original rule is equivalent to (EBNF):


        X ::= B A*


The recursive part of the original rule will expand to zero or more 'A'
components, but you eventually have to expand a B, which will go on the
beginning of the rule.


For your example:


        X == d-declarator
        A == '[' constant ']'
        B == ID | '(' d-declarator ')'


so the replacement expansion is


        d-declarator: ( ID | '(' d-declarator ')' ) d-declarator-tail
        d-declarator-tail: '[' constant ']' d-declarator-tail


for which you might need to expand the first rule as


        d-declarator: ID d-declarator-tail | '(' d-declarator ')' d-declarator-
tail


Chris Dodd
cdodd@acm.org


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.