8 Jan 2006 11:38:39 -0500

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) |

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) |

Posted-Date: | 08 Jan 2006 11:38:39 EST |

"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.