"아주 간단한 수식 문자열" 처리기를 만들어 보자. (1편. Lexer를 만들자)

해당 글은 "밑바닥부터 만드는 인터프리터" 책을 읽고 작성한 글입니다. 더 자세히 알고 싶다면 제 글이 아닌 책을 읽으시면 됩니다!

언어를 어떤 걸 쓸까 고민을 많이 했는데 TypeScript을 사용하기로 했습니다.

해당 글에서 사용되는 코드는 모두 이 레포에서 확인할 수 있습니다.

수식 문자열을 처리하는 "아주 간단한 처리기"?

1+2*3의 결과는 무엇인가? 당연히 9! 일리가 없고 7이다. 왜 그런가? 당연히 연산자 우선순위 때문에 그렇다. 모두 알고 있는 것이다. 그러나 그걸 아는가? 이 너무나도 "간단한 수식의 문자열"을 처리하는 프로그램을 짜는 것은 너무나도 어렵다는 것을 말이다.

혹자는 너무 쉽게 만들 수 있다고 말할 것이다.

const expression = '1+2*3';
const result = eval(expression);

와우! 너무 쉽다!
이번 글 끝.

그럴 리가 없지 않은가? 간단한 수식을 처리하는 함수를 짠다고 해보자.

type VerySimpleExpressionProcessor = (expression: string) => number;

const solution: VerySimpleExpressionProcessor = (expression) => {
  // 당신의 코드!
}

describe("간단한 수식을 처리하자", () => {
  it("덧셈 쯤이야", () => {
    const result = solution("1 + 2");
    expect(result).toEqual(3);
  });
  
  it("뺄쌤 쯤이야", () => {
    const result = solution("1 - 2");
    expect(result).toEqual(-1);
  });
  
  it("어..? 뺄쌤 쯤이야??", () => {
    const result = solution("-1 - -2");
    expect(result).toEqual(1);
  });
  
  it("우선순위 맞출 수 있겠어?", () => {
    const result = solution("4 / 2 + -1 * 3");
    expect(result).toEqual(-1);
  });
  
  it("별 두개는 제곱이란다", () => {
    const result = solution("2**3*4**2");
    expect(result).toEqual(128);
  });
  
  it("괄호도 처리해야지?", () => {
    const result = solution("(6*(2/(3-2)))/4");
    expect(result).toEqual(3);
  });
});

혹시 Regex를 사용해서 기호를 split 시키고 어떻게 해보려고 생각했다면 큰 오산이다. 이 것은 그렇게 간단한 문제가 아니다. 우리가 보통 프로그래밍을 처음 배우고 푸는 문제를 보면 "사칙연산 계산하기" 정도의 제목을 가진 문제들이 있다. 그런 문제들은 기초적인 조건문과 반복문을 사용할 수 있으면 풀 수 있는 문제들이 대부분이다. 그러나 현실은 만만치 않다.

위 테스트를 통과하는 solution 함수를 작성하는 것은 간단하지 않다. 그렇기에 제목이 아주 간단한 "수식 문자열" 처리기가 아닌 "아주 간단한 수식 문자열" 처리기인 것이다. 간단한 것은 해당 수식이지. 처리기가 간단한 것이 아니다.

사실은 인터프리터를 만들라는 문제

결론부터 말하면 해당 문자열을 처리할 수 있는 함수를 작성하는 것은 간단한 수준의 프로그래밍 언어를 처리하는 인터프리터를 만드는 것과 같다. 그렇게 하기 위해서 우리는 아래와 같은 순서대로 처리기를 만들어야 한다.

1. Lexer (Lexical Analysis) 렉서
2. Parser (Syntax Analysis) 파서
3. Evaluator 평가기

각 처리기를 거치면 아래와 같은 순서로 결과물들이 도출된다.

1. source code -> lexer -> tokens
2. tokens -> parser -> AST (Abstract Syntax Tree)
3. AST -> eval -> result

우리는 이번 글을 통해서 Lexer를 만들어 보고자 한다. lexer는 문자열을 받아서 해당 시스템의 의미 있는 토큰으로 치환시키는 작업을 수행한다. 그렇기에 Tokenizer로 불리기도 하고 문자열을 읽어내기 때문에 Scanner로 불리기도 한다. 혹시 Java 언어의 java.util.Scanner를 생각했다면 그것이 맞다!

