추상 구문 트리
추상 구문 트리(Abstract Syntax Tree, AST)는 컴파일러가 소스 프로그램의 구문 구조를 트리 형태로 표현한 자료 구조다. 구문 분석기가 토큰과 문법에 따라 만든 결과에서 불필요한 괄호·구분 기호 등의 표현을 생략하거나 추상화하고, 선언과 식·문·연산 관계 등 의미 있는...
| 영어 명칭 | Abstract Syntax Tree |
|---|---|
| 약칭 | AST |
| 분류 | 소스 프로그램의 트리 기반 구문 표현 |
| 생성 단계 | 파서 이후·의미 분석과 연계 |
| 구성 | 선언·식·문·연산·타입·소스 위치 |
| 특징 | 불필요한 구문 기호를 추상화 |
| 활용 | 컴파일러, IDE·리팩터링·정적 분석 |
| 관련 기술 | 구문 트리(Parse Tree), 중간 표현 |
| 대표 구현 | Clang AST, 언어별 컴파일러 AST |
| 공식 예시 | Clang Introduction to AST |
추상 구문 트리(Abstract Syntax Tree, AST)는 컴파일러가 소스 프로그램의 구문 구조를 트리 형태로 표현한 자료 구조다. 구문 분석기가 토큰과 문법에 따라 만든 결과에서 불필요한 괄호·구분 기호 등의 표현을 생략하거나 추상화하고, 선언과 식·문·연산 관계 등 의미 있는 프로그램 요소를 노드로 나타낸다. 파스 트리(Parse Tree)와는 관계가 있지만 반드시 같은 노드·구조를 가진 것은 아니다.[1]
AST의 노드는 리터럴·변수 참조·이항 연산·함수 호출과 선언·제어문 등을 나타낼 수 있다. 하위 노드의 관계와 소스 범위를 연결하면 구문 오류·타입 불일치와 변수 바인딩을 진단할 수 있다. 일부 컴파일러는 AST에 타입과 심벌 참조를 직접 기록하고, 다른 구현은 이후 별도 타입 있는 IR·HIR을 생성한다.
IDE의 코드 탐색과 자동 완성·리팩터링, 정적 분석기는 AST와 이름·타입 정보를 활용한다. 프로그램 변환에서는 노드를 다시 소스 코드로 출력할 수 있지만 원래의 주석·공백·토큰 배치를 전부 보존하지 못할 수 있어 정확한 소스 코드 변환에는 별도 구문 보존 자료가 필요할 수 있다.
AST와 LLVM IR 등의 낮은 수준 표현은 역할이 다르다. AST는 원래 언어의 선언·문장과 고수준 구조를 유지하는 경향이 있고 하위 IR은 제어·데이터 흐름, 메모리와 연산을 최적화하기 쉬운 형태로 표현한다. lowering을 통해 여러 단계의 중간 표현을 거칠 수 있다.