Computing first sets on a left-recursive grammar

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

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