4 Sep 2003 22:46:32 -0400

Related articles |
---|

FOLLOW amd FIRST functions in LLTop-down Parsing samuel@avenir.net (2003-08-23) |

Re: FOLLOW amd FIRST functions in LL Top-down Parsing kamalp@acm.org (2003-09-04) |

From: | kamalp@acm.org (Kamal R. Prasad) |

Newsgroups: | comp.compilers |

Date: | 4 Sep 2003 22:46:32 -0400 |

Organization: | http://groups.google.com/ |

References: | 03-08-070 |

Keywords: | parse, LL(1) |

Posted-Date: | 04 Sep 2003 22:46:32 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.