📌 방법 1: NFA (Nondeterministic Finite Automaton) 기반

특징:
• 구현이 상대적으로 간단해
• 백트래킹을 사용해서 모든 가능성을 탐색
• 메모리 효율적이지만 최악의 경우 느릴 수 있어
• 캡처 그룹, 백레퍼런스 같은 고급 기능 구현이 쉬워

장점:
✅ 코드가 직관적이고 이해하기 쉬움
✅ 패턴 컴파일 속도가 빠름
✅ 복잡한 기능 추가가 용이함

단점:
❌ 특정 패턴에서 지수적 시간 복잡도 가능
❌ 최악의 경우 성능 예측이 어려움

📌 방법 2: DFA (Deterministic Finite Automaton) 기반

특징:
• 각 상태에서 다음 상태가 명확하게 결정돼
• 백트래킹 없이 선형 시간에 매칭
• 메모리를 더 많이 사용하지만 예측 가능한 성능
• 구현이 복잡하고 일부 고급 기능 구현이 어려워

장점:
✅ 매칭 속도가 항상 O(n) - 입력 길이에 비례
✅ 성능 예측이 정확함
✅ 대용량 텍스트 처리에 유리

단점:
❌ 상태 폭발 문제 - 메모리 사용량이 클 수 있음
❌ 구현 복잡도가 높음
❌ 백레퍼런스 같은 기능 구현 불가

📍 + (1회 이상 반복) 구현

// + 메타문자 처리 함수
int matchplus(int c, char *regexp, char *text) {
    // 최소 1회는 매칭되어야 함
    if (*text != '\0' && matchchar(c, text)) {
        text++;
        // 이후는 * 처럼 동작
        do {
            if (matchhere(regexp, text))
                return 1;
        } while (*text != '\0' && matchchar(c, text++));
    }
    return 0;
}

// matchhere 함수에 추가
if (regexp[1] == '+')
    return matchplus(regexp[0], regexp + 2, text);

📍 ? (0회 또는 1회) 구현

// ? 메타문자 처리 함수
int matchquestion(int c, char *regexp, char *text) {
    // 0회 매칭 시도
    if (matchhere(regexp, text))
        return 1;
    
    // 1회 매칭 시도
    if (*text != '\0' && matchchar(c, text))
        return matchhere(regexp, text + 1);
    
    return 0;
}

// matchhere 함수에 추가
if (regexp[1] == '?')
    return matchquestion(regexp[0], regexp + 2, text);

📍 [] (문자 클래스) 구현

// 문자 클래스 매칭 검사
int matchcharclass(char *pattern, char *text) {
    int negate = 0;
    int match = 0;
    
    if (*text == '\0')
        return 0;
    
    // [^...] 형태 - 부정
    if (*pattern == '^') {
        negate = 1;
        pattern++;
    }
    
    // ] 까지 문자들 검사
    while (*pattern != ']' && *pattern != '\0') {
        // 범위 표현 (예: a-z)
        if (pattern[1] == '-' && pattern[2] != ']' && pattern[2] != '\0') {
            if (*text >= pattern[0] && *text <= pattern[2])
                match = 1;
            pattern += 3;
        } else {
            if (*text == *pattern)
                match = 1;
            pattern++;
        }
    }
    
    return negate ? !match : match;
}

// matchhere 함수에 추가
if (regexp[0] == '[') {
    char *end = strchr(regexp, ']');
    if (end != NULL) {
        if (matchcharclass(regexp + 1, text))
            return matchhere(end + 1, text + 1);
        return 0;
    }
}

🚀 1. 패턴 사전 컴파일

같은 패턴을 여러 번 사용한다면, 매번 파싱하는 건 비효율적이야. 패턴을 한 번만 컴파일해서 재사용하자!

// 컴파일된 패턴 구조체
typedef struct {
    char *original;           // 원본 패턴
    int *bytecode;            // 컴파일된 바이트코드
    int bytecode_len;         // 바이트코드 길이
    int flags;                // 옵션 플래그
} CompiledPattern;

