alg for "compacting" series-parallel graphs (yacc->BNF)?

Vladimir Alexiev <vladimir@cs.ualberta.ca>
3 Mar 1998 10:52:15 -0500

          From comp.compilers

Related articles
alg for "compacting" series-parallel graphs (yacc->BNF)? vladimir@cs.ualberta.ca (Vladimir Alexiev) (1998-03-03)
Re: alg for "compacting" series-parallel graphs (yacc->BNF)? carl@bitstream.net (Carl Sturtivant) (1998-03-06)
Re: alg for "compacting" series-parallel graphs (yacc->BNF)? joachim.durchholz@munich.netsurf.de (Joachim Durchholz) (1998-03-07)
Topological sorting vladimir@cs.ualberta.ca (Vladimir Alexiev) (1998-03-07)
| List of all articles for this month |

From: Vladimir Alexiev <vladimir@cs.ualberta.ca>
Newsgroups: comp.theory,sci.math,comp.compilers
Date: 3 Mar 1998 10:52:15 -0500
Organization: University of Alberta, Computing Science
Distribution: inet
Keywords: theory, question

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.
TIA, Vlad




--


Post a followup to this message

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