|FIRST() algorithm firstname.lastname@example.org (1993-04-16)|
|Re: FIRST() algorithm email@example.com (1993-04-18)|
|From:||firstname.lastname@example.org (Richard L. Goerwitz)|
|Organization:||University of Chicago|
|Date:||Fri, 16 Apr 1993 16:16:37 GMT|
Perhaps this is not a puzzle for old hands. For me, though, it's
a real conundrum. Where is the breakdown in the following sequence?
1) LR-family parser generators associate actions with reductions
2) To calculate when a reduction must take place, one uses (among
other things) the FIRST() algorithm we all know and love
3) FIRST() does not work with left recursive rules, so we must
first convert left recursion to right recursion
4) The only left recursion -> right recursion algorithms I know
are only guaranteed to work on grammars without epsilon moves
5) To remove epsilon moves from a grammar that specifies actions
for epsilon moves will alter the action-reduction assocations in
an unacceptable way
6) hence I can't do step 1 except for grammars that don't specify
actions for epsilon moves (and, by implication, for grammars that
have left recursion, since conversion to right recursion intro-
duces new nonterminals and action->epsilon-move associations).
Where's the weak link in my reasoning?
-Richard L. Goerwitz email@example.com
Return to the
Search the comp.compilers archives again.