regMatch  正規表現による文字列照合アルゴリズム
regNew    文字列照合のための非決定性オートマトンの作成

文字列照合
    char *regMatch(char *text, int len, PAIR *nda);

非決定性オートマトンの作成
    PAIR *regNew(char *pattern, int patlen);

文字列照合関数において
    text     （入力）テキスト
    len      （入力）テキストの長さ
    nda      （入力）照合パターンに対応した非決定性オートマトン

非決定性オートマトンの作成関数において
    pattern  （入力）照合パターン
    patlen   （入力）照合パターンの長さ

文字列照合関数について
    照合パターンがテキストから見つかった場合はそのポインタ、
    見つからなかった場合は 0 (NULL)。

非決定性オートマトンの作成関数について
    作成した非決定性オートマトン。作成できなかったときは 0 (NULL)。

regNew() を呼び出して非決定性オートマトンを作成した後、
regMatch() を利用して文字列照合を行う。

typedef struct _node {
    int    pass;
    int    reach;
    struct _edge *edge;
} NODE;

typedef struct _edge {
    int    c;
    struct _node *target;
    struct _edge *next;
} EDGE;

typedef struct _pair {
    NODE   *start;
    NODE   *end;
} PAIR;

typedef enum { END, SYMBOL, AND, OR, CLOSURE, LP, RP } TOKEN;
#define EPSILON  -1

#include "regMatch.h"

static int    nc;
static TOKEN  token;
static char   *pat, *patEnd;

static void getToken(void)
{
    if (pat == patEnd) {
        token = END;
        return;
    }

    switch (*pat) {
    case '|': token = OR;      break;
    case '*': token = CLOSURE; break;
    case '(': token = LP;      break;
    case ')': token = RP;      break;
    default:  token = SYMBOL;
        if (*pat == '\\' && pat+1 != patEnd) nc = *++pat;
        else nc = *pat;
    }
    pat++;
}

static NODE *newNode(void)
{
    NODE *node;
    
    if ((node = (NODE *)malloc(sizeof(NODE))) != NULL) {
        node->pass = 0;
        node->reach = 0;
        node->edge = NULL;
    }
    return node;
}

static EDGE *link(NODE *start, NODE *end, int c)
{
    EDGE *edge;

    if ((edge = (EDGE *)malloc(sizeof(EDGE))) != NULL) {
        edge->c = c;
        edge->target = end;
        edge->next = start->edge;
        start->edge = edge;
    }
    return edge;
}

static int orNode(PAIR *ret,
    NODE *start1, NODE *end1, NODE *start2, NODE *end2)
{
    NODE *start, *end;

    start = newNode();
    end   = newNode();
    if (start == NULL || end == NULL) return -1;
    link(start, start1, EPSILON);
    link(start, start2, EPSILON);
    link(end1, end, EPSILON);
    link(end2, end, EPSILON);
    ret->start = start;
    ret->end   = end;
    return 0;
}

static int andNode(PAIR *ret,
    NODE *start1, NODE *end1, NODE *start2, NODE *end2)
{
    link(end1, start2, EPSILON);
    ret->start = start1;
    ret->end   = end2;
    return 0;
}

static int closureNode(PAIR *ret, NODE *start1, NODE *end1)
{
    NODE *start, *end;
    
    start = newNode();
    end   = newNode();
    if (start == NULL || end == NULL) return -1;
    link(start, start1, EPSILON);
    link(end1, end, EPSILON);
    link(start, end, EPSILON);
    link(end1, start1, EPSILON);
    ret->start = start;
    ret->end   = end;
    return 0;
}

static int basicExpr(PAIR *ret)
{
    NODE *start, *end;

    if (token == SYMBOL || token == RP || token == OR) {
        start = newNode();
        end   = newNode();
        if (start == NULL || end == NULL) return -1;
        if (token == SYMBOL) {
            link(start, end, nc);
            getToken();
        } else link(start, end, EPSILON);
        ret->start = start;
        ret->end   = end;
    } else if (token == LP) {
        getToken();
        if (orExpr(ret) != 0) return -1;
        if (token != RP) return -1;
        getToken();
   } else return -1;
    return 0;
}

