Possible bug in Alg. 4.1 in the new Dragon book

I needed to remove left-recursion from a grammar I was working on. I had both
immediate left recursion and left recursion involving derivations of two or
more steps. I tried using Algorithm 4.1 on page 177 of the new Dragon book but
it didn't work. I had used the old Dragon book when I took a class in compiler
construction couple of years ago; I remember using the algorithm and it
worked. So I pulled out the old Dragon book and compared the old and the new
books. I noticed that the keyword ``begin'' appears at different location. In
the old book the alorithm reads:


1. Arrange the nonterminals.......
2. for i := 1 to n do
*begin*
for j := 1 to i-1 do
replace...
...
eliminate the immediate...
end


whereas in the new book, the algorithm reads


1. Arrange the nonterminals.......
2. for i := 1 to n do
for j := 1 to i-1 do *begin*
replace...
...
eliminate the immediate...
end


Matching up the begin-end in the new book implies that when i = 0, the
statment ``eliminate the immediate...'' will not be executed as it did in the
old book. This is needed to remove any immediate left recursion.
Am I missing something when using the new book's version of the algorithm?


Sohail Aslam
Department of Computer Science
University of Illinois
arpa aslam@a.cs.uiuc.edu
csnet aslam@uiuc.csnet
usenet {ihnp4,seismo}!uiucdcs!aslam
[The n in the algorithm is the number of non-terminals. It does look like a
bug -- in the very simple case in which there is only one non-terminal, the
elimination step never gets executed at all. -John]
--

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