기술 요약: 일반 문맥 자유 파서에 대한 경험적 비교

문제 정의

파싱은 컴파일러, 정적 분석기, 언어 서버, 퍼저를 포함한 소프트웨어 엔지니어링 도구의 기초적인 구성 요소입니다. 그러나 배포된 파서의 대다수는 결정론적 문맥 자유 언어의 부분 집합(LL 또는 LR)으로 제한되어 있습니다. 이러한 제약으로 인해 개발자들은 좌재귀(left recursion)를 제거하거나, 시프트-리듀스 충돌(shift-reduce conflicts)을 해결하거나, 파서의 제약을 충족시키기 위해 문법 구조를 변형하는 이른바 "문법 해킹(grammar hacking)"에 매달려야 합니다. 이 과정은 종종 언어의 표현력을 희생시키고, 유지보수 부담을 가중시키며, 결과적으로 개발자들이 미묘한 버그와 보안 취약점에 노출되기 쉬운 수작업 파서(hand-written parsers)를 선호하게 만듭니다.

모든 문맥 자유 문법을 수정 없이 수용할 수 있는 일반 문맥 자유 파서(예: CYK, Earley, GLR, GLL)에도 불구하고, 이들은 역사적으로 $O(n^3)$의 최악의 시간 복잡도 때문에 실용성이 없다는 평가를 받아왔습니다. 수십 년간의 알고 알고리즘 발전에도 불구하고, 주요 파싱 알고리즘 패밀리에 대한 엄격한 직접 비교 연구는 부재했습니다. 기존의 평가들은 구현 언어, 데이터 구조 또는 출력 표현 방식이 서로 달라 직접적인 비교가 불가능했습니다. 결과적으로, 일반화된 파싱이 지나치게 비용이 많이 든다는 오해는 여전히 해결되지 않은 채 남아 있습니다.

방법론

이러한 격차를 해소하기 위해, 저자들은 6가지 일반화된 파싱 알고리즘과 결정론적 LL(1) 및 LR(1) 베이스라인을 포함하는 통합된 통제된 벤치마크를 구현했습니다.

• 평가된 알고리즘:
  • 결정론적 베이스라인: LL(1) 및 LR(1).
  • 일반화된 (온라인, 탑다운): Earley 및 Generalized LL (GLL).
  • 일반화된 (온line, 바텀업): Right-Nulled GLR (RNGLR) 및 Binary RNGLR (BRNGLR).
  • 일반화된 (오프라인, 바텀업): CYK 및 Valiant (Method of Four Russians 사용).
• 구현: 구현상의 아티팩트를 제거하기 위해 모든 파서는 단일 프레임워크 내에서 Rust로 구현되었습니다. 이들은 동일한 문법 표현, 토큰 스트림 형식, AST 구조 및 메모리 관리 전략을 공유합니다. 모든 구현은 동일한 최적화 설정(--release)으로 컴파일되었습니다.
• 벤치마크: 단순 수식과 JSON부터 C++, Java, ANSI C, Pascal, SQL 등 전체 규모의 프로그래밍 언어에 이르는 22개의 문법을 평가했습니다.
  • 결정론적 베이스라인의 경우, 문법은 LL(1) 또는 LR(1) 제약을 충족하도록 재구성(좌재귀 제거, 좌인수화, 규칙 분할)되었습니다.
  • 일반화된 파서는 수정되지 않은 원래의 문법을 그대로 사용했습니다.
• 입력: 테스트 입력은 유계 깊이 문법 기반 퍼징(bounded-depth grammar-based fuzzing)을 통해 생성되었습니다. 가장 빠른 파서가 1초 이내에 완료될 수 있도록 입력 크기를 제한했습니다.
• 지표: 시스템 노이즈를 완화하기 위해 여러 반복 실행을 통해 중앙값 실행 시간(밀리초)과 피크 메모리 사용량(MB)을 측정했습니다.

주요 기여

1. 최초의 통합 벤치마크: 본 논문은 실제 소프트웨어 엔지니어링 문법에 대해 네 가지 알고리즘 패밀리(매트릭스 기반, 탑다운 온라인, 바텀업 온라인)에 걸친 6가지 일반화된 파싱 알고리즘의 통제된 비교를 제시합니다.
2. 재구성된 문법 분석: 동일한 언어를 인식하는 재구성된 문법에 대한 파서 성능을 상세히 비교하여, 문법 구조가 서로 다른 알고리즘 패밀리에 미치는 영향을 격리하여 분석했습니다.
3. 실무 지침: 소프트웨어 엔지니어링 도구 제작자가 일반화된 파싱을 기본으로 사용할지, 아니면 문법 해킹이 더 효율적일지에 대한 경험적 근거를 제공합니다.

결과

1. 오프라인 일반화 파서 (CYK 및 Valiant)

Valiant가 CYK($O(n^3)$)보다 우수한 점근적 복잡도($O(n^3 / \log n)$)를 가짐에도 불구하고, 실제로는 CYK보다 훨씬 느렸습니다 (예: 특정 입력에서 330배 느림). 두 오프라인 알고리즘 모두 100 토큰 미만의 입력에서도 비실용적인 것으로 나타났습니다. Earley가 두 오프라인 알고리즘보다 성능이 뛰어났으며, 이는 오프라인 매트릭스 곱셈 접근 방식이 일반적인 소프트웨어 엔지니어링 작업에는 적합하지 않음을 시사합니다.

