[프로그래밍 언어론] 파스트리(Parse tree)의 개요

* 이 포스트는 이전에 공부하면서 보고서로 작성한 것을 그대로 포스팅 한 것입니다.
* 참조교재 : 프로그래밍 언어론 (한빛미디어)

파스트리(parse tree)는 BNF 유도 과정을 이해하기 쉬운 트리 형태의 계층적 구조로 나타낸 것으로, 파스트리의 시작 기호는 근(root)입니다.

이는 어떠한 표현이 BNF에 의해 바르게 작성되었는지를 확인하기 위해 작성하는데,
문법의 시작 기호(non-terminal)로부터 적합한 생성 규칙을 적용할 때마다 가지치기가 이루어집니다.

트리의 모든 가지가 터미널로 유도되어 가지치기가 끝난 상태의 트리를 파스트리라 하며,
일 파스트리가 존재하면 이는 주어진 BNF에 의해 올바르게 작성되었음을 의미합니다.

파스트리에서 내부의 노드들은 비단말 기호로 표시되며, 모든 잎 노드(leaf node)들은 단말 기호로 표시됩니다.

다음은 앞서 BNF를 언급하며 예시로 다루었던 123에 대한 유도 과정을 파스 트리로 나타내는 과정입니다.

당시에 열심히 그린답시고 그렸었던 것 같은데 거의 발그림 수준이네요... ^^;;