파스 트리
IT 위키
Parse Tree : 파스 트리, 구문 분석 트리
문법에 맞게 작성된 식인지 확인하기 위해 구문 분석 단계에서 만드는 트리. 문법 규칙을 적용해 가며 문장을 분해한 결과를 나무 모양으로 나타낸 것이다.
- 어휘 분석 : 원시 프로그램을 토큰으로 나눈다
- 구문 분석(Parsing) : 토큰들이 문법(BNF)에 맞는지 확인하며 파스 트리를 만든다
- 의미 분석
- 중간 코드 생성 → 최적화 → 목적 코드 생성
작성된 표현식이 BNF 의 정의에 맞게 만들어졌는지 확인하기 위해 만드는 트리가 파스 트리다.
- 뿌리 : 시작 기호
- 중간 노드 : 비단말 기호(문법 규칙)
- 잎 : 단말 기호, 즉 실제 토큰
잎을 왼쪽부터 읽으면 원래 문장이 나온다.
한 문장에 대해 파스 트리가 둘 이상 만들어지면 그 문법은 모호하다고 한다. 연산자 우선순위와 결합 방향을 문법에 넣어 모호성을 없앤다.
- 이진 트리 : 자식이 둘 이하인 트리
- 이진 탐색 트리 : 왼쪽은 작고 오른쪽은 큰 값을 두는 트리
- 편향 트리(Skewed Tree) : 한쪽으로만 자란 트리
이들은 자료 구조의 형태를 가리키는 말이고, 파스 트리는 용도로 붙인 이름이다.
