# Re: Meaning of symbol in set theory?

## "Sönke Kannapinn" <soenke.kannapinn@wincor-nixdorf.com>8 Dec 2000 22:23:37 -0500

From comp.compilers

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)
| List of all articles for this month |

 From: "Sönke Kannapinn" 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