超级精简系列之二:超级精简的正则表达式C实现

嵌入式Lee

最新更新时间：2023-11-24

阅读数：

一. 前言

正则表达式是非常强大的工具 , 在嵌入式开发中很多场景都可能用到。比如之前参与开发的一个产品，量产时需要通过 U 盘导入 .db 配置文件 , 文件名可能变，后缀都是 .db, 此时就需要使用正则表达式来匹配文件名。

嵌入式开发中 , 尤其是基于资源受限的 MCU 平台开发时 , 一些开源的实现并不适用。虽然 GNU 工具链提供了跨平台的 POSIX 正则表达式 C 库， GNU regex ，但是很多嵌入式开发工具链中并没有实现，并且也还是过大。

有没有更精简，不要求功能强大 , 只要能满足一些基本的匹配语法就行 , 在资源很少的 rom 和 ram 的 MCU 上也能用的实现呢 ? 答案是肯定的！本文就来分享一个，该代码使用下来的感受就是，真香，但是还是不完美 !

二. 代码分析

正则表达式本身相关的内容网上搜索即可，这里不再赘述。我们直接来 ” show me the code ” 。

代码来源于 https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html

该代码实现了以下语法

c 匹配任意原义字符 c 。

. 匹配任意单个字符。

^ 匹配输入字符串的开始端。

$ 匹配输入字符串的结束端。

* 匹配零个或多个前一字符。

代码只有三个函数短短几十行 :

    /* match: search for regexp anywhere in text */    int match(char *regexp, char *text)    {        if (regexp[0] == '^')            return matchhere(regexp+1, text);        do {    /* must look even if string is empty */            if (matchhere(regexp, text))                return 1;        } while (*text++ != '\0');        return 0;    }

match 检查 text 中是否有满足 regexp 正则表达式的字符串 , 如果有返回 1 否则返回 0, 如果有多个则找到的的是最左边最短的。

该函数比较好理解 , 即分为两种情况处理

1. 正则表达式是 ^ 开头 , 则正则表达式只能和 text 开头开始匹配 , 即 matchhere(regexp+1, text)

2. 如果不是 ^ 开头 , 则正则表达式可以和 text 的任意位置开始匹配 , 所以遍历 text, 直到 text 的末尾。即 while (*text++ != '\0');, 如果某个位置开始匹配了就退出 , 否则 text 完后挪动一个位置继续匹配。

3. 注意上面是 do while, 即先进行一次匹配 , 因为 * 可以匹配 0 个字符 , 所以哪怕 text 是空字符串，也要先进行匹配。因为正则表达式 ” c* ” 可以和空字符串匹配。如果是 while (*text++ != '\0'){} 先判断 text 是否结束则处理不了这种情况。

   /* matchhere: search for regexp at beginning of text */    int matchhere(char *regexp, char *text)    {        if (regexp[0] == '\0')            return 1;        if (regexp[1] == '*')            return matchstar(regexp[0], regexp+2, text);        if (regexp[0] == '$' && regexp[1] == '\0')            return *text == '\0';        if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))            return matchhere(regexp+1, text+1);        return 0;    }

以上可以看出 , 最终都是通过 matchhere 完成匹配

即从当前 text 位置开始是否和正则表达式 regexp 匹配 , 匹配则返回 1 否则返回 0.

该函数采用了递归的实现方式 , 即逐步推进正则表达式和 text, 之前的匹配了了，正则表达式和 text 都往后挪动继续匹配。所以重点是考虑结束条件 :

1. 如果正则表达式匹配到了最后 , if (regexp[0] == '\0'), 说明前面的都已经匹配了 , 所以返回匹配成功。否则继续。

2. 如果 if (regexp[1] == '*') 则是 c* 的形式 , 则调用 matchstar(regexp[0], regexp+2, text); 进行 * 的匹配，见后面 matchstar 函数的实现。