Token 토큰?

앞에서 계속 토큰토큰 하는데 무엇을 토큰이라고 말하는 것일까? 간단한 수식을 하나 가져와 보자. "1+23*3.14"의 문자열을 토큰으로 분리하면 어떻게 될까?

type TokenType =
  | 'illegal'
  | 'number'
  | 'plus'
  | 'minus'
  | 'asterisk'
  | 'slash'
  | 'lparen'
  | 'rparen'
  | 'double-asterisk'
  | 'eof';

type Token = {
  type: TokenType,
  literal: string;
}

const expression = "1+23*3.14";
const tokens = [
  { type: 'number', literal: '1' },
  { type: 'plus', literal: '+' },
  { type: 'number', literal: '23' },
  { type: 'asterisk', literal: '*' },
  { type: 'number', literal: '3.14' }
];

내가 해석할 언어에서 정의되는 다른 문자열과 구분될 수 있는 특별한 문자열이 토큰이다. 보통의 언어에서는 변수명 같은 것이 토큰이 될 수 있다. 다 정의하기 나름이다. 우리가 해석할 문자열은 간단한 수식이기 때문에 위 코드에서 정의한 TokenType 정도면 충분하다.

Lexer 렉서

Lexer는 해석할 문자열을 받아서 그 안에서 정의된 Token을 꺼내는 역할을 한다. 그럼 우리가 만들 lexer의 test code를 미리 작성해 보자.

import type { Token } from "./token";
import Lexer from "./lexer";

describe("test lexer", () => {
  it("연산자", () => {
    const express = "+-*/()";

    const expectedTokens: Token[] = [
      { type: "plus", literal: "+" },
      { type: "minus", literal: "-" },
      { type: "asterisk", literal: "*" },
      { type: "slash", literal: "/" },
      { type: "lparen", literal: "(" },
      { type: "rparen", literal: ")" },
      { type: "eof", literal: "" },
    ];

    const lexer = new Lexer(express);
    for (const expected of expectedTokens) {
      const token = lexer.nextToken();
      expect(token).toEqual(expected);
    }
  });
  
  it("허용되지 않은 문자", () => {
    const express = "?";

    const expectedTokens: Token[] = [
      { type: "illegal", literal: "?" },
      { type: "eof", literal: "" },
    ];

    const lexer = new Lexer(express);
    for (const expected of expectedTokens) {
      const token = lexer.nextToken();
      expect(token).toEqual(expected);
    }
  });

  it("** 연산자", () => {
    const express = "*/**";

    const expectedTokens: Token[] = [
      { type: "asterisk", literal: "*" },
      { type: "slash", literal: "/" },
      { type: "double-asterisk", literal: "**" },
      { type: "eof", literal: "" },
    ];

    const lexer = new Lexer(express);
    for (const expected of expectedTokens) {
      const token = lexer.nextToken();
      expect(token).toEqual(expected);
    }
  });

  it("숫자", () => {
    const express = "1 3.14 300";

    const expectedTokens: Token[] = [
      { type: "number", literal: "1" },
      { type: "number", literal: "3.14" },
      { type: "number", literal: "300" },
      { type: "eof", literal: "" },
    ];

    const lexer = new Lexer(express);
    for (const expected of expectedTokens) {
      const token = lexer.nextToken();
      expect(token).toEqual(expected);
    }
  });

  it("수식", () => {
    const express = "1+2    * 3";

    const expectedTokens: Token[] = [
      { type: "number", literal: "1" },
      { type: "plus", literal: "+" },
      { type: "number", literal: "2" },
      { type: "asterisk", literal: "*" },
      { type: "number", literal: "3" },
      { type: "eof", literal: "" },
    ];

    const lexer = new Lexer(express);
    for (const expected of expectedTokens) {
      const token = lexer.nextToken();
      expect(token).toEqual(expected);
    }
  });
});

테스트 코드를 보면 이런 생각을 할 수 있을 것이다. '수식을 토큰으로 바꾼다면서 수식이 올바르지 않는걸?' 여기서 알아야 할 사실은 Lexer는 입력받은 문자열을 우리가 정의한 토큰으로 변환하는 작업만 할 뿐이지 해당 구성이 올바른지 올바르지 않은지를 검사하지 않는다는 것이다.

