Parse Tree

Parse tree, parsing tree, derivation tree, and concrete syntax tree refer to a tree structure representing a grammatically correct sentence. The word 'parse' is primarily used in computational linguistics. Syntax tree is more commonly used.

Parse trees specifically reflect the grammar of the input language, which clearly distinguishes them from abstract syntax trees used in computer programming. Unlike Reed-Kellogg sentence diagrams, which are used to teach grammar, parse trees do not use separate symbols for different types of constituents.

Parse trees are primarily built based on the constituency relationships of constituents in constituency grammars or the dependency relationships in dependency grammars. Parse trees are generated for sentences or natural languages, just as they are when programming languages are interpreted.

A related concept is the phrase marker, or P-marker, used in transformational generative grammar. A phrase marker is a linguistic expression marked with its syntactic structure. It can be represented in the form of a tree or as a bracketed expression. Phrase markers are generated by applying phrase structure rules and are themselves subject to further transformational rules. Syntactically ambiguous sentences are referred to as parse forests.

Structure-based Parse Trees #

In phrase structure grammars, structure-based trees distinguish between terminal and non-terminal nodes. Internal nodes are classified as non-terminal nodes, and leaf nodes are classified as terminal nodes. The image below shows a phrase structure-based tree, illustrating the syntactic structure of the sentence 'john hit the ball'.

Structure-based parse tree

The parse tree starts with S and ends with each of the leaf nodes (john, hit, the, ball).

S stands for sentence, the top-level structure in this example.
NP stands for noun phrase; the first (leftmost) NP, the noun 'john', acts as the subject in the sentence. The second NP is the object of the sentence.
VP stands for verb phrase, used as the predicate.
V stands for verb, in this case, the transitive verb 'hit'.
D stands for determiner, the definite article 'the'.
N stands 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 has no branches above it. In a sentence, there is only one root node. A branch node is a mother node that connects to two or more daughter nodes. A leaf node is a terminal node that does not dominate any other nodes; S is the root node, NP and VP are branch nodes, and 'john', 'hit', 'the', 'ball' (N V D N) are all leaf nodes. Leaf nodes are the lexical tokens of the sentence, and a mother node is a node that has at least one other node connected to its lower branches. For example, S is the parent of both NP and VP. A daughter node is a node that has at least one node directly connected to its upper branch; in the example, 'hit' is a daughter node of V, and the terms 'parent' and 'child' are often used for these relationships.

Dependency-based Parse Trees #

Dependency-based trees in dependency grammars consider all nodes as terminal nodes. This means they do not recognize the classification of terminal and non-terminal nodes. They are generally simpler than phrase structure-based parse trees because they contain fewer nodes. The dependency-based parse tree for the above example is as follows.

Dependency-based parse tree

This parse tree lacks the categories like S, NP, VP found in phrase structure-based parse trees, but constituency structure is still recognized. All complete subtrees of the tree are constituents.

Thus, this dependency-based parse tree, like the phrase structure-based parse tree, recognizes 'john' and the object noun phrase 'the ball' as constituents.

The distinction between constituency and dependency is extensive, and whether additional syntactic structure associated with phrase-based parse trees is necessary or beneficial is debatable.

Phrase Markers #

Phrase markers, or P-markers, were introduced in transformational generative grammar developed by Noam Chomsky and others. Phrase markers, which represent the deep structure of a sentence, are created by applying phrase structure rules. These can undergo further transformations.

Phrase markers are represented in tree form (like the phrase structure-based parse trees in the section above), but are often expressed in a bracketed form that takes up less memory space. For example, the bracketed representation following the phrase-based tree above is as follows:

As with trees, the exact construction of the expression and the amount of detail shown can vary depending on the theory applied and the point the query author wishes to illustrate.

https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4_%ED%8A%B8%EB%A6%AC