|alg for "compacting" series-parallel graphs (yacc->BNF)? email@example.com (Vladimir Alexiev) (1998-03-03)|
|Re: alg for "compacting" series-parallel graphs (yacc->BNF)? firstname.lastname@example.org (Carl Sturtivant) (1998-03-06)|
|Re: alg for "compacting" series-parallel graphs (yacc->BNF)? email@example.com (Joachim Durchholz) (1998-03-07)|
|Topological sorting firstname.lastname@example.org (Vladimir Alexiev) (1998-03-07)|
|From:||Vladimir Alexiev <email@example.com>|
|Date:||3 Mar 1998 10:52:15 -0500|
|Organization:||University of Alberta, Computing Science|
Does anyone know of an algorithm to find a "compact representation" of
a series-parallel graph? Eg
-- a -- b -- c -- should -- b --
/ \ become / \
----- a ------- c ----- -- a ----------- c --
The set of all paths from source to target should remain the same,
while the number of nodes should be minimized.
I want to use this for a convertor from yacc to BNF. Yacc only allows
top-level alternatives while BNF also allows grouping
x : a b c x : a (b | ) c
| a c
Also, how can I use the looping constructs of EBNF? I think I know how
to do it for the most-often used cases
xs : x and xs :
| xs ',' x | xs ',' x
but what would be a general algorithm?
All this is for a yacc-grammar prettyprinter, which will take a
y.output file and produce a railroad diagram using rail.sty or
syntax.sty (available on CPAN).
Please CC me if you reply; I will summarize the replies.
Return to the
Search the comp.compilers archives again.