static int closureExpr(PAIR *ret)
{
    if (basicExpr(ret) != 0) return -1;
    while (token == CLOSURE) {
        if (closureNode(ret, ret->start, ret->end) != 0) return -1;
        getToken();
    }
    return 0;
}

static int andExpr(PAIR *ret)
{
    PAIR tmp;

    if (closureExpr(ret) != 0) return -1;
    while (token == SYMBOL || token == LP) {
        if (closureExpr(&tmp) != 0) return -1;
        if (andNode(ret, ret->start, ret->end, 
                    tmp.start, tmp.end) != 0) return -1;
    }
    return 0;
}

static int orExpr(PAIR *ret)
{
    PAIR tmp;

    if (andExpr(ret) != 0) return -1;
    while (token == OR) {
        getToken();
        if (andExpr(&tmp) != 0) return -1;
        if (orNode(ret, ret->start, ret->end,
                   tmp.start, tmp.end) != 0) return -1;
    }
    return 0;
}

PAIR *regNew(char *pattern, int patlen)
{
    PAIR *nda;
    
    if ((nda = (PAIR *)malloc(sizeof(PAIR))) == NULL) return NULL;
    patEnd = pattern + patlen;
    pat = pattern;
    getToken();
    if (orExpr(nda) == 0 && token == END) return nda;
    return NULL;
}

static int stateTransit(NODE *node, int c, int reach, int pass)
{
    EDGE *edge;
    int  ret = -1;

    node->pass = pass;
    for (edge = node->edge; edge != NULL; edge = edge->next) {
        if (node->reach == reach && edge->c == c) {
             if (c == EPSILON && edge->target->reach != reach) {
                 edge->target->reach = reach;
                 stateTransit(edge->target, c, reach, pass);
                 ret = 0;
             } else if (c != EPSILON && edge->target->reach != reach+1) {
                 edge->target->reach = reach + 1;
                 stateTransit(edge->target, c, reach, pass);
                 ret = 0;
             }
        }
        if (edge->target->pass != pass) {
            if (stateTransit(edge->target, c, reach, pass) == 0) ret = 0;
        }
    }
    return ret;
}

char *regMatch(char *text, int len, PAIR *nda)
{
    int  k;
    char *p;
    static int pass  = 2;
    static int reach = 0;

    do {
        k = len;
        p = text++;
        nda->start->reach = ++reach;
        while (1) {
            stateTransit(nda->start, EPSILON, reach, pass++);
            if (nda->end->reach == reach) return text - 1;
            if (k-- == 0) break;
            if (stateTransit(nda->start, *p++, reach++, pass++) != 0)
                break;
        }
    } while (len-- != 0);
    return NULL;
}

このようなパターンの指定のことを正規表現(regular expression)と いう。より形式的に説明すると以下のようになる。ただし、PとQはい ずれも正規表現とする。

正規表現	意味（それに一致する文字列）
文字	その文字自身
\文字	その文字自身（特別記号 |、(、)、* 等を文字として使う場 合）
(P)	P
PQ	PとQをつなげたもの（連結、concatenation）
P|Q	PまたはQ（選択、union）
P*	Pの0回以上の繰り返し（閉包、closure）

連結と選択では、連結の方が優先度が高く、閉包はさらにそれよりも 高いである。

正規表現が与えられると、本アルゴリズムではそれをε遷移を含む 非決定性オートマトン（NonDeterministic Automaton）に変換した上で、 その非決定性オートマトンをシミュレートしながらテキストとの照合を 行う。

より高速に照合を行いたいときは、非決定性オートマトンをさらにそれと 等価な決定性オートマトンに変換することが考えられる。