へっぽこ正規表現

なんか少しはまともなマッチングができるようになったと思ったら、実はそうでもなかった。

Input:func pattern str:

>> match abc abc 
func:match, pattern:abc, match:abc
is_match:1

Input:func pattern str:
>> match abc abd 
func:match, pattern:abc, match:abd
is_match:0

Input:func pattern str:

>> match ab|cd acd 
func:match, pattern:ab|cd, match:acd
is_match:1

Input:func pattern str:

>> match ab|cd ad 
func:match, pattern:ab|cd, match:ad
is_match:0

Input:func pattern str:

>> match a*b b 
func:match, pattern:a*b, match:b
is_match:1

Input:func pattern str:

>> match aa*b b 
func:match, pattern:aa*b, match:b
is_match:0

Input:func pattern str:

>> 

ここまではよかった。しかし、

Input:func pattern str:

>> match abc*def abqqdef
func:match, pattern:abc*def, match:abqqdef
is_match:1

Input:func pattern str:

>>

gdbでマッチング処理の箇所を引っかき回したが、さっぱり原因がわからず、コンパイル部分まで戻って見てみたら
繰り返しのNFAを作成する関数の中で遷移先のポインタをつなげる箇所が間違っていたとかそういうオチ。

とりあえず、マッチング処理はそのままで、そこだけ直したところ、

Input:func pattern str:

>> match abc*def abqqdef
func:match, pattern:abc*def, match:abqqdef
is_match:0

Input:func pattern str:

>> match abc*def abccdef
func:match, pattern:abc*def, match:abccdef
is_match:1

Input:func pattern str:

>> match abc*def abdef 
func:match, pattern:abc*def, match:abdef
is_match:1

Input:func pattern str:

>> 

ちょっと感動した。NFAからDFAへの変換はグルーピングを実装したらやってみる。

ちなみにNFAを構築するアルゴリズムにはドラゴンブックに載ってるThompsonの構成法を使ってます。
二つの正規表現RとSに対するNFAを構築する関数は↓のような感じ。
実際の処理では、文字列のポインタを一文字一文字進めながらNFAを再帰的に作成するようになってます。

RS

NFA *joinNFA(NFA *r, NFA *s){
  if(r->status == ACCEPT_STATE) {
    *r = *s;
  }
  else {
    r->next[0] = s;
  }

  // 閉包の最初と最後へのポインタを保持
  (*r).start = r;
  (*r).end   = (*s).next[0];
  return r;
}

R*

NFA *createReIteration(NFA *r){

  NFA *epsilon_start;
  NFA *epsilon_end;
  NFA *temp;

  epsilon_start = createNFA(EPSILON, MID_STATE);
  epsilon_end   = createNFA(EPSILON, MID_STATE);
  *temp = *r;
  temp->next[0] = epsilon_end;
  *epsilon_start->next[0] = *temp;
  epsilon_start->next[1]  = epsilon_end;
  *epsilon_end->next[0] = *temp;
  epsilon_end->next[1] = createNFA(' ', ACCEPT_STATE);

  // 閉包の最初と最後へのポインタを保持
  epsilon_start->start = epsilon_start;
  epsilon_start->end   = epsilon_end->next[1];
  *r = *epsilon_start;
  return epsilon_start;
}

R|S

NFA *createSelection(NFA *r, NFA *s){

  NFA *epsilon_start;
  NFA *epsilon_end;
  NFA temp;


  epsilon_start = createNFA(EPSILON, MID_STATE);
  epsilon_end   = createNFA(EPSILON, MID_STATE);
  (*r).next[0]  = epsilon_end;
  (*s).next[0]  = epsilon_end;
  temp = *r;
  memcpy(epsilon_start->next[0], &temp, sizeof(NFA));
  (*epsilon_start).next[1] = s;
  (*epsilon_end).next[0]   = createNFA(' ', ACCEPT_STATE);
  
  // 閉包の最初と最後へのポインタを保持
  (*epsilon_start).start = epsilon_start;
  (*epsilon_start).end   = (*epsilon_end).next[0];
  *r = *epsilon_start;
  return epsilon_start;
}

NFAの構造体と一つの文字に対してNFAを作成する関数はこんな感じ。

typedef struct nfa{
  char c;
  int name;
  int status;
  struct nfa *start;
  struct nfa *end;
  struct nfa *next[2];
}NFA;

NFA *createNFA(char c, int status){
  NFA *nfa;
  nfa = malloc(sizeof(NFA));
  (*nfa).c = c;
  (*nfa).status = status;
  if(status != ACCEPT_STATE){
    (*nfa).next[0] = malloc(sizeof(NFA));
    (*nfa).next[0]->status = ACCEPT_STATE;
  }
  return nfa;
}