28

Since I know the regexes at compiletime, and building up a regex is in O(2^m) where m is the length of the regex, I would love to build up the regex at compiletime.

Is this possible with std::regex? (I don't think so, because I don't see any constexpr constructor for basic_regex)

And if not, is there a regex library which can buildup my regexes at compiletime?

Ardent Coder
  • 3,777
  • 9
  • 27
  • 53
Exagon
  • 4,798
  • 6
  • 25
  • 53

2 Answers2

24

A CppCon 2017 lightning talk by Hana Dusikova "Regular Expressions Redefined in C++” described an approach to compile-time regular expressions using a user-defined literal for regex strings and a compile-time approach to generating the matching function. The code is on GitHub, but is still experimental and highly fluid at this time. So it seems that compile-time regexes are probably going to appear sometime soon.

legalize
  • 2,214
  • 18
  • 25
  • 1
    What is the present condition? – Ardent Coder Jun 10 '20 at 11:52
  • 4
    Proposed for the standard library in C++23: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1433r0.pdf The code can be used as-is on C++17 and C++20, I believe. – legalize Jun 12 '20 at 20:04
  • Thanks, so we may have to wait until C++23? – Ardent Coder Jun 13 '20 at 05:14
  • 1
    It is proposed for inclusion in the C++23 standard library. Look at the github repository linked in my answer for current code that you can use right now. AFAIK it should work in most current C++ implementations, but I haven't tried it myself. – legalize Jun 18 '20 at 21:07
  • If it's proposed for inclusion in C++23 then that means there's a 50% chance we'll see it in c++26, and a 50% chance vendors will actually implement it before c++29. – Chris_F Aug 07 '23 at 20:41
  • https://github.com/cplusplus/papers/issues/207 implies that it is strongly in favor of being included in C++23, but the author of the proposal needs to make some modifications before final acceptance. – legalize Aug 24 '23 at 22:47
11

We need to distinguish between program compile and regex compile. The latter is really done at a program runtime and it means building a large but efficient structure (state machine) suitable for fast matching against various strings.

in c++11 regex, regex compilation is done when you construct a regex object of string:

std::regex e (your_re_string);

If you use such an object in regex_match, regex_search, regex_replace, you take the advantage of working with an already-compiled regular expression. So, if you know your string at program compile time, the best thing you can do for the sake of speed is to construct a corresponding regex object just once per program run, say, having it somewhere declared as a static variable with initializer:

static  std::regex e (your_constant_re_string);

Probably it is what you want.

Some forms of regex_match, ... function may work immediately with regular expression strings instead. But please note that although it's usually more convenient for a programmer, if you use them, the performance will suffer of doing regex compiling every time such a function called.

P.S. If you really, really, really want to have you regexp compiled at a program compile time, you may (1) Use an external regexp/lexer compiler software (like https://github.com/madelson/PrecompiledRegex.Fody, Flex https://en.wikipedia.org/wiki/Flex_(lexical_analyser_generator) or similar) (2) compile an std::regex object, then serialize and convert to C++ input (which is actually a DIY version of (1)) But I'm quite sure that it doesn't worth if only wanted in order to save one regex compile per program run. Maybe unless you have really overwhelming expressions.

AndreyS Scherbakov
  • 2,674
  • 2
  • 20
  • 27
  • 5
    Thanks for your answer. But shouldnt it be possible to build the nfa/dfa for the regex at compiletime? With C++11 and constexpr this should be possible I think. – Exagon Jan 28 '17 at 12:20
  • 1
    Theoretically yes but you should write constexpr constructor or wait for it to be added. As of 2014, it was expected in C++14 or C++17. Still i'm not sure it was added. If not, you may contribute it. This is technical work but it may occur that some operator doesn't support constexpr yet. Remember that C++ standards is always running ahead their implementation :) – AndreyS Scherbakov Jan 28 '17 at 12:34
  • If I wanted such a compiler, I would simply write a function "storeAsCPPSource(const regex&)" and make a simple app that compiles and stores the object. – AndreyS Scherbakov Jan 28 '17 at 12:39