|Re: additional regular expression operators email@example.com (MZL) (2009-04-15)|
|RE: additional regular expression operators firstname.lastname@example.org (Quinn Tyler Jackson) (2009-04-21)|
|From:||"Quinn Tyler Jackson" <email@example.com>|
|Date:||Tue, 21 Apr 2009 07:40:20 -0700|
|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
Return to the
Search the comp.compilers archives again.