RE: additional regular expression operators

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 comp.compilers page.
Search the comp.compilers archives again.