추상 구문 트리

컴퓨터 과학에서 추상 구문 트리(abstract syntax tree, AST), 또는 간단히 구문 트리(syntax tree)는 프로그래밍 언어로 작성된 소스 코드의 추상 구문 구조의 트리이다. 이 트리의 각 노드는 소스 코드에서 발생되는 구조를 나타낸다. 구문이 추상적이라는 의미는 실제 구문에서 나타나는 모든 세세한 정보를 나타내지는 않는다는 것을 의미한다. 예를 들어, 그룹핑을 위한 괄호는 암시적으로 트리 구조를 가지며, 분리된 노드로 표현되지는 않는다. 마찬가지로, if-condition-then 표현식과 같은 구문 구조는 3개의 가지에 1개의 노드가 달린 구조로 표기된다.

이것이 추상 구문 트리를 상세 구문 트리, 즉 원래의 파스 트리 개념과 구별한다. 파스 트리는 소스코드가 compile, translation되는 도중에 일반적으로는 컴파일 과정에 파서에 의해 빌드된다. 한번 빌드된 이후에는 추가 정보가 후속 처리에 의해 AST트리에 추가된다. (예시. contextual analysis)

추상 구문 트리는 프로그램 분석과 프로그램 변환 시스템에도 사용된다.

컴파일러에서의 응용

추상 구문 트리는 컴파일러에 널리 사용되는 자료 구조인데, 이는 프로그램 코드의 구조를 표현하는 프로퍼티이기 때문이다. AST는 일반적으로 컴파일러의 구문 분석 단계의 결과물이다. 컴파일러가 요구하는 여러 단계를 통해 프로그램의 중간 표현의 역할을 하며 컴파일러의 최종 결과물에 대해 강력한 영향을 준다.

동기

AST는 컴파일 과정에 도움이 되는 몇몇 추가 단계를 가지고 있다.

AST는 모든 구성요소가 가진 속성이나 주석을 통해 수정되고 개선될 수 있다. 이러한 주석과 수정은 변경을 암시하기 때문에, 프로그램의 소스코드로는 불가능하다.
소스코드와 비교해, AST는 구두점이나 구분자(괄호,세미콜론 등)을 가지고있지 않는다.
AST는 일반적으로 컴파일러의 연속적인 분석단계들로 인한 프로그램의 추가정보만을 가진다.. 예를 들어, 소스코드에서의 각 구성요소들의 위치를 저장한 뒤, 컴파일러가 유용한 에러메시지를 출력하게 한다.

AST는 프로그래밍 언어의 고유한 본질, 그리고 문서화 때문에 필요하다. 프로그래밍 언어는 본질적으로 종종 모호함을 가진다. 이러한 모호함을 피하기 위해, 프로그래밍 언어는 context-free-grammer로 특정된다. 하지만, CFG가 표현할 수 없는 문서화된 언어의 특징이 있다. 이들은 유효성과 동작을 결정하기 위해 컨텍스트가 필요한 세부정보이다. 예를 들어, 프로그래밍 언어가 새로운 타입의 선언을 허용한다면 ,CFG는 해당 타입의 이름이나 사용하는 방법등을 예측할 수 없다. 프로그래밍 언어에 사전 정의된 타입 셋이 있더라도, 적절한 사용을 적용하려면 일부 context가 필요하다.