devcken.io

Thoughts, stories and ideas.

Parser Combinator

원문: Parser Combinator

함수형 프로그래밍의 훌륭한 많은 아이디어들이 객체 지향 프로그래밍에 적용됩니다(알다시피, 함수 역시 객체죠). 특히, 파서 콤비네이터는 함수형 프로그래밍 커뮤니티에서 오랜 역사를 지닌 기술입니다.

이것은 하나의 포스트일 뿐, 그러한 아이디어에 대한 정식 참고 자료를 제공하지는 않습니다. 그것이 수십년도 더 됐다는 점과, Phil Wadler, Erik Meijer가 이 분야에서 중요한 일을 해왔다고 말할 수 있습니다. 저 자신은 Martin Odersky의 스칼라 튜토리얼을 보고 깊은 영감을 얻었습니다.

스몰토크로 간단한 파서 콤비네이터 라이브러리를 만든적이 있는데, 매우 잘 동작하는 것 같습니다. 저는 그에 대한 내용을 OO 관점으로 여기에 기록하는 것이 좋을거라고 생각했습니다.

그러면, 파서 콤비네이터라는 것이 정확히 무엇일까요? 기본적인 개념은 BNF의 연산자들(또는 해당 문제에 대한 정규표현식)을 문법의 프로덕션을 나타내는 객체들에 대해 연산하는 메서드로 보는 것입니다. 그러한 각각의 객체가 특정 프로덕션으로 지정되는 언어를 수용하는 파서입니다. 해당 메서드 호출의 결과 또한 그러한 파서입니다. 그러한 연산은 다소 난해한 기술적인 이유로 (그리고 읽기만 하는 컴퓨터를 잘 모르는 이들이 무서워하다록 하기 위해) 콤비네이터라 불립니다.

이를 구체적으로 설명하기 위해, 식별자에 대한 명확한 표준 규칙을 살펴보도록 하겠습니다:

id -> letter(letter|digit)*  

스몰토크로 만든 제 콤비네이터 라이브러리를 사용하자면, 하나는 CombinatorialParser의 하위 클래스를 정의하고, 그 안에 다음과 같이 작성합니다

id := self letter, [(self letter | [self digit]) star]  

여기서, letter란 단일 문자를 받는 파서이고, digit이란, 단일 숫자를 받는 파서입니다. 둘 다 self(스몰토크로 프로그래밍을 해보지 않은 불운한 이들의 경우 this라고 생각하면 됩니다)에 대한 메서드 호출로 얻어집니다. 하위 표현식인 self letter|[self digit]은 숫자가 허용되는 인자와 함께 문자를 허용하는 파서에 | 메서드를 호출합니다(잠시 대괄호은 잊기 바랍니다). 그 결과는 문자 또는 숫자를 받는 파서가 됩니다.

여담: 아니 버지니아, 스몰토크에는 연산자 오버로딩이 없어(역자 주: 아마도 No, Virginia, There is No Santa Claus의 내용을 빗대어 표현한 것이 아닐까요?). 스몰토크는 단순히 알파벳과 숫자가 아닌 문자를 사용하는 메서드 이름을 허용합니다. 이런 것들은 항상 이항 연산이며 모두 동일한 고정 우선 순위를 갖습니다. 어떻게 하면 그렇게 단순할까요? 그것을 미니멀리즘이라고 부르며, 모든 이들을 위한 것은 아닙니다. Mies van der Rohe나 Rococo처럼 말이죠.

