Gitsunmin

TIL

TIL
(=Today I Learned)

AST (Abstract Syntax Tree)

Abstract Syntax Tree는 한국어로 추상 구문 트리로 번역이 되어지며, 소스 코드를 특정 의미와 위치 등 정보를 바탕으로 트리를 만든 것을 말합니다.

AST의 예시

아래의 코드를 예시로 들어보겠습니다.

function sayHi() {
  console.log("hi");
}

위의 코드는 단순히 javascript에서 “hi” 로그를 찍어주는 함수입니다. 위 함수를 AST Explorer를 이용하여 AST를 확인해보겠습니다.

{
  "type": "Program",
  "start": 0,
  "end": 46,
  "body": [
    {
      "type": "FunctionDeclaration",
      "start": 0,
      "end": 46,
      "id": {
        "type": "Identifier",
        "start": 9,
        "end": 19,
        "name": "consolelog"
      },
      "expression": false,
      "generator": false,
      "async": false,
      "params": [],
      "body": {
        "type": "BlockStatement",
        "start": 22,
        "end": 46,
        "body": [
          {
            "type": "ExpressionStatement",
            "start": 26,
            "end": 44,
            "expression": {
              "type": "CallExpression",
              "start": 26,
              "end": 43,
              "callee": {
                "type": "MemberExpression",
                "start": 26,
                "end": 37,
                "object": {
                  "type": "Identifier",
                  "start": 26,
                  "end": 33,
                  "name": "console"
                },
                "property": {
                  "type": "Identifier",
                  "start": 34,
                  "end": 37,
                  "name": "log"
                },
                "computed": false,
                "optional": false
              },
              "arguments": [
                {
                  "type": "Literal",
                  "start": 38,
                  "end": 42,
                  "value": "hi",
                  "raw": "\"hi\""
                }
              ],
              "optional": false
            }
          }
        ]
      }
    }
  ],
  "sourceType": "module"
}

위 객체는 type, start, end, body 등의 속성을 가지고 있습니다. 이 속성들은 아래와 같은 의미를 가지고 있습니다.

  • type: 해당 노드의 타입을 나타냅니다.
  • start: 해당 노드의 시작 위치를 나타냅니다.
  • end: 해당 노드의 끝 위치를 나타냅니다.
  • body: 해당 노드의 자식 노드를 나타냅니다.

위의 예시에서는 Program이라는 노드가 가장 상위 노드이며, body 속성을 통해 자식 노드를 가지고 있습니다. body 속성은 FunctionDeclaration이라는 노드를 가지고 있으며, FunctionDeclaration 노드는 body 속성을 통해 자식 노드를 가지고 있습니다. 이러한 형태로 노드가 계속해서 이어지며, 최종적으로는 Literal 노드를 만나게 됩니다.

위의 예시는 javascript의 AST를 나타낸 것이며 프로그래밍 언어별로 조금씩 다 다르지만, 대부분의 프로그래밍 언어는 비슷한 형태의 AST를 가지고 있습니다.

AST의 사용

AST는 주로 컴파일러에서 사용됩니다. 컴파일러는 소스 코드를 기계어로 변환하는 역할을 하며, 이러한 변환 과정에서 AST를 사용합니다.