Re: First And Follow

Max Hailperin <max@gustavus.edu>
Tue, 24 Jun 2008 15:35:16 -0500

          From comp.compilers

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)
| List of all articles for this month |

From: Max Hailperin <max@gustavus.edu>
Newsgroups: comp.compilers
Date: Tue, 24 Jun 2008 15:35:16 -0500
Organization: Compilers Central
References: 08-06-052
Keywords: parse
Posted-Date: 24 Jun 2008 21:27:00 EDT

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


Post a followup to this message

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