predictive parsing and non-recursive predictive parsing

Hi,

I have one question regarding the difference between those two:

I can use recursive predictive parsing, which is very straightforward.
So what's the advantage of non-recursive predictive parsing. To
perform non-recursive parsing, I need to construct FIRST, FOLLOW sets
and use explicit stack. On the other hand, recursive predictive
parsing is very easy to understand. I understand non-recursive calls
have a better performance than recursive one. Is this the only reason?

Thanks,
Michael

On Jun 24, 6:56 am, unix...@gmail.com wrote:
> Hi,
>
> I have one question regarding the difference between those two:
>
> I can use recursive predictive parsing, which is very straightforward.
> So what's the advantage of non-recursive predictive parsing. To

more parsing power.

> perform non-recursive parsing, I need to construct FIRST, FOLLOW sets
> and use explicit stack. On the other hand, recursive predictive
> parsing is very easy to understand. I understand non-recursive calls

Parsing algorithms are not constructed with ease of use in mind.

> have a better performance than recursive one. Is this the only reason?
>

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.

regards
-kamal

unix.sh@gmail.com writes:

> I can use recursive predictive parsing, which is very straightforward.
> So what's the advantage of non-recursive predictive parsing. To
> perform non-recursive parsing, I need to construct FIRST, FOLLOW sets
> and use explicit stack. On the other hand, recursive predictive
> parsing is very easy to understand. I understand non-recursive calls
> have a better performance than recursive one. Is this the only reason?

In principle, you also need to construct FIRST and FOLLOW sets to use
deterministic recursive predictive parsing (aka recursive descent).

If there are no empty productions, you don't need FOLLOW and if all
productions for the same nonterminal start with different terminal
symbols, FIRST is trivial, so in these cases you can write recursive
descent parsers very easily. But in the very same cases, construction
of LL(1) parse tables is also very easy. For more complicated cases,
you do need to calculate FIRST and FOLLOW even for recursive descent
-- at least if you want to avoid backtracking.

Table-driven LL(1) is no faster than recursive descent, and it can be
slower in some cases. But tables can be made fairly compact, so
table-driven parsers can be smaller. Also, tables are slightly easier
to generate than programs.

Torben

unix.sh@gmail.com writes:

> I have one question regarding the difference between those two:
>
> I can use recursive predictive parsing, which is very straightforward.
> So what's the advantage of non-recursive predictive parsing. To
> perform non-recursive parsing, I need to construct FIRST, FOLLOW sets
> and use explicit stack. On the other hand, recursive predictive
> parsing is very easy to understand. I understand non-recursive calls
> have a better performance than recursive one. Is this the only reason?

The only reasons that I can think of to distinguish between
recursive-descent predictive parsers and explicit-stack predictive
parsers are esthetics and efficiency. Efficiency includes efficiency
of parser construction, whether manual or using a parser generator, as
well as of parsing.

Your comments about FIRST and FOLLOW sets are misleading. You need to
find the FIRST sets in order to make either kind of predictive parser,
even recursive descent. And you don't absolutely need to find the
FOLLOW sets to make either kind of predictive parser, even the
explicit-stack kind. However, if you don't know the FOLLOW sets, you
won't be able to check at parser construction time that your grammar
is really ammenable to predictive parsing, and you won't be able to
produce as high quality of syntax error messages at parse time. Those
motivations for finding the FOLLOW sets apply equally well to both
kinds of predictive parsers.

On 24 Jun, 01:56, unix...@gmail.com wrote:
> I have one question regarding the difference between those two:
>
> I can use recursive predictive parsing, which is very straightforward.
> So what's the advantage of non-recursive predictive parsing. To
> perform non-recursive parsing, I need to construct FIRST, FOLLOW sets
> and use explicit stack. On the other hand, recursive predictive
> parsing is very easy to understand. I understand non-recursive calls
> have a better performance than recursive one. Is this the only reason?

Consider what happens when your input does not conform to the expected
structure. If you are going to recover from the error in the source
and continue processing you may need a way to unwind the stack under
your control. Recursive is fine if you have a way to recover from
source errors.

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

On Jun 24, 4:13 am, torb...@pc-003.diku.dk (Torben Fgidius Mogensen)
wrote:
> unix...@gmail.com writes:
> > .... On the other hand, recursive predictive
> > parsing is very easy to understand. I understand non-recursive calls
> > have a better performance than recursive one. Is this the only reason?
>
> In principle, you also need to construct FIRST and FOLLOW sets to use
> deterministic recursive predictive parsing (aka recursive descent).
>
> If there are no empty productions, you don't need FOLLOW and if all
> productions for the same nonterminal start with different terminal
> symbols, FIRST is trivial, so in these cases you can write recursive
> descent parsers very easily. But in the very same cases, construction
> of LL(1) parse tables is also very easy. For more complicated cases,
> you do need to calculate FIRST and FOLLOW even for recursive descent
> -- at least if you want to avoid backtracking.
>
> Table-driven LL(1) is no faster than recursive descent, and it can be
> slower in some cases. But tables can be made fairly compact, so
> table-driven parsers can be smaller. Also, tables are slightly easier
> to generate than programs.

The common predictive algorithms are LL and LR. You can draw a table
with LL and LR on one axis, Recursive and Explicit Stack on the other.
The two squares in the LL column are discussed in most textbooks, and
also the LR-Explicit Stack box. The last box LR- Recursive is not
usually covered. But there is a less-known, elegant recursive
formulation for LR parsers as well. Google "recursive LR parser" for
a few papers.

Recursive formulations tend to be more readable to humans. Tables and
explicit stacks tend to be more ammenable to automatic generation from
a grammar. An explicit stack might make debugging, animation and
error recovery codes a little simpler and more efficient. That's
about it. Performance differences are marginal: unlikely to matter.

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

> usually covered. But there is a less-known, elegant recursive
> formulation for LR parsers as well. Google "recursive LR parser" for
> a few papers.

Is this what is refered to as Recursive Ascent ?

Aaron

"Aaron Gray" <ang.usenet@gmail.com> writes:

>> there is a less-known, elegant recursive formulation for LR parsers
>> as well. Google "recursive LR parser" for a few papers.
>
> Is this what is refered to as Recursive Ascent ?

It is indeed.

Torben