[논문] 일반 문맥 자유 파서들의 실증적 비교

출처: arXiv - 2606.08465v1

개요

파싱은 컴파일러와 정적 분석기부터 언어 서버, 퍼즈 테스트 도구에 이르기까지 광범위한 소프트웨어 엔지니어링 작업의 기반을 이룹니다. 그러나 실제로 사용되는 대부분의 파서는 결정적(LL 또는 LR)이며, 이는 개발자들이 파서에 맞추기 위해 문법을 억지로 변형하고, 설계하는 언어 자체를 단순화하여 표현력을 희생하게 만듭니다. 일반적인 문맥 자유 파서는 이러한 제약을 없애줍니다. 그럼에도 수십 년에 걸친 알고리즘 개발에도 불구하고, 주요 파싱 알고리즘 군을 직접 비교한 엄밀한 연구는 존재하지 않았습니다. 우리는 CYK, Valiant, Earley, GLL, RNGLR, BRNGLR 등 여섯 가지 일반 파싱 알고리즘과 결정적 LL(1)·LR(1) 기준을 Rust로 구현하고, 동일한 데이터 구조와 파스 트리 추출 방식을 공유하여 22개의 문법(간단한 식부터 전체 C++·Java까지)에서 평가한 최초의 통합·통제 벤치마크를 제시합니다. 결과는 일반성의 비용이 예상보다 낮다는 것을 보여줍니다. 결정적 문법에서는 GLR 계열이 LR(1) 대비 중간값 3배 정도의 지연만을 보이며, 변동 폭이 좁고 예측 가능합니다. GLR은 일반 파서 중 명확한 성능 우승자이며, 소프트웨어 엔지니어링 도구의 실용적인 기본 선택이 될 수 있습니다.

핵심 기여

이 논문은 다음 분야의 연구를 다룹니다.

• cs.FL
• cs.PF
• cs.PL
• cs.SE

방법론

자세한 방법론은 전체 논문을 참고하십시오.

실용적 함의

이 연구는 cs.FL 분야의 발전에 기여합니다.

저자

• Huan Vo
• Danushka Liyanage
• Hong Jin Kang
• Sasha Rubin
• Rahul Gopinath

논문 정보

• arXiv ID: 2606.08465v1
• 분류: cs.FL, cs.PF, cs.PL, cs.SE
• 발행일: 2026년 6월 7일
• PDF: PDF 다운로드