아무튼 테스트 코드를 살펴보자. Lexer를 new 하면서 문자열을 넘겨주고 nextToken() 메서드를 호출하면 변환된 Token을 하나씩 꺼내주기만 하면 lexer이다. 매우 간단하다. 어떻게 하면 이런 Lexer를 구현할 수 있을까?

결론만 얘기하면 간단하다. 그냥 하나씩 읽어가면서 그냥 입력받은 문자열을 한 자 한 자씩 읽어가면서 구분지어서 토큰을 만들어 내기만 하면 된다. 아주 간단하지 않은가? 그러기 위해서 아래와 같은 상태(instance member)를 가지고 있어야 한다.

class Lexer {
  private input: string;
  private currentPosition = -1; // 현재 보고있는 문자의 index
  private nextPosition = 0;     // 읽어야 할 문자의 index
  private character = '';       // 현재 보고 있는 문자

  constructor(input: string) {
    this.input = input;
  }

  public nextToken(): Token {
    // 다음 토큰은?!
  }
}

한자씩 읽어나간다고 했다. 그러기 위해서 곧 읽어야 할 문자의 index를 나타내는 nextPosition과 읽은(과거) 문자의 위치의 index와 문자를 나타내는 currentPosition과 character가 필요하다. nextPosition를 0으로 currentPosition를 -1로 초기화한 이유는 시작하면 바로 첫 번째 문자를 읽어야 하고 그렇기에 아직 아무 문자도 읽지 않았기 때문이다.

그러면 문자를 읽는 메서드를 만들어 보자.

class Lexer {
  // ...
  
  private readCharacter(): void {
    if (this.nextPosition >= this.input.length) {
      this.character = "";
    } else {
      this.character = this.input[this.nextPosition];
    }

    this.currentPosition = this.nextPosition;
    this.nextPosition++;
  }
}

readCharacter를 호출하면 이번에 읽어야 할 index nextPosition가 우리가 읽을 수 있는 문자열을 넘어서지 않았는지 확인하고 읽은 문자 character의 값을 대입한다. 그리고 currentPosition에 nextPosition을 대입하고 nextPosition에 1을 더해준다.

혹자는 왜 nextPosition이 이미 input.length를 넘었을 때도 index를 수정하냐고 물어볼 수 있다. 왜냐면 아무 상관없기 때문이다. 흐름에 아무 영향을 주지 않는다.

훌륭하다. 이제 문자를 읽을 수 있다. 한 가지 수정할 점이 있는데 생성자에서 문자를 하나 읽고 시작하게 하는 것이다.

class Lexer {
  // ...
  
  constructor(input: string) {
    this.input = input;
    this.readCharacter(); // 생성되면 문자를 하나 읽고 시작
  }
  
  // ...
}

이제 본격적으로 token을 만들어보자.

class Lexer {
  // ...
  
  public nextToken(): Token {
    let token: Token;

    switch (this.character) {
      case "+":
        token = { type: "plus", literal: this.character };
        break;
      case "-":
        token = { type: "minus", literal: this.character };
        break;
      case "*":
        token = { type: "asterisk", literal: this.character };
        break;
      case "/":
        token = { type: "slash", literal: this.character };
        break;
      case "(":
        token = { type: "lparen", literal: this.character };
        break;
      case ")":
        token = { type: "rparen", literal: this.character };
        break;
      case "":
        token = { type: "eof", literal: this.character };
        break;
      default:
        token = { type: "illegal", literal: this.character };
    }

    this.readCharacter();

    return token;
  }
  
  // ...
}

처리 방법은 매우 간단하다.

1. 현재 읽은 문자가 알고 있는 문자인지 확인
2. 알고 있는 문자라면 토큰으로 변환
3. default에 도달하면 모르는 문자이니 illegal 처리
4. 다음 문자를 읽기
5. 토큰 반환

고작 이게 다인가 싶을 것이다. 맞다. 이게 다이다. 이것으로 테스트 연산자와 허용되지 않은 문자를 통과시켰다.

** 연산자는 어떻게 처리할 수 있을까? 이 또한 간단하다. 현재 읽은 문자가 * 일 때 다음 문자를 미리 읽어서 또 다시 *이면 **로 처리하면 된다.

