파스 트리

Parse Tree : 파스 트리, 구문 분석 트리

문법에 맞게 작성된 식인지 확인하기 위해 구문 분석 단계에서 만드는 트리. 문법 규칙을 적용해 가며 문장을 분해한 결과를 나무 모양으로 나타낸 것이다.

언어 번역 과정에서의 위치

1. 어휘 분석 : 원시 프로그램을 토큰으로 나눈다
2. 구문 분석(Parsing) : 토큰들이 문법(BNF)에 맞는지 확인하며 파스 트리를 만든다
3. 의미 분석
4. 중간 코드 생성 → 최적화 → 목적 코드 생성

작성된 표현식이 BNF 의 정의에 맞게 만들어졌는지 확인하기 위해 만드는 트리가 파스 트리다.

구조

• 뿌리 : 시작 기호
• 중간 노드 : 비단말 기호(문법 규칙)
• 잎 : 단말 기호, 즉 실제 토큰

잎을 왼쪽부터 읽으면 원래 문장이 나온다.

모호성

한 문장에 대해 파스 트리가 둘 이상 만들어지면 그 문법은 모호하다고 한다. 연산자 우선순위와 결합 방향을 문법에 넣어 모호성을 없앤다.

비슷한 트리와의 구분

• 이진 트리 : 자식이 둘 이하인 트리
• 이진 탐색 트리 : 왼쪽은 작고 오른쪽은 큰 값을 두는 트리
• 편향 트리(Skewed Tree) : 한쪽으로만 자란 트리

이들은 자료 구조의 형태를 가리키는 말이고, 파스 트리는 용도로 붙인 이름이다.

같이 보기

• 어휘 분석
• 컴파일러
• 트리