새로운 Smart Contract 프로그래밍 언어 만들기 — Parser

Published in

teamNexters

6 min readJan 20, 2019

저번 포스트에서는 Lexer에 대해서 살펴보았습니다. Lexer에서는 텍스트를 한 글자 한 글자씩 읽어 token을 만들어줍니다. 그런데 이렇게 만들어진 token들을 컴퓨터가 이해할 수 있는 언어로 바꾸기 전에 한 가지 더 해야할 일이 있는데요. 그 역할을 parser가 맡아서 해줍니다. 이번 포스팅에서는 parser가 lexer에서 만들어준 token들을 가지고 어떤 일을 하는지에 대해 설명하려고 합니다.

이전 포스팅: koa project — Lexer가 하는 일은 무엇일까?

Parser?

parser가 하는 일이 무엇일까요? 위키피디아에 비교적 쉽게 설명되어있어 가져와보았습니다.

A parser is a software component that takes input data (frequently text) and builds a data structure — often some kind of parse tree, abstract syntax tree or other hierarchical structure — giving a structural representation of the input, checking for correct syntax in the process.

위와 같이 넓은 범위에서 parser는 input 데이터를 가지고 그것을 구조적으로 나타낼 수 있게 해줍니다. 또한 데이터를 구조적으로 바꾸는 과정에서 주어진 input 데이터가 올바른지 검증도 하게됩니다. 조금 추상적인 것 같으니 간단한 예를 들어볼까요?

> var input = '{"msg": "hello, world"}';
> var output = JSON.parse(input);
> output
> { msg: 'hello, world' }
> output.msg
'hello, world'

이해를 돕기 위해 간단한 javascript 코드를 가져와보았습니다. input으로 ‘{“msg”: “hello, world”}’ string이 주어지고 input 을 JSON.parse 뒤에 숨겨져있는 parser에게 넘겨주면 output 으로 key, value 형식으로 값을 참조할 수 있는 object로 바꿔줍니다. 그런데 이때 다음과 같은 input 을 넘겨주면 어떻게 될까요?

> var input = '{"msg": "hello, world"';

주어진 input 은 완전한 object를 만들지 못하는 string이고 이것을 parser에게 넘겨주면 다음과 같은 일이 벌어집니다.

> var output = JSON.parse(input);
Uncaught SyntaxError: Unexpected end of JSON input
> output
undefined

이렇게 parser는 자신에게 주어진 input 데이터를 구조적으로 나타낼 수 있게 바꾸면서 동시에 input 데이터가 올바른지도 검증하게 됩니다. 위와 같이 주어진 데이터가 구조적으로 바꿀 수 없는 데이터라면 데이터의 문법이 올바르지 않다고 생각하고 구조적으로 바꾸는 일을 멈춥니다. 그래서 보통 parser가 하는 일을 syntax anlysis라고 합니다.

여기까지 JSON parsing을 가지고 parser가 하는 일에 대해서 살펴보았는데요. 그런데 의문이 들 수도 있습니다. 우리가 해야하는 일은 소스코드를 parsing하는 것인데, 지금까지 예로 든 것은 JSON parser입니다. JSON parser하고 koa 소스코드를 parsing 해주는 parser는 다르지 않을까요?

개념적인 수준에서 둘이 하는 일은 다르지 않습니다. 두 가지 parser 모두 주어진 input 데이터를 읽고 구조적으로 나타내고, 나타냄과 동시에 주어진 데이터가 올바른지 검증합니다. 다만 어떤 구조체를 만들 것인지에서 차이가 있습니다.

AST

대부분의 interpreter와 compiler에서 소스 코드를 구조적으로 나타내는 자료구조로 “abstract syntax tree” (AST)를 사용합니다. 그리고 AST는 자료구조이기 때문에 한 가지 형식만 있는 것은 아닙니다. 프로그래밍 언어마다 컨셉은 비슷하지만 디테일은 조금씩 다릅니다.

# source code
let a = 1;# AST
{
  "type": "Program",
  "body": [
    {
      "type": "VariableDeclaration",
      "declarations": [
        {
          "type": "VariableDeclarator",
          "id": {
            "type": "Identifier",
            "name": "a"
          },
          "init": {
            "type": "Literal",
            "value": 1,
            "raw": "1"
          }
        }
      ],
      "kind": "let"
    }
  ],
  "sourceType": "module"
}

AST가 어떻게 생겼는지 감을 잡기 위해 간단한 Javascript 코드와 그것으로 만든 AST를 가지고 왔습니다.

위와 같이 AST에서는 세미콜론이나 ‘=’와 같은 정보들은 생략하고 소스코드에서 필요한 정보들만 트리형태로 나타낸 것을 확인할 수 있습니다. 이렇게 AST에서 ‘abstract’가 들어간 이유는 소스코드에서 불필요한 정보들은 날리고 핵심 데이터만 남겨서 트리를 구성하기 때문입니다.

실제 koa 프로젝트 코드 레벨에서 어떤 아이디어를 가지고 AST를 만들고 token들을 어떻게 파싱하는지에 대해서는 이 포스트에 쓰기에 주제를 조금 벗어나기도 하고 양이 많아질 것 같아 다른 포스트에서 전해드리도록 하겠습니다.

지금까지 parser에서 하는 일을 살펴보았습니다. 결국 parser는 토큰화된 소스코드를 가지고 AST를 만드는 일을 합니다. 그리고 이렇게 AST를 만들게 되면 이제 컴퓨터가 이해할 수 있는 언어로 바꿀 준비가 끝나게 됩니다. 그리고 이런 일은 compiler가 해주게 되는데요. compiler가 어떤 일을 하는지에 대해서는 다음 포스트에서 설명드리도록 하겠습니다.

새로운 Smart Contract 프로그래밍 언어 만들기 — Parser

Parser?

AST

Written by zeroFruit