1. 소개

함수형 프로그래밍에서 재귀 하향식 파서를 만드는 대중적인 방법은 파서를 함수로 모델링하고, 고차 함수(또는 컴비네이터)를 정의해서 시퀀싱, 선택, 반복을 제공하는 문법을 구성하는 것이다. 기본 아이디어는 최소 Burge의 “재귀적인 프로그래밍 기술(1975)”에서 찾아야 하고, Wadler (1985), Hutton (1992), Fokker (1995) 그 외 많은 이들에 의해 저술된 함수형 프로그래밍에 의해 유명해졌다. 컴비네이터는 함수형 파서를 만드는 빠르고 쉬운 방법을 제공한다. 게다가, 이 방법은 다른 함수형 파서 생성기, 예를 들어 Ratatosk (Mogensen, 1993)과 Happy (Gill & Marlow, 1995)보다 좋다.

파서가 모나드의 한 인스턴스라는 것은 일찍이 알려졌는데, 모나드란 수학에서 수많은 계산 문제를 해결하는데 유용한 것으로 증명된 대수적 구조이다. 수학적 관점에서 흥미로울 뿐만 아니라, 파서의 모나드적 천성을 인식하는 일은 실질적인 이득이 있다. 예를 들어, 파서를 만들 때 모나드식 시퀀싱 컴비네이터를 이용하면 중첩된 이전 작업 결과의 튜플을 다루는 지저분한 작업을 피할 수 있다 (바인드). 게다가, 모나드 컴프리헨션 표기를 이용하면 파서를 더욱 컴팩트하게 만들 수 있고 읽기 쉬워진다.

모나드식 접근을 더 취하면, 파서의 모나드는 두 개의 더 간단한 모나드를 통해 모듈 방식으로 표현할 수 있다. 이를 통한 즉각적인 이득은 기본적인 파서 컴비네이터가 더 이상 명시적으로 정의될 필요가 없다는 것이다. 대신, 이들은 기본 모나드 m으로부터 m을 파라미터화 한 다른 모나드를 리프팅해서 모나드 연산을 만드는 과정에서 자동으로 하나의 특수한 경우가 된다. 이는 또한 우리가 기본 모나드를 수정해서 (예를 들어 파서를 제한해서 최대 하나의 결과만 내게 하는) 파서의 천성을 바꾸면 이 수정된 파서 모나드를 위한 새로운 컴비네이터 역시 구성을 리프팅함으로써 자동으로 만들어진다는 뜻이다.

이 글의 목적은 함수형 파서를 만들기 위한 모나드식 접근을 단계 별로 설명하기 위한 튜토리얼을 제공하기 위함이며, 모나드를 적극 활용했을 때의 장점을 설명하기도 한다. 대부분의 내용은 이미 알려진 것들이다. 기여점은 튜토리얼을 제공한다는 점이다. 렉서를 따로 두지 않고 렉싱을 다루는 새로운 컴비네이터를 소개하고, 모나드의 사용법에 영향을 받아 오프사이드 규칙을 구현하는 새로운 접근도 소개한다.

---