A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term parse tree itself is used primarily in computational linguistics; in theoretical syntax, the term syntax tree is more common.

Concrete syntax trees reflect the syntax of the input language, making them distinct from the abstract syntax trees used in computer programming. Unlike Reed-Kellogg sentence diagrams used for teaching grammar, parse trees do not use distinct symbol shapes for different types of constituents.

Parse trees are usually constructed based on either the constituency relation of constituency grammars (phrase structure grammars) or the dependency relation of dependency grammars. Parse trees may be generated for sentences in natural languages (see natural language processing), as well as during processing of computer languages, such as programming languages.

A related concept is that of phrase marker or P-marker, as used in transformational generative grammar. A phrase marker is a linguistic expression marked as to its phrase structure. This may be presented in the form of a tree, or as a bracketed expression. Phrase markers are generated by applying phrase structure rules, and themselves are subject to further transformational rules. A set of possible parse trees for a syntactically ambiguous sentence is called a "parse forest."

Nomenclature

A parse tree is made up of nodes and branches. In the picture the parse tree is the entire structure, starting from S and ending in each of the leaf nodes (John, ball, the, hit). In a parse tree, each node is either a root node, a branch node, or a leaf node. In the above example, S is a root node, NP and VP are branch nodes, while John, ball, the, and hit are all leaf nodes.

Nodes can also be referred to as parent nodes and child nodes. A parent node is one which has at least one other node linked by a branch under it. In the example, S is a parent of both NP and VP. A child node is one which has at least one node directly above it to which it is linked by a branch of the tree. Again from our example, hit is a child node of V.

A nonterminal function is a function (node) which is either a root or a branch in that tree whereas a terminal function is a function (node) in a parse tree which is a leaf.

For binary trees (where each parent node has two immediate child nodes), the number of 
possible parse trees for a sentence with n words is given by the Catalan number .

Constituency-based parse trees
The constituency-based parse trees of constituency grammars (phrase structure grammars) distinguish between terminal and non-terminal nodes. The interior nodes are labeled by non-terminal categories of the grammar, while the leaf nodes are labeled by terminal categories. The image below represents a constituency-based parse tree; it shows the syntactic structure of the English sentence John hit the ball:

The parse tree is the entire structure, starting from S and ending in each of the leaf nodes (John, hit, the, ball). The following abbreviations are used in the tree:

 S for sentence, the top-level structure in this example

 NP for noun phrase. The first (leftmost) NP, a single noun "John", serves as the subject of the sentence. The second one is the object of the sentence.

 VP for verb phrase, which serves as the predicate

 V for verb. In this case, it's a transitive verb hit.

 D for determiner, in this instance the definite article "the"

 N for noun

Each node in the tree is either a root node, a branch node, or a leaf node. A root node is a node that does not have any branches on top of it. Within a sentence, there is only ever one root node. A branch node is a parent node that connects to two or more child nodes. A leaf node, however, is a terminal node that does not dominate other nodes in the tree. S is the root node, NP and VP are branch nodes, and John (N), hit (V), the (D), and ball (N) are all leaf nodes. The leaves are the lexical tokens of the sentence. A parent node is one that has at least one other node linked by a branch under it. In the example, S is a parent of both N and VP. A child node is one that has at least one node directly above it to which it is linked by a branch of a tree. From the example, hit is a child node of V. The terms mother and daughter are also sometimes used for this relationship.

Dependency-based parse trees
The dependency-based parse trees of dependency grammars see all nodes as terminal, which means they do not acknowledge the distinction between terminal and non-terminal categories. They are simpler on average than constituency-based parse trees because they contain fewer nodes. The dependency-based parse tree for the example sentence above is as follows:

This parse tree lacks the phrasal categories (S, VP, and NP) seen in the constituency-based counterpart above. Like the constituency-based tree, constituent structure is acknowledged. Any complete sub-tree of the tree is a constituent. Thus this dependency-based parse tree acknowledges the subject noun John and the object noun phrase the ball as constituents just like the constituency-based parse tree does.

The constituency vs. dependency distinction is far-reaching. Whether the additional syntactic structure associated with constituency-based parse trees is necessary or beneficial is a matter of debate.

Phrase markers
Phrase markers, or P-markers, were introduced in early transformational generative grammar, as developed by Noam Chomsky and others. A phrase marker representing the deep structure of a sentence is generated by applying phrase structure rules. Then, this application may undergo further transformations. 

Phrase markers may be presented in the form of trees (as in the above section on constituency-based parse trees), but are often given instead in the form of "bracketed expressions", which occupy less space in the memory. For example, a bracketed expression corresponding to the constituency-based tree given above may be something like :

As with trees, the precise construction of such expressions and the amount of detail shown can depend on the theory being applied and on the points that the query author wishes to illustrate.

See also

Abstract syntax tree
Constituent (linguistics)
Dependency grammar
Computational linguistics
Parsing (syntax analysis)
Phrase structure grammar
Sentence diagram
Terminal and nonterminal symbols

Notes

References

Á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.

External links
 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 (Christopher Manning)
 Penn Treebank II Constituent Tags 

Syntax
Generative syntax
Trees (data structures)
파스 트리(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에서 소개되었다. 문장의 깊은 구조를 나타내는 구문 마커는 구문 구조 규칙을 적용해서 만들어진다. 그리고, 이것은 추가 변환을 거칠 수도 있다.

구문 마커는 트리 형식으로 표현된다.(위 섹션의 구 구문 기반 파스트리와 같이) 하지만 종종 메모리 공간을 덜 차지하는 "대괄호식" 형태로 표현된다. 예를 들어, 위의 구 기반 트리를 따르는 대괄호식 표현은 보통 다음과 같다:

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

참고 문헌 

 Á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

각주 

전산언어학