31 May 2002 23:07:19 -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: | "VBDis" <vbdis@aol.com> |

Newsgroups: | comp.compilers |

Date: | 31 May 2002 23:07:19 -0400 |

Organization: | AOL Bertelsmann Online GmbH & Co. KG http://www.germany.aol.com |

References: | 02-05-149 |

Keywords: | design |

Posted-Date: | 31 May 2002 23:07:19 EDT |

"Steve Jones" <steve@istech.demon.co.uk> schreibt:

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

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

First I had some problems with the meaning of this text, without an fixed size

font ;-)

*>I'm looking for some insight on the approach I might take in traversing the*

*>graph to convert it to the text form.*

I'd use an array with the number of not yet seen in-edges for every node. Then

walk the tree and create AND expressions for all sequences, and OR expressions

from all forks. Walking stops on a follow node with yet unseen in-edges, backs

up to the last fork, and processes the next edge. Processing continues only

when all in-edges to the next node already have been seen. Parentheses should

be inserted around every OR subexpression, starting at a fork.

In your example first "A && ( B && C" is created. Then the follow node has

another yet unseen in-edge, which results in a backup to A. Then walking the

next branch results in " || X && Y", and continues with ")", since now all

in-edges of J have been seen, and with the final assignment. I'd remove the

assignment from the graph before, and replace it by an synthetic end node,

because it's a different (non boolean) operation.

DoDi

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.