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

Joachim Durchholz <joachim.durchholz@munich.netsurf.de>
7 Mar 1998 22:22:07 -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)
| List of all articles for this month |
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.