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

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/

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