Re: Computing first sets on a left-recursive grammar

Max Hailperin <>
14 Apr 2001 17:14:35 -0400

          From comp.compilers

Related articles
Computing first sets on a left-recursive grammar (Cyrus Najmabadi) (2001-04-10)
Re: Computing first sets on a left-recursive grammar (Paul Mann) (2001-04-12)
Re: Computing first sets on a left-recursive grammar (Sönke Kannapinn) (2001-04-12)
Re: Computing first sets on a left-recursive grammar (Max Hailperin) (2001-04-14)
Re: Computing first sets on a left-recursive grammar (2001-04-14)
| List of all articles for this month |

From: Max Hailperin <>
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" <> 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

Post a followup to this message

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