Re: First and Follow sets

Let me give you a simple example of First and Follow. Consider the
following language:
S->1S|1A
A->0A|0
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
expression:
1+0+


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

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