Tue, 24 Jun 2008 08:19:38 -0500

Related articles |
---|

First And Follow mr.waverlye@verizon.net (Mr.E) (2008-06-23) |

Re: First And Follow cppljevans@suddenlink.net (Larry Evans) (2008-06-23) |

Re: First And Follow max@gustavus.edu (Max Hailperin) (2008-06-24) |

Re: First And Follow max@gustavus.edu (Max Hailperin) (2008-06-24) |

Re: First And Follow paul@paulbmann.com (Paul B Mann) (2008-06-25) |

Re: First And Follow mr.waverlye@verizon.net (Mr.E) (2008-06-27) |

From: | Max Hailperin <max@gustavus.edu> |

Newsgroups: | comp.compilers |

Date: | Tue, 24 Jun 2008 08:19:38 -0500 |

Organization: | Compilers Central |

References: | 08-06-052 |

Keywords: | parse |

Posted-Date: | 24 Jun 2008 21:26:47 EDT |

"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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.