Tue, 21 Apr 2009 07:40:20 -0700

Related articles |
---|

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

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

From: | "Quinn Tyler Jackson" <quinn_jackson2004@yahoo.ca> |

Newsgroups: | comp.compilers |

Date: | Tue, 21 Apr 2009 07:40:20 -0700 |

Organization: | Compilers Central |

References: | 09-04-026 |

Keywords: | lex |

Posted-Date: | 21 Apr 2009 17:19:05 EDT |

Ralph Boland said:

*> > 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.*

MZL replied in part:

*> 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.*

In my work with grammars, I use set intersection on an almost daily basis

and in various different ways and often with effectively linear time

complexity. That said, the regular languages are closed over intersection

[Bar-Hillel et al.], so in the case of these, intersection is ultimately

just syntactic sugar. Syntactic sugar has its place, though, since a good

notation can make tackling certain problems more tractable.

Once we move into the CFLs, however, intersection becomes quite powerful and

useful. From the syntactic predicates of [Parr & Quong], to the Conjunctive

and Boolean grammars arising from [Okhotin], the syntactic sugar gets some

yeast and the cake gets a few more candles, since it becomes possible to

parse CSLs languages by intersecting two or more CFLs.

With just a wee-bit more (indexed back-referencing), it then becomes

possible to use intersection to parse Type 0 languages. In some years I have

never encountered a language that, when parsed by such a grammar, performed

worse than just under O(n^3) -- and that was a best in a test tube in the

lab (q.v. [Jackson]).

So, intersection in parsing/pattern matching has many, many uses. Once you

start solving complex parsing problems using it, its potential usefulness

becomes more clear.

[Insert standard disclaimers here.]

--

Quinn Tyler Jackson

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.