[자료구조] 구문 트리 Syntax Tree, 추상 구문 트리 AST, Abstract Syntax Tree

출처

ChatGPT

---

구문 트리(Syntax Tree)는 프로그래밍 언어나 자연어 처리에서 문장의 구문적 구조를 분석하고 표현하는 트리 구조이다. 구문 트리는 주로 컴파일러나 인터프리터에서 소스 코드를 분석하고 처리하는 과정에서 중요한 역할을 한다. 구문 트리는 프로그램의 문법을 이해하고, 이를 통해 최적화, 코드 변환, 코드 생성 등의 작업을 수행하는 데 사용된다.

 

구문 트리는 크게 두 가지로 나눌 수 있다.

1. 구문 트리 Syntax Tree : 소스 코드의 구문적 요소를 나타낸다.

2. 추상 구문 트리 AST, Abstract Syntax Tree : 불필요한 세부 요소를 생략하고, 중요한 문법 구조만을 표현한 트리이다. 컴파일러에서 주로 사용된다.

 

1. 구문 트리 Concrete Syntax Tree, CST

구문 트리는 소스 트리가 문법에 맞는지 확인하는 데 사용된다. 소스 코드를 토큰화(tokenization)한 후, 파싱(parsing) 과정을 통해 생성되며, 소스 코드의 구문적 세부 사항을 모두 포함한다. 즉, 입력된 프로그램의 모든 문법적 요소를 세밀하게 표현한 구조이다.

 

특징

• 정확한 문법 구조를 보여주며, 소스 코드의 세부 문법 정보를 모두 포함한다.
• 프로그래밍 언어의 문법(Grammar) 규칙에 따라 트리 형태로 변환된다.
• 세미콜론, 괄호 등과 같은 문법적 세부 사항도 포함된다.

 

예시

다음과 같은 수식이 있다고 가정해 보자.

((2 + 3) * (5 - 2))

 

구문 트리는 모든 구문적 세부사항을 표현합니다. 즉, 연산자뿐만 아니라 괄호와 같은 구문적 요소도 트리의 일부로 포함다.

        (*)
       /   \
     ( )    ( )
     /        \
    (+)      (-)
   /   \    /   \
  (2)  (3) (5)  (2)

 

여기서 괄호는 중요한 구문적 요소로 표현되며, 연산자 +와 -, 그리고 피연산자 2, 3, 5는 각각 괄호 안에 포함된 구조를 가지고 있다. 이처럼 구문 트리에서는 구체적인 문법적 구조가 모두 포함된다.

 

2. 추상 구문 트리 AST, Abstract Syntax Tree

추상 구문 트리는 구문 트리에서 불필요한 세부 문법 정보를 제거하고 중요한 구조적 정보만을 표현한 트리이다. AST는 컴파일러에서 소스 코드를 최적화하거나 코드 생성을 하는 데 주요한 역할을 한다. 구문 트리와 달리 세미콜론, 괄호 등의 문법적 요소는 제외되고, 의미 있는 문법 요소만 포함된다. 

 

특징

• 더 간결한 형태로 소스 코드의 구조를 표현한다.
• 컴파일러는 추상 구문 트리를 사용해 코드 분석과 최적화 작업을 수행한다.
• 연산자의 우선순위와 같은 구문적 정보는 포함되지만, 괄호나 세미콜론 등은 생략된다.

 

예시

위에서 사용한 ((2 + 3) * (5 - 2)) 를 추상 구문 트리로 표현하면, 세부 구문 정보를 생략한 형태로 트리를 간략화할 수 있다. 여기서는 괄호와 같은 구문적 세부사항이 생략된다.

        (*)
       /   \
     (+)   (-)
    /   \  /   \
   2    3 5    2

 

추상 구문 트리에서는 괄호와 같은 문법적 세부사항을 생략하여 연산의 핵심 구조만을 표현한다. 2 + 3와 5 - 2가 각각 연산의 순서만 보존되어 표현되고, 괄호는 더 이상 필요하지 않으므로 생략된다. 결과적으로, 연산자와 피연산자만 남아 간결하게 표현된다.

 

구문 트리의 역할

구문 트리는 소스 코드 분석의 핵심 단계로, 다음과 같은 역할을 한다.

1. 문법 분석

소스 코드가 문법적으로 올바른지 확인한다. 이 과정에서 소스 코드가 언어의 문법 규칙에 맞는지 검사하는 데 사용된다.

2. 코드 최적화

컴파일러는 AST를 기반으로 불필요한 연산을 제거하거나 효율적인 코드로 변환한다.

3. 코드 생성

컴파일러는 AST를 사용해 저수준 코드(기계어 또는 중간 코드)로 변환하는 과정을 진행한다.

4. 디버깅 및 분석 도구

구문 트리는 코드의 구조적 분석을 통해 코드 품질을 검토하거나, 코드 변환, 리팩토링 도구에서 활용될 수 있다.

 

구문 트리와 추상 구문 트리의 차이점

구문 트리 CST	추상 구문 트리 AST
소스 코드의 모든 문법적 요소를 포함	불필요한 문법 요소(괄호, 세미콜론 등)를 생략
매우 자세한 구조를 가짐	핵심적인 구문만 포함하여 간결함
문법 구조를 분석하는 데 사용됨	코드 최적화 및 코드 생성을 위한 구조
소스 코드의 구체적 문법을 반영	소스 코드의 핵심적인 논리 구조를 표현

 

예시 : 간단한 코드의 구문 트리와 추상 구문 트리

코드 예시

int x = (a + b) * c;

 

구문 트리

구문 트리는 int, =, ;와 같은 문법적인 요소와 괄호 등 모든 문법 정보를 포함한다.

     (=)
    /   \
 (int x)  (*)
         /   \
       (+)   (c)
      /   \
    (a)   (b)

 

추상 구문 트리

추상 구문 트리는 중요한 연산과 값만 남겨놓고 불필요한 문법적 요소를 제거한 트리이다.

     (=)
    /   \
 (x)    (*)
       /   \
     (+)   (c)
    /   \
  (a)   (b)

 

괄호나 int, ; 등의 문법적 요소는 제외되고, 변수와 연산자만 남은 것을 볼 수 있다.

 

결론

구문 트리(Syntax Tree)와 추상 구문 트리(AST)는 컴파일러나 인터프리터에서 코드를 분석하고 처리하는 데 매우 중요한 역할을 한다. 구문 트리는 소스 코드의 세부적인 문법 구조를 보여주고, 추상 구문 트리는 필수적인 논리적 구조만을 표현함으로써 효율적인 코드 변환 및 최적화를 돕는다. AST는 특히 컴파일러의 중간 단계에서 많이 사용되며, 구문적 분석 후의 최적화와 코드 생성에 필수적이다.