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

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

算法


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

基本结构


如何实现正则表达式识别功能?
程序的主要模块是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>。

语法树叶子



明天继续……

源代码下载