Re: First and Follow sets

Robert Sherry <>
21 May 2000 22:26:57 -0400

          From comp.compilers

Related articles
First and Follow sets (Jan Schulze) (2000-05-20)
Re: First and Follow sets (Robert Sherry) (2000-05-21)
Re: First and Follow sets (Paul Johnston) (2000-05-21)
Re: First and Follow sets (Hybrid) (2000-05-21)
Re: First and Follow sets (Tom Moog) (2000-05-22)
Re: First and Follow sets (Ben Pfaff) (2000-05-24)
Re: First and Follow sets (Pat Terry) (2000-05-28)
| List of all articles for this month |

From: Robert Sherry <>
Newsgroups: comp.compilers
Date: 21 May 2000 22:26:57 -0400
Organization: @Home Network
References: 00-05-074
Keywords: parse, LALR

Let me give you a simple example of First and Follow. Consider the
following language:
In the above example the start symbol is S and the alphabet is {0,1}.
The above language consists of all strings of 0 and 1 such that:
1) There is a least one 1.
2) There is a lest one 0.
3) All the 1 appear before any of the 0.
The above language can be represented by the following regular

Intuitively First(S) represents the set of terminals ( alphabet
symbols ) that can start a valid string in the language. It should be
obviously for the above language that First(S) = { 1 }. I will now
derive first(s) using the rules on page 189 of "Compilers -
Principles, Techniques, and Tools" (by Aho, Sethi and Ullman).

S is not a terminal hence we skip rule 1.
S->e (epsilon) is not a valid rule hence we skip rule 2
Now we have rule 3.
Since 1 is a terminal and all grammar symbols before 1 in the production
S->1S go to epsilon ( This statement is true because there are not
grammar symbols before 1 on the right hand side of the production ) we
add 1 to the First(S). By the same argument for the rule S->1A we can
add 1 to the First(S). However adding 1 does not matter because it
already had been added.

Now lets consider Follow. Lets image I have a sentential form XYZ
where X,Y and Z are grammar symbols. By a grammar symbol I mean either
a terminal or a non-terminal. In addition lets assume that Y is a
non-terminal. Follow is the set of terminals that can appear just
after Y in some sentential form. In our case, FOLLOW(S) is { $, 0 }. I
will now derive this using the rules in the book "Compilers -
Principles, Techniques, and Tools" (by Aho, Sethi and Ullman).

Since S is the start symbol we include $ in Follow(S). We have a
production in the form S->1S so by rule 2 we include everything in the
First(S) which is { 1 }.
We can not apply rule 3 for the production S->1S because First(1) does
not include epsilon.

I hope this simple example helps. I am not sure what part of
the book's example you did not understand. I think the words used to
describe their First and Follow example are left incomplete to save
space. Perhaps you would like to make you question more specific. If
so, feel free to write back to me.

I would like to recommend the book, "The Design and Construction of
Compilers" by Hunter. The book is only about 200 pages and it leaves out
a lot
of material but I think what it covers, it covers well.

Robert Sherry

Jan Schulze wrote:
> construction of First and Follow sets to me, for example for the following
> grammar:
> E ::= TE'
> E' ::= +TE' | e
> T ::= FT'
> T' ::= *FT' | e
> F ::= (E) | id
> where E, E', T, T', F are nonterminals
> (, ), *, +, id are terminals
> and 'e' is the empty (epsilon) transition

Post a followup to this message

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