Re: Computing "first" in LR(1) parsing (Max Hailperin)
29 Nov 2001 23:09:46 -0500

          From comp.compilers

Related articles
Computing "first" in LR(1) parsing (2001-11-26)
Re: Computing "first" in LR(1) parsing (Sönke Kannapinn) (2001-11-29)
Re: Computing "first" in LR(1) parsing (2001-11-29)
Re: Computing "first" in LR(1) parsing (2001-11-29)
Re: Computing "first" in LR(1) parsing (2001-11-29)
Re: Computing "first" in LR(1) parsing (2001-12-03)
| List of all articles for this month |

From: (Max Hailperin)
Newsgroups: comp.compilers
Date: 29 Nov 2001 23:09:46 -0500
References: 01-11-123
Keywords: LR(1), parse
Posted-Date: 29 Nov 2001 23:09:46 EST (Hans Aberg) wrote in message news:01-11-123...
> I want to compute the function "first" of LR(1) parsing: If x is a
> string of grammar symbols, first(x) is the set of terminals that begin
> the strings derivable from x with respect to the given grammar, plus
> the empty string, if derivable as well. In Aho et al, "Compilers", sec
> 4.4, p.189, 3, it says that if x is a nonterminal and there is a
> production x -> y1 ... yk, then to first(x) one should add first(yi)
> if the empty string is part of first(y1), ..., first(y{i-1}).
> But it does not say what happens if this procedure recurses, that is,
> if say when computing first(y1), one recurses back via some other
> relations to first(x). If that happens, is that not a LR(1) grammar,
> or how should this situation be handled?

What Aho, Sethi, and Ullman do not clearly explain is that this is an
iterative algorithm, convering on a least fixed point by working up
from below. So at each point in the iteration, you have some lower
bound on the eventual FIRST sets. Based on the current (iteration n)
lower bounds on the FIRST(yi), you calculate a new (iteration n+1)
lower bound on FIRST(x), in the manner you summarize above.

For an alternative presentation of this, you might see a pedagogical
paper I wrote on the topic, which is at

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