Syntax Repair as Language Intersection

기술 요약: 언어 교차로서의 구문 복구 (Syntax Repair as Language Intersection)

문제 정의
본 논문은 구문 복구(syntax repair)의 과제를 다룬다. 즉, 유효하지 않은 문자열(예: 오타나 구분자가 누락된 프로그램)과 해당 언어를 정의하는 문맥 자유 문법(CFG)이 주어졌을 때, 어떻게 원래의 문자열과 유사하면서도 저자에게 자연스러운 유효한 구문 대안들을 소량의 집합으로 생성할 것인가 하는 문제이다. 기존의 접근 방식들은 트레이드오프에 직면해 있다: 고전적인 오류 수정 파서(error-correcting parsers)는 종종 단일 복구안이나 취약한 휴리스틱에 기반한 집합을 반환하며, 이는 모호성을 처리하거나 넓은 탐색 공간을 제공하는 데 실패한다. 반대로, 학습 기반 시스템(예: 신경망 언어 모델)은 통계적으로는 견고하지만, 일반적으로 근사 추론에 의존하기 때문에 비용이 많이 드는 후처리나 거부 샘플링(rejection sampling)을 필요로 하며, 문법적 유효성을 보장하기 어렵다. 이러한 방법들은 저자의 의도된 복구안을 효과적으로 찾아내기에 너무 적은 후보를 생성하는 경우가 많다. 저자들은 로컬 구문 오류에 대해서는 **완전성(completeness)**이 주요 목표가 되어야 한다고 주장한다: 즉, 시스템은 최적의 하나를 선택하기 전에 광범의 유효한 후보 집합을 먼저 검색해내야 한다는 것이다.

방법론
본 연구의 핵심 기여는 유계 구문 복구(bounded syntax repair)를 문맥 자유 언어(CFL)와 정규 언어의 교집합으로 정식화한 것이다.

1. 형식적 구성:

   • 문제는 $L(\mathcal{G}) \cap L(\mathcal{A})$를 찾는 것으로 정의된다. 여기서 $\mathcal{G}$는 프로그래밍 언어의 CFG이고, $\mathcal{A}$는 유효하지 않은 입력으로부터 특정 편집 거리(예: 3번의 편집) 내에 있는 모든 문자열을 나타내는 무방향 레벤슈타인 오토마타(acyclic Levenshtein automaton)이다.
   • 저자들은 CFL-정규 교집합을 위한 Bar-Hillel 구성을 활용하되, 이를 무방향 오토마타에 특화하여 적용했다. 수많은 불필요한 생성 규칙을 만들어내는 Salomaa의 비효율적인 명시적 구성 대신, 저자들은 Bar-Hillel 교집합과 CFL 도달 가능성(reachability) 사이의 대응 관계를 활용한다.
   • 저자들은 전이 관계의 스팬(span)에 대해 선형 병렬 시간 내에 교집합의 비공집합 여부를 결정하는 병렬 행렬 폐쇄(parallel matrix-closure) 절차(정리 3.1)를 제안한다. 이는 터미널 생성 규칙으로 차트(chart)를 초기화하고, "제곱(squaring)" 연산(차트 세미링 사용)을 반복적으로 적용하여 문법과 오토마타 상태를 통해 도달 가능성을 전파하는 과정을 포함한다.

2. 증거 생성 및 디코딩 (Witness Generation and Decoding):

   • 교집합이 확립되면, 저자들은 유한한 복구 언어를 나타내는 **스타-프리 정규 표현식(star-free regular expression)**을 구축한다(정리 3.2).
   • 후보를 열거하기 위해 저자들은 **브로조스키 미분(Brzozowski derivatives)**을 채택한다. 이를 통해 거부 샘플링 없이 교집합 문법으로부터 빠르고 점진적인 디코딩을 수행할 수 있다. 경량 디코더(초기에는 평활화된 $n$-gram 또는 Nederhof의 정규 근사 기반 가중 유한 상태 오토마타(WDFA))가 유한 언어를 순회하며 후보 집합을 생성한다.
   • WDFA는 사운드한 과대 근사(sound overapproximation) 역할을 하여 상수 시간의 다음 토큰 스코어링을 제공하며, 디코더가 교집합에 의해 정의된 정확한 후보 공간을 탐색하면서 동시에 확률에 따라 후보 순위를 매길 수 있도록 보장한다.

