7 Mar 1998 22:31:58 -0500

Related articles |
---|

alg for "compacting" series-parallel graphs (yacc->BNF)? vladimir@cs.ualberta.ca (Vladimir Alexiev) (1998-03-03) |

Topological sorting vladimir@cs.ualberta.ca (Vladimir Alexiev) (1998-03-07) |

From: | Vladimir Alexiev <vladimir@cs.ualberta.ca> |

Newsgroups: | comp.theory,sci.math,comp.compilers |

Date: | 7 Mar 1998 22:31:58 -0500 |

Organization: | University of Alberta, Computing Science |

Distribution: | inet |

References: | 98-03-015 |

Keywords: | theory |

In-reply-to: | Vladimir Alexiev's message of 3 Mar 1998 10:52:15 -0500 |

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]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.