rxcg： 用于 IoT 的简单文本匹配 C 代码生成器
5.00/5 (9投票s)
生成紧凑的 C 代码以基于正则表达式匹配文本
引言
更新：在大多数情况下生成更紧凑的代码。
更新 2：修复了 blockend 生成中的错误。
更新 3：将 XXXX_capture_t 的名称更改为 XXXX_match_t。
更新 4：删除了常见类型（如 match_t）的命名空间前缀，并添加了几个命令行选项。改进了代码生成。
我写了这么多正则表达式引擎和它们的代码生成器，这几乎是我的本能了。我这样做是为了好玩。这一次，我这样做是因为它很有用。
我需要从 REST 式 Web 服务获得的 JSON 结果中提取单个字段。我需要在小型物联网设备上完成这项工作，而且我不想在整个 JSON 库中浪费宝贵的程序空间，而我只需要一小部分关键数据。
实际上，我需要的是正则表达式，但我也避免浪费空间在正则表达式引擎上。
最终，这意味着需要一个代码生成器，它能根据输入的正则表达式生成匹配器代码。通过使用这种工具，我可以获得正则表达式功能，但仅限于完成工作所需的功能，而在最终结果中不包含任何不必要的东西。与其将正则表达式馈送到 regex 引擎并在运行时进行处理和解释，不如使用已经针对硬编码的正则表达式进行优化的代码，而无需在运行时进行解释。
理解这段乱码
rxcg 是一个表驱动的 DFA/非回溯代码生成器。它生成的代码的复杂度为 O(n)，其中 n 是输入字符串的长度。总而言之，这意味着在从左到右遍历流时，它最多只访问每个字符一次。
这也意味着它使用数据数组/表来驱动匹配，而不是硬编码的 goto。这在某些情况下会以速度为代价来换取大小，因为基于数组的技术可以减小闪存占用空间，但运行速度可能不如基于 goto 的编排。
这是一个朴实的设置，目的是使最终代码简单高效。它不支持子捕获组。您可以进行分组，但这只会改变运算符优先级。它不会将子捕获到组中。它不支持 ^ 或 $ 等锚点。但它确实支持 Unicode，一直到 UTF-32，以及常见的字符类，包括像 IsLetter 和 IsDigit 这样的 Unicode 字符类。
为了灵活性，它使用一个回调函数来检索输入流中的下一个 UTF-32 代码点。您负责实现回调函数以检索您的数据，无论这些数据来自文件、字符串还是网络。这也意味着您需要负责将您的流转换为 UTF-32 代码点，无论您如何实现。幸运的是，生成器提供了这样的代码，并且我在示例中包含了从 UTF-8 或 ASCII 文件或字符串中执行此操作的代码。
输入文件采用 Reggie/Rolex 文件格式。
它是一种基于行的格式，每行类似于以下内容
CIdent<ignoreCase>= '[A-Z_][0-9A-Z_]*'
或者更普遍地表示为 EBNF
identifier [ "<" attributes ">" ] "=" ( "'" regexp "'" | "\"" literal "\"" )
每个属性都是一个标识符，后面可以选择性地跟着 = 和一个 JSON 风格的字符串、布尔值、整数或其他值。如果未指定值，则为 true，这意味着 ignoreCase 设置为 true。请注意，字面量表达式用双引号括起来，而正则表达式用单引号括起来！
有几个可用的属性，如下所示
ignoreCase- 表示表达式应被解释为不区分大小写blockEnd- 表示指定符号的多字符结束条件。遇到时，匹配器将继续读取直到找到blockEnd值，并将其消耗掉。这对于具有多字符结束条件的表达式很有用，例如 C 块注释、HTML/SGML 注释和 XML CDATA 部分。请记住，如果blockEnd是字符串，请使用双引号；如果它是正则表达式，请使用单引号。
如上所述，正则表达式语言支持基本的非回溯构造和常见的字符类，以及 [:IsLetter:]/[:IsLetterOrDigit:]/[:IsWhiteSpace:]/等等，它们映射到 .NET 的对应项。请务必转义单引号，因为它们在文件中用于分隔表达式。
该工具是一个基于命令行的应用程序，它接受一个输入文件和一个可选的 /size <capture_size> 参数，并从中生成两个文件：Name.h 和 Name.c，其中 Name 是输入文件的名称。对于 MyMatch.rl，该工具将生成 MyMatch.h 和 MyMatch.c。
/size 参数表示捕获缓冲区的大小。在匹配时，会返回匹配文本的代码点，但它们不能大于指定的大小，否则捕获将被截断。这可以是一个数值，也可以是已定义的 #define 宏的名称，例如 CAPTURE_SIZE。
代码生成器本身是用 C# 编写的，并使用了我的 FastFA 正则表达式引擎，该引擎也用于我的另一个项目 Reggie。事实上，我无耻地借鉴了该项目的大量代码来用于此项目，因此请访问该链接以获取概述。我本可以编写一个 Reggie 插件来完成这项工作，但老实说，Reggie 对此来说有点过于笨重，而且我想对其进行一些简化，特别是对于物联网而言，执行词法分析等操作是适得其反的。
使用这个烂摊子
命令行工具很简单。让我们从使用屏幕开始
Usage: rxcg.exe <input> [/size <capture_size>] [/ifstale] [/stdint] [/prefix]
<input> The input file to use
<capture_size> The size of the capture
buffer. Default is 256
<ifstale> Only generate if source
is newer than target
<prefix> Generate a prefix for
the match struct
<stdint> Use <stdint.h>
第一个参数是必需的，它是 Rolex 词法分析器格式的输入文件，如上所述。其余参数是可选的
<capture_size>可以是字面值，也可以是预处理器宏，用于指定捕获缓冲区的大小。<ifstale>将跳过源文件的生成，除非输入比输出新。<prefix>将文件名前置于常见名称（如match_t）之前，就像以前的版本那样。<stdint>将导致生成的代码使用<stdint.h>作为其数值类型。
编写这个混乱的程序
使用生成的代码首先涉及进行回调。如果您只关心 7 位 ASCII，这很容易，您可以通过将每个 ASCII 字符强制转换为 int32_t 来作弊，但对于 Unicode 支持，您需要付出一些实际的努力。
示例项目包含两个基本的回调实现 - 一个用于字符串，一个用于文件。在每种情况下，我们需要跟踪输入以及我们在其中的位置，以便在每次被调用时返回下一个字符，或者在到达末尾时返回 -1。这些实现也作为生成代码的一部分提供，但被 #if 0 掉了。
这是字符串实现
// holds the current string pointer
typedef struct string_cb_state {
char* sz;
} string_cb_state_t;
int32_t string_callback(
unsigned long long* out_advance,
void* state) {
string_cb_state_t* ps = (string_cb_state_t*)state;
int32_t cp;
if (!*ps->sz) {
// end of stream
*out_advance = 0;
return -1;
}
// decode UTF-8 to UTF-32
uint8_t byte = (uint8_t)*ps->sz;
if ((byte & 128) == 0) {
cp = ((uint32_t) *ps->sz & ~128);
*out_advance = 1;
}
if ((byte & 224) == 192) {
cp=((uint32_t) ps->sz[0] & ~224) << 6 |
((uint32_t) ps->sz[1] & ~192);
*out_advance = 2;
}
if ((byte & 240) == 224) {
cp=((uint32_t) ps->sz[0] & ~240) << 12 |
((uint32_t) ps->sz[1] & ~192) << 6 |
((uint32_t) ps->sz[2] & ~192);
*out_advance = 3;
}
if ((byte & 248) == 240) {
cp=((uint32_t) ps->sz[0] & ~248) << 18 |
((uint32_t) ps->sz[1] & ~192) << 12 |
((uint32_t) ps->sz[2] & ~192) << 6 |
((uint32_t) ps->sz[3] & ~192);
*out_advance = 4;
}
// advance the pointer by
// what we consumed
ps->sz+=*out_advance;
return cp;
}
大部分混乱在于处理 Unicode。除此之外，我们所做的只是在 state（类型为 string_cb_state_t）中推进指针，并在完成后返回 -1。
文件实现类似，尽管在某些方面更简单，因为 state 只是一个 FILE 句柄，它会跟踪并推进自己的光标。请注意，在 Arduino 上，您会使用 File 对象并与之一起工作，但示例是标准的 C。
int32_t file_callback(
unsigned long long* out_advance,
void* state) {
FILE* h = (FILE*)state;
int32_t cp;
int i = fgetc(h);
if (i==-1) {
*out_advance = 0;
return -1;
}
uint8_t byte = (uint8_t)i;
if ((byte & 128) == 0) {
cp = ((uint32_t) i & ~128);
*out_advance = 1;
}
if ((byte & 224) == 192) {
cp=((uint32_t) i & ~224) << 6 |
((uint32_t) fgetc(h) & ~192);
*out_advance = 2;
}
if ((byte & 240) == 224) {
cp=((uint32_t) i & ~240) << 12 |
((uint32_t) fgetc(h) & ~192) << 6 |
((uint32_t) fgetc(h) & ~192);
*out_advance = 3;
}
if ((byte & 248) == 240) {
cp=((uint32_t) i & ~248) << 18 |
((uint32_t) fgetc(h) & ~192) << 12 |
((uint32_t) fgetc(h) & ~192) << 6 |
((uint32_t) fgetc(h) & ~192);
*out_advance = 4;
}
return cp;
}
在字符串实现之后，这个实现应该很明显了。
请注意，所有这些例程都假定流是 7 位 ASCII 或有效的 UTF-8。没有进行检查，因此可能会发生非常糟糕的事情™，特别是当字符串回调函数收到无效流时。
现在让我们探讨一下如何使用它。
对于输入文件中的每个命名正则表达式，都会生成一个名为 match_Name() 的函数，其中 Name 是输入文件中 = 左侧的名称。
考虑 Example.rl 文件中的以下行
Identifier = '[_[:IsLetter:]][_[:IsLetterOrDigit:]]*'
这将生成一个名为 match_Identifier() 的函数，然后可以使用它来查找匹配该 Unicode 表达式的字符串。
int main(int argc, char** argv) {
char* test =
"a1234 foobar /*5678 abc123 */ -";
unsigned long long pos = 0;
string_cb_state_t st;
st.sz = test;
while (1) {
match_t c =
match_Identifier(&pos,
string_callback,
&st);
if (0 == c.length) {
// empty capture indicates end
return 0;
}
// print the capture buffer
// (assumes ASCII)
for(int i = 0;i<c.length;++i) {
printf("%c",(char)c.capture[i]);
}
printf("\n");
}
}
这里的想法是反复调用匹配函数，每次都获取一个新的 match_t，直到返回一个 length 为 0 的值，这表示已到达输入末尾。
请注意，捕获缓冲区本身由 int32_t 值组成，而不是人们可能期望的 char。此匹配器捕获的是 UTF-32 代码点，而不是字符。这解释了代码末尾循环并打印 capture 内容的部分。另请注意，捕获缓冲区不是以 null 结尾的。
注意：如果您想在 Arduino 框架中使用此代码，应在编译器的命令行上定义 ARDUINO 为一个常量。或者，修改生成的头文件以无条件地 #include <Arduino.h>，或者只是确保它在 Arduino.h 之后包含。
关注点
此代码生成容纳 DFA 数组所需的最小元素类型。这意味着如果它是 ASCII 表达式且状态机足够小，它将使用 int8_t 作为数组元素类型。否则，它将根据需要使用 int16_t 或 int32_t。每个数组类型使用一个匹配器例程。这意味着将生成 1 到 3 个匹配器实现来处理所有匹配。它们都几乎相同，以下是它们的样子，并包含 blockend 代码
(请原谅换行，这个例程很长很深。)
match_t Example_runner32(int32_t* dfa, int32_t* blockEnd,
unsigned long long* position, Example_callback callback, void* callback_state) {
match_t result;
result.position = 0;
result.length = 0;
unsigned long long adv = 0;
int tlen;
int32_t tto;
int32_t prlen;
int32_t pmin;
int32_t pmax;
int32_t i, j;
int32_t ch;
int32_t state = 0;
int32_t acc = -1;
int done;
unsigned long long cursorPos = *position;
ch = callback(&adv, callback_state);
while (ch != -1) {
result.length = 0;
result.position = cursorPos;
acc = -1;
done = 0;
while (!done) {
start_dfa:
done = 1;
#if defined(ARDUINO) && !defined(CORE_TEENSY) && !defined(ESP32)
acc = (int32_t)pgm_read_dword((uint32_t*)(dfa + (state++)));
tlen = (int32_t)pgm_read_dword((uint32_t*)(dfa + (state++)));
#else
acc = dfa[state++];
tlen = dfa[state++];
#endif
for (i = 0; i < tlen; ++i) {
#if defined(ARDUINO) && !defined(CORE_TEENSY) && !defined(ESP32)
tto = (int32_t)pgm_read_dword((uint32_t*)(dfa + (state++)));
prlen = (int32_t)pgm_read_dword((uint32_t*)(dfa + (state++)));
#else
tto = dfa[state++];
prlen = dfa[state++];
#endif
for (j = 0; j < prlen; ++j) {
#if defined(ARDUINO) && !defined(CORE_TEENSY) && !defined(ESP32)
pmin = (int32_t)pgm_read_dword((uint32_t*)(dfa + (state++)));
pmax = (int32_t)pgm_read_dword((uint32_t*)(dfa + (state++)));
#else
pmin = dfa[state++];
pmax = dfa[state++];
#endif
if (ch < pmin) {
break;
}
if (ch <= pmax) {
if (result.length < 256) {
result.capture[result.length++] = ch;
}
ch = callback(&adv, callback_state);
++cursorPos;
state = tto;
done = 0;
goto start_dfa;
}
}
}
if (acc != -1) {
if (blockEnd != NULL) {
state = 0;
while (ch != -1) {
acc = -1;
done = 0;
while (!done) {
start_block_end:
done = 1;
#if defined(ARDUINO) && !defined(CORE_TEENSY) && !defined(ESP32)
acc = (int32_t)pgm_read_dword((uint32_t*)
(blockEnd + (state++)));
tlen = (int32_t)pgm_read_dword((uint32_t*)
(blockEnd + (state++)));
#else
acc = blockEnd[state++];
tlen = blockEnd[state++];
#endif
for (i = 0; i < tlen; ++i) {
#if defined(ARDUINO) && !defined(CORE_TEENSY) && !defined(ESP32)
tto = (int32_t)pgm_read_dword((uint32_t*)
(blockEnd + (state++)));
prlen = (int32_t)pgm_read_dword((uint32_t*)
(blockEnd + (state++)));
#else
tto = blockEnd[state++];
prlen = blockEnd[state++];
#endif
for (j = 0; j < prlen; ++j) {
#if defined(ARDUINO) && !defined(CORE_TEENSY) && !defined(ESP32)
pmin = (int32_t)pgm_read_dword((uint32_t*)
(blockEnd + (state++)));
pmax = (int32_t)pgm_read_dword((uint32_t*)
(blockEnd + (state++)));
#else
pmin = blockEnd[state++];
pmax = blockEnd[state++];
#endif
if (ch < pmin) {
break;
}
if (ch <= pmax) {
if (result.length < 256) {
result.capture[result.length++] = ch;
}
ch = callback(&adv, callback_state);
++cursorPos;
state = tto;
done = 0;
goto start_block_end;
}
}
}
}
if (acc != -1) {
return result;
}
else {
if (result.length < 256) {
result.capture[result.length++] = ch;
}
ch = callback(&adv, callback_state);
++cursorPos;
}
state = 0;
}
state = 0;
continue;
}
else {
if (result.length > 0) {
return result;
}
}
}
ch = callback(&adv, callback_state);
++cursorPos;
state = 0;
}
}
result.length = 0;
return result;
}
它作为一个有趣的奇观提供给有兴趣的读者。请注意，blockend 部分仅在被使用时生成。总之，我们不会详细探讨它，因为它遍历从正则表达式生成的数组，并且当这些数组被编译时，所有有趣的逻辑都已内置其中。遍历它很有效，但并不直观。
历史
- 2022 年 9 月 5 日 - 初次提交
- 2022 年 9 月 15 日 - 通过消除未使用的 blockend 代码使代码生成更紧凑
- 2022 年 9 月 15 日 - 修复了为 blockend 生成正则表达式匹配数组的错误
- 2022 年 9 月 16 日 - 稍微更改了命名
- 2023 年 11 月 15 日 - 添加了几项功能并更改了命名