Re: LL(n) parsers

whatis@gnu.ai.mit.edu (Steve Boswell) writes:
>Hi all, I'm writing a LL(n) backtracking parser generator, and I've
>hit upon a snag. Eliminating immediate and non-immediate left
>recursion by modifying the grammar is easy enough (and well documented
>in the Dragon Book, which is my reference) but I'd rather do it
>using programmed methods. I have an algorithm for the immediate left
>recursion, but I'm having trouble generalizing it to the non-immediate
>case. Does anyone know of ways to do this, or where I can look it
>up?


Pardon me if I'm not answering the question you're asking, but the
Dragon Book does contain an algorithm for removing all left recursion.
The algorithm for *immediate* left recursion appears in section 2.4
(p. 50 of my edition). The algorithm for eliminating *all* left
recursion is Algorithm 4.1 in section 4.3 (p. 177 of my edition).
This classic algorithm appears also in Hopcroft and Ullman's standard
theory text.


(Hmmmm....looks like my edition is dated March, 1986.)
--
William J. Schmidt
Iowa State University
schmidt@kickapoo.cs.iastate.edu
--

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