Re: Computing FIRST and FOLLOW in a grammar

torbenm@diku.dk (Torben AEgidius Mogensen)17 Oct 1997 22:48:02 -0400

From comp.compilers

Related articles
Computing FIRST and FOLLOW in a grammar msm@spaceworks.com (Michael Mstowski) (1997-10-16)
Re: Computing FIRST and FOLLOW in a grammar torbenm@diku.dk (1997-10-17)
| List of all articles for this month |

 From: torbenm@diku.dk (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 <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)
--

Post a followup to this message