Parse tree

For the trees used in computer science, see Abstract syntax tree.

A concrete syntax tree or parse tree or parsing tree^[1] is an ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar. In a parse tree, the interior nodes are labeled by non-terminals of the grammar, while the leaf nodes are labeled by terminals of the grammar. 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. Parse trees are distinct from abstract syntax trees (also known simply as syntax trees), in that their structure and elements more concretely reflect the syntax of the input language.

If a formal grammar is ambiguous, there can be multiple parse trees for some given string (Syntactic ambiguity).

Basic description

A parse tree is made up of nodes and branches. The image below represents a linguistic parse tree, here representing the English sentence "John hit the ball". (The parse tree here is a greatly simplified one; for more information, see X-bar theory.) The parse tree is the entire structure, starting from S and ending in each of the leaf nodes (John, hit, the, ball). We use the following abbreviations in the example:

• 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".
• Det for determiner, in this instance the definite article "the"
• N for noun

A simple parse tree

Hybrid constituency/dependency tree from the Quranic Arabic Corpus

In a parse tree, each node is either a root node, a branch node, or a leaf node. In the example to the right, S is a root node, NP and VP are branch nodes, while John, hit, the, and ball are all leaf nodes. The leaves are the lexical tokens of the sentence.^[2]

A node can also be referred to as parent node or a child node. 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 NP 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 the tree. Again from our example, hit is a child node of V. The terms mother and daughter are also sometimes used for this relationship.

See also

• Computational linguistics
• Nanosyntax
• Parsing
• Sentence diagram

References

1. ^ Chiswell, Ian; Hodges, Wilfrid (2007). Mathematical Logic. Oxford: Oxford University Press. p. 34. ISBN 9780199215621. 
2. ^ Aho, Alfred V. et al. Compilers: Principles, Techniques, & Tools. Boston: Pearson/Addison Wesley, 2007. Print.

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)
• Qtree – LaTeX package for drawing parse trees
• TreeForm Syntax Tree Drawing Software