aslam%blatz.cs.uiuc.edu@a.cs.uiuc.edu (Sohail Aslam) (07/29/87)
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]
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.ARPA
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | cca}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers. Meta-mail to ima!compilers-request