# Re: predictive parsing and non-recursive predictive parsing

## unix.sh@gmail.com

Wed, 25 Jun 2008 17:37:07 -0700 (PDT)

*From comp.compilers*

| List of all articles for this month |

**From: ** | unix.sh@gmail.com |

**Newsgroups: ** | comp.compilers |

**Date: ** | Wed, 25 Jun 2008 17:37:07 -0700 (PDT) |

**Organization: ** | Compilers Central |

**References: ** | 08-06-053 08-06-055 08-06-061 |

**Keywords: ** | parse |

**Posted-Date: ** | 25 Jun 2008 20:58:08 EDT |

On Jun 24, 10:28 pm, m...@gustavus.edu wrote:

*> On Jun 24, 2:49 am, kamal <kama...@hp.com> wrote:*

*>*

*> > ...*

*> > Recursive (descent) parsing is leftmost. You have the follow set in*

*> > non-recursive parsing to figure out what *can* follow, and so opt to*

*> > reduce by a different rule than the leftmost reduction. It helps in*

*> > overcoming ambiguities that RDP have.*

*>*

*> (1) Yes, recursive descent parsing is leftmost, but that word*

*> "leftmost" means that the leftmost nonterminal is expanded out at each*

*> step, rather than anything about a "leftmost reduction" or, as your*

*> phrase "reduce by a different rule" suggests you might have meant,*

*> leftmost production. There is no reduction done at all in a recursive*

*> descent parser, and the choice of productions is not influenced by*

*> their order.*

*>*

*> (2) The non-recursive parsing that was being discussed in the original*

*> post was non-recursive *predictive* parsing, i.e., LL(1) top-down*

*> parsing. As such, it has no reductions either and follows the same*

*> sequence of parsing actions. It too is constructing a leftmost*

*> derivation.*

*>*

*> (3) Recursive descent parsers do not have ambiguities, because*

*> ambiguity is a property of a grammar or a language, not a parser.*

Thanks, guys. I appreciate it.

I think Max was right. According to the red dragon book p.181,

predictive parsing is the special case of recursive descent parsing.

For predictive parsing, it doesn't need backtracking. As I

understanding, predictive parsing can parse LL(0), and recursive

decent can parse LL(1). Also ANTLR can parse LL(*) which uses

predicates. Please correct me if I am wrong.

Michael

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.