자바스크립트로 컴파일러 만들기


원글
Mariko Kosaka, https://medium.com/@kosamari/how-to-be-a-compiler-make-a-compiler-with-javascript-4a8a13d473b4

어느 멋진 일요일 Bushwick, Brooklyn의 한 책방에서 John Maeda가 쓴 "Design by Numbers"라는 책을 보았다. 이 책은 DBN 프로그래밍 언어(90년대 말 MIT 미디어 연구소에서 시각적인 방법으로 프로그래밍 개념을 소개하도록 고안된 언어)를 차근 차근 설명했다.

DBN-code-sample

DBN 코드 샘플: http://dbn.media.mit.edu/introduction.html

자바 환경에서 DBN 코드를 실행시키는 것보다 브라우저에서 실행할 수 있도록 SVG로 DBN을 만드는 것이 2016년의 꽤 흥미로운 프로젝트가 될 것으로 생각했다.

우선 DBN-to-SVG 컴파일러를 만들 필요가 있었다. 그래서 컴파일러 만들기를 공부하기 시작했다. "Making Compiler"는 수 많은 컴퓨터 과학처럼 들린다. 그런데 코딩 인터뷰에서조차 노드를 탐색해본적이 없던 내가 컴파일러를 만들 수 있을까?

compiler

내 상상 속 컴파일러는 코드가 벌 받기 위해 가는 곳이다. 만약 코드가 나쁘면, 에러 메시지에 영원히 찍혀있을 것이다.

먼저 컴파일러가 되어 보자.

컴파일러는 코드 조각을 가져와서 다른 어떤 무언가로 돌리는 매커니즘이다. 간단한 DBN 코드를 가져와서 직접 그려보자.

다음 DBN 코드로 된 3개의 커맨드가 있다. "Paper"는 종이의 색을 정의하며, "Pen"은 펜의 색을 정의한다. 마지막으로 "Line"은 선을 그린다. 색을 나타내는 파라미터에서 100은 흑색 100%, CSS의 RGB(0%, 0%, 0%)을 의미한다. DBN으로 만들어진 이미지는 전부 흑백(그레이 스케일)이다. DBN에서 종이는 항상 100x100 사이즈이고, 선의 두께는 항상 1이다. 그리고 선은 왼쪽 최하단을 기준으로 한 x-y 좌표계를 이용하며 시작점과 끝점으로 정의한다.

이제 종이와 펜을 쥐고 직접 컴파일러가 되어 다음 코드를 컴파일하고 그려보자.

Paper 0
Pen 100
Line 0 50 100 50

종이의 한 가운데를 횡단하는 검은색 선을 그렸는가? 축하한다. 당신은 컴파일러가 되었다.

compiled-result

컴파일 결과

컴파일러는 어떻게 동작할까?

우리의 머리가 컴파일러로서 어떤 일을 했는지 생각해보자.

1. 어휘 분석(Lexical Analysis, Tokenization)

우리는 먼저 (토큰이라 부르는) 각 키워드를 공백 기준으로 분리하였다. 또한, 우리가 이 분리작업을 하는 동안 "단어", "숫자"와 같은 원시적인 타입으로 각 토큰을 구분했다.

lexical-analysis

어휘 분석

2. 파싱(Parsing, Syntactical Analysis)

텍스트가 토큰들로 분리되고나면, 각각 살펴보며 토큰들 사이의 관계를 찾는다. 앞의 커맨드에서 우리가 숫자와 연관된 키워드를 함께 그룹화한 경우이다. 그리고나서 이 코드의 구조를 파악하기 시작했다.

parsing

파싱

3. 변형(Transformation)

파싱을 통해 문법을 분석하고 나면, 그 구조를 적합하게 변형하여 최종 결과를 얻고자 한다. 앞에서 우리가 컴파일할 때 우리가 이미지를 그리고자 했기에 명령(Instruction)을 차근차근 사람이 이해하기 쉽도록 변형한 것이다.

transformation

변형

4. 코드 생성

마지막으로 우리는 컴파일된 결과로 그림을 그린다. 이때, 우리는 이전에 만들었던 명령들을 단순히 따르는것 뿐이다.

code-generation

코드 생성

그리고 바로 컴파일러가 하는 일이다.

우리가 그린 그림은 컴파일된 (C 코드를 컴파일해서 만든 .exe 파일과 같은)결과이다. 우리는 컴파일된 결과로서의 그림을 누구에게나, 어느 기기(스캐너, 카메라 등)에게나 연결할 수 있고, 다 함께 중앙에 그어진 검은 선 하나를 볼 수 있을 것이다.