제가 강조한 유일한 세부 내용은 대괄호입니다. 대괄호는 클로저를 나타내므로, [self digit]는 적용 시, 숫자를 허용하는 파서를 만들어냅니다. 이렇게 한 이유가 뭘까요? 문법 규칙은 종종 서로 회귀할 수 있기 때문입니다. 프로덕션 A가 만약 프로덕션 B 내에서 사용되고 그 반대의 경우도 있다면, 그들 중 하나(예를 들어 A)는 다른 프로덕션(예를 들어 B)이 아직 정의되지 않고 아직 정의되지 않은 시점에 먼저 정의되어야 합니다. 하나의 클로저 내에서 참조를 다른 프로덕션으로 래핑하는 것은 평가를 지연시키고 이러한 문제가 발생합니다. 하스켈과 같은 lazy한 언어에서 이 점은 문제(중요한 한 가지 원인)가 되지 않습니다. 하스켈은 DSL 정의에 매우 좋습니다. 하지만, 스몰토크의 클로저 문법은 매우 가볍습니다(대부분의 함수형 언어의 람다보다도 더 말이죠)! 그러니 이것은 큰 문제가 아닙니다. 그리고 스몰토크의 이항 메서드와 후위 단항 메서드는 전반적으로 매우 유쾌한 결과를 가져다 줍니다.

그러면 해당 결과에 star 메서드를 호출하겠습니다

(self letter | [self digit]) star

위 예제는 문자 또는 숫자가 0개 이상 나오는 경우를 허용하는 파서를 만듭니다.

더 많은 이들이 이해하는 문법으로 표현하자면 다음과 같을 겁니다:

(1) letter().or(new DelayedParser(){ public Parser value(){ return digit();} }).star()

자바가 클로저를 가지고 있다면 다음과 같을 겁니다:

(2) letter().or({=> digit()}).star()

이것이 더 나아보이지만, 어떤 방법이든, 실행 가능한 문법 작성의 목적은 별로 중요하지 않습니다. 그럼에도 불구하고, 대부분의 사람들이 (1)을 더 선호하고, 나머지 대다수는 "기괴한" 스몰토크 문법에 비해 (2)를 선호하는 것으로 보입니다. 어떤 어두운 면이 사람의 마음 속에 있는지 누가 알까요.

letter에서 호출한 메서드에 파서를 인자로 전달했습니다. "," 메서드는 (BNF에서는 암시적인) 시퀀싱(연결) 콤비네이터입니다. 그것을 먼저 수신자(자바로 치면 타겟)의 언어를 받아들이고 인자에 대한 언어를 받는 파서를 반환합니다. 이 경우, 결과는 우리가 예상한대로 뒤에 0개 이상의 문자 또는 숫자가 오는 단일 문자를 허용한다는 것을 의미합니다. 마지막으로, 이 결과를 식별자에 대한 프로덕션을 나타내는 아이디에 할당합니다. 다른 규칙들은 아이디를 접근자(즉, self id)를 호출하여 사용할 수 있습니다.

또한 이 예제는 구문 분석에 대한 접근 방법이 렉서(lexer)와 파서 모두를 다루고 있음을 보여줍니다.

렉싱(lexing)과 파싱 간에 구분이 안되는 부분은 약간 문제입니다. 전통적으로, 입력을 토크나이즈하기 위해 렉서에 의존해왔습니다. 그렇게 함으로써, (공백 문자를 중요하게 여기는 언어들은 제외하고) 공백 문자와 주석을 없앱니다. 이것은 새로운 연산자인 tokenFor:를 정의해 쉽게 처리되는데, 이 연산자는 파서 p를 받고 앞에 나오는 공백 문자와 주석을 건너뛴 후 p가 허용한 것은 무엇이든 허용하는 새로운 파서를 반환합니다. 또한 이 파서는 해당 결과에 소스의 시작 인덱스와 끝 인덱스를 붙일 수 있어, 파서를 IDE와 통합할 때 매우 편리합니다. 더 높은 수준의 문법 프로덕션의 관점에서, 그렇게 토크나이즈된 결과를 만들어내는 프로덕션 식별자 참조는 유용합니다:

identifier := self tokenFor: self id.  

이런 과정을 언어 속 모든 토큰에 대해 자연스럽게 진행한 후, 전통적인 BNF에서 그랬던 것처럼, 공백 문자 또는 주석과는 관계없이 구문적인 문법을 정의하게 됩니다. 다음 예제는 스몰토크의 return 문에 대한 규칙입니다

