14 Jan 1997 20:06:31 -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) |

[3 later articles] |

From: | mfinney@lynchburg.net |

Newsgroups: | comp.compilers |

Date: | 14 Jan 1997 20:06:31 -0500 |

Organization: | Compilers Central |

Keywords: | parse, LL(1) |

I have noticed the occassional post here, as well as assertions in

various texts, that left recursion is not usable with recursive

descent (and LR parsers in general).

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>

when expanding (1), at the first term I simply check to see if the

current token in the input stream is the same as the last time that

the rewriting rule was expanded. If it is, then the parse has not

advanced and you have the infinite loop situation. I simply fail the

expansion and select an alternate rewriting rule for expansion. This

approach only requires the storage of a token # per left recursive

rewriting rule and single check of that token # against the current

token # (which can just be the line and column of the first character

in the token since that is usually maintained for error reporting).

It is very fast and does not significantly slow down the parsing. It

does require backtracking in the sense that a different rewriting rule

has to be selected, but there is no work associated with the

backtracking since it only occurs at the start of the left recursive

rewriting rule.

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?

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.