31 May 2002 23:09:25 -0400

Related articles |
---|

Boolean expressions represented as directed graph steve@istech.demon.co.uk (Steve Jones) (2002-05-27) |

Re: Boolean expressions represented as directed graph vbdis@aol.com (VBDis) (2002-05-31) |

Re: Boolean expressions represented as directed graph heinrich@idirect.com (Kenn Heinrich) (2002-05-31) |

From: | "Kenn Heinrich" <heinrich@idirect.com> |

Newsgroups: | comp.compilers |

Date: | 31 May 2002 23:09:25 -0400 |

Organization: | Posted via Supernews, http://www.supernews.com |

References: | 02-05-149 |

Keywords: | parse |

Posted-Date: | 31 May 2002 23:09:25 EDT |

Steve Jones wrote:

*>*

*> A simple example:*

*>*

*> A -+-> B -> C -+-> J*

*> +-> X -> Y -+*

*>*

*> would equate to:*

*>*

*> J = A and ( ( B and C) or ( X and Y ) )*

*>*

Steve,

It depends on what you want your output to look like. Assuming this

is for automated C-code generation, or something similar, then you can

traverse your graph and label the nodes with boolean expressions,

using something like a BDD (Boolean Decision Diagram) -- there are

lots of good packages like Buddy available for doing this.

Doing a depth-first search of predecessors (a DFS on the dual graph)

from the terminal (assignment) nodes, and propogating the expression

by forming the disjunct of the values at all incoming nodes, then

conjuncting with the current node's value, would yield a BDD at the

terminal node which you could expand by walking the BDD tree and

rewriting it with C-style selection operators (x ? y : z).

Keep in mind that not all graphs would generate the simple Boolean

expressions you might be expecting -- if there are loops or

overlapping paths, some of the terms generated would be redundant

unless minimization exists. You might want to check that there are no

loops in the graph first (with Tarjan's algorithm for finding strongly

connected components).

Consider the difficulty with this graph:

+-- b <--

v |

x --> a --+--> Y

with a loop through B around "a". The expression denoted by this is

simply "Y := a". To resolve loops you would likely need to find a

fixpoint of the loop, which requires checking equivalence of the

underlying expressions (simple using BDD's, very hard using strings!).

Also, if the semantics of this visual designer are such that the

labels on the graph can be arbitrary program code, you want to watch

out for side-effects. Applying short-circuit evaluation to children of

a graph node is not deterministic unless you create a well-defined

ordering of children. For example, what is the effect of code

generated by this?

a +-> (if *c++ != 0) --+-> J

+-> (if *b++ != 0) --+

Hope this helps,

- Kenn

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.