Re: Computing FIRST and FOLLOW in a grammar

Michael Mstowski <msm@spaceworks.com> 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
        arrow.


  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
names.


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
        end
    end.


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


Torben Mogensen (torbenm@diku.dk)
--

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