如何构造正则引擎

基本思路

学过编译原理的话，目前就有一种编译原理上的路子，通过分析正则表达式的字符串，进行词法分析，语法分析（构造DFA），语义分析等，构造一个强大的正则表达式引擎。

如果是不实现|的正则，十分的简单，但这里我想构造一个功能完备的正则表达式引擎，并且具有一定的速度，需要支持完整的正则文法，编写一个高效的one-pass正则编译器。

但一切基于实现最最基本的正则引擎，目前，在下也只完成了一小部分的功能，并且没有实现过多的高级特性。这些高级技巧今后会慢慢加上，这是一个长时间更新的项目。（目前准备试试求导方法）

NFA

为什么从NFA开始，因为之前的字符串处理有很多种方法，都有效，但目前并没有找到一个高效间洁的方法处理字符串——将正则转化为最最基本的正则语法。因此暂时跳过，以后补充

NFA构造

NFA相信学过编译原理的人都很熟悉，作为常用的递归或者循环的思想实现，它具有很多有趣的功能。现在使用NFA构造正则引擎是很常规的做法。

  • 首先需要一个结构（类）来存放NFA中的状态和状态边。这里我采用了一种取巧的做法，约定俗成第n个边对应第n个状态边；例如：

    1
    2
    3
    4
    NFANode node = new NFANode();
    NFAEdge edge = node.getEdges().get(i);
    NFANode deNode = node.getDsNode().get(i);
    //这里i个边对应当前状态输入i边能到达的状态

  • 然后便需要实现一个添加一个边为一的函数。

    1
    2
    3
    4
    5
    void addSingleEdge(Character c,NFANode dsNode){
      if(dsNode==null)
        return;
      edges.add(c); nodes.add(dsNode);
    }

  • 为了方便使用，这里封装一下添加边的函数

    1
    2
    3
    4
    5
    private void addEdgeToState(String state,Character edge,String desState){
        NFANode from = getNode(state);
      	NFANode to = getNode(desState);
      	from.addEdge(edge,to);
    }

  • 同样地，封装一个获取开始和结束状态结点的函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    private NFANode getStertState(){
      for(NFANode n : nodes){
          if(n.start)
            return n;
      }
      return null;
    }

    private NFANode getEndState(){
      for(NFANode n: nodes)
        if(n.end)
          return n;
      return null;
    }

  • 下面是实现NFA之间合并的操作。最基本的有connect和parallel操作，目前只需要connect这一个操作，不过parallel的函数实现也会给出

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    //we need a function size() and a rename function;
    private int size(){ return nodes.size(); }
    void stateRename(){
      for(int i = 0; i < nodes.size(); i++)
        nodes.get(i).state=String.valueOf(i);
    }

    void connect(NFA nfa){
      if(nfa.size()==0)
        return;
      if(size()==0)
        return nfa;
      NFANode end = getEndState();
      if(end!=null){
          end.end=false;
      }
      if(end!=null){
          end.addEdge(EPSLION,nfa.getStartState());
      }
      nfa.getStartState().start=true;
      nodes.addAll(nfa.nodes);
      stateRename();// necessary and important
    }

    void parallel(NFA nfa){
      if(nfa.size()==0){
      	return;
      }
      if(size()==0){
        return nfa;
      }
      NFANode start1=getStartState();
      NFANode start2 = nfa.getStartState();
      NFANode end1 = getEndState();
      NFANode end2 = getEndState();
      start1.start=start2.start=false;
      end1.end=end2.end=false;
      NFA nnfa = new NFA();
      nnfa.addNodeToNFA("S"); nnfa.addNodeToNFA("E");
      NFANode nstart=nnfa.getState("S");
      NFANode nend = nnfa.getState("E");
      nstart.start=true;
      nend.end=true;
      nstart.addEdge(EPSLION,start1);
      nstart.addEdge(EPSLION,start2);
      end1.addEdge(EPSLION,nend);
      end2.addEdge(EPSLION,nend);
      nnfa.nodes.addAll(nodes);
      nnfa.nodes.addAll(nfa.nodes);
      nnfa.stateRename();
      this=nnfa;
      }

  • 下面需要实现一个闭包的操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    void closureStar(){
      NFA newNfa = new NFA();
            newNfa.addNodeToNFA("S");
            newNfa.setStart("S");
            newNfa.addNodeToNFA("E");
            newNfa.setEnd("E");

            NFANode start = getStartState();
            NFANode end = getEndState();

            start.start = false;
            if (end != null) {
                end.end = false;
            }

            newNfa.getStartState().addEdge(Utils.EPSILON, start);
            if (end != null) {
                end.addEdge(Utils.EPSILON, newNfa.getEndState());
            }

            if (end != null) {
                end.addEdge(Utils.EPSILON, start);
            }

            newNfa.getStartState().addEdge(Utils.EPSILON, newNfa.getEndState());
            newNfa.nodes.addAll(nodes);
            newNfa.stateRename();
            nodes = newNfa.nodes;
    }

    ​

