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

SLK Mail <parsersinc@earthlink.net>
Wed, 20 Aug 2008 16:50:23 -0400

          From comp.compilers

Related articles
Recursive Descent Parsers only with LL(1)-grammars? formatzeh@gmx.de (Gilbert Mirenque) (2008-08-20)
Re: Recursive Descent Parsers only with LL(1)-grammars? parsersinc@earthlink.net (SLK Mail) (2008-08-20)
Re: Recursive Descent Parsers only with LL(1)-grammars? torbenm@pc-003.diku.dk (2008-08-21)
Re: Recursive Descent Parsers only with LL(1)-grammars? jaluber@gmail.com (Johannes) (2008-08-21)
| List of all articles for this month |

From: SLK Mail <parsersinc@earthlink.net>
Newsgroups: comp.compilers
Date: Wed, 20 Aug 2008 16:50:23 -0400
Organization: Compilers Central
References: 08-08-041
Keywords: parse, LL(1)
Posted-Date: 23 Aug 2008 14:42:55 EDT

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/


Post a followup to this message

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