
related topics 
{math, number, function} 
{language, word, form} 
{woman, child, man} 
{album, band, music} 
{game, team, player} 
{son, year, death} 

A concrete syntax tree or parse tree 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 nonterminals 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.
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 Xbar 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:
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.
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
External links
Full article ▸


related documents 
Elias gamma coding 
Linear function 
Regular graph 
Inner automorphism 
Unitary matrix 
Injective function 
Axiom of power set 
Earley parser 
Unit interval 
Connectedness 
Subring 
Euler's identity 
Profinite group 
Disjunctive normal form 
Hausdorff maximal principle 
Subset 
Row and column spaces 
Class (set theory) 
Identity matrix 
Specification language 
Inverse transform sampling 
Discrete probability distribution 
Additive function 
Random sequence 
Urysohn's lemma 
Inequation 
Kleene star 
Just another Perl hacker 
SharpP 
Irreducible fraction 
