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

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