컴파일러를 만들어 보자.

이제 컴파일러가 어떤 일을 하는지 알았으니, JavaScript로 컴파일러를 하나 만들어보자. 이 컴파일러는 DBN 코드를 입력받아 SVG 코드로 변환한다.

1. 렉서 함수(Lexer function)

우리는 영어 문장 "I have a pen"을 [I, have, a, pen]으로 분리할 수 있는 것처럼, 렉서 함수는 코드 문자열을 작고 의미 있는 조각(토큰)들로 분리한다. DBN은 각 토큰을 공백들로 구분하고, "단어" 또는 "숫자"로 분류한다.

function lexer (code) {
  return code.split(/\s+/)
          .filter(function (t) { return t.length > 0 })
          .map(function (t) {
            return isNaN(t)
                    ? {type: 'word', value: t}
                    : {type: 'number', value: t}
          })
}

코드: https://gist.github.com/kosamari/dbfa64a22482640f6ec717e6e445b544#file-lexer-js

input: "Paper 100"
output: [
    { type: "word", value: "Paper" }, { type: "number", value: 100 }
]

2. 파서 함수(Parser function)

파서 함수는 각 토큰들을 돌아다니며 문법적 정보를 찾고, AST(추상 구문 트리)라 부르는 객체를 만든다. 우리의 각 코드가 어떻게 구성되는지를 이해하기 위한 방법으로 AST를 하나의 맵으로도 생각할 수 있다.

우리 코드에는 "NumberLiteral"과 "CallExpression"의 2개의 문법적 타입이 있다. NumberLiteral은 숫자 값을 의미하고, 이를 CallExpression의 파라미터 인자로 사용한다.

function parser (tokens) {
  var AST = {
    type: 'Drawing',
    body: []
  }
  // extract a token at a time as current_token. Loop until we are out of tokens.
  while (tokens.length > 0){
    var current_token = tokens.shift()

    // Since number token does not do anything by it self, we only analyze syntax when we find a word.
    if (current_token.type === 'word') {
      switch (current_token.value) {
        case 'Paper' :
          var expression = {
            type: 'CallExpression',
            name: 'Paper',
            arguments: []
          }
          // if current token is CallExpression of type Paper, next token should be color argument
          var argument = tokens.shift()
          if(argument.type === 'number') {
            expression.arguments.push({  // add argument information to expression object
              type: 'NumberLiteral',
              value: argument.value
            })
            AST.body.push(expression)    // push the expression object to body of our AST
          } else {
            throw 'Paper command must be followed by a number.'
          }
          break
        case 'Pen' :
          ...
        case 'Line':
          ...
      }
    }
  }
  return AST
}

코드: https://gist.github.com/kosamari/041282ca510f9d5e699dc4c419688422#file-parser-js

input: [
  { type: "word", value: "Paper" }, { type: "number", value: 100 }
]
output: {
  "type": "Drawing",
  "body": [{
    "type": "CallExpression",
    "name": "Paper",
    "arguments": [{ "type": "NumberLiteral", "value": "100" }]
  }]
}

3. 변형 함수(Transformer function)

이전 단계에서 만든 AST는 코드에서 어떤 일이 발생했는지는 잘 설명해줄 수 있지만, SVG 파일을 만드는데는 유용하지 않다. 예를 들어 "Paper"는 오직 DBN에만 존재하는 컨셉일 뿐이다. SVG에서는 Paper를 나타내기 위해 엘리먼트를 사용해야 한다. 변형 함수는 AST를 SVG에 더 가까운 또 다른 AST로 변환시킨다.

function transformer (ast) {
  var svg_ast = {
    tag : 'svg',
    attr: {
      width: 100, height: 100, viewBox: '0 0 100 100',
      xmlns: 'http://www.w3.org/2000/svg', version: '1.1'
    },
    body:[]
  }

  var pen_color = 100 // default pen color is black

  // Extract a call expression at a time as `node`. Loop until we are out of expressions in body.
  while (ast.body.length > 0) {
    var node = ast.body.shift()
    switch (node.name) {
      case 'Paper' :
        var paper_color = 100 - node.arguments[0].value
        svg_ast.body.push({ // add rect element information to svg_ast's body
          tag : 'rect',
          attr : {
            x: 0, y: 0,
            width: 100, height:100,
            fill: 'rgb(' + paper_color + '%,' + paper_color + '%,' + paper_color + '%)'
          }
        })
        break
      case 'Pen':
        pen_color = 100 - node.arguments[0].value // keep current pen color in `pen_color` variable
        break
      case 'Line':
        ...
    }
  }
  return svg_ast
 }

