Tue, 28 Jul 87 18:21:16 cdt

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.