功能：通过正规表达式获取NFA

简单的Thompson

设计一个节点数据结构

实现目的为正则表达式
假设：

  1. 状态机一定有一个初始状态节点和一个结束状态节点；
  2. 任何一个状态节点，至多只有两个指向外面的转换边；
  3. 每个状态节点，所拥有的边，最多只有三种可能，as follow：
    1. 有一条非epsilon的边
    2. 有一条epsilon的边
    3. 有两条epsion的边

根据这三个假设构造一个NFA的节点

  1. //这里仍旧使用java代码
  2. public class NFA{
  5.     public enum anchor{
  6.         NONE,
  7.         START,
  8.         END,
  9.         BOTH
  10.     }
  12.     //定义几个路径状态
  13.     public static final int EPSILON = -1;//边对应的是ε
  14.     public static final int CCL = -2;//边对应的是字符集
  15.     public static final int EMPTY = -3;//没有指向外面的边
  16.     private static final int ASCII_COUNT=127;//?????
  18.     //记录转换边对应的输入，输入可以是空，CCL，epsilon
  19.     private int edge;
  20.     public int getEdge()
  21.     {    return edge;    }
  22.     public void setEdge(int type)
  23.     {    edge = type;    }
  25.     //一个状态节点的重要属性
  26.     public Set<Byte> inputSet;
  27.     public NFA next;        //通过边转跳到下一个节点，可以为空
  28.     public NFA next2;        //根据之前的假设，一个节点至多拥有两个指向外侧的边
  29.     public ANCHOR anchor;    //对应的正则表达式是否开头含有^，或者结尾含有$
  30.     private int stateNum;    //节点编号
  31.     private boolean visited = false;//节点是否被访问过
  33.     public void setVisited(){
  34.         visited = true;
  35.     }
  36.     public boolean isVisited(){
  37.         return visited;
  38.     }
  40.     public NFA(){
  41.         inputSet = new HashSet<Byte>();//使用一个hashset存储输入？
  42.         clearState();//在创建NFA的时候清除一次状态
  43.     }
  45.     public void setStateNum(int num){
  46.         stateNum = num;
  47.     }
  48. }

词法分析器

  1. public class Lexer{
  2.     public enum Token{
  3.         EOS,        //end of string
  4.         ANY,        //.通配符
  5.         AT_BOL,        //开头匹配符^
  6.         AT_EOL,        //结尾匹配夫$
  7.         CCL_END,    //字符集类结尾括号]
  8.         CCL_START,    //字符集类开始括号[
  9.         //...etc...
  10.     }
  12.     //lexer的各种属性
  13.     private final int ASCII_COUNT = 128;
  14.     private Token[] tokenMap = new Token[ASCII_COUNT];    //token数组
  15.     private Token currentToken = Token.EOS;
  16.     RegularExpressionHandler exprHandler = null;        //句柄
  17.     //...etc
  19.     public Lexer(RegularExpressionHandler exprHandler){
  20.         initTokenMap();
  21.         this.exprHandler = exprHandler;
  22.     }
  24.     private void initTokenMap(){
  25.         //首先把全部的
  26.         for(int i=0;i<ASCII_COUNT;i++)
  27.             tokenMap[i] = Token.L;
  28.         //将特殊字符修改为特殊含义
  29.         tokenmap['.'] = Token.ANY;
  30.         tokenMap['['] = Token.CCL_START;
  31.         //etc...
  32.     }
  34.     public Token advance(){
  35.         if(currentToken == Token.EOS){
  36.             //一个正则表达式结束了,进入下一个正则表达式
  37.             if(exprCount >= exprHandler.getRegularExpressionCount()){
  38.                 currentToken = Token.END_OF_INPUT;
  39.                 return currentToken;
  40.             }
  41.             else{
  42.                 //当前没有解析完成全部的内容
  43.                 curExpr = exprhandler.getRegularExpressionCount(exprCount);
  44.                 exprCount++;
  45.             }
  46.         }
  47.         if(charIndex >= curExpr.length()){
  48.             currentToken = Token.EOS;
  49.             charIndex = 0;
  50.             return currentToken;
  51.         }
  52.     }
  54. }

NFA节点的情况

NFA节点对应于情况3.a（一条非epsilon的边）

  1. edge = CCL；如果
  2. next->下一个节点

  3. next2->null

    NFA节点对应于情况3.b（一条epsilon的边）

  4. edge = epsilon;

  5. next->下一节点

  6. next2->null

    NFA节点对应于情况3.c（两条epsilon的边）

  7. edge = epsilon

  8. next->下一节点

  9. next2->下一节点

    NFA节点没有指向外侧的边

  10. edge = empty

  11. next->null

  12. next2->null

    关于inputSet属性

    inputSet是专门用来存放字符集的，在这个题目中，仅仅存在ascii输入，因此inputSet至多包含127个元素（因为是HashSet集合….因此不会重复）

    节点的内存管理

    当程序要生成一个NFA节点的时候，不直接使用new，采用了类似工厂模式的方法，NFAManager用于构造&回收节点（这部分其实使用new也可以….这里使用了工厂模式和池模型，能够更好的保证对性能的利用）

    有一个起始状态和一个结束状态

    使用一个类….内包含两个NFA对象，一个指向起点，一个指向终点即可；

    NFA状态机构造实现

    简单状态1：单个字符匹配

  13. 判断输入的正则表达式是否为单字匹配的模式？

  14. 如果是，则分配两个NFA节点，起始状态指向节点A，结束状态指向节点B
  15. 让节点A的next->节点B
  16. 将节点A的edge设置为目标匹配字符

例如，单字匹配a，起始节点的edge=’a’，起始节点.next->结束节点

简单状态2：任意单个字符匹配

  1. 分配起始节点和结束节点
  2. 起始节点.next->结束节点
  3. 起始节点的edge赋值为CCL

  4. 起始节点的inputSet中添加除了回车换行之外的所有ascii字符

    简单状态3：范围匹配（构建NFA状态机[abcd]、[0-9]）

    分析：[abcd]可以匹配任何abcd中的任何一个字符

  5. 分配两个NFA节点作为开始&结束

  6. [abcd]仍旧属于字符集识别，起始节点的edge=CCL

  7. 调用一个方法检查正则表达式是否存在只包含”[“或者”]”的情况，如果有这种情况，正则表达式是不能成立的，直接报错;

    1. 如果没有”-“，即离散的n个字符，将这些字符添加到inputSet中
    2. 如果存在”-“，那么就需要使用for循环挨个往inputSet中添加

      简单状态4：重复某个结构

      例如：9.（ digitMap的写法，正则表达式应当是9* ）
      此时（重复0次）；9（重复1次）；99（重复2次）…….99999….99（重复n次）；均可匹配

  8. 分配四个节点

节点1-(epsilon)->节点2-(9)->节点3-(epsilon)->节点4
| |——(e)———| |
|———————————-(epsilon)————————-|
该模型可以完成重复0次->重复n次的效果

关于NFA节点的模型

NFA节点最多只会存在两个向外的边