3. 재순위화 (LaTeR):

   • 복구의 충실도(자연스러움)를 해결하기 위해, 시스템은 **레벤슈타인 정렬 트랜스포머 재순위화기(Levenshtein-aligned Transformer Reranker, LaTeR)**를 사용한다.
   • 디코더는 빠른 WDFA를 사용하여 상위-$k$개의 후보(예: 상위-512개)를 검색한다.
   • LaTeR은 깨진 코드 조각과 후보 간의 특정 편집 정렬(삽입, 삭제, 교체) 모두를 조건으로 하는 트랜스포머 모델을 사용하여 이 후보들의 순위를 다시 매긴다. 이는 지지(support)(형식적 방법을 통한 유효성 및 완전성 보장)와 순위 지정(ranking)(신경망 모델을 통한 자연스러움 보장)의 과업을 분리한다.

주요 기여

1. 정식화: 본 논문은 유계 구문 복구를 정확한 언어 교집합 문제로 정식화하고, 무방향 레벤슈타인 오토마타를 사용하여 임의의 CFG에 대한 실용적인 구성을 제공한다.
2. 알고리즘 효율성: 교집합의 비공집합 여부를 결정하기 위한 병렬 행렬 폐쇄 절차를 도입하였으며, 폐쇄 단계에서 선형 횟수의 제곱 라운드가 필요함을 증명하였다. 이는 매우 병렬적인 복구 가능성 결정 절차를 가능하게 한다.
3. 시스템 구현: 저자들은 멀티코어 CPU 및 GPU 상에서 전체 파이프라인(교집합 구성, WDFA 가이드 디코딩, LaTeR 재순위화)을 구현하고 평가하였다.
4. 실험 결과: 자연적으로 발생하는 Python 구문 오류 데이터셋(최대 80개 토큰 및 3개 렉시컬 편집)에 대해, 이 도구(Tidyparse)는 서브 세컨드(subsecond) 레이턴시로 동작한다. 이는 유사한 자원 제한 하에서 기존 시스템(Seq2Parse, Break-It-Fix-It, GPT-5.4)보다 Top-1 복구 정밀도(precision)를 최대 5배 향상시켰다.

결과 및 평가

• 정밀도: Tidyparse는 Baseline 대비 Precision@1에서 현저한 성능 우위를 보인다. 특히, 신경망 기반 Baseline들이 급격히 저하되는 것과 달리, Tidyparse는 편집 거리가 증가하더라도 높은 정밀도를 유지한다.
• 완전성 대 효율성: 본 연구는 기존 신경망 모델들이 너무 적은 후보를 생성하기 때문에 유효한 복구안을 발견하지 못하는 경우가 많다는 점을 강조한다. Tidyparse는 유한 교집합 언어를 철저하게(또는 거의 철저하게) 샘플링함으로써 실제 복구안이 후보 집합 내에 존재하도록 보장한다.
• 레이턴시: 시스템은 CPU 대비 GPU에서 3-5배의 속도 향상을 달inea한다. 거의 모든 복구를 10초 이내에 처리하며, 90%는 1초 미만에 완료된다.
• 절제 실험(Ablation): 실험 결과, 경량 WDFA 스코어러가 많은 정답 복구안을 찾아낼 수는 있지만, 트랜스포머 기반 재순위화기가 이들을 올바르게 정렬하는 데 필수적임을 보여준다. 그러나 재순위화기는 초기 검색 단계에서 실패할 경우 복구안을 회복할 수 없는데, 이는 교집합 단계가 제공하는 완전성의 중요성을 강조한다.

의의
본 논문은 현재 구문 복구 방법의 핵심 한계가 "너무 적은 수의 복구안을 생성한다"는 점이라고 주장한다. 복구를 언어 교집합으로 취급함으로써, 저자들은 건전성(soundness)(모든 복구가 유효함), 완전성(completeness)(탐색 공간이 의도된 복구안을 포함할 만큼 충분히 넓음), 그리고 자연스러움(naturalness)(재순위화를 통해)을 동시에 달성할 수 있음을 입증한다.

이 연구의 의의는 패러다임을 "가능성 높은 문자열을 생성하고 필터링하는 것"에서 "유효한 문자열의 정확한 집합을 구축하고 순위를 매기는 것"으로 전환했다는 데 있다. 이러한 접근 방식은 순수 신경망 방식에서 흔히 발생하는 환각(hallucination) 및 부적절한 유효성 문제를 피하며, 휴리스틱 기반 파서의 취약성을 극복한다. 저자들은 이 작업을 제약 조건 충족을 위한 형식 언어 이론의 정밀함과 순위 지정을 위한 신경망 모델의 자연스러움을 결합한 하이브리드 뉴로심볼릭(neurosymbolic) 도구의 단계로 제시하며, IDE에서의 실시간 구문 지원을 위한 실용적인 솔루션을 제공한다.