파스 트리

파스 트리(parse tree), 파싱 트리(parsing tree), 어원 트리(derivation tree), 구체적인 구문 트리(concrete syntax tree)는 올바른 문장에 대해 트리 구조로 나타낸 것을 말한다. parse라는 단어는 주로 전산 언어학에서 사용된다. syntax tree가 더 종종 사용된다.

파스 트리는 입력 언어의 문법을 구체적으로 반영하는데 이것은 컴퓨터 프로그래밍에서 쓰이는 추상 구문 트리와 확실하게 구분을 지어준다. 문법을 가르치기 위해 사용되는 Reed-Kellogg의 문장 다이어그램과 달리 파스 트리는 다른 종류의 구성요소를 위해서 별개의 기호를 사용하지 않는다.

파스 트리는 주로 구성 요소들의 constituency grammars 관계나 독립적인 문법의 독립 관계를 기반으로 만들어진다. 파스 트리는 컴퓨터 언어(프로그래밍 언어)가 해석될 때와 같이 문장이나 자연어를 위해 생성된다.

관련된 개념으로는 transformational generative 문법에서 사용되는 구문 마커나 P-marker가 있다. 구문 마커는 구문 구조로 표시된 언어 표현이다. 이것은 트리의 형식으로 표현되거나 대괄호로 묶인 표현으로 표현될 수 있다. 구문 마커는 구문 구조 규칙을 적용하여 생성되고 그 자체는 추가적인 변환 규칙의 적용 대상이다. 구문적으로 모호한 문장은 "파스 포레스트(parse forest)"라고 한다.

구 구조 기반 파스 트리

구 문법에서 구조 기반 트리는 단말 노드와 비단말 노드를 구분한다. 안쪽에 있는 노드는 비단말 노드로 분류하고, 리프 노드들은 단말 노드로 분류한다. 아래의 이미지는 구 구조 기반 트리를 나타낸다. John hit the ball이라는 영어 문장의 구문 구조를 나타낸다.

파스 트리는 S로 시작하고 각각의 리프 노드(John, hit, the ball)로 종료되는 전체 구조이다. 다음과 같은 약어가 트리에서 사용된다.

• S는 문장(sentence), 이 예시의 최상위 레벨 구조.
• NP는 명사구(noun pharase), 가장 첫번째 (가장 왼쪽의) NP, 명사 "John", 은 문장에서 주어 역할을 한다. 두번째 NP는 문장의 목적어이다.
• VP는 동사구(verb phrase), 술어로 사용된다.
• V는 동사(verb). 이 경우에서는 타동사인 hit이다.
• D는 관사(determiner). 정관사인 the이다.
• N은 명사(noun)이다.

트리의 각 노드는 루트 노드나 브랜치 노드나 리프 노드 중 하나이다. 루트 노드는 상위에 브랜치를 하나도 가지고 있지 않은 노드이다. 문장안에서, 루트 노드는 오직 하나이다. 브랜치 노드는 두 개 이상의 딸 노드들을 연결하는 엄마 노드이다. 리프 노드는 다른 노드를 지배하지 않는 말단 노드이다. S는 루트 노드이고, NP와 VP는 브랜치 노드이고, John(N), hit(V), the(D), ball(N)은 모두 리프 노드이다. 리프 노드들은 문장의 어휘 토큰이다. 엄마 노드는 이것의 하위 브랜치에 연결된 적어도 하나의 다른 노드를 가지는 노드이다. 예를 들어서, S는 N과 VP 모두의 부모이다. 딸 노드는 상위 브랜치로 직접 연결된 적어도 한개의 노드를 가진 노드이다. 예시에서 살펴보면, hit은 V의 딸 노드이다. 부모와 자식이라는 용어는 종종 이러한 관계에서 사용된다.

의존성 기반 파스 트리

의존 문법의 의존성 기반트리는 모든 노드를 말단 노드로 본다. 이것은 그들은 단말 노드와 비단말 노드의 분류를 인정하지 않는다는 것을 뜻한다. 더 적은 수의 노드를 포함하기 때문에 대체적으로 구 구조 기반 파스 트리보다 간단하다. 위의 예문의 의존성 기반 파스 트리는 다음과 같다.

이 파스 트리는 구 구조 기반 파스 트리에 존재하는 구 분류(S, VP, NP)가 없다. 구 구조 기반 파스트리와 같이 구성 구조가 인정된다. 트리의 완전 하위 트리는 모두 구성 요소이다.

따라서 이 의존성 기반 파스 트리는 구 구조 기반 파스 트리와 같이 주어 명사 John 과 목적어 명사구 the ball 을 구성 요소로 인정한다.

구와 의존성을 구별하는 것은 광범위하다. 구 기반 파스 트리와 관련된 추가적인 구문 구조가 필요하거나 유익한 지의 여부는 논쟁의 여지가 있다.

구문 마커

구문 마커나 P-markers는 Noam Chomsky 등에 의해 만들어진 transformational generative grammar에서 소개되었다. 문장의 깊은 구조를 나타내는 구문 마커는 구문 구조 규칙을 적용해서 만들어진다. 그리고, 이것은 추가 변환을 거칠 수도 있다.

구문 마커는 트리 형식으로 표현된다.(위 섹션의 구 구문 기반 파스트리와 같이) 하지만 종종 메모리 공간을 덜 차지하는 "대괄호식" 형태로 표현된다. 예를 들어, 위의 구 기반 트리를 따르는 대괄호식 표현은 보통 다음과 같다:
$[_{S}\ [_{\mathit {N}}\ John]\ [_{\mathit {VP}}\ [_{V}\ hit]\ [_{\mathit {NP}}\ [_{\mathit {D}}\ the]\ [_{N}\ ball]]]]$

트리와 마찬가지로 표현식의 정확한 구성과 표시된 세부 사항의 양은 적용된 이론과 쿼리 작성자가 설명하고자하는 요점에 따라 달라질 수 있다.

같이 보기

• 추상 구문 트리
• 의존 문법
• 전산언어학
• 구문 분석

참고 문헌

• Ágel, V., Ludwig Eichinger, Hans-Werner Eroms, Peter Hellwig, Hans Heringer, and Hennig Lobin (eds.) 2003/6. Dependency and valency: An international handbook of contemporary research. Berlin: Walter de Gruyter.
• Carnie, A. 2013. Syntax: A generative introduction, 3rd edition. Malden, MA: Wiley-Blackwell.
• Chiswell, Ian and Wilfrid Hodges 2007. Mathematical logic. Oxford: Oxford University Press.
• Aho, A. V., Sethi, R., and Ullman, J. D. 1986. Compilers: Principles, techniques, & tools. Reading, MA: Addison-Wesley.

외부 링크

• Syntax Tree Editor
• Linguistic Tree Constructor
• phpSyntaxTree – Online parse tree drawing site
• phpSyntaxTree (Unicode) – Online parse tree drawing site (improved version that supports Unicode)
• rSyntaxTree Enhanced version of phpSyntaxTree in Ruby with Unicode and Vectorized graphics
• Qtree – LaTeX package for drawing parse trees
• TreeForm Syntax Tree Drawing Software
• Visual Introduction to Parse Trees Introduction and Transformation
• OpenCourseOnline Dependency Parse Introduction (Christoper Manning)
• Penn Treebank II Constituent Tags