// 패턴 컴파일 함수
CompiledPattern* compile_pattern(char *regexp, int flags) {
    CompiledPattern *cp = malloc(sizeof(CompiledPattern));
    cp->original = strdup(regexp);
    cp->flags = flags;
    
    // 패턴을 바이트코드로 변환
    // (실제 구현은 복잡하지만 개념은 간단해)
    cp->bytecode = parse_to_bytecode(regexp, &cp->bytecode_len);
    
    return cp;
}

// 컴파일된 패턴으로 매칭
int match_compiled(CompiledPattern *cp, char *text) {
    return execute_bytecode(cp->bytecode, cp->bytecode_len, text);
}

// 사용 예시
CompiledPattern *email_pattern = compile_pattern(
    "[a-zA-Z0-9]+@[a-zA-Z0-9]+\\.[a-z]+", 0
);

// 여러 텍스트에 재사용
match_compiled(email_pattern, "test@example.com");
match_compiled(email_pattern, "user@domain.org");

🚀 2. 메모이제이션 (Memoization)

같은 (패턴 위치, 텍스트 위치) 조합을 여러 번 검사하는 걸 방지하자!

#define MEMO_SIZE 1024

// 메모이제이션 테이블
typedef struct {
    char *regexp_pos;
    char *text_pos;
    int result;
    int valid;
} MemoEntry;

MemoEntry memo_table[MEMO_SIZE];

// 해시 함수
unsigned int memo_hash(char *regexp, char *text) {
    unsigned long h = 5381;
    h = ((h << 5) + h) + (unsigned long)regexp;
    h = ((h << 5) + h) + (unsigned long)text;
    return h % MEMO_SIZE;
}

// 메모이제이션을 사용하는 matchhere
int matchhere_memo(char *regexp, char *text) {
    unsigned int hash = memo_hash(regexp, text);
    
    // 캐시 확인
    if (memo_table[hash].valid &&
        memo_table[hash].regexp_pos == regexp &&
        memo_table[hash].text_pos == text) {
        return memo_table[hash].result;
    }
    
    // 실제 매칭 수행
    int result = matchhere(regexp, text);
    
    // 결과 캐싱
    memo_table[hash].regexp_pos = regexp;
    memo_table[hash].text_pos = text;
    memo_table[hash].result = result;
    memo_table[hash].valid = 1;
    
    return result;
}

이 기법은 특히 복잡한 패턴에서 엄청난 성능 향상을 가져와! 🎊

🚀 3. 조기 종료 최적화

매칭이 불가능한 경우를 빨리 판단해서 불필요한 연산을 줄이자!

// 패턴 분석 정보
typedef struct {
    int min_length;           // 최소 매칭 길이
    int max_length;           // 최대 매칭 길이 (-1이면 무제한)
    char first_chars[256];    // 가능한 첫 문자들
    int has_anchor;           // ^ 또는 $ 포함 여부
} PatternInfo;

// 패턴 사전 분석
PatternInfo analyze_pattern(char *regexp) {
    PatternInfo info = {0};
    
    // 최소/최대 길이 계산
    // 가능한 첫 문자 집합 구축
    // 앵커 존재 여부 확인
    
    return info;
}

// 최적화된 매칭
int match_optimized(char *regexp, char *text, PatternInfo *info) {
    int text_len = strlen(text);
    
    // 텍스트가 너무 짧으면 즉시 실패
    if (text_len < info->min_length)
        return 0;
    
    // 첫 문자 빠른 검사
    if (info->first_chars[(unsigned char)*text] == 0)
        return 0;
    
    // 실제 매칭 수행
    return match(regexp, text);
}

🧪 테스트 프레임워크 구축

// 테스트 케이스 구조체
typedef struct {
    char *pattern;
    char *text;
    int expected;
    char *description;
} TestCase;

