Dart 正規表現 Engine を作成する (3) FSM(有限オートマトン)で表現

VMの作成(http://qiita.com/kyorohiro/items/cbd2617a979a31efb3ba)
と、Parserの作成(http://qiita.com/kyorohiro/items/eed9617aebdbe450aad3)
でVM型の正規表現エンジンを作成しました。

ついでに、FSM(有限オートマタ)での実現方法も紹介しておきます。

FSMだと以下のように簡単に描けます。30行もないですね。

dart

bool fsm(String target, int currentStatus, Map<Action, int> table, List<int> goal) {
  if (target.length == 0) {
    return goal.contains(currentStatus);
  } else {
    Action expectAction = new Action(currentStatus, target[0]);
    if (table.keys.contains(expectAction)) {
      return fsm(target.substring(1), table[expectAction], table, goal);
    } else {
      return false;
    }
  }
}

class Action extends Object {
  int status;
  String character;
  Action(int status, String character) {
    this.status = status;
    this.character = character;
  }
  int get hashCode => status << 8 | character.codeUnitAt(0);
  bool operator ==(Action t) => this.hashCode == t.hashCode;
}

いくつか簡単な例を見ていきましょう。

"a"をFSMで表現

"a"をFSMで図で表現

(1) -a-> (2)

"a"をFSMをコードで表現

void main() {
  var table = <Action,int> {
    new Action(1, 'a'): 2,
  };
  var goal = [2];
  print(fsm("a", 1, table, goal));// true
  print(fsm("aa", 1, table, goal));// false
  print(fsm("b", 1, table, goal));// false
}

"a+"をFSMで表現

"a+"をFSMで図で表現

           __a_
          |    |
(1) -a-> (2)<--

"a+"をFSMをコードで表現

void main() {
  var table = <Action,int> {
    new Action(1, 'a'): 2,
    new Action(2, 'a'): 2,
  };
  var goal = [2];
  print(fsm("a", 1, table, goal));// true
  print(fsm("aa", 1, table, goal));// true
  print(fsm("b", 1, table, goal));// false
}

"[a-b][c-d]?"をFSMで表現

"[a-b][c-d]?"をFSMをコードで表現

  //
  var table = <Action,int> {
    new Action(1, 'a'): 2,
    new Action(1, 'b'): 2,
    new Action(2, 'c'): 3,
    new Action(2, 'd'): 3
  };
  var goal = [2,3];
  print(fsm("a", 1, table, goal)); //true
  print(fsm("b", 1, table, goal)); //true
  print(fsm("ad", 1, table, goal)); //true
  print(fsm("e", 1, table, goal)); //false

おわり

こんな感じで、オートマトンに直接落としてしまうのもありですね。
ref https://www.udacity.com/course/programming-languages--cs262