First And Follow

Can a first and follow set be derived from a tree?

As many texts as I've read on the subject I've been unable to create
first and follow sets. I unfortunately don't understand the math
(though I got an A in discrete mathematics) or maybe I just cant
understand all the symbols or think abstractly enough. In either case
I've met with repeated failure attempting to obtain a first and follow
from a grammar. I had an idea the other day which I thought may
work. I wondered is it possible to derive the first and follow sets
of a grammar by building a tree (or graphs) of the grammar. I was
thinking that maybe if I did a first depth search through a tree that
I could pull this off. After further contemplation I wasn't sure if I
could identify the follow set or possible recursions (I think they are
referred to as cycles?).

I realize I could enter grammar into some programs and they would
output what I desired but I'm still intent on being able to do this,
even if it isn't by a conventional or efficient method, so long as I
can understand it.


Thank you for any guidance you can provide,

W.

On 06/23/08 14:39, Mr.E wrote:
> Can a first and follow set be derived from a tree?

See:

http://www.boostpro.com/vault/index....42f5bcef8e00ee

which is based on:

http://www.boostpro.com/vault/index....42f5bcef8e00ee

"Mr.E" <mr.waverlye@verizon.net> writes:

>...
> As many texts as I've read on the subject I've been unable to create
> first and follow sets. I unfortunately don't understand the math
> (though I got an A in discrete mathematics) or maybe I just cant
> understand all the symbols or think abstractly enough.

I'd suggest that these limitations can be overcome. Though you
haven't yet understood the math, with some coaching, I bet you could.
(I've helped plenty of students through it who hadn't earned As in
discrete math.)

Whether you take that approach or whether you take the approach you
suggest, of looking for a graph formulation, you will make your own
life easier if you first limit yourself to grammars where no
productions have empty right-hand sides (conventionally written using
the Greek letter epsilon). Once you have mastered that limited case,
then you can go back to considering the more general case.

> ... I wondered is it possible to derive the first and follow sets
> of a grammar by building a tree (or graphs) of the grammar. ...

Finding the FIRST sets is a straightforward graph problem in the case
with no empty right-hand sides. Build a directed graph with one vertex
for each terminal or nonterminal symbol. For each production in the
grammar, the graph should have a directed edge from the nonterminal
symbol that is the production's left-hand side to the leftmost of the
symbols appearing on the production's right-hand side. (This might be
either a terminal symbol or a nonterminal symbol.) To find the FIRST
set of a symbol, you just find the set of terminals that you can reach
in the directed graph starting from the given symbol.

"Mr.E" <mr.waverlye@verizon.net> writes:

> ... I wondered is it possible to derive the first and follow sets
> of a grammar by building a tree (or graphs) of the grammar. ...

I realized belatedly that my first response addressed this question
only for FIRST sets, not for FOLLOW sets. Perhaps that was because
the directed graph construcion is more complicated for FOLLOW sets.
Nonetheless, here it is, once again using the simplifying assmption of
no empty right-hand sides (epsilon productions):

(1) Make a directed graph with one vertex for each nonterminal or
terminal symbol, as well as one for the special end-of-input marker,
which is conventionally written as $.

(2) Add a directed edge from the grammar's start symbol to $.

(3) For each production in the grammar, consider in turn each of the
symbols on the right-hand side with the exception of the rightmost
one. If the symbol is a terminal, nothing needs doing. But if it is
a nonterminal (let's say A), then look at the symbol that is
immediately after it in the production's right-hand side; let's call
that symbol x. Note that x could be either a terminal or a
nonterminal symbol. Consider in turn each element of FIRST(x); each
of these will be a terminal symbol, let's say b. For each one, add a
directed edge from A to b.

(4) Consider in turn each production in the grammar that has a
nonterminal symbol as the rightmost symbol of its right-hand side.
Call that rightmost symbol A and the production's left-hand side B.
In each of these cases, add a directed edge from A to B.

Having built the directed graph in this way, then the FOLLOW set of
any nonterminal symbol consists of those terminal or end-of-input
symbols that are reachable from it.

> Can a first and follow set be derived from a tree?

That question was answered a long time ago in this group, here is the
discussion:

http://compilers.iecc.com/comparch/article/01-04-088

Paul B Mann
http://lrgen.com

Unfortunately, I have some mental roadblock that's prohibiting me from
being able to do this. I played with trying to make a tool that would
list the first and follow sets no matter how inefficient it did it. I
had a few ideas that I batted around. I'll have to try again another
time. I'm getting ready to start another semester and will have to
put my pet projects down again.

One day the light bulb will come on... sigh.

Mr. Evans - Thank you for the code. I will do my best to study it.
Mr.Hailperin - Thank you for direction on how to create the first and
follow sets.
Mr. Mann - Thank you for directions to previous text on this subject.


Thank you all for your replies.


W.