Thompson NFA 구현 이해하기

AI.md

정규표현식 NFA 엔진 요약

오토마타 (Automata)

상태(state) + 전이(transition)로 구성된 추상 기계. 입력을 읽으며 상태 이동, 최종 상태가 수락 상태면 매칭 성공.

[상태A] --입력--> [상태B] --입력--> [수락상태]

---

DFA vs NFA

	DFA	NFA
각 입력에 대한 다음 상태	정확히 1개	0개, 1개, 또는 여러 개
ε-전이	없음	있음
현재 상태	항상 1개	여러 개 동시 가능
구현	단순	시뮬레이션 필요

ε-전이: 입력 소비 없이 다른 상태로 이동. a*에서 "0번 매칭" 경로가 이것.

NFA가 정규표현식에 적합한 이유: 패턴 → NFA 변환이 직관적. |는 분기, *는 루프로 자연스럽게 대응.

---

NFA 시뮬레이션

왜 "시뮬레이션"인가: NFA는 "동시에 여러 상태"라는 비물리적 개념. 실제 컴퓨터는 한 번에 한 상태만 처리 가능. 따라서 NFA의 동작을 결정적 알고리즘으로 흉내내는 것.

백트래킹

한 경로 선택 → 끝까지 탐색 → 실패 시 되돌아가서 다른 경로.

경로1 시도 → 실패 → 경로2 시도 → 실패 → ...

문제: 경로 수가 지수적 폭발 가능. a?{n}a{n} 패턴에서 O(2^n).

그럼에도 대부분 언어가 채택한 이유: 역참조(\1), lookahead 등 확장 기능 지원 필요. 이건 순수 NFA로 불가능. 메모이제이션도 캡처 내용이 키에 포함되어 효과 없음.

Thompson 알고리즘

모든 가능한 상태를 집합으로 동시 추적.

current = {가능한 상태들}
for ch in input:
    next = {current에서 ch로 전이 가능한 상태들의 ε-closure}
    current = next
return MATCH ∈ current

핵심 최적화 - list_id:

if s.lastlist == list_id:  # 이번 라운드에 이미 추가됨
    return                  # 중복 처리 안 함
s.lastlist = list_id

같은 상태에 100개 경로로 도달해도 한 번만 처리. O(nm) 보장.

메모이제이션 백트래킹과 비교:

• 시간복잡도 동일: O(nm)
• 공간: Thompson O(m), 메모이제이션 O(nm)
• Thompson이 더 효율적

---

주의: .는 연결 연산자

이 구현에서 .은 일반 정규식의 "아무 문자 매칭"이 아님.

일반 정규식: a.b  → a + (아무 문자) + b
이 코드:     ab.  → a와 b를 연결 (postfix 표기)

re2post()가 암묵적 연결을 명시적 . 연산자로 변환:

infix:   ab    →  postfix: ab.
infix:   abc   →  postfix: ab.c.

---

함수 흐름 요약

match(pattern, text)
  │
  ├─→ re2post(pattern)      // "a(b|c)*" → "abc|*.""
  │     infix → postfix 변환. 연결을 명시적 '.'로 삽입.
  │
  ├─→ post2nfa(postfix)     // postfix → NFA 그래프
  │     스택 기반. 리터럴/연산자마다 Fragment 조립.
  │     최종 Fragment의 매달린 엣지를 matchstate에 연결.
  │
  └─→ match(start, text)    // NFA 실행
        │
        ├─→ startlist()     // 초기 상태 집합 (ε-closure)
        │
        ├─→ step()          // 문자 하나 처리, 다음 상태 집합 계산
        │     내부에서 addstate() 호출 (ε-closure 포함)
        │
        └─→ ismatch()       // 최종 집합에 matchstate 있는지

---

C 코드 핵심 - 이론과의 대응

상태 표현

enum { Match = 256, Split = 257 };
struct State {
    int c;           // 문자(0-255), Match, Split 중 하나
    State *out;      // 다음 상태
    State *out1;     // Split일 때 두 번째 분기
    int lastlist;    // 중복 방문 방지
};

• c < 256: 리터럴. 해당 문자 소비 후 out으로 전이.
• c == Split: ε-전이 2개. out과 out1로 동시 이동.
• c == Match: 수락 상태.