// 테스트 실행 함수
void run_tests(TestCase *tests, int count) {
    int passed = 0;
    int failed = 0;
    
    printf("=== 정규표현식 엔진 테스트 ===\n\n");
    
    for (int i = 0; i < count; i++) {
        int result = match(tests[i].pattern, tests[i].text);
        int success = (result == tests[i].expected);
        
        if (success) {
            passed++;
            printf("✓ ");
        } else {
            failed++;
            printf("✗ ");
        }
        
        printf("테스트 %d: %s\n", i + 1, tests[i].description);
        printf("  패턴: \"%s\", 텍스트: \"%s\"\n", 
               tests[i].pattern, tests[i].text);
        printf("  예상: %d, 결과: %d\n\n", 
               tests[i].expected, result);
    }
    
    printf("=== 테스트 결과 ===\n");
    printf("통과: %d/%d\n", passed, count);
    printf("실패: %d/%d\n", failed, count);
    printf("성공률: %.1f%%\n", (passed * 100.0) / count);
}

// 테스트 케이스 정의
TestCase basic_tests[] = {
    {"abc", "abc", 1, "정확한 문자열 매칭"},
    {"abc", "abcd", 1, "부분 문자열 매칭"},
    {"abc", "xabc", 1, "중간에 패턴 존재"},
    {"abc", "ab", 0, "불완전한 매칭"},
    {"^abc", "abc", 1, "문자열 시작 앵커"},
    {"^abc", "xabc", 0, "시작 앵커 실패"},
    {"abc$", "abc", 1, "문자열 끝 앵커"},
    {"abc$", "abcd", 0, "끝 앵커 실패"},
    {"a.c", "abc", 1, "점 메타문자"},
    {"a.c", "axc", 1, "점 메타문자 (다른 문자)"},
    {"a*b", "b", 1, "별표 0회 반복"},
    {"a*b", "ab", 1, "별표 1회 반복"},
    {"a*b", "aaab", 1, "별표 여러 번 반복"},
    {"a+b", "b", 0, "플러스 0회 실패"},
    {"a+b", "ab", 1, "플러스 1회 성공"},
    {"a?b", "b", 1, "물음표 0회"},
    {"a?b", "ab", 1, "물음표 1회"},
    {"[abc]", "a", 1, "문자 클래스 매칭"},
    {"[abc]", "d", 0, "문자 클래스 불일치"},
    {"[a-z]", "m", 1, "범위 표현"},
};

int main() {
    run_tests(basic_tests, sizeof(basic_tests) / sizeof(TestCase));
    return 0;
}

🔍 디버깅 도구 만들기

// 디버그 모드 플래그
int debug_mode = 0;

// 디버그 출력 함수
void debug_print(int level, char *format, ...) {
    if (!debug_mode)
        return;
    
    // 들여쓰기로 재귀 깊이 표현
    for (int i = 0; i < level; i++)
        printf("  ");
    
    va_list args;
    va_start(args, format);
    vprintf(format, args);
    va_end(args);
    printf("\n");
}

// 디버그 정보를 출력하는 matchhere
int matchhere_debug(char *regexp, char *text, int level) {
    debug_print(level, "matchhere(\"%s\", \"%s\")", regexp, text);
    
    if (regexp[0] == '\0') {
        debug_print(level, "→ 패턴 끝 도달, 성공!");
        return 1;
    }
    
    if (regexp[1] == '*') {
        debug_print(level, "→ * 메타문자 처리");
        return matchstar_debug(regexp[0], regexp + 2, text, level + 1);
    }
    
    if (regexp[0] == '$' && regexp[1] == '\0') {
        int result = (*text == '\0');
        debug_print(level, "→ $ 앵커: %s", result ? "성공" : "실패");
        return result;
    }
    
    if (*text != '\0' && matchchar(regexp[0], text)) {
        debug_print(level, "→ '%c' 매칭 성공, 다음으로", *text);
        return matchhere_debug(regexp + 1, text + 1, level + 1);
    }
    
    debug_print(level, "→ 매칭 실패");
    return 0;
}

// 사용 예시
int main() {
    debug_mode = 1;  // 디버그 모드 활성화
    
    printf("=== 디버그 추적 ===\n\n");
    match_debug("a*b", "aaab");
    
    return 0;
}