3. 如果是正则表达式到了末尾即 $ 结束， if (regexp[0] == '$' && regexp[1] == '\0') ，此时只有 text 也到了末尾才能匹配，否则 text 后面还有的话肯定不匹配。

4. 如果 text 还没结束 , 且正则表达式是 . ，或者正则表达不是 . 是普通字符且匹配，那么说明本位置的字符匹配，正则表达式和 text 都往后挪动一个位置继续匹配。

5. 其他情况，比如字符串结束了，此时正则表达式还没到结束，那么说明匹配失败返回 0.

注意以上递归的深度取决于正则表达式的长短 , 递归深度太深可能会导致栈溢出，尤其是在嵌入式平台是需要注意的。

再来看 matchstar

    /* matchstar: search for c*regexp at beginning of text */    int matchstar(int c, char *regexp, char *text)    {        do {    /* a * matches zero or more instances */            if (matchhere(regexp, text))                return 1;        } while (*text != '\0' && (*text++ == c || c == '.'));        return 0;    }

这里也依然是 do while 先检查，然后再推进 text ，而不是 while{}, 原因同上。

如果 text 还未到结束，且当前 text 的字符和 c 匹配 ( 匹配可能是普通字符或者 .) ，

即 C* 或者 .* 的形式，则 text 往后罗董，继续匹配。

如下是 matchstar 的一个修改版本，实现最左最长 c* 形式匹配，

text 先挪动到满足 c* 的最后去，然后再来看后面的是否匹配，不匹配则往前面 text 再匹配。

比如对于

正则表达式 :a*abc

字符串 :aaaaa abc

则字符串先挪到 bc 处和正则表达式后面的 abc 比不匹配，于是再往前挪动到 abc 于是匹配。

即匹配的 a* 序列最长。

而上面的实现是从左边逐渐推进 text 匹配。

  /* matchstar: leftmost longest search for c*regexp */    int matchstar(int c, char *regexp, char *text)    {        char *t;
        for (t = text; *t != '\0' && (*t == c || c == '.'); t++)            ;        do {    /* * matches zero or more */            if (matchhere(regexp, t))                return 1;        } while (t-- > text);        return 0;    }

核心思想就是正则表达式和字符串逐步推进，如果当前位置匹配则两者都继续推进 ( 即递归 ) 。在某个时候如果正则表达式或者字符串提前结束了，那么说明不匹配。

而如果两者同时结束则说明匹配。所以重点是处理当前阶段的结束条件。

三. 应用

以上代码实现了支持以下语法的正则表达式，实际大部分场景这些就足够了

c 匹配任意原义字符 c 。

. 匹配任意单个字符。

^ 匹配输入字符串的开始端。

$ 匹配输入字符串的结束端。

* 匹配零个或多个前一字符。

所以大部分情况以上代码都可以应用。

以下是基于 uCFS 的文件系统 , ls, cp 等操作支持正则表达式匹配的实现。

其中回调函数 callback 可以用于指定具体操作，比如移动或者复制等等。

