Re: Meaning of symbol in set theory?

"Sönke Kannapinn" <>
8 Dec 2000 22:23:37 -0500

          From comp.compilers

Related articles
Meaning of symbol in set theory? (2000-12-06)
Re: Meaning of symbol in set theory? (Carl Offner) (2000-12-07)
Re: Meaning of symbol in set theory? (Sönke Kannapinn) (2000-12-08)
Re: Meaning of symbol in set theory? (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: (at relayer

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