Re: LL(n) parsers (Kirk Hays)
6 Aug 91 18:17:10 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: (Kirk Hays)
Keywords: LL(1), parse, errors, books
Organization: Intel Supercomputer Systems Division
References: 91-07-053 91-07-066
Date: 6 Aug 91 18:17:10 GMT

In article 91-07-066, (William J. Schmidt) writes:
|> 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.

Note that versions of the Aho, Sethi, and Ullman Dragon Book dated prior to July,
1987, have a bug in algorithm 4.1, as discussed on the net in July, 1987.

Essentially, the `begin' on the second `for' should be on the first `for'. This
bug prevents removal of immediate left recursion.

The version in the original Dragon Book is correct, as well.

Ravi Sethi confirmed the problem. I have a paper copy of the relevant postings
stuck into my December, 1985 version.

|> (Hmmmm....looks like my edition is dated March, 1986.)

It's got the bug, then.

Did anyone else notice when they went to the thinner paper stock on the newer

Kirk Hays

Post a followup to this message

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