Topological sorting

I kinda solved my "compacting" series-parallel graphs". First, note
that we start from a fully expanded representation (yacc input is very
simple: a sum/alternative of products/concatenations). Thus we don't
need a full-generality algorithm. My algorithm basically squeezes the
"strands" (sequences) of the alternative starting from the ends, and
going as far towards the center as possible. When it has to stop
because not all strands have the same bead (atom) at the end, it picks
up the matching strands and applies itself recursively to them. If
anyone is interested, I can post the perl function that does this.


The algorithm is incomplete because it won't factor ax|ay|bx|by into
(a|b)(x|y). But I hope nobody will write such a thing in a grammar. If
people write the more sensible
    S : AB XY ;
    AB: a | b ;
    XY: x | y ;
and then instruct my convertor to inline AB and XY, it will come out ok.


Now, can someone help me with another problem: is there a fast
"stable" topological sorting algorithm? I found lots of references on
generating and counting all total extensions of a poset, but no
descriptions of an algorithm that finds a linear extension "closest"
to a given initial total order. Currently I first take the transitive
closure of the partial order (so that I can tell quickly if A<B), then
do bubble-sort, comparing every element to every other.


Some comments on posts people have made:


chris dircks <chrisd@sfu.ca>:
> This is equivalent to minimizing the number of states in a dfa, or
> deterministic finite accepter.


I see that it can be seen as a *N*FA, because two alternatives may
start with the same atom. But why is it the same as minimization?
Could you please elaborate?


spin@vuse.vanderbilt.edu (Jeremy Spinrad):
> You happen to have an excellent resource for questions on graph classes
> right in your department; you can contact Professor Lorna Stewart to
> answer such questions.


I thought about that but decided that it's not only a graph problem
(as will be seen below), and that Lorna perhaps has enough things on
her head already.


> use a known trick for storing adjacency matrices without
> initializing them


What does this mean?


> Valdes, Tarjan, Lawler; The Recognition of Series Parallel Digraphs,
> SIAM J Computing 11, 1982, 298-313. One section is devoted to your
> problem, which he calls recognition of ESP (edges series-parallel)
> graphs.


I'll take a look at this. In fact I found some techreports using the
CSTR server, but they all talked about recognition (not
factorization), so that put me off.


Aaron Leon Kaplan <lkaplan@complang.tuwien.ac.at>
> If you are doing that program I think you might be interested in a
> simmilar program "YaccViso" which also displays yacc files
> http://mars.tuwien.ac.at/~jjl


This program produces the dependency graph of the grammar using
dot/vcg. That graph doesn't contain all the info about the grammar. I
may be mistaken though, because it uses record-shape nodes; I haven't
yet looked at the sample output. [The program segfaults for me on
sunos 4.1.4]


I think I'll add a dot backend to my script too. If all the info from
the grammar is to be present, then factorization and loopization are
in order.


Carl Sturtivant <carl@bitstream.net>
> It seems to me that this is equivalent to the problem of minimizing the
> size of an algebraic expression with addition and non-commutative
> multiplication... the literature on algorithms for algebra systems
> may provide a rich source of possibilities. Mathematica, Maple,
> Macsyma, etc.


I realized this and I even spent a couple of hours digging through
Maple, trying to find some reusable libraries or algorithm
descriptions. Then I figured that it will take me more time to dig it
out (having no experience with symbolic math systems) than to reinvent
it.
[For topological sort, there's a straightforward O(N) algorithm in
Knuth Vol 1. -John]




--

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