Wed, 15 Apr 2009 07:57:04 -0700 (PDT)

Related articles |
---|

additional regular expression operators rpboland@gmail.com (Ralph Boland) (2009-03-29) |

Re: additional regular expression operators m.helvensteijn@gmail.com (2009-03-30) |

Re: additional regular expression operators zaimoni@zaimoni.com (2009-03-30) |

Re: additional regular expression operators haberg_20080406@math.su.se (Hans Aberg) (2009-03-30) |

Re: additional regular expression operators torbenm@pc-003.diku.dk (2009-03-31) |

Re: additional regular expression operators rpboland@gmail.com (Ralph Boland) (2009-03-31) |

Re: additional regular expression operators torbenm@pc-003.diku.dk (2009-04-14) |

Re: additional regular expression operators zayenz@gmail.com (MZL) (2009-04-15) |

Re: additional regular expression operators anton@mips.complang.tuwien.ac.at (2009-04-16) |

Re: additional regular expression operators gah@ugcs.caltech.edu (glen herrmannsfeldt) (2009-04-16) |

Re: additional regular expression operators torbenm@pc-003.diku.dk (2009-04-17) |

Re: additional regular expression operators mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2009-04-17) |

RE: additional regular expression operators quinn_jackson2004@yahoo.ca (Quinn Tyler Jackson) (2009-04-21) |

From: | MZL <zayenz@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Wed, 15 Apr 2009 07:57:04 -0700 (PDT) |

Organization: | Compilers Central |

References: | 09-03-111 09-03-123 09-04-001 |

Keywords: | lex |

Posted-Date: | 16 Apr 2009 12:30:00 EDT |

On Apr 1, 3:07 am, Ralph Boland <rpbol...@gmail.com> wrote:

*> I have never found a useful example of set intersection though.*

*> I have found so far only one paper on implementing these operators*

*> and it is complex.*

While this is quite a special case, you might find it interesting. In

constraint programming regular languages can be used to specify

constraints. Given that more than one regular constraint can be and

typically is used at the same time over the same set of variables,

intersection of two regular languages can be used to strengthen

constraint propagation. It is not widely used, though, since the

intersection operation is quite often quadratic which makes the gain

in pruning power quite expensive.

When I implemented the intersection operation, it was quite simple,

although as said it was also inherently inefficient. The basic idea

(IIRC) was to take the product of the two automatas state-spaces which

allows the concurrent check of both languages.

Cheers,

MZL

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.