코드: https://gist.github.com/kosamari/0dd2a76984e3375c11462276cdf014e1#file-transformer-js

input: {
  "type": "Drawing",
  "body": [{
    "type": "CallExpression",
    "name": "Paper",
    "arguments": [{ "type": "NumberLiteral", "value": "100" }]
  }]
}
output: {
  "tag": "svg",
  "attr": {
    "width": 100,
    "height": 100,
    "viewBox": "0 0 100 100",
    "xmlns": "http://www.w3.org/2000/svg",
    "version": "1.1"
  },
  "body": [{
    "tag": "rect",
    "attr": {
      "x": 0,
      "y": 0,
      "width": 100,
      "height": 100,
      "fill": "rgb(0%, 0%, 0%)"
    }
  }]
}

4. 생성 함수(Generator function)

컴파일러의 마지막 단계로, 생성 함수는 이전 단계에서 새로 만든 AST를 기반으로 SVG 코드를 만들어낸다.

function generator (svg_ast) {

  // create attributes string out of attr object
  // { "width": 100, "height": 100 } becomes 'width="100" height="100"'
  function createAttrString (attr) {
    return Object.keys(attr).map(function (key){
      return key + '="' + attr[key] + '"'
    }).join(' ')
  }

  // top node is always <svg>. Create attributes string for svg tag
  var svg_attr = createAttrString(svg_ast.attr)

  // for each elements in the body of svg_ast, generate svg tag
  var elements = svg_ast.body.map(function (node) {
    return '<' + node.tag + ' ' + createAttrString(node.attr) + '></' + node.tag + '>'
  }).join('\n\t')

  // wrap with open and close svg tag to complete SVG code
  return '<svg '+ svg_attr +'>\n' + elements + '\n</svg>'
}

코드: https://gist.github.com/kosamari/82209aadb7f5b974a9637c438b19bdad#file-generator-js

input: {
  "tag": "svg",
  "attr": {
    "width": 100,
    "height": 100,
    "viewBox": "0 0 100 100",
    "xmlns": "http://www.w3.org/2000/svg",
    "version": "1.1"
  },
  "body": [{
    "tag": "rect",
    "attr": {
      "x": 0,
      "y": 0,
      "width": 100,
      "height": 100,
      "fill": "rgb(0%, 0%, 0%)"
    }
  }]
}
output:
<svg width="100" height="100" viewBox="0 0 100 100" version="1.1" xmlns="http://www.w3.org/2000/svg">
  <rect x="0" y="0" width="100" height="100" fill="rgb(0%, 0%, 0%)">
  </rect>
</svg>

5. 이 모든것을 합쳐 하나의 컴파일러가 된다.

지금까지 만든 함수들을 합쳐 "sbn compiler"(SVG by numbers compiler)라 부르자. 렉서, 파서, 변형, 생성 메서드를 가지는 sbn 객체를 만들고, 메서드들을 체인으로 연결하는 "compile"이라는 메서드를 추가하자.

이제 코드 문자열을 컴파일 메서드에 넘기면 SVG 출력을 얻을 수 있다.

var sbn = {}
sbn.VERSION = '0.0.1'
sbn.lexer = lexer
sbn.parser = parser
sbn.transformer = transformer
sbn.generator = generator

sbn.compile = function (code) {
  return this.generator(this.transformer(this.parser(this.lexer(code))))
}

// call sbn compiler
var code = 'Paper 0 Pen 100 Line 0 50 100 50'
var svg = sbn.compile(code)
document.body.innerHTML = svg

코드: https://gist.github.com/kosamari/6c610165c0f48c699679bc5a8bab6327#file-compiler-js

위에 나온 컴파일러의 각 스텝들을 보여줄 수 있는 반응형 데모와, sbn 컴파일러 코드를 github에 공유하고 있으며, 지금도 더 많은 기능을 추가하고 있다. 만약 이번 글에서 만든 기본 컴파일러를 확인하고 싶다면 simple branch를 확인하면 된다.

https://kosamari.github.io/sbn/

https://kosamari.github.io/sbn/

컴파일러는 재귀와 탐색(Traversal) 등을 하면 안되는가?

그렇다. 재귀와 탐색 모두 컴파일러를 만들기 위한 멋진 기술들이지만, 컴파일러를 만들기 위해 처음부터 접근해야 할 방식을 뜻하는 것은 아니다.

