Re: LL(n) parsers (William J. Schmidt)
Fri, 26 Jul 1991 18:28:37 GMT

          From comp.compilers

Related articles
LL(n) parsers (1991-07-24)
Re: LL(n) parsers (1991-07-26)
Re: LL(n) parsers (1991-08-06)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (William J. Schmidt)
Keywords: LL(1), parse
Organization: Iowa State University, Ames IA
References: 91-07-053
Date: Fri, 26 Jul 1991 18:28:37 GMT
Return-Path: <> (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

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

Post a followup to this message

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