|Computing first sets on a left-recursive grammar email@example.com (Cyrus Najmabadi) (2001-04-10)|
|Re: Computing first sets on a left-recursive grammar firstname.lastname@example.org (Paul Mann) (2001-04-12)|
|Re: Computing first sets on a left-recursive grammar email@example.com (Sönke Kannapinn) (2001-04-12)|
|Re: Computing first sets on a left-recursive grammar firstname.lastname@example.org (Max Hailperin) (2001-04-14)|
|Re: Computing first sets on a left-recursive grammar email@example.com (2001-04-14)|
|From:||Max Hailperin <firstname.lastname@example.org>|
|Date:||14 Apr 2001 17:14:35 -0400|
|Posted-Date:||14 Apr 2001 17:14:35 EDT|
"Cyrus Najmabadi" <email@example.com> 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.
Associate Professor of Computer Science
Gustavus Adolphus College
800 W. College Ave.
St. Peter, MN 56082
Return to the
Search the comp.compilers archives again.