Re: predictive parsing and non-recursive predictive parsing

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.


  -Max Hailperin
    Professor of Computer Science
    Gustavus Adolphus College

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