/** ***************************************************************************** * \fn          static int scan_files(char* regular,char* path,int pathlen,char* dstpath,int dstpathlen,FSAPI_ScanFile_CallBack callback) * \brief       扫描文件,输出文件信息或执行回调函数. * \param[in]   regular 正则表达式. * \param[in]   path 待扫描文件路径. * \param[in]   dstpath 目的路径(cp操作时需要). * \note        path dstpath会作为工作区,所以传入的path缓冲区必须足够长(大于最长文件路径).,必须由调用者分配足够大的空间.   * \retval      -1 失败 * \retval      0 成功 ***************************************************************************** */static int scan_files(char* regular,char* path,int pathlen,char* dstpath,int dstpathlen,FSAPI_ScanFile_CallBack callback){    FRESULT res;    FS_DIR dir;    UINT i;    UINT j;    static FILINFO fno;    if((path==0) || strlen(path)>=pathlen)    {        return-1;    }    if((dstpath!=0) && strlen(dstpath)>=pathlen)    {        return-1;    }    res = f_opendir(&dir, path);                          if (res == FR_OK)     {        for (;;)         {            res = f_readdir(&dir, &fno);                              if ((res != FR_OK) || (fno.fname[0] == 0))            {                break;             } //            if (fno.fname[0] == '.') /*uCFS支持当前目录格式.*///            {//                printf("%s/%s\r\n",path,fno.fname); //                continue; //            }            if ((fno.fattrib & FS_ENTRY_ATTRIB_DIR) || (fno.fattrib & FS_ENTRY_ATTRIB_DIR_ROOT))             {                                   i = strlen(path);                if((i+strlen(fno.fname))                {                    sprintf(&path[i], "/%s", fno.fname);                 }                if(dstpath != 0)                {                    j = strlen(dstpath);                     if((j+strlen(fno.fname))                    {                        sprintf(&dstpath[j], "/%s", fno.fname);                    }                   }                if(match(regular,path))                {                    printf("%s\r\n", path);                }                if(scan_files(regular,path,pathlen,dstpath,dstpathlen,callback) != 0)                {                    if(callback!=0)                    {                        /*如果搜索的文件名匹配了正则表达式则执行回调函数操作*/                        if(match(regular,path))                        {                            callback(path,dstpath);                          }                    }                    //break; 这里不能break 否则文件目录后面的文件将不能搜索到                }                /*从子目录返回截断子目录*/                if(i                {                    path[i] = 0;                }                if(dstpath != 0)  /*之前这里没加条件判断导致内存异常改写hardfault*/                {                    if(i                    {                        dstpath[j] = 0;                    }                }            }             else             {                unsigned int flen;                /*补全文件名*/                i = strlen(path);                if((i+strlen(fno.fname))                {                    sprintf(&path[i], "/%s", fno.fname);                 }                if(dstpath != 0)                {                    j = strlen(dstpath);                     if((j+strlen(fno.fname))                    {                        sprintf(&dstpath[j], "/%s", fno.fname);                    }                }                flen = strlen(fno.fname);                                 if(callback==0)                {                    /*如果未指定回调函数则显示文件信息*/                    /*如果搜索的文件名匹配了正则表达式则打印信息*/                    if(match(regular,path))                    {                        printf("%s", path);                        //printf(" %4d年-%02d月-%02d日",((fno.fdate>>9)&0x7F)+1980,((fno.fdate)>>5)&0x0F,((fno.fdate)>>0)&0x1F);                        printf(" %d\r\n",fno.fsize);                     }                }                else                {                    /*如果搜索的文件名匹配了正则表达式则执行回调函数操作*/                    if(match(regular,path))                    {                        callback(path,dstpath);                      }                }                  /*截断文件名*/                i = strlen(path);                if(i>=(flen+1))                {                    i -= (flen+1);                     path[i]=0;                }                if(dstpath != 0)                {                    j = strlen(dstpath);                    if(j>=(flen+1))                    {                        j -= (flen+1);                         dstpath[j]=0;                    }                }             }        }        f_closedir(&dir); /*uCFS目录是动态创建需要关闭*/    }    if (res == FR_OK)    {        return 0;    }    else    {        return -1;    }}

四. 总结

以上代码满足了我们对简单，够用，刚刚好等的要求，这些特点使其适用于嵌入式平台。但是还有一个致命的缺点可能使得我们在产品代码中应用时，需要斟酌一番，即它使用的是递归实现方式，递归意味着栈的消耗随着递归深度增加而增加，这在嵌入式平台中是非常危险的，很可能会导致栈溢出。所以这里预留一个 @todo ，后面完成非递归实现。

本系列文章会继续分享一些实用的组件 , 代码 , 不追求功能大而全 , 而是追求满足需求刚刚好，坚持一贯的极简风格。