오토마톤 학습은 블랙박스 시스템으로부터 해당 시스템에 대응하는 오토마톤을 추론하는 알고리즘입니다. 대표적인 알고리즘인 Angluin의 L* 알고리즘은 멤버십 쿼리(주어진 문자열이 시스템에 의해 수용되는가?)와 동등성 쿼리(학습된 오토마톤이 실제 시스템과 일치하는가?)를 통해 시스템의 동작을 학습합니다. 하지만 L* 알고리즘은 정규 언어(Regular Language)에만 적용 가능하며, 루비와 같이 복잡한 문법을 가진 언어는 일반적으로 문맥 자유 언어(Context-Free Language) 또는 그 이상의 복잡성을 가지므로 직접 적용하기 어렵습니다. 이 문제를 해결하기 위해 발표자는 푸시다운 오토마톤(Pushdown Automaton)의 제한된 형태인 가시 푸시다운 오토마톤(Visibly Pushdown Automaton, VPA)에 주목합니다. VPA는 괄호의 중첩과 같은 구조를 처리할 수 있어 루비 문법의 일부를 모델링하는 데 적합하며, L* 알고리즘을 확장하여 학습이 가능합니다. 발표자는 이러한 아이디어를 바탕으로 Ruby로 작성된 오토마톤 학습 라이브러리인 ‘Lernen’을 개발했습니다. ‘Lernen’을 사용하여 제한된 문자 집합(문자열 리터럴 ‘A’, 콜론, 괄호)에 대한 Parse.y와 Prism의 파서-대응 오토마톤을 학습시킨 결과, Prism에서 (:A) 문자열이 심볼 리터럴로 잘못 파싱되는 버그를 발견했습니다. 이 버그는 보고되었고 이미 수정이 완료되었습니다. 이는 오토마톤 학습이 실제 파서의 호환성 문제를 발견하는 데 효과적임을 입증하는 사례입니다.
오토마톤 학습을 이용한 Ruby 파서 호환성 검증
[JA] Make Parsers Compatible Using Automata Learning / Hiroya Fujinami @makenowjust
작성자
RubyKaigi
발행일
2025년 05월 27일
핵심 요약
- 1 Ruby의 두 파서(Parse.y, Prism) 간의 호환성 문제를 체계적으로 해결하기 위해 오토마톤 학습이 활용되었습니다.
- 2 제한된 문자 집합에 대한 파서를 학습하여 Prism에서 `(:A)`와 같은 심볼 리터럴 파싱 오류를 발견하고 수정했습니다.
- 3 `Lernen`이라는 Ruby 라이브러리를 개발하여 오토마톤 학습을 실제 문제 해결에 적용할 수 있음을 보여주었습니다.
도입
Ruby는 현재 Parse.y와 Prism이라는 두 가지 주요 파서 구현체를 가지고 있습니다. 이 두 파서 간의 호환성을 보장하는 것은 루비 개발자들에게 중요한 과제입니다. 기존의 단위 테스트, 퍼징(fuzzing), 공개된 젬 파싱 등의 방법은 방대한 양의 테스트를 통해 정확성을 보장하려 하지만, 마이너하거나 새로운 구문, 또는 복잡한 문법의 모든 경우를 포괄하기 어려워 잠재적인 버그를 놓칠 수 있습니다. 이러한 한계를 극복하기 위해 발표자는 오토마톤 이론과 오토마톤 학습을 활용하여 파서 호환성 문제를 체계적으로 해결하는 새로운 접근 방식을 제안합니다. 특히, 오토마톤의 대칭 차(Symmetric Difference) 연산을 통해 두 파서의 동작 차이를 효율적으로 식별할 수 있음을 강조합니다.
결론
오토마톤 학습은 파서의 호환성 문제를 식별하는 강력한 도구로 활용될 수 있음을 본 발표를 통해 확인했습니다. 특히, 'Lernen' 라이브러리를 통해 오토마톤 학습이 실제 문제 해결에 적용될 수 있는 사용자 친화적인 방안을 제시했습니다. 그러나 루비 전체 문법과 같은 복잡한 시스템의 완전한 파서를 학습하는 것은 현재 기술로는 여전히 도전적인 과제입니다. 이는 파서의 방대한 상태 공간과 루비 문법 자체의 복잡성(예: `/` 연산자의 문맥 의존성) 때문입니다. 또한, 단순히 파싱 성공 여부를 넘어 파싱 결과로 생성되는 추상 구문 트리(AST)의 동일성을 검증하는 방향으로 연구가 확장될 필요가 있습니다. 발표자는 이러한 남은 과제들이 연구자로서의 지속적인 연구 동기가 된다고 밝히며, 오토마톤 학습 기술의 발전과 실제 적용 가능성에 대한 기대를 표명했습니다.