# Possible bug in Alg. 4.1 in the new Dragon book

## aslam%blatz.cs.uiuc.edu@a.cs.uiuc.edu (Sohail Aslam)Tue, 28 Jul 87 18:21:16 cdt

From comp.compilers

Related articles
Possible bug in Alg. 4.1 in the new Dragon book aslam%blatz.cs.uiuc.edu@a.cs.uiuc.edu (1987-07-28)
| List of all articles for this month |

 Date: Tue, 28 Jul 87 18:21:16 cdt From: aslam%blatz.cs.uiuc.edu@a.cs.uiuc.edu (Sohail Aslam) Us-Snail: 31B DCL, Univ. of Illinois, 1304 W. Springfield Av., Urbana, Ill 61801

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]
--

Post a followup to this message