8 Dec 2000 22:23:37 -0500

Related articles |
---|

Meaning of symbol in set theory? mikesw@whiterose.net (2000-12-06) |

Re: Meaning of symbol in set theory? offner@zko.dec.com (Carl Offner) (2000-12-07) |

Re: Meaning of symbol in set theory? soenke.kannapinn@wincor-nixdorf.com (Sönke Kannapinn) (2000-12-08) |

Re: Meaning of symbol in set theory? eil@kingston.net (John H. Lindsay) (2000-12-08) |

From: | "Sönke Kannapinn" <soenke.kannapinn@wincor-nixdorf.com> |

Newsgroups: | comp.compilers |

Date: | 8 Dec 2000 22:23:37 -0500 |

Organization: | Siemens Inc. |

References: | 00-12-018 |

Keywords: | theory |

Posted-Date: | 08 Dec 2000 22:23:37 EST |

X-Envelope-Sender-Is: | news@news.mch.sbs.de (at relayer goliath.siemens.de) |

*> Also in the above mentioned paper [Tarjan: Depth First Search (DFS)]*

*> it talks about "Biconnectivity", "Strong Connectivity" and*

*> "Triconectivity" along with "fronds" and "cross-links". Have these*

*> concept ever been applied to Compilers and such?*

Oh yes! E.g. "Strongly Connected Components" (SCCs) and Tarjan's SCC

algorithm do have applications in compiler construction.

For example, Frank DeRemer and Tom Pennello perform their "Efficient

Computation of LALR(1) lookahead-sets" (ACM TOPLAS 24(4)) by set

computations while traversing directed graphs by a streamlined version

of Tarjans DFS algorithm.

What is described in that article from 1982 is, generally speaking,

the efficient computation of sets F(x) which are defined as the

smallest sets that, for each x out of a finite set S, satisfy the

equation

F(x) = F'(x) union { F(y) | x R y }

where the relation R is a subset of S x S and F' is a set-valued function

over S.

In other words, compute

F(x) = { F'(y) | x R* y }.

This efficient set computation algorithm is very useful in general,

i.e. not only for the computation of LALR(1) lookahead sets. For

example, it can also be applied by parser generators to compute the

sets FIRST(A) and FOLLOW(A) for the nonterminals A of a context-free

grammar. (Exercise: What is R and F' for the two scenarios?!)

Best wishes,

Soenke Kannapinn

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.