범용 문맥 자유 파서(General Context-Free Parsers)에 대한 경험적 비교

파싱(Parsing)은 컴파일러(Compilers)와 정적 분석기(Static Analyzers)부터 언어 서버(Language Servers) 및 퍼징 테스트(Fuzz Testing) 도구에 이르기까지 방대한 범위의 소프트웨어 엔지니어링 작업의 근간을 이룹니다. 그러나 실제 현장에 배치된 대부분의 파서는 결정론적(Deterministic, LL 또는 LR) 방식이며, 이로 인해 개발자들은 파서에 맞추기 위해 문법(Grammars)을 왜곡해야 할 뿐만 아니라, 파싱 가능성(Parseability)을 위해 설계 중인 언어 자체의 표현력(Expressiveness)을 희생하며 단순화해야만 합니다. 범용 문맥 자유 파서(General Context-Free Parsers)는 이러한 제약을 제거합니다. 하지만 수십 년간의 알고리즘 개발에도 불구하고, 주요 파싱 알고리즘 계열 간의 엄격한 일대일 비교는 존재하지 않았습니다. 본 논문에서는 CYK, Valiant, Earley, GLL, RNGLR, BRNGLR의 6가지 범용 파싱 알고리즘과 결정론적 LL(1) 및 LR(1) 베이스라인을 포함하여, 최초의 통합된 통제 벤치마크를 제시합니다. 이들은 모두 공유 데이터 구조와 파스 트리(Parse-tree) 추출 기능을 갖춘 Rust 언어로 구현되었으며, 단순한 표현식부터 완전한 C++ 및 Java에 이르는 22개의 문법을 통해 평가되었습니다. 연구 결과, 범용성을 확보하는 데 드는 비용이 널리 알려진 것보다 낮다는 것을 보여줍니다. 결정론적 문법(Deterministic Grammars)에서 GLR 계열은 LR(1) 대비 중앙값 기준 3배의 속도 저하만을 보였으며, 분산(Variance) 또한 좁고 예측 가능했습니다. GLR은 범용 파서 중에서 명확한 성능 우위를 점하고 있으며, 소프트웨어 엔지니어링 도구를 위한 실용적인 기본 선택지(Default choice)입니다.