29 Nov 2001 23:09:46 -0500

Related articles |
---|

Computing "first" in LR(1) parsing remove.haberg@matematik.su.se (2001-11-26) |

Re: Computing "first" in LR(1) parsing kan@cs.tu-berlin.de (SÃ¶nke Kannapinn) (2001-11-29) |

Re: Computing "first" in LR(1) parsing chrisd@reservoir.com (2001-11-29) |

Re: Computing "first" in LR(1) parsing max@gustavus.edu (2001-11-29) |

Re: Computing "first" in LR(1) parsing kgw-news@stiscan.com (2001-11-29) |

Re: Computing "first" in LR(1) parsing remove.haberg@matematik.su.se (2001-12-03) |

From: | max@gustavus.edu (Max Hailperin) |

Newsgroups: | comp.compilers |

Date: | 29 Nov 2001 23:09:46 -0500 |

Organization: | http://groups.google.com/ |

References: | 01-11-123 |

Keywords: | LR(1), parse |

Posted-Date: | 29 Nov 2001 23:09:46 EST |

remove.haberg@matematik.su.se (Hans Aberg) wrote in message news:01-11-123...

*> I want to compute the function "first" of LR(1) parsing: If x is a*

*> string of grammar symbols, first(x) is the set of terminals that begin*

*> the strings derivable from x with respect to the given grammar, plus*

*> the empty string, if derivable as well. In Aho et al, "Compilers", sec*

*> 4.4, p.189, 3, it says that if x is a nonterminal and there is a*

*> production x -> y1 ... yk, then to first(x) one should add first(yi)*

*> if the empty string is part of first(y1), ..., first(y{i-1}).*

*>*

*> But it does not say what happens if this procedure recurses, that is,*

*> if say when computing first(y1), one recurses back via some other*

*> relations to first(x). If that happens, is that not a LR(1) grammar,*

*> or how should this situation be handled?*

What Aho, Sethi, and Ullman do not clearly explain is that this is an

iterative algorithm, convering on a least fixed point by working up

from below. So at each point in the iteration, you have some lower

bound on the eventual FIRST sets. Based on the current (iteration n)

lower bounds on the FIRST(yi), you calculate a new (iteration n+1)

lower bound on FIRST(x), in the manner you summarize above.

For an alternative presentation of this, you might see a pedagogical

paper I wrote on the topic, which is at

http://www.gustavus.edu/~max/ffp-sigcse.html

-Max Hailperin

Associate Professor of Computer Science

Gustavus Adolphus College

800 W. College Ave.

St. Peter, MN 56082

USA

http://www.gustavus.edu/~max/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.