Re: LL(n) parsers

In article 91-07-066, schmidt@kickapoo.cs.iastate.edu (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
versions?


--
Kirk Hays
--

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