3 Dec 2001 20:21:53 -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: | remove.haberg@matematik.su.se (Hans Aberg) |

Newsgroups: | comp.compilers |

Date: | 3 Dec 2001 20:21:53 -0500 |

Organization: | Mathematics |

References: | 01-11-123 01-11-129 |

Keywords: | LR(1), summary |

Posted-Date: | 03 Dec 2001 20:21:52 EST |

Thank for all replies and private communications with Chris Dodd

<chrisd@reservoir.com>. Here is a summary response:

In article 01-11-129, "Sönke Kannapinn"

<kan@cs.tu-berlin.de> wrote:

*>The algorithm described in the old Aho et*

*>al. "Compilers..." book produces correct results but is inelegant and*

*>"slow". (Similar remarks hold for "follow".)*

Whenever it converges:

In article 01-11-142, max@gustavus.edu (Max Hailperin) wrote:

*>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.*

This was what confused me: Strictly speaking, the description in Aho,

Sethi, and Ullman is mathematically incorrect for use with LR(1), as it

may not converge. (An LL(1) grammar cannot contain left recursion, so the

algorithm always converges for LL(1) grammars.)

In article 01-11-144, kgw-news@stiscan.com wrote:

*>Compute the empty relation first.*

*>empty(x) if x->*

*> or x->y[1],...,y[n] and empty(y[i])*

*>This can be done by iterating until there are no changes*

*>or if you have an inverted production list(used by)*

*>you can add potentially affected productions to a todo list*

*>until the todo list becomes empty.*

*>*

*>Then first and last and next are easy and local.*

Actually, I was thinking of this myself, so it is good that you confirm

this is a good way to go. Your "empty(x)" function above is in reality

what one would denote $first_0(x)$. For any n >= 0, one defines

$first_n(x)$ to be the set of at most n terminals long heads of all

strings derivable from x with respect to the given grammar (including the

empty string, if derivable). Then $first = first_1$.

I have a book by Walte, Goos, "Compiler Construction", which I like

because it uses a more mathematical language, describing some of this.

(But most would think it is overly formal and unreadable. It is a good

complement to more informal descriptions.)

Also, Axel Kittenberger <axel@dtone.org> pointed out a nice book available

online at:

http://www.cs.vu.nl/~dick/PTAPG.html

with some details.

Hans Aberg * Anti-spam: remove "remove." from email address.

* Email: Hans Aberg <remove.haberg@member.ams.org>

* Home Page: <http://www.matematik.su.se/~haberg/>

* AMS member listing: <http://www.ams.org/cml/>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.