AST (& Parse Tree)

AST (Abtract Syntax Tree)

 

AST - 추상 구문 트리

어휘 분석(lexical analysis 또는 scan) 단계에서 도출된 토큰들을 가지고 해당 언어의 문법에 입각하여 트리 구조로 재편한 것이 AST다. (※ 추가 설명은 맨 아래)

예를 들어,

a = b + c

라면 아래와 같은 트리 구조가 나올 수 있다.

=
|
a -- +
     | -- |
     b    c

 

위의 구문 트리가 추상적(abstract)인 이유가 있다. 원래의 구문 트리는 아래와 같은 형태가 된다. (BNF는 생략)

E
|
|---|---|
E   E   E
|   |   |
id  op  |
|   |   |
a   =   |
        |---|---|
        E   E   E
        |   |   |
        id  op  id
        |   |   |
        b   +   c

 

파스 트리(Parse Tree)라고 부르는데 꽤 복잡하다. 이를 컴퓨터(컴파일러)가 처리하기 쉽게 간략화(추상화)한 것이 AST다.

 

예를 하나 더 들어보겠다.

if (x - c) a = 1

if
|
|-----------|
-           |
|           |
|---|       |
x   c       |
            |
            =
            |
            |---|
            a   1

 

드래곤북의 4장 구분 분석 단계에선 Parse Tree 표현으로 설명한다. 구문 분석 단계를 배울 때 AST는 축약이 너무 많기 때문에 교육용으로는 적합하지 않나 보다.

 

※ 어휘 분석 단계 다음은 구문 분석(Syntax Analysis 또는 그냥 파싱) 단계이며 여기서 토큰들을 AST로 재구성해 준다. 중요한 점은 파싱 단계에서의 문법은 CFG(Context-Free Grammar) 즉, 문맥자유문법이라 칭하는 한정된 문법만을 적용한다는 점이다. 아래 포스트에 자세한 설명을 해 놓았으니 참고하시기 바란다.

 

https://swjman.tistory.com/236

Context-Free Grammar 그리고 CFG의 반댓말