본 발표는 A와 시스템 매니지먼트의 코바야시 씨가 'G 인플리멘테이션즈 오브 어드밴스드 LR 파서 알고리즘'이라는 제목으로 진행한 내용으로, LR 파서의 한계를 극복하기 위한 고급 파서 알고리즘인 IELR의 이론과 Ripper에의 구현에 초점을 맞춥니다. Ripper는 Ruby 3.3부터 내부 파서 생성에 사용되는 Ruby 전용 파서 생성기로, IELR은 Ripper 0.7 버전부터 사용 가능합니다. 이 발표는 IELR이 기존 LR 파서가 겪는 파싱 충돌 문제를 어떻게 해결하고, 그 구현 과정에서 겪었던 어려움과 해결책, 그리고 향후 루비 언어 적용 가능성에 대해 심도 있게 다룹니다.
LR 파서는 ‘시프트(shift)’와 ‘리듀스(reduce)’라는 두 가지 주요 액션을 사용하여 프로그램을 앞에서부터 순차적으로 분석하는 하향식 구문 분석 알고리즘입니다. ‘시프트’는 다음 토큰을 읽어 들이는 동작이며, ‘리듀스’는 읽어 들인 토큰들을 묶어 상위 구조(부모)를 만드는 동작입니다. 문제는 특정 시점에서 여러 규칙에 매치될 수 있어 파서가 어떤 액션을 취해야 할지 결정하지 못하는 ‘충돌(conflict)’이 발생한다는 것입니다. 특히, 선행 토큰(lookahead token)을 통해 액션을 결정하는 LR1 파서조차도 특정 상황에서는 시프트-리듀스 충돌이나 리듀스-리듀스 충돌에 직면할 수 있습니다.
IELR은 이러한 충돌을 해결하기 위해 ‘지금까지 읽어 들인 토큰’이라는 문맥 정보를 적극적으로 활용합니다. 기존 LR 파서가 언어 전체에서 다음 출현 가능한 토큰의 집합(lookahead set)을 계산하는 반면, IELR은 파서가 이미 읽어 들인 토큰에 의해 필터링된 부분집합 내에서 lookahead set을 구성합니다. 이는 특정 문맥에서 불필요한 선택지를 제거하여 파싱의 정확도를 높입니다. 예를 들어, 동일한 do 키워드라도 if 문맥과 while 문맥에서 다르게 해석되어야 하는 루비의 ‘4가지 do’와 같은 복잡한 문법 구조에서 IELR의 강점이 발휘될 수 있습니다.
IELR의 Ripper 구현은 크게 두 가지 단계로 진행됩니다. 첫째, 충돌이 발생하는 상태에 ‘어노테이션(annotation)’을 붙여 해당 충돌 정보를 이전 상태로 역전파(forward propagation)합니다. 이 어노테이션은 충돌 발생 위치, 관련 토큰, 연관된 액션 등을 포함합니다. 둘째, 초기 상태부터 lookahead set을 재계산하며 전파(backward propagation)합니다. 이 과정에서 어노테이션이 붙은 상태에 도달하면, 전파될 lookahead set과 현재 상태의 ‘호환성(consistency)’을 확인합니다. 호환성이 없는 경우, 해당 상태를 분할하여 새로운 상태를 생성하고 파싱 경로를 재조정함으로써 충돌을 해소합니다.
구현 과정에서는 여러 난관에 봉착했습니다. 오토마톤에 루프가 있어 어노테이션 전파가 무한 루프에 빠지거나, lookahead set 계산이 매우 느려지는 문제가 발생했습니다. 또한, 불필요한 어노테이션이 대량으로 생성되어 성능 저하를 야기했습니다. 이러한 문제들은 이전에 전파된 정보 기록, 캐싱 변수 도입, 강한 연결 요소 분해(SCC) 알고리즘 활용, 그리고 관련성 있는 어노테이션만 전파하는 최적화를 통해 해결되었습니다. 이러한 개선을 통해 Ripper에서의 IELR 파서 생성 시간은 기존 수 시간에서 약 1분 정도로 단축되었습니다.
결론적으로, IELR은 기존 LR 파서의 근본적인 한계였던 파싱 충돌 문제를 문맥 정보를 활용하여 효과적으로 해결하는 진보된 알고리즘입니다. Ripper에 성공적으로 구현됨으로써, 루비 언어의 복잡한 문법을 보다 견고하고 정확하게 파싱할 수 있는 기반을 마련했습니다. 특히, 루비의 '4가지 do'와 같이 모호성이 내재된 구문 분석에 IELR의 적용 가능성을 확인했으며, 이는 향후 루비 파서의 발전 방향을 제시합니다. 앞으로 IELR의 성능 최적화와 루비의 다양한 난해한 문법 문제에 대한 적용 연구가 지속될 것으로 기대됩니다. 본 연구는 언어 처리 분야에서 파서 생성 기술의 중요성과 발전 가능성을 다시 한번 입증한 사례로 평가됩니다.