Re: FOLLOW amd FIRST functions in LL Top-down Parsing

samuel@avenir.net (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
set.


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


regards
-kamal

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