case "*":
  if (this.input[this.nextPosition] == "*") {
    const character = this.character;
    this.readCharacter();
    const literal = `${character}${this.character}`;
    token = {
      type: "double-asterisk",
      literal,
    };
  } else {
    token = { type: "asterisk", literal: this.character };
  }
break;

많이 왔다. 이제 숫자를 해석해야만 한다. 현재 숫자 테스트 코드에서 아래와 같은 메세지가 나고 있다.

  Object {
    "literal": "1",
-   "type": "number",
+   "type": "illegal",
  }

숫자는 어떻게 해석할 수 있을까? 설마 case "1":, case "2":와 같은 무시무시한 코드를 짜야하는 것은 아닐까? 당연히 그럴 리 없다. 그런 식이면 뭘 할 수가 없다.

우선 우리가 읽으려 하는 문자가 숫자인지 확인하는 helper 하나를 만들어 보자.

const isDigit = (ch: string): boolean => {
  const code = ch.charCodeAt(0);
  return 48 <= code && code <= 57;
}

ascii(unicode라고 해도 상관없다)에서 0과 9는 각각 48, 57이다. 우리가 보는 문자가 해당 코드 범위 안에 있다면 그 문자는 숫자인 것이다.

default:
  if (isDigit(this.character)) {
    const literal = this.readNumber();
    token = { type: "number", literal };
    return token;
  } else {
    token = { type: "illegal", literal: this.character };
  }

default 아래 내용을 위와 같이 변경하면 이제 숫자를 읽어낼 수 있게 된다. 물론 readNumber 메서드를 추가 작성해야만 한다. 하나 주의할 점은 다른 케이스와 다르게 숫자를 읽는 메서드를 호출 후 즉시 return 한다는 점이다. readNumber 메서드의 실제 코드를 보면 이해할 수 있을 것이다.

class Lexer {
  // ...
  
  private readNumber(): string {
    const startPosition = this.currentPosition;
    let dotAppeared = false;
    while (isDigit(this.character) || (this.character === "." && !dotAppeared)) {
      if (this.character === ".") {
        dotAppeared = true;
      }
      this.readCharacter();
    }
    return this.input.substring(startPosition, this.currentPosition);
  }
  
  // ...
}

readNumber 내부를 보면 숫자로 인식될 수 있는 것이 있다면 계속해서 읽어드리면서 하나의 숫자를 완성해 간다. 숫자로 해석될 수 있는 범위를 먹어치우며 substring을 통해서 literal을 반환한다. 이미 다음 문자를 읽었기 때문에 아까 위 token을 만들자마자 즉시 return 한 것이었다.

dotAppeared 변수를 통해서 실수를 받아들일 수 있다. dot(.)은 두 번 이상 등장할 수 없다. 그건 실수가 아니기 때문이다. 만약 점이 두 번 등장하게 되면 조건에 충족하지 못해 빠져나가게 될 것이고 다음번 nextToken에서 illegal 처리될 것이다.

코드를 잘 보면 7. 과 같은 문자열도 실수로 인식되는 것을 알 수 있다. 그게 맞다. 못 믿겠으면 지금 바로 console 창으로 열어서 확인해 보면 된다.

훌륭하다. 이제 숫자도 읽을 수 있다. 그런데 테스트가 통과되지 않는다. 왜냐면 작성한 문자열이 "1 3.14 300"이기 때문이다. 다음과 같은 에러가 나고 있다.

  Object {
-   "literal": "3.14",
-   "type": "number",
+   "literal": " ",
+   "type": "illegal",
  }

흠... 공백이 문제가 되고 있다. 공백을 무시하게 하자. 공백을 왜 무시하냐고 물을 수 있다. 그건 내가 이 언어(수식 문자열)를 그렇게 처리되게끔 의도하기 때문이다.

class Lexer {
  // ... 
  
  public nextToken(): Token {
    let token: Token;

    this.ignoreWhitespace();
    
    // ...
  }
  
  // ...
  
  private ignoreWhitespace(): void {
    while (this.character === " " || this.character === "\t" || this.character === "\n" || this.character === "\r") {
      this.readCharacter();
    }
  }
  
  // ...
}

훌륭하다! 공백도 처리되고 이제 우리가 알고 있는 제한된 문자조합으로 구성된 수식을 토큰화할 수 있게 되었다.