Re: LL(1)/Recursive Descent Parsing Question

"SLK Parsers" <>
25 Mar 2002 01:14:12 -0500

          From comp.compilers

Related articles
LL(1)/Recursive Descent Parsing Question (2002-03-19)
Re: LL(1)/Recursive Descent Parsing Question (jacob navia) (2002-03-21)
Re: LL(1)/Recursive Descent Parsing Question (Peter H. Froehlich) (2002-03-21)
Re: LL(1)/Recursive Descent Parsing Question (Joachim Durchholz) (2002-03-22)
Re: LL(1)/Recursive Descent Parsing Question (SLK Parsers) (2002-03-25)
| List of all articles for this month |

From: "SLK Parsers" <>
Newsgroups: comp.compilers
Date: 25 Mar 2002 01:14:12 -0500
Organization: Parsers Inc.
References: 02-03-106
Keywords: parse
Posted-Date: 25 Mar 2002 01:14:12 EST

Neelakantan Krishnaswami <> 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 handles
small grammars of up to 64 nonterminals and 256 productions.

Post a followup to this message

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