7 Mar 1998 22:22:07 -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) |

From: | Joachim Durchholz <joachim.durchholz@munich.netsurf.de> |

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

Date: | 7 Mar 1998 22:22:07 -0500 |

Organization: | Compilers Central |

Distribution: | inet |

References: | 98-03-015 |

Keywords: | theory |

Vladimir Alexiev wrote:

*>*

*> Does anyone know of an algorithm to find a "compact representation" of*

*> a series-parallel graph?*

You could use the algorithm that converts nondeterministic finite

automata to deterministic ones. That algorithm is in Aho/Ullman,

Principles of Compiler Design (the famous "Dragon book"). Basically,

the algorithm traces all states of the nondeterministic automaton and

constructs the deterministic one (the deterministic one may become

larger by a factor of 2**n in the worst case, but usually it doesn't

do that). I'm not aware of an algorithm that converts the resulting

DFA into an [E]BNF grammar, but the book may contain a reference to

one.

Regards,

Joachim

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.