Computing "first" in LR(1) parsing

remove.haberg@matematik.su.se (Hans Aberg)
26 Nov 2001 21:57:11 -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: remove.haberg@matematik.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 26 Nov 2001 21:57:11 -0500
Organization: Mathematics
Keywords: LR(1)
Posted-Date: 26 Nov 2001 21:57:11 EST

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


Post a followup to this message

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