|eliminating left-recursion firstname.lastname@example.org (aegis) (2006-01-07)|
|Re: eliminating left-recursion email@example.com (Russell Shaw) (2006-01-08)|
|Re: eliminating left-recursion firstname.lastname@example.org (Chris Dodd) (2006-01-08)|
|Re: eliminating left-recursion DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-01-09)|
|Re: eliminating left-recursion email@example.com (jackycn) (2006-01-09)|
|From:||Chris Dodd <firstname.lastname@example.org>|
|Date:||8 Jan 2006 11:38:39 -0500|
|Posted-Date:||08 Jan 2006 11:38:39 EST|
"aegis" <email@example.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-
Return to the
Search the comp.compilers archives again.