[ Compiler ] Abstract syntax tree

2018. 8. 28. 13:41공부 자료/컴파일러

[ Compiler ] Abstract syntax tree


    AST, 다른말로 "Abstract Syntax Tree" 혹는 "Syntax Tree" 라고 불리는 이 Tree는 프로그래밍 언어로 쓰여진 소스코드의 abstract syntactic 구조를 표현하기 위해서 사용됩니다. 쉽게 말하자면 특정 프로그래밍 언어로 작성된 프로그램 소스 코드를 각각 의미별로 분리하여 컴퓨터가 이해할 수 있는 구조로 변경시킨 트리를 의미합니다.

    "Abstract Syntactic"란 프로그래밍 언어의 문법 및 각 문단의 역할을 표현하기 위한 규칙인데, data의 구조와 종류만 포함됩니다. 프로그램에서 data의 구조 / 종류라는 말은, 예를 들어 C언어에서 while이 의미하는 것은 "condition"을 의미하는"Statement" 이며, int a 에서 a가 의미하는 것은 "변수명"이라는 "identifier"이라는 것이 data의 구조 / 종류입니다. 즉, " "statement", "expression", "identifier" 과 같이 나눌 수 있도록 정의하는 문법 표현을 위한 규칙 " 이라고 Abstract Syntactic 을 이해하면 되겠다.

    그림을 보면 AST에 대하여 이해하기 훨씬 편한데, 다음 코드를 AST로 표현하면 다음과 같습니다.

while b != 0:
    if a > b:
        a = a − b
    else:
        b = b − a
return a


[ 사진 1 : abstract syntax tree example ]

    트리의 각 노드는 소스코드를 구성합니다. abstract라는 단어의 의미대로 실제 문법상의 의미를 자세하게 표현 ( 예를 들어 함수의 재귀 호출등을 다시 파고들어 node로 표시하거나.. ) 하는 것이 아니라, 대략적으로 "if-condition-then-statement" 를 하나의 뭉치( 트리 )로 표현하는 것을 의미합니다. AST는 abstract하게 짜여진 parsing tree 이므로, 컴파일 단계에서 더 추가적으로 데이터나 정보들이 붙을 수 있다는 것에 유의하도록 합시다.

   AST는 컴파일러가 프로그램의 각 부분의 사용이 옳바른지, 프로그래밍 언어의 사용이 틀린 부분은 없는지 Semantic Analysis( 문맥적인 소스코드 검사 )의 단계에서 사용되곤 합니다. AST의 모든 단계를 거쳤을 때 이상이 없다는 것은 프로그램이 정확하다는 의미를 뜻한다. 






# 참조