추상 구문 트리(abstract syntax tree, AST)에 대하여..

AST가 만들어지는 과정

컴파일러가 소스 코드를 처리하는 단계 [이미지 출처 및 학습한 사이트] - dev.to

위 이미지를 설명하자면 아래와 같습니다.

  1. 소스 코드는 먼저 어휘 분석 과정(Lexer)을 통해 토큰이라는 더 작은 단위로 나뉩니다.
    어휘 분석은 소스 코드를 토큰으로 분해하므로 토큰화     라고도 합니다 .
  2. 그런 다음 토큰은 파서(Parser)에 의해 구문 트리라고 하는 트리로 구문 분석됩니다.
  3. 이 과정을 거쳐서 최종적으로 AST가 만들어지게 됩니다.

해당 순서에 대한 자세한 설명은 아래에서 진행하도록 하겠습니다!

 

컴파일러의 첫 번째 단계 : 어휘 분석

렉서(Lexer) = 어휘분석
렉서는 소스 코드를 읽어 토큰(Token)이라는 의미 있는 단위로 분해합니다.

문자에서부터 인코딩, 유니코드, 공백, 주석 등 텍스트와 관련된 모든 것을 분해하여, 다음 단계인 구문 분석이 신경 쓰지 않도록 깔끔하게 정리해주죠

이처럼 텍스트를 토큰으로 바꾸는 전체 과정을 어휘 분석이라고 합니다. 또한 토큰으로 바꾼다고 하여, 토큰화 라고도 부릅니다.

토큰이란?

토큰이란 컴파일러가 코드를 이해하는 최소 단위로, 키워드(if, for), 식별자(변수명), 연산자(+, =), 리터럴(10, "hello") 등이 해당됩니다.

우리가 문장을 명사, 동사, 형용사 등 단어로 나누는 것처럼,

컴파일러는 소스 코드를 다양한 유형의 토큰으로 나누려고 합니다. 이 단계가 어휘 분석 단계죠

따라서 컴파일러가 이해하고 있는 내용과 함께 분해한 텍스트를 넣게 됩니다!

예) int a = 10; ⇒ [int] [a] [=] [10] [;] ⇒ [키워드 : int] [이름 : a] [연산자 : =] [리터럴 : 10] [문장부호 : ;]

컴파일러의 두 번째 단계 : 구문 분석

파서(Parser) = 구문분석

파서는 렉서로부터 전달받은 토큰들의 흐름을 분석하여 코드의 문법 구조를 파악하고, 이를 AST라는 트리 형태로 만드는 과정입니다. =(토큰을 받아 AST, 즉 추상 구문 트리로 변환함)

이 과정에서 토큰 간의 관계, 중첩 구조(예: if문 안의 for문), 연산 우선순위 등 코드의 전체적인 구조를 처리하게 됩니다.

나눈 단어들이 모여서 만들어진 문장을 주어, 목적어, 서술어 등으로 문장의 구조를 파악하는 것처럼,
컴파일러는 토큰들을 조합하여 그 구조를 파악하고 이를 이용해 트리 노드를 만듭니다!

예) [키워드 : int] [이름 : a] [연산자 : =] [리터럴 : 10] [문장부호 : ;]

  1. 키워드 int는 타입이니까, 타입 노드를 만들고 int를 연결
  2. (int라는 타입이 나왔으니, 뒤에 오는 것은 변수의 이름이겠군)
  3. a는 변수의 이름, 변수의 이름 노드를 만들고 a를 연결,
  4. (연산자 = 가 나왔으니, 뒤에 오는 것은 초기 값 노드에 넣어야겠다)
  5. 10은 리터럴 값이니까, 리터럴 노드를 만들고 10을 연결,
  6. (문장부호 ;가 나왔으니 끝났구만)

하지만 위의 예시처럼 사실 파서는 단순히 토큰 하나씩만 보면서 판단하는게 아닙니다! 앞으로 나올 토큰들도 고려해서 판단하죠.

왼쪽부터 시작하는 하향식 파서(LL Parser)를 포함한 여러 파서들은 lookahead를 가지고 있기 때문에, 아직 처리되지 않은 다음 토큰들을 미리 엿보고 난 후 판단합니다! (참고자료: 위키피디아 - LL parser)

만약 a.init()을 순서대로 본다면?

init을 판단 할 때 lookahead가 없어서 ()를 보지 못했다면 이게 멤버 변수인지 멤버 함수인지 판단하기 어려웠겠죠.

 

컴파일러의 결과물 : AST

이 과정을 거쳐서 만들어진 트리가 바로 AST(abstract syntax tree) 입니다.

int a = 10; 라는 코드는 AST로 아래와 같이 트리 형태로 정리되었죠!

그렇다면 이번 미션의 요구사항인 var a = new A.init(); 코드는 자바스크립트에서 어떻게 AST로 표현될까요?

지금까지 학습한 내용을 바탕으로 코드를 AST로 표현하기 위한 설계를 한번에 이어서 해보겠습니다!

 

자바 스크립트에서의 AST 설계

