問題発生

構文木を照合に使うSkRegExpを実装中。

一応すべての正規表現を実装したので、本番のテストプログラムを起動させて見ました。すると早速エラーが発生。

まあ、エラーを出すためのテストプログラムなんですが、エラーの内容が悪かった。

今の構文木の構造だと、ループをうまく処理できないことが判明しました。

最長一致は何とかなるんですが、最短一致はどうにもならないことがわかりました。

最短一致を処理するにはパーサーを次のような構造にしないとだめそうです。

正規表現が a*?b の場合。

  1. a を読み込みスタックに退避
  2. * を読み込みスタックに退避
  3. ? を読み込みスタックに退避
  4. b を読み込み左の枝に最短一致に使う b を、右の枝にループに使う a をぶら下げる

今のパーサーはこういう構造になっていないので、書き直さないとダメです。

やはり甘くはなかったです。

でも、意欲は衰えていません。

やることは明確ですから前に進むだけです。

コメントを残す

メールアドレスが公開されることはありません。