如何实现正则表达式识别功能？

如何实现正则表达式识别功能？

算法

算法参照《正则表达式识别》

基本结构

程序的主要模块是RegInterpreter，后面简称为Interp。
它接受正则表达式字符串，输出一个识别该字符串的DFA。

Interp先将字符串转换成语法树。
为了简化对字符的判断，开一个包含所有1～127的ascii的表，描述字符的类型。比如这个字符是文本还是运算符，是数字还是字母，是不是括号等等。再加入宏，方便判断。

语法树的所有结点都是RegNodes。
根据前一章，一个结点除了需要保存二叉树，还需要保存FirstSet，LastSet， FollowSet，Inputs，Nullable。
为了提高效率可以先预分配结点的空间。然后使用的时候龋

得到语法树之后，再计算出DFA。

这些计算都需要集合运算的支持。
为了方便比较，相同的集合只创建一个实例。这样拥有相同的句柄，就是相同的集合。NULL表示空集合。
所有的集合都放在一个hash表里。创建新集合的时候，先在表里找一下是不是有相同的集合。有就返回现有的。没有再添加一个新集合。

分析并建立语法树

参照语法图建立自顶向下分析程序
<re> ::= <expr> { <expr> }
| <re> '|' <re>
<expr> ::= <term>
| <term> '*' <<< 像前看一个字符
<term> ::= <label>
| '(' <re> ')' <<< 这里有一个冲突，下面会说明怎么解决
<label> ::= <symbol>
| '[' <range> { <range> } ']'
| '[' '^' <range> { <range> } ']'
<range> ::= <symbol>
| <symbol> '-' <symbol>
<symbol> ::= '.' <<< 这个通配符已经在算法部分讨论过了，
| 0 .. n (any element of alphabet) <<< 对于不同的编码，会变化，这里只考虑ASCII码。
| '/' <symbol> <<< 逃逸符需要更复杂的判断，比如/xFF或者/071。

这里有一个比较关键的地方是<re>可能是以字符串结束结尾的，也可能是右括号结束的。
但是并不是出现了右括号就一定是右括号结尾。只有从<term> ::= '(' <re> ')' 推导出来的<re>是以右括号结束的。

虽然可以通过改写语法来解决这种冲突。但是实际上并没有必要。可以在<re>对应的函数加个参数，表明，这个正则表达式可以以什么符号结束。这个标记从上向下传递。
所以

1. 当出现 <term> ::= '(' <re> ')' 时，在结束标志里加入括号。
2. 当出现任一表达式，使得<re>推导出一个子<re>的时候，把上一级的终结标志传递给下一级。

定义下面函数来进行自顶向下分析
inline REG_NODE* re( REG_INTERP* inter, REG_CHAR_TYPE end_mask = END_MARK );
inline REG_NODE* expr( REG_INTERP* inter );
inline REG_NODE* term( REG_INTERP* inter );
inline REG_NODE* label( REG_INTERP* inter );
inline REG_NODE* symbol( REG_INTERP* inter );
inline REG_NODE* anti_ranges( REG_INTERP* inter );
inline REG_NODE* ranges( REG_INTERP* inter );

字符集

使用REG_CHAR_TYPE来描述终结符号。这是一个DWORD的值，描述一个字符的类型。
为了提高程序识别效率，开了一个0～127范围的表。描述每个ASCII字符的类型。
这样使用一次便宜运算就可以求出一个字符的所有属性。而不需要反复调用c函数来判断。

一个字符可以有这么几个属性
REG_ TEXT REG_OPER REG_WILDCHAR REG_HEX REG_OCT PAIR_MARK
再加上给re函数用的结束控制位
END_MARK END_BY_PAREN

文本符 含有 REG_TEXT
运算符 含有 REG_OPER
通配符 含有 REG_WILDCHAR（这个实现的时候为0xFF，因为它可以看作任何东西，所有含有所有属性）
PAIR_MARK表示一个括号，如果字符同时含有END_MARK，则是一个括号配对的结束。
这样一个右括号的属性就是PAIR_MARK | REG_OPER | END_MARK | END_BY_PAREN
END_BY_PAREN 是给 re函数使用的终结控制符号。描述<term> ::= '(' <re> ')'的情况用。
字符/0的属性是 END_MARK。字符串结束符号只能作为终止控制符用。

当且仅当，输入字符的属性包含end_mask的属性的时候，才可以终结当前的<re>。

语法树叶子

明天继续……

源代码下载