파스테이블 생성 콤비네이터

Abstract

Scala의 파서 콤비네이터를 사용하면 프로그래밍 언어의 파서를 비교적 손쉽게 구현할 수 있다. 그런데 Scala의 파서 콤비네이터는 몇 가지 문제점이 있다. 첫째, 파싱을 할 때마다 파서를 생성해야 하는 온라인 방식이라 처리속도가 늦을 수밖에 없다. 둘째, 하향식 파서라 좌 재귀 문법을 처리하지 못하는 문제가 있다. 따라서 좌 재귀가 없도록 문법을 작성해야한다. 본 논문에서는 위의 문제들을 해결하는 파스테이블 생성 콤비네이터를 새로 정의한다. 파스테이블 생성 콤비네이터는 콤비네이터 연산을 사용해 파스테이블을 생성하여 LALR(1)과 같은 알고리즘을 사용할 수 있다. 또한 파스테이블을 사용하는 일반적인 이동-감축 알고리즘에서 의미규칙 연산을 정의하여 문법구조에 의미규칙을 기술할 수 있다.