Re: Computing Follow set

torbenm@app-2.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Fri, 07 Mar 2008 09:38:37 +0100

          From comp.compilers
Related articles
Computing Follow set pavan.mail@gmail.com (pavan) (2008-03-06)
Re: Computing Follow set rsc@swtch.com (Russ Cox) (2008-03-06)
Re: Computing Follow set torbenm@app-2.diku.dk (2008-03-07)
Re: Computing Follow set max@gustavus.edu (Max Hailperin) (2008-03-07)
Re: Computing Follow set haberg_20080207@math.su.se (Hans Aberg) (2008-03-08)
| List of all articles for this month |
From: torbenm@app-2.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Newsgroups: comp.compilers
Date: Fri, 07 Mar 2008 09:38:37 +0100
Organization: Department of Computer Science, University of Copenhagen
References: 08-03-033
Keywords: LR(1)
Posted-Date: 08 Mar 2008 10:56:45 EST

pavan <pavan.mail@gmail.com> writes:


> I have a question regarding the computation of FOLLOW sets.
> Consider the following grammar:
>
> A -> aB | a
> B -> bA | b
>
> From the production A -> aB, we have FOLLOW(B) contains FOLLOW(A).
> From the production B -> bA, we have FOLLOW(A) contains FOLLOW(B).
>
> This ends up being an infinite loop when I code it. I would appreciate
> your suggestions on this.




You need to do some kind of fixed-point iteration. The simplest form
is to initialise all FOLLOW sets to empty, and then treat each
constraint of the form FOLLOW(A) contains FOLLOW(B) as an assignment
FOLLOW(A) := FOLLOW(A) U FOLLOW(B). Run through all constraints this
way repeatedly until a pass over the constraints makes no changes in
any FOLLOW set.


You can see more details in chapter 3 of Basics of Compiler Design,
which you can download from http://www.diku.dk/~torbenm/Basics


You can make convergence faster by using a worklist algorithm.


Torben


Post a followup to this message

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