# How can I implement regular expressions on an embedded device?

I have some (I thought) pretty portable code that uses <regex.h>. When I tried to port this over to compile for a PIC18 with xc8, the compiler could not find the header file for the library.

module/ciface/ciface.h:12:10: fatal error: 'regex.h' file not found
#include <regex.h>
^~~~~~~~~
1 error generated.


Is there any way to use regexs on an embedded device?

• regular expressions trade memory for execution speed, a pic18 is fairly memory constrained, are you sure that this is the best approach. Sep 4 '19 at 9:28
• @Jasen can you link to some further reading about this? All of the information I can find suggests regexs are just state machines? Sep 4 '19 at 9:47
• Please don't mix up header files and libraries. The error message tells you that the header file is not found. That does not mean that the library is not found. An error message of that kind would be generated by the linker. Sep 4 '19 at 9:59
• No, the library as I ment is a file that is read at link time. What the compiler tells you is a missing file at compile time. But if you interpret "library" as the set of files that are delivered from the makers, then perhaps, one could say that a header file is part of a library. Please note that the relation between header files and library files are m:n. Header files are needed by the compiler to get known about some objects (functions, variables, types, ...) which the including source uses. Library files are needed by the linker to resolve referenced objects. Sep 4 '19 at 10:26
• the state machine associated with the regex often uses more more memory than a native parser Sep 4 '19 at 11:51

Since you wrote your own answer, it's clear that you wanted to promote a particular solution.

In a more general sense, the standard C regex library is for both compiling and executing regular expressions, and relies on services provided by a POSIX-compliant operating system. Compiling is much more complicated (it involves first parsing the regular expression itself) and memory-intensive, and that's why it isn't available on a target system that doesn't have an OS, or has only a simple OS that doesn't include regex support.

But if your regex is known at compile time, then the only thing you need to do on the embedded target is execute it. The development system host can do all of the heavy lifting associated with compiling it.

re2c is an interesting approach, but hardly the only one. The lexical analyzer generators lex and flex do the same thing, using a different syntax to describe the expression(s). They also generate "pure C" code that can be compiled into a target system.

If you need to parse more complicated syntax, then you also have the parser generators yacc and bison. These tools have been used for ages to process command lines, both on desktop and embedded systems.

• Just sharing the way I got it working :) Sep 4 '19 at 11:31
• 'relies on services provided by a POSIX-compliant operating system' - do you have a reference for this? And do you mean that regexp compilation and execution is in the kernel (rather than glibc)? That's very unusual - the kernel normally only contains things that interact in a protected fashion (IO, process management, etc). Regex is very much usermode. EDIT: and this is the code in glibc: github.com/bminor/glibc/blob/master/posix/regex_internal.c
– Rich
Sep 4 '19 at 21:19
• @Rich, there's more to an operating system than just the kernel.
– Mark
Sep 4 '19 at 23:05
• @Mark I see your point. A C (shared) library is bundled with most OSs because the mandatory system tools like the shell are written in C. This didn't happen with some earlier OSs (MSDOS!) where you had to explicitly install it or statically link. (And classic Unix bundled the compiler. And adventure).The real answer here is that embedded systems often bundle a cut-down C library minus expensive functionality like regex (and e.g. floating point printf).
– Rich
Sep 5 '19 at 0:00

Although it could be possible to get the library to compile with xc8, I had better luck using re2c, which is a utility that uses special syntax in your source file to produce a FSM that runs a regex.

An example from their website:

static int lex(const char *YYCURSOR) // YYCURSOR is defined as a function parameter
{                                    //
const char *YYMARKER;            // YYMARKER is defined as a local variable
/*!re2c                          // start of re2c block
re2c:define:YYCTYPE = char;      //   configuration that defines YYCTYPE
re2c:yyfill:enable  = 0;         //   configuration that turns off YYFILL
//
* { return 1; }                  //   default rule with its semantic action
digit  = [0-9];                  //   named definition of 'digit'
number = digit+;                 //   named definition of 'number'
//
number {                         //   a normal rule with its semantic action
printf("number\n");          //     ... semantic action (continued)
return 0;                    //     ... semantic action (continued)
}                                //   end of semantic action
//
*/                               // end of re2c block
}                                    //



In this example the function returns 1 when the input is not a number, and returns 0 when it is.

Once this is run through re2c with the command:

re2c inputfile.re -o outputfile.c


A state machine is produced, replacing the comment in the function. This is pure C so doesn't require any libraries to be included at compile time.

Personally, I like to look at this state machine and re-write it myself, which can range from a pretty simple job to a much harder one depending on your regex.