2. 온라인 일반화 파서 (Earley, GLL, RNGLR, BRNGLR)

• RNGLR 및 BRNGLR: 이들은 일관되게 가장 빠른 일반화된 파서였으며, 일반적으로 GLL보다 23배 빠르고 Earley보다 410배 빨랐습니다. 두 알고리즘 간의 차이는 무시할 수 있는 수준이었습니다 (실행 시간 차이 15% 이내).
• GLL: 성능이 문법 구조에 매우 민다는 것을 보였습니다. GLL은 LL 친화적인(우재귀) 입력에서는 경쟁력이 있었으나, 좌재귀 문법(예: 좌재귀가 포함된 JSON)에서는 성능이 심각하게 저하되었습니다 (좌재귀 JSON에서 RNGLR보다 20배 느림).
• Earley: 모든 문법에서 일관되게 가장 느린 일반화된 파서였습니다.

3. 결정론적 vs. 일반화된 파서

• 런타임 오버헤드: 결정론적 문법에서 **GLR 패밀리 (RNGLR/BRNGLR)**는 LR(1) 대비 3배의 중앙값 속도 저하만을 기록했으며, 편차가 좁고 예측 가능했습니다 (사분위 범위 ±0.2배).
• GLL 변동성: GLL은 훨씬 높은 변동성을 보였습니다. 중앙값 6배의 오버헤드를 기록했으며, 좌재귀 문법에서는 최대 139배의 최악의 속도 저하를 보였습니다.
• 메모리: 결정론적 파서와 GLR 변형 모델들은 모든 입력 크기에 대해 무시할 수 있는 수준의 메모리 사용량(측정 하한선인 ~0.016 MB)을 유지했습니다. 반면, GLL은 상당한 메모리 증가(Pascal에서 최대 12.5 MB)를 보였으며, Earley는 GLR보다는 높지만 상대적으로 완만한 증가를 보였습니다.

4. 문법 재구성 (Grammar Hacking)

• 결정론적 이득: 문법을 LL(1) 또는 LR(1)로 재구성하면 특정 문법 형태에 대한 최적의 일반화된 파서보다 일관되게 4~7배의 속도 향상을 얻을 수 있었습니다.
• 구조적 민감도: 문법 구조는 일반화된 파서에 큰 영향을 미칩니다. RNGLR은 좌재귀에서 이득을 얻지만 우재귀에서는 성능이 저하되는 반면, GLL은 그 반대로 동작합니다. LL(1)을 만족하도록 문법을 재구성(우재귀 도입)하는 행위는 의도치 않게 GLR 파서를 저하시키는 동시에 GLL을 돕게 될 수 있습니다.
• 모호성: 재귀 규칙에 모호성을 추가하더라도 기저의 재귀 구조가 고정되어 있다면 일반화된 파서의 런타임에 미미한 영향만을 주었습니다.

의의 및 주장

본 논문은 일반성의 비용이 널리 알려진 것보다 낮다고 주장합니다. 구체적으로:

• GLR은 실용적인 기본값임: 일반화된 파서 중에서 GLR 패밀리(RNGLR/BRNGLR)는 속도와 메모리 효율성 측면에서 최적의 조합을 제공합니다. LR(1) 대비 3배의 중앙값 오버헤드는 광범위한 소프트웨어 엔지니어링 도구(컴파일러, 언어 서버, 정적 분석기)에 수용 가능한 수준입니다.
• 문법 해킹의 트레이드오프: 문법 해킹을 통해 결정론적 파싱을 활성화함으로써 상당한 성능 이득(4~7배)을 얻을 수 있지만, 이는 유지보수 비용과 취약성을 동반합니다. 저자들은 대부분의 도구에서 적절한 GLR 오버헤드가 재구성된 문법의 복잡성을 감수하는 것보다 낫다고 제안합니다.
• 알고리즘 선택 가이드:
  • RNGLR/BRNGLR: 문법의 유연성을 우선시하는 도구에 권장됩니다.
  • LL(1)/LR(1): 문법을 엄격하게 결정론적으로 유지할 수 있는 경우, 최대 처리량이 필요한 도구에만 권장됩니다.
  • GLL: 탑다운 아키텍처 스타일이 반드시 필요한 경우 합리적인 대안이 될 수 있으나, 좌재귀의 함정을 피하기 위해 문법 형태를 신중하게 선택해야 합니다.
  • Earley/CYK/Valiant: 성능이 낮거나 비실용적이므로 본 문맥에서의 프로덕션 사용을 권장하지 않습니다.

본 연구는 특히 GLR을 중심으로 한 일반화된 파싱이 안전하고 효율적인 기본값이며, 이를 통해 제한적인 문법 엔지니어링의 필요성을 제거함으로써 더 견고하고 유지보수가 용이한 소프트웨어 엔지니어링 도구를 지원할 수 있다고 결론짓습니다.