Re: predictive parsing and non-recursive predictive parsing

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

Return to the comp.compilers page.
Search the comp.compilers archives again.