Re: predictive parsing and non-recursive predictive parsing

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.

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