Re: Computing Follow set (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Fri, 07 Mar 2008 09:38:37 +0100

          From comp.compilers

Related articles
Computing Follow set (pavan) (2008-03-06)
Re: Computing Follow set (Russ Cox) (2008-03-06)
Re: Computing Follow set (2008-03-07)
Re: Computing Follow set (Max Hailperin) (2008-03-07)
Re: Computing Follow set (Hans Aberg) (2008-03-08)
| List of all articles for this month |

From: (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 <> 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

You can make convergence faster by using a worklist algorithm.


Post a followup to this message

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