returnStatement := self hat, [self expression].  

좋습니다. 문법을 써내려가는 것으로 파서를 멋지게 정의할 수 있습니다. 하지만, 하나의 언어를 받아들이는 것만으로는 그렇게 유용하지 않습니다. 일반적으로, AST를 결과로 만들어내야 합니다. 이를 해결하기 위해, 새로운 연산자인 wrapper:를 도입했습니다. 이 연산자의 결과는 동일한 언어를 수신자로 허용하는 파서입니다. 하지만, 구문 분석 과정에서 만들어지는 결과는 다릅니다. 구문 분석된 토큰을 반환하는 대신, 유일한 파라메터로 받는 클로저를 사용해 이러한 토큰들을 처리합니다. 클로저는 해당 파서의 출력을 입력으로 받고, 어떤 결과(일반적으로 추상 구문 트리)를 산출합니다.

returnStatement := self hat,  [self expression]

     wrapper:[:r :e  | ReturnStatAST new expr:e; start: r start; end: e end].

문법 프로덕션은 구분 라인의 AST 생성으로 명확하게 구분됩니다. 하지만, 저는 문법을 원래 그대로의 상태로 두는 것을 더 좋아합니다. 그것은 쉽습니다. 모든 AST 생성 코드를 하위 클래스에 두는 것이죠. 이 때 문법 프로덕션의 접근자가 재정의됩니다. 그래서:

returnStatement  
^super returnStatement
    wrapper:[:r :e  | ReturnStatAST new expr:e; start: r start; end: e end].    

예를 들어, 동일한 언어를 구문 분석하고 자신의 AST를 각각 허용하는 다른 백엔드에 전달하고자 하는 경우에 유용합니다. 또는 구문 컬러링과 같은 다른 목적을 위해 파서를 사용해야 하지만 문법을 공유하고자 하는 경우에도 말이죠. 이러한 방식의 또 다른 좋은 점은 언어의 확장을 매우 분명하게 뽑아낼 수 있다는 것입니다(특히 믹스인을 사용하는 경우). 그것이 일반적인 범용 언어에 DSL을 임베드하는 이점 중 하나입니다(여러분의 DSL이 호스트 언어의 모든 기능을 상속할테니까요). 이런 경우, DSL은 상속을 상속받습니다.

그럼 안좋은 점은 뭘까요? 음, 구문 분석에 대한 좀 더 효율적인 접근 방식을 상상해볼 수 있습니다. 스몰토크에서, 보통 한번에 하나의 메서드를 구문 분석하니, 메서드들이 작아지는 경향이 있습니다. 비록 그렇게 빠르지는 않은 Squeak를 사용하여 구문 컬러링을 하기 위해 모든 키스트로크마다 메서드를 구문 분석하긴 하지만, 완전히 만족스럽습니다. 큰 메서드의 경우, 지연이 눈에 띌 만큼 클 수도 있습니다. 그러나 성능 향상을 위한 튜닝 방법이 존재합니다. 우리가 가진 방법 말이죠...

다른 문제는 다음과 같은, 좌측 재귀입니다:

expr -> expr + expr | expr * expr | id  

이러한 경우 문법을 리팩터링해야만 합니다. 저는 이것이 큰 문제가 아니라고 생각하지만, 원칙 상 파서는 문제 해결을 위해 자신을 동적으로 리팩터링할 수 있습니다. 이것이 스몰토크에서는 상대적으로 쉽게 할 수 있는 것 중 하나이며, 다른 언어에서는 더 어렵게 여겨지는 것입니다.

요약하자면, 파서 콤비네이터는 정말 좋습니다. 스몰토크에서 멋지게 동작하죠. 그것을 구현하고 사용하면서 즐거웠습니다. 가장 중요한 것은, 객체 지향과 함수형 프로그래밍이 시너지를 내는 방식에 대한 아주 훌륭한 예제라는 것입니다. 좀 더 알아보려면, 주로 하스켈의 세계에, 많은 작품들이 존재합니다.