21 May 2000 22:26:57 -0400

Related articles |
---|

First and Follow sets csuhu@csv.warwick.ac.uk (Jan Schulze) (2000-05-20) |

Re: First and Follow sets rsherry@home.com (Robert Sherry) (2000-05-21) |

Re: First and Follow sets johnston.p@worldnet.att.net (Paul Johnston) (2000-05-21) |

Re: First and Follow sets hybrid@dol.ru (Hybrid) (2000-05-21) |

Re: First and Follow sets tmoog@polhode.com (Tom Moog) (2000-05-22) |

Re: First and Follow sets pfaffben@msu.edu (Ben Pfaff) (2000-05-24) |

Re: First and Follow sets p.terry@ru.ac.za (Pat Terry) (2000-05-28) |

From: | Robert Sherry <rsherry@home.com> |

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:

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*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.