셀프 호스팅 시동: 렉서, 파서, 그리고 공유된 트리

앞 Part는 작은 자기 참조로 끝났다: Mere에 대한 문서를 생성하는 Mere 프로그램. Part V는, 이 연재 전체가 향해 온 큰 것 —— Mere 자신을 처리하는 Mere 프로그램 —— 의 이야기다. 지금까지의 컴파일러는 OCaml로 쓰여 있다: OCaml 렉서, OCaml 파서, OCaml 타입 검사기, 평가기, 코드 생성기. 셀프 호스팅 이란, 그 모두를 Mere로 다시 써서, 언어가 자기 자신의 소스를 컴파일할 수 있게 될 때까지 하는 것이다. 이번 회는 프론트엔드: 소스 텍스트의 문자열을, 구조화된 구문 트리로 바꾸는 부분이다.

프리티 프린터가 먼저 와서, 과녁을 세웠다

컴파일러 프론트엔드를 세우는 명백한 순서가 있다 —— 렉서, 그다음 파서, 그다음 파서의 출력을 소비하는 모든 것. 이 프로젝트는 일부러 그것을 거꾸로 했고, 그 이유는 이해할 가치가 있다. 이후의 모든 것을 빚었기 때문이다.

첫 셀프 호스트 부품은 파서가 아니었다; 그것은 프리티 프린터 —— 구문 트리를 취해, 깨끗한 소스 텍스트로 정형해 되돌리는 도구 —— 였다. 그것은 순서가 어긋나 보인다: 트리를 만드는 파서를 아직 갖지 못한 채, 어떻게 트리를 정형하는가? 답은, 프리티 프린터가 처음에는 손으로 쓴 트리를 받았고, 그리고 쓰이는 중에, 하류의 모든 것이 의존하는 하나를 선언해야 했다는 것이다: 구문 트리 그 자체의 형태. 트리를 정형하려면, 먼저 트리가 무엇인가를 말해야 한다 —— let 노드가 어떻게 보이는지, if가 무엇을 쥐는지, 함수 적용이 어떻게 표현되는지. 프리티 프린터가 그 데이터 타입을 정의했다.

즉, 파서가 쓰일 차례가 되었을 때, 그것은 자기 출력을 발명할 자유를 갖지 못했다. 고정된 과녁이 있었다: 프리티 프린터가 이미 소비하는 트리를, 꼭 만들어라. 계약은 파서가 존재하기 전에 세워져 있었다. 그리고 보답은 각 단계에서 구체적이었다 —— 프리티 프린터가 도므로, 프론트엔드의 각 단이 눈에 보이는 결과를 가졌다. 포매터는 이미 브라우저에서 손으로 쓴 트리 위에서 돌았다; 파서는, 프로젝트 자신의 말로, 손으로 짠 트리가 아니라 타이핑된 소스를 받는 진짜 브라우저 내 포매터로의, 마지막 장애였다.

공유된 트리가 등뼈다

그 구문 트리 —— 추상 구문 트리, AST —— 는, 셀프 호스트 컴파일러 전체에서 가장 중요한 객체다. 그것이 모든 단계 사이의 계약이기 때문이다. 파서가 그것을 만든다. 프리티 프린터가 그것을 소비한다. 타입 검사기, 평가기, 코드 생성기 —— 모두 이 Part의 뒤에 온다 —— 도 그것을 소비한다. 한 번 정의하면, 모든 부품이 서로에게 같은 언어를 말한다. 그것을 먼저, 프리티 프린터를 통해 정의한 것은, 파서가 움직이는 점이 아니라 고정된 점을 겨눴음을 뜻하고, 뒤에 세워진 모든 것이 같은 고정점을 이어받았다.

그리고 여기서, 연재의 바로 초입의 결정이 다시 보답받는다. AST는, 구조적으로, 노드 형의 합이다: 식은 리터럴 이거나 변수 이거나 if 이거나 적용 이거나 match이고, 각 형은 자기 필드를 나른다. 그것은 바로 대수적 데이터 타입 —— 레코드의 variant —— 이고, 그것이야말로 Mere가, 작은 ML 계열 언어로서, 깔끔하게 표현하기 위해 세워진 것이다. 초입의 OCaml을 고르는 회는, 대수적 데이터 타입을 가진 호스트가 컴파일러 쓰기를 자연스럽게 한다는 내기를 걸었다; 셀프 호스트 컴파일러는, 같은 내기를 언어 자신의 말로 회수한다. Mere가 Mere의 구문 트리를 기술하는 것은, 언어를 자기 자신에게 겨눈 것이고, 그것이 들어맞는 것은, 구문 트리야말로 합 타입이 그것을 위해 있는 정전적인 것이기 때문이다.

렉서, 그다음 파서, 기준에 유지되어

트리가 정의되어, 프론트엔드는 두 부품이다. 렉서는 생 소스 문자열을, 평평한 토큰의 리스트 —— 키워드, 연산자, 리터럴, 식별자 —— 로 바꾼다. 언어의 작은 어휘를 인식하고, 갈라낸다. 파서는, 그 토큰 리스트를 재귀 하강으로 걷고, 언어의 열 몇 단의 연산자 우선순위를 오르며, 프리티 프린터가 정의한 트리를 조립한다. 어느 것도 개념적으로 새롭지 않다; 둘 다 손으로 쓴 프론트엔드의 표준적인 형태가, 이제 Mere로 표현된 것이다.

그것들을 정직하게 유지하는 것은, backend를 다스린 것과 같은 규율이다. 이미 OCaml 렉서와 OCaml 파서 —— 원래의 프론트엔드 —— 가 있고, 그것들이 기준을 맡는다. 셀프 호스트 파서는 그것들에 대해 cross-validate된다: 같은 소스를 받으면, OCaml 파서가 만드는 것과 같은 트리를 만들어야 한다. 이것은 Part IV의 parity 규칙을, 한 단 올린 것이다. 네 backend가 인터프리터의 바이트에 유지된 곳에서, 셀프 호스트 프론트엔드는 OCaml 프론트엔드의 트리에 유지된다 —— “이 소스를 파싱하라”의 두 구현이, 일치할 것을 요구받고, 벌어짐이 신뢰로 지나쳐지는 것이 아니라 자동으로 잡힌다.

프론트엔드는 또, 기준보다 작을 수 있었다. 그것은, 셀프 호스트 컴파일러 자신이 쓰여 있는 Mere의 부분집합만 파싱하면 되기 때문이다. 컴파일러가 자기 자신에 아직 쓰지 않는 구문은, 미룰 수 있었다 —— 프로젝트 전체가 도는, 같은 최소의 정직한 판의 규율이, 이제 컴파일러가 자기 동류를 파싱하는 것에 적용되었다. 당신이 실제로 쓴 언어를 읽는 데, 꼭 족할 만큼의 언어를 세운다.

프론트엔드는 이제 Mere에 존재한다: 소스 텍스트가 들어가고, 공유된 구문 트리가 나오고, 그것은 기준에 일치한다. 하지만, 작성자밖에 돌리지 않은 파서는, 아직 증명되지 않았다. 가장 날카로운 테스트는, 그것을 손에 넣을 수 있는 가장 까다로운 입력에 겨누는 것이다 —— 그 자신의 소스 코드, 그리고 다른 셀프 호스트 부품의 소스. 다음 회: 포매터와 cross-validation 하네스, 그리고, 셀프 호스트 프론트엔드가 셀프 호스트 프론트엔드를 파싱하는 순간.