Re: Meaning of symbol in set theory?

> 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

Return to the comp.compilers page.
Search the comp.compilers archives again.