RE: additional regular expression operators

"Quinn Tyler Jackson" <>
Tue, 21 Apr 2009 07:40:20 -0700

          From comp.compilers

Related articles
Re: additional regular expression operators (MZL) (2009-04-15)
RE: additional regular expression operators (Quinn Tyler Jackson) (2009-04-21)
| List of all articles for this month |

From: "Quinn Tyler Jackson" <>
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.