15 Jan 1997 11:54:48 -0500

Related articles |
---|

Recursive descent and left recursion mfinney@lynchburg.net (1997-01-14) |

Re: Recursive descent and left recursion fjh@mundook.cs.mu.OZ.AU (1997-01-15) |

Re: Recursive descent and left recursion hogan@rintintin.Colorado.EDU (1997-01-15) |

Re: Recursive descent and left recursion dlmoore@ix.netcom.com (David L Moore) (1997-01-16) |

Re: Recursive descent and left recursion cfc@world.std.com (1997-01-16) |

Re: Recursive descent and left recursion fjh@murlibobo.cs.mu.OZ.AU (1997-01-16) |

Re: Recursive descent and left recursion cfc@world.std.com (1997-01-17) |

Re: Recursive descent and left recursion will@ccs.neu.edu (William D Clinger) (1997-01-17) |

Re: Recursive descent and left recursion cfc@world.std.com (Chris F Clark) (1997-01-21) |

[1 later articles] |

From: | hogan@rintintin.Colorado.EDU (Apollo) |

Newsgroups: | comp.compilers |

Date: | 15 Jan 1997 11:54:48 -0500 |

Organization: | University of Colorado, Boulder |

References: | 97-01-099 |

Keywords: | parse, LL(1) |

*>However, I have been using recursive descent with left recursive*

*>grammers for more than a decade. All it takes is the trivially*

*>obvious check to allow the left recursion. Take, for example...*

*>*

*> (1) <exp> := <exp> + <term>*

*> (2) <exp> := <term>*

*>*

*> . . . .*

*>*

*>Has anyone else used this technique? Does anyone know if there are*

*>any "hidden" problems with it? Could it be applied to LR or LALR*

*>parsers?*

It seems to me that this simple check will parse a different language

than the original.

That is, if we have the grammar:

E -> E + T

E -> T

T -> a

Then this grammar will accept the following language:

a (+ a)*

However, with your parsing strategy (at least how I understand it,

the string

a + a + a

will not be accepted, because we need the following parse tree:

E

/ | \

/ | \

/ | \

/ | \

E + T

/ | \ |

/ | \ |

/ | \ |

T + T a

| |

| |

a a

Which requires expanding E twice while still on the same input token.

Am I confused?

--Apollo

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.