Thompson在他1968年的论文当中介绍了多重状态的模拟。在他的设想当中,NFA由短小精悍的机器码表示,状态的变化只是指令的调用。实际上,Thompson把正则表达式编译成了机器码。四十年之后,计算机速度变快了,机器码运行不再必要。原文使用C语言实现,并且只能编译显式连接的后缀正则表达式,而本文实现了标准的简单正则表达式的编译。

表示

本项目(SimpleRegex)采用Java语言编写,Java的两个重要特性大大方便了正则表达式引擎的实现:

  • Unicode:原生支持Unicode支持,不必额外考虑Unicode字符匹配

  • 垃圾回收:可以免去复杂的NFA链接结构的内存管理

首先需要使用特定的数据结构来表示NFA,我们把NFA表示为关于状态的链接集合。

状态

NFA由状态(AbstractState)链接而成,其中可以分为三类状态:

  • 普通状态(State):如果输入的字符复合状态的要求,那么进入下一个状态,普通的状态又可以有三种情况

    • 通配(WildCardState):对应正则表达式中的.

    • 单字符(CharState):对应正则表达式中普通字符,例如a

    • 字符集合(CharClassState):对应正则表达式中字符集合,例如[0-9]或者\d

  • 分支状态(SplitState):状态面临多种选择

  • 匹配状态(MatchedState):字符串匹配成功

根据状态的分类,可以设计一个状态的继承关系:

片段

在生成NFA的过程之中,我们需要保存很多的NFA片段,就用Fragment表示,Fragment只有一个入口状态,但是有很多的出口状态。正则表达式的编译过程主要在对Fragment进行操作:

从普通状态构造片段

Fragment最简单的情况就是只有一个普通状态,那么这个普通状态既是入口,同时也是出口。

串联

首先,将e1的所有出口状态的后继状态设为e2的入口状态。然后,创建一个新的Fragment,以e1的入口状态为入口状态,以e2的出口状态集合为出口状态集合。

并联

首先,创建一个分支状态,将e1和e2的入口作为这个分支状态的两个后继状态。然后,创建一个新的Fragment,以分支状态为入口状态,以e1和e2的出口状态并集为出口状态集合。

匹配至多一个

创建一个分支状态,将e的入口作为分支状态的一个后继状态。然后,创建一个新的Fragment,以分支状态作为入口,以e的出口状态集合加上分支状态作为出口状态集合。

匹配一个以上

创建一个分支状态,将e的入口作为分支状态的一个后继状态,同时也将分支状态作为e出口状态集合的后继状态。然后,创建一个新的Fragment,以分支状态作为入口,以分支状态作为出口状态。

匹配任意个

创建一个分支状态,将分支状态作为e出口状态集合的后继状态。然后,创建一个新的Fragment,以e入口状态作为入口,以分支状态作为出口状态。

匹配指定次数

匹配指定次数可以采用上面定义好的操作来实现,也可以自定义一些特殊的结构

e{n} 将指定的e拷贝成n份,然后全部串联起来
e{n,} 将e{n}和e*进行串联,当n>0时也可以将e{n-1}和e+进行串联
e{n,m} 将e{n}和(e?){m-n}进行串联

模式

对于一个NFA,只需要知道它的入口即可,使用Pattern来保存NFA的入口状态。NFA对于用户是不可见的,Pattern提供了匹配字符串的方法以及创建一个NFA的静态方法。

编译

正则表达式的文法有些复杂,手写LL(1)递归下降分析器效率非常低,广泛使用的LALR分析器手写难度非常大,所以本项目使用了Bison来生成分析器代码。

词法分析

正则表达式中,同样的字符在不同的环境中有着不同的意义,例如+a+中表示重复一次以上,但是在[+]中只是加号,因此词法分析(Lexer)只能简单地对字符进行分类。

控制 +?*|.()\ux[^-]{,}
数字 0123456789
其他 除了上面提到的全部字符

语法制导翻译

正则表达式的文法(parser.yacc)比较复杂,需要考虑运算优先级,同时也要求文法符合LALR要求。

%code imports {
import com.google.common.collect.Range;
import com.google.common.collect.RangeSet;
import com.google.common.collect.TreeRangeSet;
import com.sine_x.regexp.exeception.RegexException;
import com.sine_x.regexp.state.*;
import com.sine_x.regexp.Pattern;
}

%language "Java"
%parse-param {Pattern pattern}
%define public
%define package com.sine_x.regexp.parser
%define parser_class_name {Parser}
%define throws {RegexException}

%token DIGIT
%token OTHER
%type <Character> OTHER DIGIT hex char exp_char set_char exp_op rep_op set_op
    'x' 'u' '+' '?' '*' '[' ']' '{' '}' '(' ')' '|' '.' ',' '-' '^' '\\'
%type <Integer> number
%type <Repeater> repeater
%type <Range> item
%type <RangeSet<Character>> items set
%type <Fragment> alternations concatenations closed

%%

expression:
  %empty                            { pattern.setStart(new MatchedState());     }
