Fri, 16 Apr 1993 16:16:37 GMT

Related articles |
---|

FIRST() algorithm goer@midway.uchicago.edu (1993-04-16) |

Re: FIRST() algorithm mauney@csljon.csl.ncsu.edu (1993-04-18) |

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.