FIRST() algorithm

goer@midway.uchicago.edu (Richard L. Goerwitz)
Fri, 16 Apr 1993 16:16:37 GMT

          From comp.compilers

Related articles
FIRST() algorithm goer@midway.uchicago.edu (1993-04-16)
Re: FIRST() algorithm mauney@csljon.csl.ncsu.edu (1993-04-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: goer@midway.uchicago.edu (Richard L. Goerwitz)
Keywords: LR(1), question
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 goer%midway@uchicago.bitnet
      goer@midway.uchicago.edu rutgers!oddjob!ellis!goer
--


Post a followup to this message

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