10 Apr 2001 01:45:12 -0400

Related articles |
---|

Computing first sets on a left-recursive grammar cyrus@stwing.upenn.edu (Cyrus Najmabadi) (2001-04-10) |

Re: Computing first sets on a left-recursive grammar paul@parsetec.com (Paul Mann) (2001-04-12) |

Re: Computing first sets on a left-recursive grammar soenke.kannapinn@wincor-nixdorf.com (Sönke Kannapinn) (2001-04-12) |

Re: Computing first sets on a left-recursive grammar max@max.mcs.gac.edu (Max Hailperin) (2001-04-14) |

Re: Computing first sets on a left-recursive grammar parag@pinhead.parag.codegen.com (2001-04-14) |

From: | "Cyrus Najmabadi" <cyrus@stwing.upenn.edu> |

Newsgroups: | comp.compilers |

Date: | 10 Apr 2001 01:45:12 -0400 |

Organization: | University of Pennsylvania |

Keywords: | LALR, question |

Posted-Date: | 10 Apr 2001 01:45:12 EDT |

Sorry if this question has come up before, but I couldn't get a

satisfactory answer from checking old posts.

I'm trying to understand (while simultaneously code) the algorithm for

computing first and follow sets in the Dragon book (p177).

Unfortunately, I'm being pretty unsuccessful at implementing this

obfuscated explanation. The fault seems to lie in left-recursive

grammar productions. Because "First" calls itself on the individual

elements of the yield of the production, a left-recursive production

will cause "first" to loop forever.

Unfortunately, I find the explanation on these functions in the

Dragon book rather difficult to understand, so I'm making no headway

into determining if this a limitation of the "First" function, or if

there's some simple way to get about this problem. If it's a

limitation, is the correct solution to eliminate left-recursion? Or,

if it's not a limitation, can someone post (or link to) an algorithm

that can calculate the "first" set even on a left-recursive

production.

Thanks!

-- Cyrus

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.