7
$\begingroup$

Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about the construction of DFAs, but for a real paper on how it is actually done in programming languages implementation, and what is considered simple or difficult. I expect differences between languages may have an inpact. A formal paper on how REGEXP implementation should be done is useful too :-)

$\endgroup$
  • $\begingroup$ Obviously this is an old question, but I thought that I'd add that as an alternative to the Thompson-construction, I quite like the idea of the Berry-Sethi-construction, which uses exactly one more state than the regex has terminal symbols. Seeing how matching for NFAs is done by finding the reachable states on the fly, this is almost a mute point, though. Maybe the lack of $\epsilon$-transitions is appealing. The only reference I can give are these slides. $\endgroup$ – G. Bach Jul 30 '14 at 10:27
  • $\begingroup$ @G.Bach There is no such thing as an old question, unless technical advances have made the topic itself obsolete. AFAIK, this can also be an answer, if you can really relate it to REGEXP implementation in programming languages. It may be either existing uses, or suggested uses. The programming languages versions of REGEXP have a variety of bells and whistles that may or may not be compatible with the Berry-Sethi method. I think the Berry-Sethi construction is used in the implementation of the Esterel language, but not for REGEXP, AFAIK. $\endgroup$ – babou Jul 30 '14 at 12:16
  • $\begingroup$ I don't really think a separate answer is merited, it was more meant as a remark that "there are other constructions than the Thompson one that are similarly efficient"; I don't really know where it's used in any tools, I just liked the idea of it when I learned about it, which was in fact in the context of building an $\epsilon$-free NFA accepting the language of a regular expression. $\endgroup$ – G. Bach Jul 30 '14 at 14:22
  • $\begingroup$ @G.Bach I thought it might be useful to remind people of interesting variants. But turning it into a proper answer to the question as asked might indeed be some work. Thanks anyway. $\endgroup$ – babou Jul 30 '14 at 14:28
5
$\begingroup$

I believe most interpreted regular expression matchers start with Thompson's construction algorithm to turn the regular expression into a non-deterministic finite automata. The article that first described these is: Ken Thompson, "Programming Techniques: Regular expression search algorithm", Communications of the ACM, 11(6):419-422, June 1968. But that paper is a little hard to read, since he was compiling to machine code.

My favorite tutorial on regular expression implementation is this series of blog posts by Russ Cox, the author of the RE2 regular expression library. He gives lots of historical discussion. He argues that the most efficient approach to simulating the NFA is to convert to DFA on the fly with caching of just the DFA states that you actually reach. (In contrast to, for example, the implementation of regular expressions in Perl, which use backtracking.) There are cases (e.g., when you get an extended regular expressions with backreferences) where you need to use backtracking, but Cox suggests that you should only use backtracking when you need to.

The other place you might look is Henry Spencer's regular expression library. According to that web site this was described in the book: Dale Schumacher (ed), Software Solutions In C, Academic Press, 1994.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.