자바 스크립트 ESTree를 기준으로 설계하며, 설계에 대한 명세는 ESTree GitHub를 따릅니다.
ESTree GitHub

[어휘 분석 과정 진행]

우선, 어휘 분석을 진행하여 소스 코드를 토큰으로 나눠야 합니다.

var a = new A.init(); 를 저는 먼저 아래와 같이 나눠보겠습니다.

var a = new A . init ( ) ;

이후 의미를 판단해서 넣어주면 아래와 같이 토큰값이 됩니다.

키워드 : var 이름 : a 연산자 : = 키워드 : new 이름 : A 문장부호 : . 이름 : init

문장부호 : ( 문장부호 : ) 문장부호 : ;

[구문 분석 과정 진행]

  1. 키워드 var 로 시작하니 가장 큰 노드를 변수 선언으로 둬야겠어
  2. 변수의 구성 노드를 만들고, 변수 이름과 초기값을 자식으로 둬야지
  3. var로 시작했으니 뒤에는 변수 이름이 오겠구나. 변수의 이름 노드를 추가해야지
  4. 이름 a 가 왔으니 이게 변수의 이름이겠군! a를 변수의 이름 노드의 자식 노드에 넣자
  5. = 가 나왔으니 뒤에는 초기 값이 오겠구나. 초기값 노드를 추가해야지

  1. new 키워드가 나왔으니 객체 생성을 하겠구나. 객체 생성을 초기값 노드의 자식 노드에 넣자
  2. 이름 A가 나왔네, lookahead로 보니 .과 init이 있구나.
  3. 이것은 . 을 이용해 A라는 객체의 init이라는 멤버에 접근하는 것이군, 멤버 접근 노드를 객체 생성 노드의 자식 노드에 넣어야겠다.
  4. 멤버 접근 노드의 자식 노드에 변수의 이름 A 와, 멤버의 이름 init 을 넣어야겠다.
  5. ( 와 ) 가 나왔네? init은 멤버 함수였군, 함수 호출 노드가 나왔으니 객체 생성 자식 노드에 인자를 넣어야겠다
  6. ; 가 나왔으니 끝이군

 

다이어그램 설계를 바탕으로 데이터 구조로 변환

위의 설계를 자바스크립트의 데이터 구조로 변환하기 위해 역시 ESTree의 공식 명세를 따르겠습니다.
https://github.com/estree/estree/blob/master/es5.md

먼저, var a = 까지의 변환은 아래와 같습니다.

// var a = 까지의 구조
{
  "type": "VariableDeclaration", // 변수 선언
  "declarations": [
    {
      "type": "VariableDeclarator", // 변수의 구성
      "id": {
        "type": "Identifier", // 변수의 이름
        "name": "a"
      },
      "init": { // 초기값
  ],
  "kind": "var" // var 키워드로 변수 선언 (var, let, const가 있음)
}

변수 선언 이후, 변수의 구성(VariableDeclarator) 노드로 다시 이어주는 이유는, var a = 1, b = "hello" 와 같이 하나의 var 키워드에 2개의 변수를 선언할 수 있기 때문에 이를 나누어 주는 역할을 합니다.

// **VariableDeclaration**
interface VariableDeclaration <: Declaration {
    type: "VariableDeclaration";
    declarations: [ VariableDeclarator ];
    kind: "var";
}

// **VariableDeclarator**
interface VariableDeclarator <: Node {
    type: "VariableDeclarator";
    id: Pattern;
    init: Expression | null;
}

결과적으로 var 키워드로 선언된 변수의 경우, VariableDeclaration - VariableDeclarator 를 거쳐, id(이름)과 init(초기값)을 노드로 가지게 됩니다.

초기값 이후의 과정들을 나타내면 아래와 같습니다.

{
  "type": "VariableDeclaration", // 변수 선언
  "declarations": [
    {
      "type": "VariableDeclarator", // 변수의 구성
      "id": {
        "type": "Identifier", // 변수의 이름
        "name": "a"
      },
      "init": { // 초기값
        "type": "NewExpression", // 객체 생성
        "callee": {
          "type": "MemberExpression", // 멤버 접근
          "object": {
            "type": "Identifier", // 변수의 이름
            "name": "A"
          },
          "property": {
            "type": "Identifier", // 멤버의 이름
            "name": "init"
          }
        },
        "arguments": []
      }
    }
  ],
  "kind": "var" // var 키워드로 변수 선언 (var, let, const가 있음)
}

 

  1. https://www.youtube.com/watch?v=ZI198eFghJk
  2. https://dev.to/balapriya/abstract-syntax-tree-ast-explained-in-plain-english-1h38
  3. https://en.wikipedia.org/wiki/LL_parser
  4. https://github.com/estree/estree/blob/master/es5.md
저작자표시 (새창열림)

'CS 공부' 카테고리의 다른 글

해시함수 - 버킷사이즈 - 분리체이닝(Separate Chaining)  (2) 2025.08.05
메모리 구조  (0) 2023.11.10
OOP의 5대 원칙  (0) 2023.11.08
프로세스와 스레드  (0) 2023.11.07

티스토리툴바