# Computing first sets on a left-recursive grammar

## "Cyrus Najmabadi" <cyrus@stwing.upenn.edu>10 Apr 2001 01:45:12 -0400

From comp.compilers

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)
| List of all articles for this month |

 From: "Cyrus Najmabadi" 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
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