Re: LL(n) parsers

hays@ssd.intel.com (Kirk Hays)
6 Aug 91 18:17:10 GMT

          From comp.compilers

Related articles
LL(n) parsers whatis@gnu.ai.mit.edu (1991-07-24)
Re: LL(n) parsers schmidt@kickapoo.cs.iastate.edu (1991-07-26)
Re: LL(n) parsers hays@ssd.intel.com (1991-08-06)
| List of all articles for this month |

Newsgroups: comp.compilers
From: hays@ssd.intel.com (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, 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
--


Post a followup to this message

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