3 Mar 1998 10:52:15 -0500

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) |

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.