Javaによる正規表現エンジン(NFA Regex Engine)

Javaで正規表現エンジンを作成しました。使える演算子は、?, *, +, |と(, )です。
プログラムの中で、matchは文字列と正規表現の全体一致(full match)をチェックする関数です。
また、infix2postfixはinfix表記をpostfix表記に変換する関数です。

infix表記とpostfix表記

infix表記          postfix表記
   abc       →       ab.c.
  a|b|c      →       ab|c|

main.java

class Main {
  static void match(String string, String regexp) {
    System.out.println("\"" + string + "\"" + " =~ " + "/" + regexp + "/" + " -> " + new NFA(new RegexConverter().infix2postfix(regexp)).match(string));
  }
  public static void main(String[] args) {
    match("ab", "(a?b)*|(c?d)+");
  }
}

regex_converter.java

class RegexConverter {
  int index;
  String infix2postfix(String infix) {
    StringBuilder postfix = new StringBuilder();
    int countcon = 0; //the counter of concatenation operands
    int countalt = 0; //the counter of alternation operators
    for (int length = infix.length(); index < length; index++) {
      char c = infix.charAt(index);
      if (Character.isLetterOrDigit(c)) {
        if (countcon > 1) {
          postfix.append('.');
        }
        postfix.append(c);
        countcon++;
      }
      else if (c == '?' || c == '*' || c == '+') {
        postfix.append(c);
      }
      else if (c == '|') {
        if (countcon > 1) {
          postfix.append('.');
        }
        if (countalt > 0) {
          postfix.append('|');
        }
        countcon = 0;
        countalt++;
      }
      else if (c == '(') {
        if (countcon > 1) {
          postfix.append('.');
        }
        index++;
        postfix.append(infix2postfix(infix));
        countcon++;
      }
      else if (c == ')') {
        if (countcon > 1) {
          postfix.append('.');
        }
        if (countalt > 0) {
          postfix.append('|');
        }
        return postfix.toString();
      }
      else {
        return null;
      }
    }
    if (countcon > 1) {
      postfix.append('.');
    }
    if (countalt > 0) {
      postfix.append('|');
    }
    return postfix.toString();
  }
}

regex_engine.java

import java.util.*;

abstract class State {
  abstract void addto(List<State> states);
  abstract void transit(char chara, List<State> states);
  abstract void setnextstate(State state);
}

class AcceptState extends State {
  void addto(List<State> states) {
    states.add(this);
  }
  void transit(char chara, List<State> states) {}
  void setnextstate(State state) {}
}

class CharaState extends State {
  char inputchara;
  State nextstate1;
  CharaState(char inputchara) {
    this.inputchara = inputchara;
    this.nextstate1 = null;
  }
  void addto(List<State> states) {
    states.add(this);
  }
  void transit(char chara, List<State> states) {
    if (inputchara == chara) {
      nextstate1.addto(states);
    }
  }
  void setnextstate(State state) {
    nextstate1 = state;
  }
}

class SplitState extends State {
  State nextstate1;
  State nextstate2;
  SplitState() {
    this.nextstate1 = null;
    this.nextstate2 = null;
  }
  void addto(List<State> states) {
    nextstate1.addto(states);
    nextstate2.addto(states);
  }
  void transit(char chara, List<State> states) {
    System.err.println("Regex Error!");
  }
  void setnextstate(State state) {
    nextstate2 = state;
  }
}

class Fragment {
  State initialstate;
  List<State> finalstates;
  Fragment(State initialstate, List<State> finalstates) {
    this.initialstate = initialstate;
    this.finalstates = finalstates;
  }
  void attach(State state) {
    for (State s : finalstates) {
      s.setnextstate(state);
    }
  }
  Fragment patch(Fragment fragment) {
    attach(fragment.initialstate);
    return new Fragment(initialstate, fragment.finalstates);
  }
}

class NFA {
  State initialstate;
  NFA(String postfix) {
    CharaState charastate;
    SplitState splitstate;
    List<State> finalstates;
    Fragment fragment, fragment1, fragment2;
    Stack<Fragment> stack = new Stack<>();
    for (char c : postfix.toCharArray()) {
      switch (c) {
        case '?':
          fragment = stack.pop();
          splitstate = new SplitState();
          splitstate.nextstate1 = fragment.initialstate;
          finalstates = new LinkedList<>();
          finalstates.add(splitstate);
          finalstates.addAll(fragment.finalstates);
          stack.push(new Fragment(splitstate, finalstates));
          break;
        case '*':
          fragment = stack.pop();
          splitstate = new SplitState();
          fragment.attach(splitstate);
          splitstate.nextstate1 = fragment.initialstate;
          finalstates = new LinkedList<>();
          finalstates.add(splitstate);
          stack.push(new Fragment(splitstate, finalstates));
          break;
        case '+':
          fragment = stack.pop();
          splitstate = new SplitState();
          fragment.attach(splitstate);
          splitstate.nextstate1 = fragment.initialstate;
          finalstates = new LinkedList<>();
          finalstates.add(splitstate);
          stack.push(new Fragment(splitstate.nextstate1, finalstates));
          break;
        case '.':
          fragment2 = stack.pop();
          fragment1 = stack.pop();
          stack.push(fragment1.patch(fragment2));
          break;
        case '|':
          fragment2 = stack.pop();
          fragment1 = stack.pop();
          splitstate = new SplitState();
          splitstate.nextstate1 = fragment1.initialstate;
          splitstate.nextstate2 = fragment2.initialstate;
          finalstates = new LinkedList<>();
          finalstates.addAll(fragment1.finalstates);
          finalstates.addAll(fragment2.finalstates);
          stack.push(new Fragment(splitstate, finalstates));
          break;
        default:
          charastate = new CharaState(c);
          finalstates = new LinkedList<>();
          finalstates.add(charastate);
          stack.push(new Fragment(charastate, finalstates));
      }
    }
    fragment = stack.pop();
    fragment.attach(new AcceptState());
    initialstate = fragment.initialstate;
  }
  boolean match(String string) {
    List<State> currentstates = new LinkedList<>();
    initialstate.addto(currentstates);
    for (char c : string.toCharArray()) {
      List<State> nextstates = new LinkedList<>();
      for (State s : currentstates) {
        s.transit(c, nextstates);
      }
      currentstates = nextstates;
    }
    for (State s : currentstates) {
      if (s instanceof AcceptState) {
        return true;
      }
    }
    return false;
  }
}

バグがあれば、ご指摘願います。


参考サイト

1.Implementing Regular Expressions
2.Regular Expression Matching Can Be Simple And Fast
3.NFAベースの正規表現エンジン(Python)
4.Regular Expression Matching: the Virtual Machine Approach
5.PHPで仮想マシンベースの正規表現エンジンを作ってみる

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中