17 Oct 1997 22:48:02 -0400

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) |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.