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)로 변환한 다음, 그 비결정성 자동 장치를 시뮬레이트 하면서 텍스트와의 조합을 실시한다.

보다 고속으로 조합을 실시하고 싶을 때는, 비결정성 자동 장치를 한층 더 그것과 등가인 결정성 자동 장치로 변환하는 것을 생각된다.