14 Apr 2001 17:14:35 -0400

Related articles |
---|

Computing first sets on a left-recursive grammar cyrus@stwing.upenn.edu (Cyrus Najmabadi) (2001-04-10) |

Re: Computing first sets on a left-recursive grammar paul@parsetec.com (Paul Mann) (2001-04-12) |

Re: Computing first sets on a left-recursive grammar soenke.kannapinn@wincor-nixdorf.com (Sönke Kannapinn) (2001-04-12) |

Re: Computing first sets on a left-recursive grammar max@max.mcs.gac.edu (Max Hailperin) (2001-04-14) |

Re: Computing first sets on a left-recursive grammar parag@pinhead.parag.codegen.com (2001-04-14) |

From: | Max Hailperin <max@max.mcs.gac.edu> |

Newsgroups: | comp.compilers |

Date: | 14 Apr 2001 17:14:35 -0400 |

Organization: | HickoryTech Internet |

References: | 01-04-062 |

Keywords: | LL(1), parse |

Posted-Date: | 14 Apr 2001 17:14:35 EDT |

"Cyrus Najmabadi" <cyrus@stwing.upenn.edu> writes:

....

*> I'm trying to understand (while simultaneously code) the algorithm for*

*> computing first and follow sets in the Dragon book (p177).*

*> Unfortunately, I'm being pretty unsuccessful at implementing this*

*> obfuscated explanation. The fault seems to lie in left-recursive*

*> grammar productions. Because "First" calls itself on the individual*

*> elements of the yield of the production, a left-recursive production*

*> will cause "first" to loop forever....*

Others have addressed the question of how to compute FIRST, but not

directly explained what Mr. Najmabadi's mis-understanding of the

dragon book is.

The problem is that the dragon book's algorithm (really on p. 189;

p. 177 is left-recursion elimination) uses FIRST(X) to mean not the

actual FIRST set for X, but rather the current approximation to that

FIRST set, which as the algorithm runs is modified to move up to the

real set from below. The modification to FIRST(X) calls for looking

at what is in FIRST(Y_i), but this does *not* mean a recursive

procedure call is needed to do the whole algorithm and find out what

FIRST(Y_i) really is. Instead, it means to look at the current

approximation to FIRST(Y_i), so far as it is already known.

If you think in imperative programming terms, this makes a fair bit of

sense: FIRST(X) and FIRST(Y_i) are just variables that get mutated as

the iteration progresses.

If, on the other hand, you are more mathematically inclined and want a

mathematical formulation, or to think of it as functional programming

rather than imperative programming, then you need to add a subscript

to FIRST to indicate which approximation you are talking about.

-Max Hailperin

Associate Professor of Computer Science

Gustavus Adolphus College

800 W. College Ave.

St. Peter, MN 56082

USA

http://www.gustavus.edu/~max/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.