# Re: predictive parsing and non-recursive predictive parsing

## Gene <gene.ressler@gmail.com>

Wed, 25 Jun 2008 17:31:27 -0700 (PDT)

*From comp.compilers*

| List of all articles for this month |

**From: ** | Gene <gene.ressler@gmail.com> |

**Newsgroups: ** | comp.compilers |

**Date: ** | Wed, 25 Jun 2008 17:31:27 -0700 (PDT) |

**Organization: ** | Compilers Central |

**References: ** | 08-06-053 08-06-056 |

**Keywords: ** | parse |

**Posted-Date: ** | 25 Jun 2008 20:57:37 EDT |

On Jun 24, 4:13 am, torb...@pc-003.diku.dk (Torben Fgidius Mogensen)

wrote:

*> unix...@gmail.com writes:*

*> > .... On the other hand, recursive predictive*

*> > parsing is very easy to understand. I understand non-recursive calls*

*> > have a better performance than recursive one. Is this the only reason?*

*>*

*> In principle, you also need to construct FIRST and FOLLOW sets to use*

*> deterministic recursive predictive parsing (aka recursive descent).*

*>*

*> If there are no empty productions, you don't need FOLLOW and if all*

*> productions for the same nonterminal start with different terminal*

*> symbols, FIRST is trivial, so in these cases you can write recursive*

*> descent parsers very easily. But in the very same cases, construction*

*> of LL(1) parse tables is also very easy. For more complicated cases,*

*> you do need to calculate FIRST and FOLLOW even for recursive descent*

*> -- at least if you want to avoid backtracking.*

*>*

*> Table-driven LL(1) is no faster than recursive descent, and it can be*

*> slower in some cases. But tables can be made fairly compact, so*

*> table-driven parsers can be smaller. Also, tables are slightly easier*

*> to generate than programs.*

The common predictive algorithms are LL and LR. You can draw a table

with LL and LR on one axis, Recursive and Explicit Stack on the other.

The two squares in the LL column are discussed in most textbooks, and

also the LR-Explicit Stack box. The last box LR- Recursive is not

usually covered. But there is a less-known, elegant recursive

formulation for LR parsers as well. Google "recursive LR parser" for

a few papers.

Recursive formulations tend to be more readable to humans. Tables and

explicit stacks tend to be more ammenable to automatic generation from

a grammar. An explicit stack might make debugging, animation and

error recovery codes a little simpler and more efficient. That's

about it. Performance differences are marginal: unlikely to matter.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.