|Computing Follow set email@example.com (pavan) (2008-03-06)|
|Re: Computing Follow set firstname.lastname@example.org (Russ Cox) (2008-03-06)|
|Re: Computing Follow set email@example.com (2008-03-07)|
|Re: Computing Follow set firstname.lastname@example.org (Max Hailperin) (2008-03-07)|
|Re: Computing Follow set email@example.com (Hans Aberg) (2008-03-08)|
|From:||firstname.lastname@example.org (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)|
|Date:||Fri, 07 Mar 2008 09:38:37 +0100|
|Organization:||Department of Computer Science, University of Copenhagen|
|Posted-Date:||08 Mar 2008 10:56:45 EST|
pavan <email@example.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.
Return to the
Search the comp.compilers archives again.