DFA

  • 构造完NFA之后，就是将NFA处理为DFA了。这里采用一种最为朴素的方法，从第一个开始状态开始，找出它的闭包，将所有可能出现的边遍历一遍。因此需要实现一些工具函数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    static HashSet<NFANode> closure(NFANode node){
      Queue<NFANode> queue = new LinkedList<>();
      HashSet<NFANode> dstates = new HashSet<>();
      dstates.add(node);
      queue.offer(node);
      while(!queue.isEmpty()){
        NFANode n = queue.poll();
        for(int i =0;i<n.edges.size();i++){
          if(destate.edges.get(i).equals(EPSLION)){
            if(!dstates.contains(n.destates.get(i)){
              dstates.add(n.destates.get(i));
              queue.offer(n.destates.get(i));
            } 
          }
        }
      }
      return dstates;
    }
    static HashSet<NFANode> closure(HashSet<NFANode> nodes){
      HashSet<NFANode> result = new HashSet<>();
      for(NFANode node : nodes){
        HashSet<NFANode> re = closure(node);
        result.addAll(re);
      }
      return result;
    }

    static HashSet<NFANode> move(HashSet<NFANode> nodes,char i){
      HashSet<NFANode> result = new HashSet<>();
      for(NFANode n : node){
          for(int i =0;i<n.edges.size();i++){
            if(n.edges.get(i)==i&&!result.contains(n.destates.get(i))){
                result.add(n.destates.get(i));
            }
          }
      }
      return result;
    }

    ​

  • 那么如何具体的处理NFA呢？我们使用以下的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void constructFromNFA(NFA nfa){
  if(nfa==null)
    return;
  HashSet<HashSet<NFANode>> result = new HashSet<>();
  Stack<HashSet<NAFNode>> stack = new Stack<>();
  HashSet<NFANode> start = closure(nfa.getStartState());
  stack.push(start);
  result.add(start);
  addNodeToDFA(start);
  while(!stack.isEmpty()){
    HashSet<NFANode> currentNode = stack.pop();
    for(int i =1;i<ASCII_MAX;i++){
      HashSet<NFANode> re = closure(move(currentNode));
      if(re.size()>0&&!result.contains(re)){
        stack.push(re); result.add(re); addNodeToDFA(re);
      }
      if(currentNode.size()>0&&re.size()>0){
        addEdgeToState(currentNode,(char)i,re);
      }
    }
  }
}
  • 最基本的DFA已经构造完成了，下面是实现如何用DFA匹配字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
boolean match(String s){
  DFANode startNode = null;
  for(DFANode n: node){
      if(n.start)
        startNode = n;
  }
  for(Character c: s.toCharArray()){
    if(startNode ==null)
      return false;
    if(startNode.hasPath(c)){
        startNode = (DFANode) startNode.desNodes.get(startNode.edges.indexof(c))
    }else{
        return false;
    }
  }
  return startNode!=null&&startNode.end;
}

todo

java

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！