2

I am on a memory limited system, boost::regex is too large. What options exist to compile my regular expression straight to C/C++ and how many KB of code size should I except? With the goal of reducing memory and code size as much as possible.

I am looking for under 100kb of code size and the same in memory usage. Boost regex appears to be approx 470kb which is too large.

16
  • Anyway, boost::regex is C++, not C.
    – netcoder
    Sep 20, 2012 at 2:06
  • How complex do your regular expressions need to be? In the book 'Beautiful Code', there are some simple regular expression functions that probably amount to a couple hundred bytes of code and an amount of stack space mostly controlled by the number of stars (*) that appear in the regular expressions. But these are very simple regexes. Sep 20, 2012 at 2:07
  • Regular expressions that will match different parts of the HTTP protocol, so more than just basic * and +
    – dongle26
    Sep 20, 2012 at 2:08
  • 2
    Matches HTTP what? URLs? Requests? Headers? Body?
    – netcoder
    Sep 20, 2012 at 2:10
  • (GET|POST|HEAD)[[:blank:]]+(?:([[:alpha:]]{1,6})://([^/[:blank:]]+))?(/[^[:blank:]]*)(?:[[:blank:]]+HTTP/([[:digit:]]{1,3})\\.([[:digit:]]{1,4}))? for example.
    – dongle26
    Sep 20, 2012 at 2:12

3 Answers 3

4

lex (and flex) produce table-driven lexers which are generally pretty small; they go back to the days when 100kB would have been considered a supercomputer :) The basic flex code skeleton is tiny (a few kB) and the tables depend on how many token types you have and how complicated the regular expressions are, but a simple flex scanner table are typically a few kB as well.

However, if you're not using them for building an interpreter/compiler, they do have a couple of annoying characteristics: first, they insist on doing your input and buffering for you, which is nice if you're always reading from a file but can be less cool if your input is coming from a socket or terminal (or, worse, being preprocessed by some kind of translator), and second they are designed for an environment where you have a few simple token types, and you have a parser which is responsible for interpreting the sequencing. (Hence yacc or bison.) You could use these tools to parse HTTP, certainly, and you might even find that you've learned some useful new skills.

There is a tool called re2c (i.e. regular expression to C) which you might find a little more comfortable. Unlike lex, it produces customized C code, which is quite a bit bulkier, but arguably runs slightly faster. I don't think it's being actively maintained, but I had quite a lot of success with it some years back. You should be able to find it on SourceForge.

Good luck.

2

People seem to forget that this problem has been solved long time ago by lex and yacc.

8
  • Sort of, with lex, but not really. You compile the set of possible regexes with lex, but you can't adapt to new regexes at runtime with lex. Sep 20, 2012 at 2:19
  • @Jonathan, yes, true, but who said anything about runtime? What's the use of C code at runtime? Sep 20, 2012 at 2:23
  • So you need to qualify your answer along the lines of: if the set of regular expressions to be managed is fixed when the program is compiled, then you may be able to use lex to recognize those expressions. Sep 20, 2012 at 2:28
  • I don't want to build a compiler just to parse HTTP. I've looked at lex and yacc and can't figure them out. Also don't compilers use alot of memory (relatively speaking)?
    – dongle26
    Sep 20, 2012 at 2:30
  • 1
    Hmm, don't think so. The question is titled "convert/compile regular expressions to C code", and then says "What options exist to compile my regular expression straight to C/C++ ...". I don't see any ambiguity here. Sep 20, 2012 at 2:33
1

re2c is an application designed to do exactly that

http://sourceforge.net/projects/re2c/

(also available as a debian package etc)

Licence: Public Domain

alternatively it may be possible to compile a regex to bytecode and link the interpreter part of pcre2 (or whichever regex style you want) only eg:

https://www.pcre.org/current/doc/html/pcre2api.html#SEC25

It is possible to save compiled patterns on disc or elsewhere, and reload them later, subject to a number of restrictions. The host on which the patterns are reloaded must be running the same version of PCRE2, with the same code unit width, and must also have the same endianness, pointer width, and PCRE2_SIZE type. Before compiled patterns can be saved, they must be converted to a "serialized" form, which in the case of PCRE2 is really just a bytecode dump. The functions whose names begin with pcre2_serialize_ are used for converting to and from the serialized form. They are described in the pcre2serialize documentation. Note that PCRE2 serialization does not convert compiled patterns to an abstract format like Java or .NET serialization.

So, to include precompiled regex for RCRE2 you may need to run the compile on the target system or under emulation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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