| alternations                      { pattern.setStart($1.getStart());
                                      $1.patch(new MatchedState());             }

alternations:
  concatenations                    { $$ = $1;                  }
| concatenations '|' alternations   { $$ = $1.alternates($3);   }

concatenations:
  closed                            { $$ = $1;                  }
| closed concatenations             { $$ = $1.concatenate($2);  }

closed:
  exp_char                          { $$ = new Fragment(new CharState($1));     }
| set                               { $$ = new Fragment(new CharClassState($1));}
| '.'                               { $$ = new Fragment(new WildCardState());   }
| closed repeater                   { $$ = $2.repeat($1);                       }
| '(' alternations ')'              { $$ = $2;                                  }

exp_char:
  char                              { $$ = $1;    }
| set_op                            { $$ = $1;    }
| rep_op                            { $$ = $1;    }
| '\\' exp_op                       { $$ = $2;    }
| '\\' '\\'                         { $$ = $2;    }

/* Character */

exp_op:
  '+'                               { $$ = $1;    }
| '?'                               { $$ = $1;    }
| '*'                               { $$ = $1;    }
| '{'                               { $$ = $1;    }
| '['                               { $$ = $1;    }
| '.'                               { $$ = $1;    }
| '('                               { $$ = $1;    }
| ')'                               { $$ = $1;    }
| '|'                               { $$ = $1;    }

set_op:
  '^'                               { $$ = $1;    }
| '-'                               { $$ = $1;    }
| ']'                               { $$ = $1;    }

rep_op:
  ','                               { $$ = $1;    }
| '}'                               { $$ = $1;    }

char:
  OTHER                             { $$ = $1;    }
| DIGIT                             { $$ = $1;    }
| 'x'                               { $$ = $1;    }
| 'u'                               { $$ = $1;    }
| '\\' 'x' hex hex                  { $$ = Util.ascii($3,$4);           }
| '\\' 'u' hex hex hex hex          { $$ = Util.unicode($3,$4,$5,$6);   }

hex:
  OTHER                             { $$ = $1;    }
| DIGIT                             { $$ = $1;    }

/* Repeater */

repeater:
  '+'                               { $$ = Repeater.REP_MORE_THAN_ONCE;                }
| '*'                               { $$ = Repeater.REP_ANY_TIME;                    }
| '?'                               { $$ = Repeater.REP_NONE_OR_ONCE;                }
| '{' number '}'                    { $$ = new Repeater($2, Repeater.NUM_NONE);        }
| '{' number ',' '}'                { $$ = new Repeater($2, Repeater.NUM_INFINITY);    }
| '{' number ',' number '}'         { $$ = new Repeater($2, $4);                    }

number:
  DIGIT                             { $$ = $1 - '0';                }
| number DIGIT                      { $$ = $1 * 10 + ($2 - '0');    }

/* Character set */

set:
  '[' items ']'                     { $$ = $2;                   }
| '[' '^' items ']'                 { $$ = $3.complement();      }
| '\\' OTHER                        { $$ = Util.get($2);         }

items:
  item                              { RangeSet<Character> set = TreeRangeSet.create(); set.add($1); $$ = set; }
| item items                        { RangeSet<Character> set = $2; set.add($1); $$ = set;                    }
| '\\' OTHER                        { RangeSet<Character> set = Util.get($2);                                 }
| '\\' OTHER items                  { RangeSet<Character> set = $3; set.addAll(Util.get($2)); $$ = set;       }

item:
  set_char                          { $$ = Range.singleton($1);  }
| set_char '-' set_char             { $$ = Range.closed($1, $3); }

set_char:
  char                              { $$ = $1;    }
| exp_op                            { $$ = $1;    }
| rep_op                            { $$ = $1;    }
| '\\' set_op                       { $$ = $2;    }
| '\\' '\\'                         { $$ = $2;    }
  • expression:合法的正则表达式字符串,空的正则表达式也是合法的

  • alternations:子表达式的并联

  • concatenations:子表达式的串联

  • closed:封闭的正则表达式,对于封闭的正则表达式e,对于任意包含e的正则表达式e1...e...en,语义与e1...(e)...en等价

  • exp_char:正则表达式中合法的字符表示

字符

将所有的字符进行分类可以方便处理。

  • exp_op:正则表达式中的控制字符,使用的时候需要转义,但是在集合中不需要转义使用

  • set_op:集合中的控制字符,集合中使用需要转义,但是在其他情况下不需要转义

  • rep_op:重复中的控制字符

  • char:非控制字符,包括\x00\u0000形式的字符

  • hex:十六进制数

重复

重复的方式保存在Repeater中,Repeater提供将Fragment重复的方法。

  • repeater:重复方式,有6种形式

  • number:十进制二负数,用来表示重复的次数

集合

本项目中的集合采用Guava中的区间树来实现。

  • set:字符的集合,使用[...]或者元字符表示

  • items:[...]字符集合的内容

  • item:[...]字符集合内部的条目,可以是单个字符、字符区间或者元字符

  • set_char:[...]内合法的字符表示,控制字符需要转义