Re: Computing Follow set

pavan <pavan.mail@[EMAIL PROTECTED]
> 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