NFA 빌드 - Ptrlist 트릭

union Ptrlist {
    Ptrlist *next;
    State *s;
};

아직 연결 안 된 State* 포인터들을 linked list로 관리. 메모리 추가 할당 없이 포인터 자체를 저장소로 재활용.

patch(e.out, s);  // 매달린 포인터들에 실제 상태 주소 기록

NFA 실행

void addstate(List *l, State *s) {
    if (s == NULL || s->lastlist == listid) return;  // 중복 방지
    s->lastlist = listid;
    if (s->c == Split) {
        addstate(l, s->out);   // ε-전이 따라감
        addstate(l, s->out1);
        return;
    }
    l->s[l->n++] = s;  // 실제 문자 상태만 리스트에 추가
}

NFA.py

# 원본 링크: https://swtch.com/~rsc/regexp/nfa.c.txt
# 원본 C코드는 이해하기 어려워서 Python으로 변환한 코드

# =========================
# constants
# =========================
# 0–255는 문자용. 256, 257은 특수 상태.
# ASCII만 다룬다면 128, 129로 줄여도 됨.
STATE_MATCH = 256  # 매칭 성공 상태
STATE_SPLIT = 257  # ε-전이 분기 상태


# =========================
# NFA state
# =========================
class State:
    """NFA의 단일 상태."""
    def __init__(self, char_code: int, out_edge: 'State' = None, out_edge1: 'State' = None):
        self.char_code = char_code  # 문자(0-255), MATCH, SPLIT 중 하나
        self.out_edge = out_edge    # 다음 상태 (전이)
        self.out_edge1 = out_edge1  # SPLIT일 때 두 번째 분기
        self.lastlist = 0           # 중복 방문 방지용 마킹


# =========================
# fragment (build-time only)
# =========================
class Fragment:
    """NFA 빌드 중 사용하는 조각. postfix_to_nfa 스택에서만 씀."""
    def __init__(self, start: 'State', out_states: list['State']):
        self.start = start          # 이 조각의 시작 상태
        self.out_states = out_states  # 아직 연결 안 된 매달린 상태들


# =========================
# infix -> postfix
# =========================
def re2post(pattern: str) -> str | None:
    """
    정규식을 postfix로 변환. 암묵적 연결을 '.'로 명시화.
    예: "ab" -> "ab.", "a|b" -> "ab|", "a*b" -> "a*b."
    실패 시 None 반환.
    """
    output: list[str] = []
    stack: list[tuple[int, int]] = []  # 괄호 진입 시 (nalt, natom) 저장

    nalt = 0   # 현재 레벨의 | 개수
    natom = 0  # 현재 레벨의 피연산자 개수

    for ch in pattern:
        match ch:
            case '(':
                # 연결 보류, 현재 상태 저장 후 새 레벨 시작
                if natom > 1:
                    natom -= 1
                    output.append('.')
                stack.append((nalt, natom))
                nalt = natom = 0

            case '|':
                # 지금까지의 원자들 연결 후 alternation 카운트
                if natom == 0:
                    return None
                while natom > 1:
                    natom -= 1
                    output.append('.')
                nalt += 1
                natom = 0

            case ')':
                # 괄호 내부 마무리: 연결 → alternation → 이전 레벨 복원
                if not stack or natom == 0:
                    return None
                while natom > 1:
                    natom -= 1
                    output.append('.')
                while nalt > 0:
                    output.append('|')
                    nalt -= 1
                nalt, natom = stack.pop()
                natom += 1  # 괄호 전체가 하나의 원자

            case '*':
                # 단항 연산자: 바로 출력
                if natom == 0:
                    return None
                output.append('*')

            case _:
                # 리터럴: 이전 원자와 연결 필요하면 '.' 추가
                if natom > 1:
                    natom -= 1
                    output.append('.')
                output.append(ch)
                natom += 1

    if stack:  # 괄호 안 닫힘
        return None

    # 남은 연결과 alternation 처리
    while natom > 1:
        natom -= 1
        output.append('.')
    while nalt > 0:
        output.append('|')
        nalt -= 1

    return ''.join(output)


