Re: Computing FIRST and FOLLOW in a grammar (Torben AEgidius Mogensen)
17 Oct 1997 22:48:02 -0400

          From comp.compilers

Related articles
Computing FIRST and FOLLOW in a grammar (Michael Mstowski) (1997-10-16)
Re: Computing FIRST and FOLLOW in a grammar (1997-10-17)
| List of all articles for this month |

From: (Torben AEgidius Mogensen)
Newsgroups: comp.compilers
Date: 17 Oct 1997 22:48:02 -0400
Organization: Department of Computer Science, U of Copenhagen
References: 97-10-078
Keywords: LALR

Michael Mstowski <> writes:

>I'm having a difficult time computing FOLLOW{}. Could anyone
>email me a real world "simple" example of how to compute this?
>I know how to find FIRST, and I know that you need FIRST{} to
>find FOLLOW{}, but I'm still struggling with FOLLOW{}. Any
>help is appreciated.

An easy and efficient method is to collect a set of constraints and
then solve these. The constraints are found by the following rules:

  1) Add the constraint ({$} \subseteq FOLLOW(S)), where S is the start
        symbol of the grammar.

  2) For every production A -> \alpha B \beta, add the constraint
        ((FIRST{\beta}-{\epsilon}) \subseteq FOLLOW(B)). This is done for
        every occurence of a nonterminal on the right-hand side of an

  3) For every production A -> \alpha B \beta such that \epsilon \in
        FIRST(\beta), add the constraint FOLLOW(A) \subseteq FOLLOW(B).

The notation I use is taken from "The Dragon Book", using LaTeX symbol

The constraints generated by rules 1 and 2 are easy to solve: You just
add the left-hand sets to the right-hand set. The constraints
generated by rule 3 must be handled with more care, as changing the
left-hand set may require the constraint to be handled again. A
work-set algorith handles this fine: Start by noting for each
nonterninal A the set of nonterminals B such that there is a
constraint FOLLOW(A) \subseteq FOLLOW(B). Now put all nonterminals in
a work-list and do the following

    while worklist is non-empty do begin
        take A from worklist;
        for all B in A's list of constrained nonterminals do begin
            add FOLLOW(A) to FOLLOW(B);
            if FOLLOW(B) changes as a result, add B to the worklist

At the end of this, each FOLLOW set is complete.

Torben Mogensen (

Post a followup to this message

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