|Computing first sets on a left-recursive grammar email@example.com (Cyrus Najmabadi) (2001-04-10)|
|Re: Computing first sets on a left-recursive grammar firstname.lastname@example.org (Paul Mann) (2001-04-12)|
|Re: Computing first sets on a left-recursive grammar email@example.com (Sönke Kannapinn) (2001-04-12)|
|Re: Computing first sets on a left-recursive grammar firstname.lastname@example.org (Max Hailperin) (2001-04-14)|
|Re: Computing first sets on a left-recursive grammar email@example.com (2001-04-14)|
|From:||"Cyrus Najmabadi" <firstname.lastname@example.org>|
|Date:||10 Apr 2001 01:45:12 -0400|
|Organization:||University of Pennsylvania|
|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
Return to the
Search the comp.compilers archives again.