Re: LL(1)/Recursive Descent Parsing Question

Neelakantan Krishnaswami <neelk@alum.mit.edu> wrote in message


> I'm working on the syntax for a small programming language, and I'd
> like to make sure that my language is parseable with an LL(1) grammar.
> However, I'm still messing around with the grammar, and it's quite
> unpleasant to have to write my grammar rules in an epsilon-free,
> left-factored left-recursion-free form.


LL(1) grammars are not required to be epsilon-free. The need to left-factor
and eliminate left-recursion justifiably gives top-down grammars a bad
reputation. The indirect forms are even much more trouble to handle than the
direct forms. For example,


A -> d e | B
B -> C
C -> D
D -> d f


The indirect forms require first hoisting up the offending productions
until a direct form results, and then removing the direct form.


There are published algorithms that will remove these constructs from
somewhat limited grammar forms. One in the Dragon book requires an
epsilon-free grammar to guarantee success, so I assume this is why you
included that requirement. The algorithms that I have seen tend to
transform the original grammar in such a way as to make it pretty much
unrecognizable, so useless to the human reader.


SLK contains new heuristics that can left-factor and remove
left-recursion from context-free grammars. The resulting grammars are
usually quite readable. This is especially true for left-recursion
elimination, which tends to be straightforward.


A benefit of LL(k) over LL(1) is that left-factoring is not always
necessary. The grammar shown above is LL(2), but not LL(1). SLK can
detect which productions do not need to be left-factored for a given k
value, and leave them alone.


The free educational version of SLK on http://parsers.org/slk handles
small grammars of up to 64 nonterminals and 256 productions.

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