Re: FOLLOW amd FIRST functions in LL Top-down Parsing (Kamal R. Prasad)
4 Sep 2003 22:46:32 -0400

          From comp.compilers

Related articles
FOLLOW amd FIRST functions in LLTop-down Parsing (2003-08-23)
Re: FOLLOW amd FIRST functions in LL Top-down Parsing (2003-09-04)
| List of all articles for this month |

From: (Kamal R. Prasad)
Newsgroups: comp.compilers
Date: 4 Sep 2003 22:46:32 -0400
References: 03-08-070
Keywords: parse, LL(1)
Posted-Date: 04 Sep 2003 22:46:32 EDT (Samuel Thomas) wrote
> I am trying to understand the various top down parsing schemes. The LL
> parsing method creates the parsing table for a grammar using 2
> functions - FOLLOW and FIRST. I only have a superficial understand of
> the subject and would be very grateful if somebody could help me.
> 1. Why do we need the FOLLOW function? If I fully left factorize and
> remove left recursion wouldn't the FIRST fucntion help me decide which
> production to use? What does the FOLLOW function try to get?

It tries to get the symbols that would trail (or follow) the
derivation being reduced. left factoring eliminates ambiguity between
2 rules for an LL(1) parser generator, but we still need the follow

> 2. One of the rules of FOLLOW says, "If there is a production
> A-->alpha B beta where beta = episilon or episilon member of
> FIRST(beta), then everything on FOLLOW(A) is in FOLLOW(B)". Can some
> one tell me why this is needed or why this works etc? I am totally
> confused of what this does.

The way it works is that, if beta -> epsilon is possible, then it is
possible that A could be reduced without consuming any terminals while
reducing beta, ie the symbols following reduction of A could
definately be encountered after reduction of B.


Post a followup to this message

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