Re: predictive parsing and non-recursive predictive parsing

unix.sh@gmail.com
Wed, 25 Jun 2008 17:37:07 -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)
Re: predictive parsing and non-recursive predictive parsing DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-06-28)
Re: predictive parsing and non-recursive predictive parsing ang.usenet@gmail.com (Aaron Gray) (2008-06-28)
[3 later articles]
| 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.