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

Joachim Durchholz <>
7 Mar 1998 22:22:07 -0500

          From comp.compilers

Related articles
alg for "compacting" series-parallel graphs (yacc->BNF)? (Vladimir Alexiev) (1998-03-03)
Re: alg for "compacting" series-parallel graphs (yacc->BNF)? (Carl Sturtivant) (1998-03-06)
Re: alg for "compacting" series-parallel graphs (yacc->BNF)? (Joachim Durchholz) (1998-03-07)
| List of all articles for this month |

From: Joachim Durchholz <>
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


Post a followup to this message

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