고급 LR 파서 알고리즘 구현 (IELR) 및 Lrama 적용 사례

Lrama 및 IELR 소개

• Lrama: Bison과 호환되는 Ruby 기반 파서 제너레이터로, Ruby 3.3부터 CRuby의 내부 파서(parse.y) 생성에 활용되고 있습니다. 현재 CRuby 3.5를 위한 0.7 버전이 개발 중입니다.
• IELR (Informed/Improved LR): 2010년 논문으로 발표된 LR 파서 생성 알고리즘의 일종입니다. 이미 읽어 들인 토큰 정보를 활용하여 다음에 나올 수 있는 토큰을 LR 파서보다 정확하게 예측합니다. Python에는 이 알고리즘의 구현체가 존재합니다.

LR 파서의 기본 동작 및 한계

• LR 파서: 하향식(bottom-up) 구문 분석 알고리즘으로, 시프트(shift)와 리듀스(reduce) 두 가지 액션을 사용합니다.
  • 시프트: 렉서로부터 다음 토큰을 읽어 프로그램 진행.
  • 리듀스: 읽어 들인 토큰들을 묶어 상위 노드 생성.
• 선행 탐색(Lookahead): 특정 규칙에 매칭되었을 때 리듀스를 수행할지 결정하기 위해 다음 토큰을 미리 확인하는 과정입니다(LR(1)의 ‘1’이 이를 의미).
• 충돌(Conflict): 선행 탐색만으로는 동작을 유일하게 결정할 수 없는 상황을 의미합니다. 시프트-리듀스 충돌(shift-reduce conflict)과 리듀스-리듀스 충돌(reduce-reduce conflict)이 있습니다.

IELR의 충돌 해결 메커니즘

• LR과 IELR의 Lookahead Set 차이:
  • LR: 언어 전체에서 특정 규칙 다음으로 나타날 수 있는 토큰 집합을 사용합니다.
  • IELR: 파서가 지금까지 읽어 들인 토큰에 의해 필터링된 부분집합 내에서 다음에 나타날 수 있는 토큰 집합을 구성하여, 더 정확한 예측을 가능하게 합니다.
• Mysterious Conflicts: IELR에서 해결되지만 LR에서는 발생하는 특정 유형의 충돌입니다. LR 파서의 상태 병합(state merging) 과정에서 발생하며, IELR은 이를 해결하기 위해 상태를 분할합니다.

Lrama IELR 구현

• 기본 아이디어:
  1. 충돌이 발생하는 상태에 어노테이션을 부착합니다.
  2. 이 어노테이션 정보를 이전 상태로 역전파(backward propagation)합니다.
  3. 초기 상태부터 Lookahead Set을 재계산하며 전방으로 전파(forward propagation)합니다.
  4. 어노테이션이 부착된 상태로 Lookahead Set을 전파할 때, 전파 대상 상태와의 ‘호환성(compatibility)’을 확인합니다.
  5. 호환성이 없는 경우, 해당 상태를 분할하고 새로운 상태를 생성하여 전이 경로를 변경합니다.
• 성능 최적화:
  1. 오토마톤 루프: 어노테이션 역전파 시 무한 루프 발생. 이전에 전파된 정보를 추적하여 해결.
  2. Lookahead Set 계산 지연: 캐시 변수 도입 및 SCC(Strongly Connected Components) 알고리즘을 활용한 사전 계산으로 최적화.
  3. 불필요한 어노테이션 생성: 전파 시 관련성 체크를 통해 필요한 어노테이션만 생성하도록 개선.
• 결과: 최적화 후 parse.y 대상 파서 생성 시간이 2시간 이상에서 약 1분으로 단축되었습니다.

향후 계획

• 속도 개선: 현재 1분도 여전히 느리다는 피드백에 따라 추가적인 속도 최적화가 필요합니다.
• Ruby 언어 응용: Ruby의 ‘네 가지 do’ 문제(괄호 있는/없는 메서드 호출의 do, while do, lambda do)와 같이 복잡한 문법 구조를 IELR의 강력한 분석 능력으로 해결할 가능성을 모색합니다.