Re: Are there any good examples of FIRST () and FOLLOW ()?

cosc143u@rosie.uh.edu (91F9774) writes:
|> We are going over predictive parsers right now (we won't actually be using
|> them for our project but have to know how to build them for the test). My
|> book has two examples total on these subjects and I just can't seem to
|> understand the FOLLOW () function. Does anyone out there have a good
|> explanation of the FOLLOW () function and how it is used in building the
|> predictive parse table?
|>
|> Example:
|> S->AB | epsilon
|> A->aA
|> | a
|> B->BS
|> | b
|>
|> To remove left recursion I need to change B->BS to
|> B->bB'
|> B'->BS | eps.
|>
|> FIRST (S) = {$} U FIRST (A) = {a}
|> FIRST (B) = {b}
|>
|> FOLLOW (S) = {$,b}?
|> FOLLOW (A) = FIRST (B) = {b}?
|>
|> PP table
|> a b $
|> S S->AB S-> eps.
|> A A->a
|> A->aA
|> B B->bB'
|> B' B'->BS
|>
|> I'm pretty sure I have problems with this table but I can't see where.
|> Any comments are appreciated. The questions on the FOLLOW's indicate that
|> I'm not sure if that is the correct follow. In our book, "COMPILERS:
|> Principles, Techniques, and Tools", the "$" is in the FOLLOW of S by
|> definition. Apparently in some texts there would be an extra transition,
|> "S'->S | epsilon" that explains this...


You need to do a bit more. You need a distinguished start symbol, a
left-factored grammar and a non-left-recursive grammar. Even then, you can
get into trouble. Your grammar is pretty hard to handle by ANY parsing
method. Yacc (bison, really) throws up its hands in horror no matter how
you transform the grammar. So, naturally enough, does an LL1 parser
generator. It seems to me to be inherently ambiguous.


As for the why and how of FOLLOWS etc, here is what I usually tell my
students (condensed!):
      We need to know which production to use if we have a choice.
      The lookaheads for L -> R include FIRST(R), i.e. anything that
      can begin R. If R is nullable (i.e. R ->* epsilon) then the
      lookaheads also include FOLLOW(L).
      To calculate FOLLOW(X), find all the places where X is on the
      RHS of a production, i.e. L -> A X Y.
      If X is followed by Y, then FIRST(Y) is in FOLLOW(X). If Y ->* epsilon,
      then FOLLOW(L) is in FOLLOW(X).
      To calculate FIRST(L), if L -> A B then FIRST(A B) is in FIRST(L).
      FIRST(A) is in FIRST(A B). If A ->* epsilon, then FIRST(B) is also
      in FIRST(A B).


FYI, here is the output listing from my LL1 parser generator on the
transformed grammar:


%% -> # -- the grammar meta-symbol and end-of-production symbol
%%
a b $ -- terminal symbols
%%
%%
%% -- now the productions
S' -> S $ #
-- S' is the distinguished starting symbol
-- the prediction stack starts out with its unique RHS
S -> A B #
S -> #
-- note how the A has been left-factored here
A -> a A' #
A' -> A #
A' -> #
B -> b B' #
B' -> S B' #
B' -> #
%%
Generator Listing:


0 syntax errors found.
*** Warning: S is ambiguous on a - earlier production will be used
*** Warning: B' is ambiguous on a - earlier production will be used
*** Warning: B' is ambiguous on $ - earlier production will be used
3 ambiguous rule(s), 0 unreachable rules.
Recovery Information
~~~~~~~~ ~~~~~~~~~~~
a A' B
b B'


Production Look-Aheads
~~~~~~~~~~ ~~~~~~~~~~~
S' (not nullable)
      First Set: a $
      Follow Set:


S' -> S $ #
      Director Set: a $


      --------------------------------------------
S (nullable)
      First Set: a
      Follow Set: a $


S -> A B #
      Director Set: a
S -> #
      Director Set: a $


      --------------------------------------------
A (not nullable)
      First Set: a
      Follow Set: b


A -> a A' #
      Director Set: a


      --------------------------------------------
B (not nullable)
      First Set: b
      Follow Set: a $


B -> b B' #
      Director Set: b


      --------------------------------------------
A' (nullable)
      First Set: a
      Follow Set: b


A' -> A #
      Director Set: a
A' -> #
      Director Set: b


      --------------------------------------------
B' (nullable)
      First Set: a
      Follow Set: a $


B' -> S B' #
      Director Set: a $
B' -> #
      Director Set: a $


      --------------------------------------------




--
# Andrew Dunstan
# Department of Computer Science
# University of Adelaide
# South Australia
# net: andrewd@cs.adelaide.edu.au
--

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