Re: predictive parsing and non-recursive predictive parsing

max@gustavus.edu
Tue, 24 Jun 2008 19:28:06 -0700 (PDT)

          From comp.compilers

Related articles
predictive parsing and non-recursive predictive parsing unix.sh@gmail.com (2008-06-23)
Re: predictive parsing and non-recursive predictive parsing kamalpr@hp.com (kamal) (2008-06-24)
Re: predictive parsing and non-recursive predictive parsing torbenm@pc-003.diku.dk (2008-06-24)
Re: predictive parsing and non-recursive predictive parsing max@gustavus.edu (Max Hailperin) (2008-06-24)
Re: predictive parsing and non-recursive predictive parsing james.harris.1@googlemail.com (James Harris) (2008-06-24)
Re: predictive parsing and non-recursive predictive parsing max@gustavus.edu (2008-06-24)
Re: predictive parsing and non-recursive predictive parsing gene.ressler@gmail.com (Gene) (2008-06-25)
Re: predictive parsing and non-recursive predictive parsing unix.sh@gmail.com (2008-06-25)
Re: predictive parsing and non-recursive predictive parsing ang.usenet@gmail.com (Aaron Gray) (2008-06-27)
Re: predictive parsing and non-recursive predictive parsing torbenm@pc-003.diku.dk (2008-06-27)
Re: predictive parsing and non-recursive predictive parsing kamalpr@hp.com (kamal) (2008-06-27)
Re: predictive parsing and non-recursive predictive parsing max@gustavus.edu (Max Hailperin) (2008-06-28)
[5 later articles]
| List of all articles for this month |

From: max@gustavus.edu
Newsgroups: comp.compilers
Date: Tue, 24 Jun 2008 19:28:06 -0700 (PDT)
Organization: Compilers Central
References: 08-06-053 08-06-055
Keywords: parse, LL(1)
Posted-Date: 25 Jun 2008 17:15:36 EDT

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


Post a followup to this message

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