# =========================
# postfix -> NFA (Thompson)
# =========================
def postfix_to_nfa(postfix: str) -> State:
    """
    postfix 정규식을 NFA 그래프로 변환 (Thompson 구성법).
    스택에 Fragment 쌓으면서 연산자마다 조립.
    최종 Fragment를 MATCH 상태에 연결 후 시작 상태 반환.
    """
    stack: list[Fragment] = []

    for ch in postfix:
        match ch:
            case '.':  # 연결: frag1 뒤에 frag2 붙임
                frag2 = stack.pop()
                frag1 = stack.pop()
                for s in frag1.out_states:
                    s.out_edge = frag2.start
                stack.append(Fragment(frag1.start, frag2.out_states))

            case '|':  # 선택: SPLIT에서 양쪽으로 분기
                frag2 = stack.pop()
                frag1 = stack.pop()
                s = State(STATE_SPLIT, frag1.start, frag2.start)
                stack.append(Fragment(s, frag1.out_states + frag2.out_states))

            case '*':  # 반복: SPLIT → frag → 다시 SPLIT (루프)
                frag = stack.pop()
                s = State(STATE_SPLIT, frag.start, None)  # out1은 탈출용
                for st in frag.out_states:
                    st.out_edge = s  # frag 끝에서 SPLIT으로 복귀
                stack.append(Fragment(s, [s]))  # s.out_edge1이 매달린 엣지

            case _:  # 리터럴: 단일 상태 생성
                s = State(ord(ch))
                stack.append(Fragment(s, [s]))

    # 최종 조립: 매달린 엣지들을 MATCH에 연결
    frag = stack.pop()
    match_state = State(STATE_MATCH)
    for s in frag.out_states:
        s.out_edge = match_state

    return frag.start


# =========================
# NFA execution (list + id)
# =========================
list_id = 0  # 전역 세대 카운터. 매 상태 집합 생성 시 증가.


def add_state(states: list[State], s: State) -> None:
    """
    상태 s를 states에 추가. ε-전이(SPLIT)는 재귀적으로 따라감.
    list_id로 같은 라운드 내 중복 방문 방지.
    """
    global list_id

    if s is None or s.lastlist == list_id:
        return  # None이거나 이미 이번 라운드에 추가됨

    s.lastlist = list_id
    states.append(s)

    if s.char_code == STATE_SPLIT:  # ε-전이: 양쪽 재귀 탐색
        add_state(states, s.out_edge)
        add_state(states, s.out_edge1)


def nfa_match(start: State, text: str) -> bool:
    """
    NFA 시뮬레이션. 입력 문자마다 상태 집합 전이.
    모든 문자 소비 후 MATCH 상태 포함 여부로 판정.
    """
    global list_id

    # 초기 상태 집합: start의 ε-closure
    current: list[State] = []
    list_id += 1
    add_state(current, start)

    # 각 문자 처리
    for ch in text:
        next_states: list[State] = []
        list_id += 1

        for s in current:
            if s.char_code == ord(ch):  # 이 문자로 전이 가능?
                add_state(next_states, s.out_edge)

        current = next_states

    # 최종 상태에 MATCH 있으면 성공
    return any(s.char_code == STATE_MATCH for s in current)


# =========================
# public API
# =========================
def match(pattern: str, text: str) -> bool:
    """정규식 pattern이 text 전체와 매칭되는지 검사."""
    postfix = re2post(pattern)
    if postfix is None:
        raise ValueError("invalid regex")

    start = postfix_to_nfa(postfix)
    return nfa_match(start, text)


# =========================
# tests
# =========================
def run_tests() -> None:
    tests = [
        ("a", "a", True),
        ("a", "b", False),
        ("ab", "ab", True),
        ("a|b", "b", True),
        ("a*", "", True),
        ("a*", "aaa", True),
        ("(ab)*", "abab", True),
        ("a(b|c)*", "abcbcbc", True),
        ("a(b|c)*", "accc", True),
        ("a(b|c)*", "b", False),
    ]

    for pat, text, expected in tests:
        result = match(pat, text)
        print(f"{pat!r:10} {text!r:10} -> {result} (expected {expected})")


if __name__ == "__main__":
    run_tests()