이렇게 하면 매칭 과정을 단계별로 볼 수 있어서 문제를 찾기가 훨씬 쉬워져! 🎯

🧠 1. Thompson의 NFA 구성 알고리즘

Ken Thompson이 개발한 이 알고리즘은 정규표현식을 NFA로 변환하는 가장 우아한 방법이야. 핵심 아이디어는 각 정규표현식 연산자를 작은 NFA 조각으로 만들고, 이들을 조합하는 거지.

// NFA 상태 구조체
typedef struct State {
    int c;                    // 매칭할 문자 (특수값: SPLIT, MATCH)
    struct State *out;        // 다음 상태
    struct State *out1;       // 분기 상태 (SPLIT용)
    int lastlist;             // 방문 표시용
} State;

#define SPLIT 256
#define MATCH 257

// NFA 프래그먼트
typedef struct Frag {
    State *start;
    State **out;              // 아직 연결 안 된 출력들
} Frag;

// 기본 문자 NFA 생성
Frag char_frag(int c) {
    State *s = new_state(c, NULL, NULL);
    Frag f = {s, &s->out};
    return f;
}

// 연결 (concatenation)
Frag cat_frag(Frag f1, Frag f2) {
    patch(f1.out, f2.start);  // f1의 출력을 f2의 시작에 연결
    return (Frag){f1.start, f2.out};
}

// 선택 (alternation) - |
Frag alt_frag(Frag f1, Frag f2) {
    State *s = new_state(SPLIT, f1.start, f2.start);
    return (Frag){s, append(f1.out, f2.out)};
}

// 반복 (repetition) - *
Frag star_frag(Frag f) {
    State *s = new_state(SPLIT, f.start, NULL);
    patch(f.out, s);          // 출력을 다시 시작으로
    return (Frag){s, &s->out1};
}

이 방식의 장점은 패턴을 한 번만 스캔하면서 NFA를 만들 수 있다는 거야! 시간 복잡도가 O(n)이지. 😎

🔄 2. NFA에서 DFA로 변환 (Subset Construction)

NFA는 구현이 쉽지만 느릴 수 있어. DFA로 변환하면 매칭 속도가 훨씬 빨라져!

// DFA 상태
typedef struct DFAState {
    int *nfa_states;          // 포함된 NFA 상태들
    int num_states;
    struct DFAState *next[256]; // 각 문자에 대한 전이
    int is_match;             // 매칭 상태 여부
} DFAState;

// epsilon 클로저 계산
void epsilon_closure(int *nfa_states, int *result, int *result_size) {
    // NFA 상태들에서 epsilon 전이로 도달 가능한 모든 상태 찾기
    // (구현 생략)
}

// NFA를 DFA로 변환
DFAState* nfa_to_dfa(State *start) {
    DFAState *dfa_start = malloc(sizeof(DFAState));
    
    // 시작 상태의 epsilon 클로저 계산
    epsilon_closure(&start, dfa_start->nfa_states, &dfa_start->num_states);
    
    // BFS로 모든 DFA 상태 생성
    Queue *q = queue_create();
    queue_push(q, dfa_start);
    
    while (!queue_empty(q)) {
        DFAState *current = queue_pop(q);
        
        // 각 입력 문자에 대해
        for (int c = 0; c < 256; c++) {
            // 전이 가능한 NFA 상태들 찾기
            int *next_nfa = find_transitions(current->nfa_states, c);
            
            if (next_nfa) {
                // 새 DFA 상태 생성 또는 기존 상태 재사용
                DFAState *next_dfa = get_or_create_dfa_state(next_nfa);
                current->next[c] = next_dfa;
                
                if (!next_dfa->visited) {
                    queue_push(q, next_dfa);
                    next_dfa->visited = 1;
                }
            }
        }
    }
    
    return dfa_start;
}

DFA는 메모리를 더 쓰지만, 매칭 속도가 정말 빨라! 특히 같은 패턴을 여러 번 사용할 때 효과적이야. 💨

