Incremental Regex Parsing with Fixed Strings

[Sergey Vinokurov]

Modifying regular expressions reminds me of the great functional pearl
called 'A Play on Regular Expressions'. Perhaps this is the approach you
were thinking about?

Sergey

On 28/02/2019 18:43, Andrew Martin wrote:
> 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
> 
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>