# Re: Computing "first" in LR(1) parsing

## max@gustavus.edu (Max Hailperin)29 Nov 2001 23:09:46 -0500

From comp.compilers

Related articles
Computing "first" in LR(1) parsing remove.haberg@matematik.su.se (2001-11-26)
Re: Computing "first" in LR(1) parsing kan@cs.tu-berlin.de (Sönke Kannapinn) (2001-11-29)
Re: Computing "first" in LR(1) parsing chrisd@reservoir.com (2001-11-29)
Re: Computing "first" in LR(1) parsing max@gustavus.edu (2001-11-29)
Re: Computing "first" in LR(1) parsing kgw-news@stiscan.com (2001-11-29)
Re: Computing "first" in LR(1) parsing remove.haberg@matematik.su.se (2001-12-03)
| List of all articles for this month |

 From: max@gustavus.edu (Max Hailperin) Newsgroups: comp.compilers Date: 29 Nov 2001 23:09:46 -0500 Organization: http://groups.google.com/ References: 01-11-123 Keywords: LR(1), parse Posted-Date: 29 Nov 2001 23:09:46 EST

remove.haberg@matematik.su.se (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
http://www.gustavus.edu/~max/ffp-sigcse.html

-Max Hailperin
Associate Professor of Computer Science