NFA를 이용한 정규표현식 구현

이 글은 톰슨의 구성을 사용하여 정규표현식을 구현하는 과정을 상세히 설명합니다. 정규표현식을 후위표현식으로 변환하고, 이를 바탕으로 NFA(Non-deterministic Finite Automata) state diagram을 만드는 핵심 단계를 다룹니다. Aho-corasick 알고리즘과의 유사점을 언급하며, tri 구조에서 state diagram으로의 발전된 자료 구조 사용을 강조합니다. 코드 예시와 함께 `split` 및 `match` 노드를 포함한 special node와 정규표현식 operator에 대응하는 NFA fragment를 시각적으로 제시하여 이해를 돕습니다. 특히, 파이썬으로 구현된 `post2nfa` 함수는 후위표현식을 state로 변환하는 방법을 설명하며, `re2post` 함수는 정규표현식을 후위표현식으로 변환하는 과정을 상세히 다룹니다. 마지막으로, graphviz를 사용하여 NFA diagram을 시각화하는 방법을 제시하며, 실제 정규표현식 예제에 대한 결과물을 제공합니다. 이 글을 통해 독자는 정규표현식 엔진의 핵심 원리를 이해하고, NFA를 이용한 패턴 매칭 구현에 대한 깊이 있는 통찰력을 얻을 수 있습니다.