Computing "first" in LR(1) parsing

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?


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.matematik.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

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