Thu, 25 Jun 1992 08:05:25 GMT

Related articles |
---|

Are there any good examples of FIRST () and FOLLOW ()? cosc143u@rosie.uh.edu (1992-06-20) |

Re: Are there any good examples of FIRST () and FOLLOW ()? jos@and.nl (1992-06-22) |

Re: Are there any good examples of FIRST () and FOLLOW ()? andrewd@cs.adelaide.edu.au (1992-06-25) |

Re: Are there any good examples of FIRST () and FOLLOW ()? andrewd@cs.adelaide.edu.au (1992-06-29) |

Newsgroups: | comp.compilers |

From: | andrewd@cs.adelaide.edu.au (Andrew Dunstan) |

Organization: | Compilers Central |

Date: | Thu, 25 Jun 1992 08:05:25 GMT |

References: | 92-06-100 |

Keywords: | LL(1), question |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.