AST(Abstract Syntax Tree; 추상 구문 트리)는 실제 코드에서 기호(괄호, 세미콜론 등)와 같이 필요없는 정보를 제외하고 만든 트리이다.
Syntax Tree는 괄호, 세미콜론 등 모든 것을 포함한 트리이다.
컴파일러에서 많이 사용하는 자료 구조이다.
고급 언어 컴파일러에서 사용되는데, AST를 만든 후 이 트리로 목적 코드를 만든다.
int a = 10;
C
복사
위 코드는 자료형 int인 Keyword, 변수 이름인 Identifier, 마지막으로 변수의 값인 Literal로 이루어져 있다.
만약, a + b * c + d 라는 식이 있다면
1.
a + b 그리고 c + d를 계산 후 곱 연산
2.
b * c 이후 더하기 연산
등 다양한 연산 방법이 있다.
이를 AST로 변환하면 어떤 순서로 연산을 해야되는지 알 수 없는데 이를 해결하기 위해 연산자 우선순위가 생겼다.
컴파일 과정
1.
Lexical Analysis (낱말 또는 어휘 분석)
a.
입력된 코드들을 의미가 있는 단위로 묶는다. 이후 Token을 만들어낸다.
2.
Syntax Analysis (구문 분석)
a.
위에서 만들어진 Token으로 Syntax Tree를 만든다.
b.
이 때 문법적 오류를 확인한다.
3.
Semantic Analysis (의미 문석)
a.
Semantic(의미)에 따라 필요한 정보만 트리로 만드는데 이 때 결과물이 AST이다.
b.
이 때 변수 자료형이 불일치 하는 등의 오류를 확인한다.
4.
Intermediate Representation (중간 표현)
a.
소스 코드를 표현하기 위해 내부적으로 사용하는 코드이다.
b.
최적화 처리에 사용된다.
c.
C언어의 경우 이 과정에서 GIMPLE Tree를 만든다.
5.
이후 어셈블리어 등으로 명령어를 바꾸고 최적화한다.
6.
최종적으로 기계어로 바꾼다.
1번부터 4번까지의 과정을 컴파일러 프론트엔드, 이후 과정을 컴파일러 백엔드라고 한다.