# How are REGEXP implemented in programming languages?

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 :-)

• 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. – G. Bach Jul 30 '14 at 10:27
• @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. – babou Jul 30 '14 at 12:16
• 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. – G. Bach Jul 30 '14 at 14:22
• @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. – babou Jul 30 '14 at 14:28