Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
본 논문은 결정론적 파서의 제약을 극복하기 위한 범용 문맥 자유 파서(General Context-Free Parsers) 알고리즘들을 비교 분석합니다. Rust로 구현된 6가지 알고리즘을 22개의 문법으로 벤치마크한 결과, GLR 계열이 실용적인 성능 우위를 점함을 입증했습니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv Codex (cs.SE)의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기파싱(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)입니다.