이 컴파일러는 DNB 프로그래밍 언어의 부분 집합으로 아주 작고 한정된 기능으로 만들기 시작하였다. 그리고서 그 범위를 확장하여 변수, 코드 블록, 루프 등의 기능을 추가할 계획이다. 재귀 탐색과 같은 기술을 사용하는 것은 좋은 아이디어일 수 있지만, 시작할 때부터 필요하지는 않다.

컴파일러를 만드는것은 멋지다.

자신만의 컴파일러를 만들면 무엇을 할 수 있을까? 아마 스페인어 버전의 자바스크립트 같은 것들을 만들어 보고 싶을 수도 있는데, español 스크립트는 어떤가?

// ES (español script)
función () {
  si (verdadero) {
    return «¡Hola!»
  }
}

프로그래밍 언어를 Emoji (Emojicode)로 만드는 사람들도 있고, 색상 이미지 (Piet programming language)로 만드는 사람들도 있다. 가능성은 무궁무진하다.

컴파일러 만들기를 통해 배운것

컴파일러 만들기는 재밌기도 했지만 가장 중요했던 점은 내가 소프트웨어 개발에대한 많은 것들을 생각해볼 수 있었던 것이다. 다음은 내가 컴파일러를 만들며 몇가지 배운 것들이다.

box-of-fun

How I imagine compiler after making one self

1. 익숙하지 않은 것을 해보는 것도 괜찮다.

처음 만든 어휘 분석기처럼, 처음부터 모든것을 알 필요는 없다. 만약 코드나 기술을 이해하지 못한 것이 있더라도, 그냥 "그런게 있다." 정도로만 말해도 괜찮다. 그리고 다음 스텝으로 넘어가자. 다 이해하지 못한 것에 스트레스 받지 말자. 결국엔 이해하지 못했던 지점에 도착하고 이해하게 될 것이다.

2. 나쁜 에러 메시지로 못되게 굴지 말자.

파서의 역할은 규칙을 따르고 코드가 규칙에 따라 쓰였는지 확인한다. 그래서 자주 에러가 발생할 것이다. 에러가 발생했을 때, 도움이되고 환영 받는 메시지로 넘기자. "그렇게 동작하지 않아."라고 (자바스크립트의 "ILLEGAL Token"이나 "undefined is not a function"처럼)말하는 것은 쉽지만, 사용자에게 더 많은 것들을 알려주려고 노력해보자.

팀 내 커뮤니케이션도 마찬가지다. 누군가가 어떤 질문에 쩔쩔매고 있다면, 아마 당신은 "난 어떤 문서의 몇 페이지를 읽어보길 추천해."나 "난 구글에 어떤 키워드로 검색하려 했어." 처럼 대답해줄 수 있을 것이다. 직접 대신 일을 해줄 필요는 없지만, 조금 더 많은 정보를 주는 등의 도움은 줄 수 있고, 그럼 그 누군가도 일을 더 잘하고 빨리할 수 있을 것이다.

Elm은 이런 방식을 채택한 프로그래밍 언어다. 이 언어는 에러메시지에 "Maybe you want to try this?"과 같은 문구가 있다.

3. 컨텍스트가 전부다.

우리의 변형 함수가 기존 AST를 결과에 조금 더 적합한 또 다른 AST로 변형했던것 처럼, 모든 것들은 맥락에 따라 다르다.

어떤 일을 하는 완벽한 방법은 없다. 단순히 인기가 있었던 방식이나, 예전에 해보지 못했던 방식이라고 그대로 따라하지 말자. 맥락을 먼저 생각하자. 한 사용자가 쓰는 방법이 또 다른 사용자에게는 재앙일 수 있다.

그리고 이런 변형기와 같은 역할을 하는 이에게 고마워하자. 당신은 아마 당신의 팀에서 이런 역할을 잘하는 사람을 알고 있을 것이다. 비록 직접 코드를 만들지 않는다 해도 우수한 산출물을 만드는 데는 매우 중요한 것이다.


여러분이 이 글을 즐겼으면 좋겠다. 컴파일러가 되어보고 만들어보는 것이 얼마나 멋진 일인지 이제 알았을 것이다.

이 글은 "JSConf Colombia 2016 in Medellin"에서 발췌한 것으로, 더 자세히 알고 싶다면 발표 슬라이드를 참고해보길 바란다.


크리에이티브 커먼즈 라이선스
이 저작물은 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제 라이선스에 따라 이용할 수 있습니다.
이민규2016.11.07
Back to list