The Super Tiny Compiler | Github

The Super Tiny Compiler

The Super Tiny Compiler는 babel 개발자가 Javascript로 작성된 컴파일러의 주요 부분을 학습용으로 아주 단순하게 개발한 컴파일러이다.

코드의 전체 양이 주석을 제외하면 200줄 미만 밖에 안되고, 학습용으로 작성되어 주석으로 컴파일러 관련 기본 지식들이 잘 설명되어 있어서 한번 처음부터 끝까지 살펴보려고 한다.

목적

LISP 형태의 코드를 파싱해서 C와 같은 코드로 변환하는 것이 The Super Tiny Compiler의 목표이다.

	LISP	C
2 + 2	(add 2 2)	add(2, 2)
4 - 2	(subtract 4 2)	subtract(4, 2)
2 + (4 - 2)	(add 2 (subtract 4 2))	add(2, subtract(4, 2))

컴파일러의 구성 단계

대부분의 컴파일러는 3가지 단계로 나눌 수 있다.
1. Parsing은 원문 코드를 추상적인 표현으로 바꾸는 단계이다.
2. Transformation은 추상적인 표현을 컴파일러가 원하는 대로 변환하는 단계이다.
3. Code Generation은 변환된 코드의 표현을 새로운 코드로 바꾸는 단계이다.

Parsing

Parsing은 두 가지 부분으로 나눌 수 있다.

Lexical Analysis (tokenizer)

원문 코드를 가져와서 떨어지는 조각인 토큰으로 분할한다.

토큰은 아주 작은 문법의 조각을 설명하는 object이다. (숫자, 이름, 연산자 .. 등등)

Syntax analyzer (parser)

토큰들을 취해서 문법이나 관계를 나타내는 표현으로 다시 구성한다. 추상 구문 트리

추상 구문 트리(AST)는 프로그래밍 언어로 작성된 소스 코드의 추상 구문 구조의 트리이다.

예시

(add 2 (subtract 4 2))

-> tokenizer

 [
     { type: 'paren',  value: '('        },
     { type: 'name',   value: 'add'      },
     { type: 'number', value: '2'        },
     { type: 'paren',  value: '('        },
     { type: 'name',   value: 'subtract' },
     { type: 'number', value: '4'        },
     { type: 'number', value: '2'        },
     { type: 'paren',  value: ')'        },
     { type: 'paren',  value: ')'        },
]

-> parser

{
     type: 'Program',
      body: [{
       type: 'CallExpression',
       name: 'add',
       params: [{
         type: 'NumberLiteral',
         value: '2',
       }, {
         type: 'CallExpression',
         name: 'subtract',
         params: [{
           type: 'NumberLiteral',
           value: '4',
         }, {
           type: 'NumberLiteral',
           value: '2',
         }]
       }]
     }]
}

코드 보기

tokenizer (주석을 제외한 ver)

function tokenizer(input) {
  let current = 0;
  let tokens = [];

  while (current < input.length) {
    let char = input[current];

    if (char === '(') {
      tokens.push({ type: 'paren', value: '('});
      current++;
      continue;
    }

    if (char === ')') {
      tokens.push({ type: 'paren', value: ')'});
      current++;
      continue;
    }

    let WHITESPACE = /\s/;
    if (WHITESPACE.test(char)) {
      current++;
      continue;
    }

    let NUMBERS = /[0-9]/;
    if (NUMBERS.test(char)) {
      let value = '';

      while (NUMBERS.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({ type: 'number', value });
      continue;
    }

    if (char === '"') {
      let value = '';
      char = input[++current];

      while (char !== '"') {
        value += char;
        char = input[++current];
      }
      char = input[++current];
      tokens.push({ type: 'string', value });
      continue;
    }


    let LETTERS = /[a-z]/i;
    if (LETTERS.test(char)) {
      let value = '';

      while (LETTERS.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({ type: 'name', value });
      continue;
    }

    throw new TypeError('I dont know what this character is: ' + char);
  }
  
  return tokens;
}

parser (주석을 제외한 ver)

function parser(tokens) {
  let current = 0;

  function walk() {
    let token = tokens[current];

    if (token.type === 'number') {
      current++;
      
      return { type: 'NumberLiteral', value: token.value };
    }

    if (token.type === 'string') {
      current++;

      return { type: 'StringLiteral', value: token.value};
    }

    if (token.type === 'paren' && token.value === '(') {
      token = tokens[++current];

      let node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };

      token = tokens[++current];

      while ((token.type !== 'paren') 
             || (token.type === 'paren' && token.value !== ')')) 
      {
        node.params.push(walk());
        token = tokens[current];
      }
      current++;

      return node;
    }

    throw new TypeError(token.type);
  }

  let ast = { type: 'Program', body: [] };

  while (current < tokens.length) {
    ast.body.push(walk());
  }
  
  return ast;
}

+) Transformation, Code Generation