추상 구문 트리 (Abstract Syntax Tree)
쉽게 풀면
"3 + 4 * 5"라는 수식을 생각해 보세요. 컴퓨터는 이 문장을 사람처럼 눈으로 읽는 게 아니라, 곱셈이 덧셈보다 먼저 계산되어야 한다는 규칙에 따라 나무 구조로 정리합니다. 맨 위에 "+"가 있고, 그 왼쪽 가지에는 "3", 오른쪽 가지에는 "*"가 있으며, 그 "*" 아래에 다시 "4"와 "5"가 달리는 식입니다. 이렇게 코드의 실제 의미(연산 순서, 구조)만 남기고 불필요한 기호는 걷어낸 나무 형태가 추상 구문 트리입니다. 컴파일러나 인터프리터는 코드를 실행하기 전에 반드시 이런 트리 형태로 먼저 정리한 뒤 다음 단계로 넘어갑니다.
왜 중요한가
AST는 프로그래밍 언어 처리의 거의 모든 단계에서 출발점이 되는 자료구조입니다. 컴파일러의 최적화, 타입 검사, 코드 생성이 전부 이 트리 위에서 이루어지기 때문에, 정적 분석·코드 자동완성·리팩토링 도구 같은 소프트웨어 공학 연구는 AST를 다루는 방식에서 성능이 갈립니다. 최근에는 코드를 자연어처럼 다루는 딥러닝 연구(코드 생성, 결함 탐지, 코드 클론 탐지 등)에서도 텍스트만으로는 놓치는 구조적 정보를 보완하기 위해 AST를 입력 표현으로 활용하는 경우가 많아, 프로그래밍 언어 이론과 머신러닝 연구를 잇는 다리 역할을 합니다.
논문에서는 이렇게 쓰입니다
이 문장은 "프로그램 코드를 텍스트 그대로가 아니라, 구조화된 나무 형태로 바꾼 다음 그 구조를 분석해 버그를 찾아냈다"는 뜻입니다. 코드를 문자열이 아닌 트리 구조로 다루면 들여쓰기나 변수 이름 같은 겉모습 차이에 흔들리지 않고 진짜 로직을 비교할 수 있습니다.
컴파일러 최적화 연구에서는 AST를 한 번 만들고 끝나는 게 아니라, 여러 번 훑으면서 미리 계산 가능한 값은 계산해두고(상수 폴딩) 실행되지 않는 코드는 지우는 식으로 트리 자체를 점진적으로 다듬어 나갑니다.
코드 표절·클론 탐지 연구에서는 변수 이름이나 줄바꿈처럼 겉모습만 다른 코드를 구분하기 위해, 텍스트 비교 대신 두 AST가 구조적으로 얼마나 다른지를 계산하는 방식을 흔히 사용합니다.
조금 더 깊게 보면
AST를 다루는 논문을 읽다 보면 트리를 순회(traversal)하는 방식이 자주 등장하는데, 대표적으로 방문자 패턴(visitor pattern)을 이용해 각 노드 타입별로 처리 로직을 나누는 구현이 많습니다. 또한 AST는 이후 단계에서 심볼 테이블과 결합되어 타입 검사나 스코프 분석에 쓰이며, 최적화 단계에서는 제어 흐름 그래프(CFG)나 데이터 흐름 그래프 같은 다른 표현으로 변환되기도 합니다. 딥러닝 기반 연구에서는 AST를 그래프 신경망이나 트리 구조 인코더(tree-LSTM 등)의 입력으로 바꾸어 벡터로 임베딩하는 경우가 많은데, 이때 트리의 깊이나 노드 수가 클수록 정보 손실이나 계산 비용 문제가 논의되곤 합니다.
주의할 점
추상 구문 트리는 코드의 모든 글자를 그대로 담는 구문 트리(parse tree)와는 다릅니다. 괄호나 구분 기호처럼 실행 의미에 영향을 주지 않는 표기는 생략하고, 실제 연산과 구조만 남긴다는 점에서 "추상적"이라는 이름이 붙었습니다.