Recursive Descent Parsers only with LL(1)-grammars?

Hello NG,

I'm not so familiar with compiler construction just interested in it.
What appears curious is that I have heard that it is only possible to
implement recursive descent parsers for LL(1)-grammars. But I imagine
that it isn't a problem to look ahead more than just one symbol. So my
question is why it is only possible for LL(1)-grammars?

greets
Gilbert

In general, it is very hard (NP-Hard) to determine "where to go next"
for an LL(k) grammar for k>1. Doing it by hand in a hand coded parser
would take forever and produce a huge program because of the large
number of possibilities, if done using naive algorithms. So,
impractical but not impossible, depending on the grammar.

Tools like ANTLR solve this problem by using a linear approximation to
LL(k). SLK does a real LL(k) analysis, usually very quickly. The
complexity of the proprietary algorithm that it uses is proportional
to the number of conflicts present in the grammar, which can become
exponential in the worst case, but not usually, or for any real world
grammars that I have seen.

SLK produces table-driven parsers. However, you can use it to analyze
your LL(k) grammar and tell you what the lookahead token strings are
where k>1. This information can be used to write an LL(k) recursive
descent parser because the number of such strings is small for many
grammars.

I have considered providing a library that would give access to an
LL(k) conflict table. This would give the advantage of tabular "where
to go next" that could be used along with most parsing paradigms, even
LR(k) in an SLR(k) sort of way.

SLK Parser Generator: http://home.earthlink.net/~slkpg/

Gilbert Mirenque <formatzeh@gmx.de> writes:


> I'm not so familiar with compiler construction just interested in it.
> What appears curious is that I have heard that it is only possible to
> implement recursive descent parsers for LL(1)-grammars. But I imagine
> that it isn't a problem to look ahead more than just one symbol. So my
> question is why it is only possible for LL(1)-grammars?

That depends on how you define recursive descent. It is often defined
as deterministically deciding the next action by only looking at the
next input symbol. This effectively reduces lookahead to 1, but it is
easy to generalise recursive descent to arbitrary lookaheads and even
backtracking, which will allow parsing larger classes of grammars.

If you allow backtracking, you can parse all CF languages, but time
may be exponential.

Torben

On Aug 20, 7:33 pm, Gilbert Mirenque <format...@gmx.de> wrote:
> Hello NG,
>
> I'm not so familiar with compiler construction just interested in it.
> What appears curious is that I have heard that it is only possible to
> implement recursive descent parsers for LL(1)-grammars. But I imagine
> that it isn't a problem to look ahead more than just one symbol. So my
> question is why it is only possible for LL(1)-grammars?

LL(1) is far too limiting the possibilities. Maybe the people confused
it with a fixed look-ahead, which LL(k) is traditionally known for.
But with ANTLR (http://www.antlr.org) now LL(*) is supported, which
allows infinite look-ahead. Basically LR and LL are pretty much equal
in recognition power (although people are going to correct me on
that .

Johannes