<div dir="auto"><div>I'm not too optimistic in general about editing regex machines interactively. I'd expect you to do a lot of work to save a little. But I'd expect you could win a good bit (at least in some common cases) by using something like a suffix tree of your text. That'll let you jump quickly to the end of "Lost ", for example, and may offer other interesting opportunities.</div><div dir="auto"><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">On Thu, Feb 28, 2019, 1:43 PM Andrew Martin <<a href="mailto:andrew.thaddeus@gmail.com">andrew.thaddeus@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div dir="ltr">Greetings,<div><br>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?</div><div><br></div><div>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:</div><div><br></div><div>Regex: Lost (dog|cat) loo for home</div><div>Sample: Lost dog looking for home</div><div><br></div><div>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.</div><div><br></div><div>[1] <a href="http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html" target="_blank" rel="noreferrer">http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html</a><br><br><br><div><div>-- <br><div dir="ltr" class="m_8343670398669717726gmail_signature">-Andrew Thaddeus Martin</div></div></div></div></div></div>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div></div></div>