🎯 3. 백레퍼런스와 캡처 그룹

진짜 강력한 기능! 매칭된 부분을 나중에 다시 참조할 수 있어.

// 캡처 그룹 정보
typedef struct {
    int group_num;
    char *start;
    char *end;
} CaptureGroup;

// 백레퍼런스를 지원하는 매칭
int match_with_backrefs(char *regexp, char *text, CaptureGroup *groups, int *group_count) {
    // (pattern) - 캡처 그룹
    if (*regexp == '(') {
        char *group_start = text;
        char *pattern_end = find_matching_paren(regexp);
        
        // 그룹 내부 패턴 매칭
        if (match_with_backrefs(regexp + 1, text, groups, group_count)) {
            // 캡처 저장
            groups[*group_count].group_num = *group_count + 1;
            groups[*group_count].start = group_start;
            groups[*group_count].end = text;
            (*group_count)++;
            
            // 그룹 이후 계속
            return match_with_backrefs(pattern_end + 1, text, groups, group_count);
        }
        return 0;
    }
    
    // \1, \2 등 - 백레퍼런스
    if (*regexp == '\\' && isdigit(regexp[1])) {
        int group_num = regexp[1] - '0';
        
        if (group_num <= *group_count) {
            CaptureGroup *ref = &groups[group_num - 1];
            int len = ref->end - ref->start;
            
            // 캡처된 내용과 동일한지 확인
            if (strncmp(text, ref->start, len) == 0) {
                return match_with_backrefs(regexp + 2, text + len, groups, group_count);
            }
        }
        return 0;
    }
    
    // 일반 매칭 계속...
}

// 사용 예: 중복 단어 찾기
// 패턴: \b(\w+)\s+\1\b
// "the the" 같은 중복 단어를 찾을 수 있어!

🔍 프로젝트 1: 코드 검색 도구

소스 코드에서 특정 패턴을 찾는 도구를 만들어봐. grep 같은 거지만 더 똑똑하게!

// 기능 아이디어:
// - 함수 정의 찾기
// - TODO 주석 추출
// - 사용되지 않는 변수 찾기
// - 코딩 스타일 검사

void search_code_patterns(char *directory, char *pattern) {
    // 디렉토리 순회
    // 각 파일에서 패턴 검색
    // 결과를 파일명:라인번호:내용 형식으로 출력
}

📊 프로젝트 2: 로그 분석기

서버 로그를 분석해서 유용한 정보를 추출하는 도구!

// 기능 아이디어:
// - 에러 패턴 감지
// - 접속 통계 생성
// - 이상 패턴 알림
// - 성능 병목 지점 찾기

typedef struct {
    int total_requests;
    int error_count;
    int unique_ips;
    double avg_response_time;
} LogStats;

LogStats analyze_logs(char *logfile, char **patterns, int pattern_count);

✉️ 프로젝트 3: 이메일 필터

스팸 메일을 걸러내거나 중요한 메일을 분류하는 시스템!

// 기능 아이디어:
// - 스팸 패턴 감지
// - 발신자 화이트리스트/블랙리스트
// - 키워드 기반 자동 분류
// - 우선순위 자동 설정

typedef enum {
    CATEGORY_SPAM,
    CATEGORY_IMPORTANT,
    CATEGORY_NEWSLETTER,
    CATEGORY_PERSONAL,
    CATEGORY_WORK
} EmailCategory;

EmailCategory classify_email(char *subject, char *body, char *sender);

🔐 프로젝트 4: 데이터 마스킹 도구

민감한 정보를 자동으로 마스킹하는 도구!

// 기능 아이디어:
// - 주민등록번호 마스킹
// - 신용카드 번호 마스킹
// - 이메일 주소 부분 마스킹
// - 전화번호 마스킹

char* mask_sensitive_data(char *text, int mask_level) {
    // mask_level에 따라 마스킹 강도 조절
    // 0: 부분 마스킹 (예: 010-****-5678)
    // 1: 완전 마스킹 (예: ***-****-****)
    // 2: 해시로 대체
}