正規表現エンジンの実装(1)

これから数回をかけて正規表現エンジンをC言語で実装します。この回では、メタ記号('(',')', '|','?','+'..)無しの正規表現を作ります。すると結局、文字列の比較をするプログラムを作るということになります。例えば"./a.out hello hello"としたら"match\n"、"./a.out hello hell"とすると"no match\n"と標準出力されるようなものです。

1st commit

(正規表現)->(ポストフィックス　ノーテーション)(PFN)->(NFA)に変換させてから、文字列にマッチするかどうか調べるという方式で実装します。正規表現からPNへの変換部分を実装するわけですが、"|"が導入できるようにするためには、どの文字と文字が接続されているかを指定する必要があります。例えば、"ab"はaとbが接続されていて、これを"ab."と表現することにします。"abc"はaとbが接続されていて、cは"ab."に接続されています。なので"ab.c."となります。ちょうど、逆ポーランド記法(rpn)と同じ要領です。

+#include <stdio.h>
+#include <assert.h>
+#include <string.h>
+char* reg2post(const char* re) {
+static char buf[8000];
+char* dst;
+int i = 0;
+  dst = &buf[0];
+  for(;*re;re++) {
+    if(i > 1) {
+      *dst++ = '.';
+    }
+    *dst++ = *re;
+    i++;
+  }
+  if(i > 1)
+    *dst++ = '.';
+  return buf;
+}
+
+void test(void);
+int main(void) {
+  test();
+  return 0;
+}
+void test(void) {
+  assert(!strcmp("a",reg2post("a")) && "a -> a");
+  assert(!strcmp("ab.",reg2post("ab")) && "ab -> ab.");
+  assert(!strcmp("ab.c.d.e.f.g.",reg2post("abcdefg")) && "abcdefg -> ab.c.d.e.f.g.");
+}
+

その後の展開

ここにソースコード置いておきます。