16 Jan 1997 11:20:32 -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) |

Re: Recursive descent and left recursion schoebel@eicheinformatik.uni-stuttgart.de (1997-01-25) |

From: | cfc@world.std.com (Chris F Clark) |

Newsgroups: | comp.compilers |

Date: | 16 Jan 1997 11:20:32 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 97-01-099 |

Keywords: | parse, LL(1), LR(1) |

mfinney@lynchburg.net wrote:

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

^^

I thought certainly someone else would catch this mis-impression, but

since no one has mentioned it. LR parsers allow left-recursion as

well as right recursion and any other recursion. It is LL parsers

which don't like left recursion. In fact, that is the main reason for

using LR (or LALR) parsing over LL. You can write your expression

grammars "naturally" with out inventing extra non-terminals to handle

precedence levels. That is:

expression : expression "+" expression

| expression "*" expression

. . .

By the way, it is little cited fact that those extra non-terminals to

handle precedence cost something. In a recursive descent parser, they

are extra subroutine calls. In an LR parser they are extra reductions

and in a table driven parser extra columns in each row of the table.

Chris Clark

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.