|LL(n) parsers email@example.com (1991-07-24)|
|Re: LL(n) parsers firstname.lastname@example.org (1991-07-26)|
|Re: LL(n) parsers email@example.com (1991-08-06)|
|From:||firstname.lastname@example.org (Kirk Hays)|
|Keywords:||LL(1), parse, errors, books|
|Organization:||Intel Supercomputer Systems Division|
|Date:||6 Aug 91 18:17:10 GMT|
In article 91-07-066, email@example.com (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
Return to the
Search the comp.compilers archives again.