Incremental Regex Parsing with Fixed Strings

[Andrew Martin]

Greetings,

In Dan Piponi's blog post Fast Incremental Regular Expression Matching with
Monoids [1], he outlines a way to take advantage of fingertrees to perform
increment regex matching. In his article, the regular expression (more
accurately, its equivalent DFA) is fixed, and the strings we are matching
on are modified incrementally. What I'm interested in is the opposite: What
if the regular expression is modified incrementally and the string we are
testing is static?

Thinking about this, it seems to run into problems immediately. Typically,
to evaluate a regular expression, I would convert it to a NFA (and then
maybe to a DFA). But there is no way to do incremental graph modification
on the resulting graphs. (Or is there?). And even if there were a way, it
seems unclear how one would go about exploiting its incremental nature. To
provide an example, consider the following regex and sample string:

Regex: Lost (dog|cat) loo for home
Sample: Lost dog looking for home

In the regex, I'm currently in the middle of typing "looking", so it
doesn't match the sample string. But large parts of it do. So when I update
the regex by typing "k", I'd like to be able to not redo this work. Maybe
there's a certain subset of regex that's amenable to this kind of
incremental evaluation. Maybe not. If anyone has any additional insights or
can point me to any research, I would appreciate it greatly. Thanks.

[1] http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html


-- 
-Andrew Thaddeus Martin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20190228/fef6125c/attachment.html>