Re: predictive parsing and non-recursive predictive parsing

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

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