正则表达式是非常强大的工具,在嵌入式开发中很多场景都可能用到。比如之前参与开发的一个产品，量产时需要通过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
字符串:aaaaaabc
则字符串先挪到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，后面完成非递归实现。
本系列文章会继续分享一些实用的组件,代码,不追求功能大而全,而是追求满足需求刚刚好，坚持一贯的极简风格。
