Re: Computing first sets on a left-recursive grammar

"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/

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