LR 파서는 ‘Shift’와 ‘Reduce’ 동작으로 문장을 분석하며 ‘선행 읽기(Lookahead)’를 통해 다음 동작을 결정합니다. 그러나 문법 모호성으로 인해 ‘Shift-Reduce’ 또는 ‘Reduce-Reduce’ 충돌이 발생할 수 있고, 기존 LLR 파서는 ‘미스터리 충돌’ 같은 문제에 취약했습니다.
IELR은 LLR의 한계를 극복하고자 읽어 들인 토큰 정보를 활용해 선행 읽기 집합을 정교하게 좁혀 문맥에 따른 충돌을 효과적으로 해결합니다. 이는 푸시다운 오토마톤 모델에 기반하며, 충돌 지점에 ‘어노테이션’을 부여해 역방향으로 전파하여 원인을 식별하고, 초기 상태부터 선행 읽기 집합을 순방향으로 재계산하며 호환되지 않는 상태 발견 시 분할하여 충돌을 해소합니다.
발표자는 IELR을 Ruby 파서 생성기 Ryuma에 성공적으로 구현했습니다. 초기에는 오토마톤 루프 및 느린 선행 읽기 계산 등으로 파서 생성 시간이 매우 길었으나, 캐싱 및 불필요한 어노테이션 제거 등 최적화 작업을 통해 약 1분 내외로 단축, 실용적인 수준에 도달했습니다.