Abstract Syntax Tree(AST) 추상구문트리란?

우선 컴파일을 한다는 것은 언어간의 의미론적인 매핑(mapping)과정을 뜻합니다.

더 직설적으로 말하면 고급언어를 의미의 변화없이 기계어로 매핑하는 과정이죠.

그런데 고급언어로 넘어가면서 어셈블리어와 같은 저급언어에는 없는 여러가지 추가개념이

들어가게 되었습니다. 어셈블리어에서의 매크로야 그나마 일차원적인 대치 과정이니 상관없지만

함수, 객체지향 쪽으로 들어가면 골치가 아파집니다. 언어는 점점 더 풍부한 요소들이 있는데

이것을 어떻게 단순히 평면적으로 번역할까요? 게다가 규모도 장난이 아니니 일차원적인

자료구조로는 사실상 관리가 불가능합니다. 그럼 어떤 구조로 해야하나? 이런 체계적이고

복잡하고 광범위한 자료 덩어리에 가장 잘 써먹을 수 있는 구조가 바로 트리(tree)입니다.

컴파일러는 내부적으로 여러가지 컴포넌트로 구성되어 있는데 그 첫단계가 바로 소스코드를

파싱해서 AST(Abstract Syntax Tree)라고 불리는 자료구조를 만들어내는 것입니다. 모든 고급

언어의 컴파일러가 하는 것이 바로 이것입니다. 이 트리를 검사하고 최적화하고 정해진 기계어로

대치해서 나오는 것이 기계어 덩어리, 목적코드입니다. 일단 거기는 범위를 벗어나니까 생략하고..

'트리를 어떻게 구성할 것인가?'

AST 관점에서 연산자 우선순위란 바로 이런 것입니다.

'a + b * c + d'라는 문장을 파싱해서 AST를 생성한다고 가정해봅시다

 

 

이 트리구조는 우리의 의도와는 다르지만 유효합니다.

이럴 경우 컴파일러, 정확히 말해서 파서는

 

(1) +에 a, b를 속하게 할 것인지 (순서대로 트리를 구성)

(2) *에 b, c를 속하게하고 그것을 +에 속하게 할 것인지 (곱셈을 우선해서 트리를 구성)

 

를 결정해야합니다. 근데 그게 불가능하죠, 이건 선택의 문제이니까요. 파서가

내릴 수 있는 판단은 기껏해야 파싱과정에서 문법과 일치하느냐 틀리냐인데 두가지 경우

모두 문법적으로는 틀리지 않습니다. 이런 경우를 모호하다(ambiguous)라고 말합니다.

 

결국 연산자 우선순위는 'AST를 구성하는 과정에서 문법적으로 옳은 두가지 이상의

경우를 만났을 때 모호함을 없애기 위한 규칙'인 것입니다.

출처:http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=103652566&qb=YWJzdHJhY3Qgc3ludGF4IHRyZWU=&enc=utf8&section=kin&rank=1&search_sort=0&spq=1&pid=TPT15lpySEdsstUnohdssssssOh-388548&sid=eAk6QwofZ2FIf1WOuLKY2g%3D%3D