A parse tree or concrete syntax tree is a tree that represents the syntactic structure of a string according to some formal grammar. A program that produces such trees is called a parser. 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. In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ... For other uses, see Syntax (disambiguation). ... In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... In computer science and linguistics, a formal grammar, or sometimes simply grammar, is a precise description of a formal language — that is, of a set of strings. ... An example of parsing a mathematical expression. ... In linguistics, a sentence is a unit of language, characterized in most languages by the presence of a finite verb. ... The term natural language is used to distinguish languages spoken and signed (by hand signals and facial expressions) by humans for general-purpose communication from constructs such as writing, computer-programming languages or the languages used in the study of formal logic, especially mathematical logic. ... Natural language processing (NLP) is a subfield of artificial intelligence and linguistics. ... A diagram of the operation of a typical multi-language, multi-target compiler. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ...

Basic description

A parse tree is made up of nodes and branches. Below is a linguistic parse tree, here representing the English sentence "John hit the ball". (Note: this is only one possible parse tree for this sentence; different kinds of linguistic parse trees exist.) The parse tree is the entire structure, starting from S and ending in each of the leaf nodes (John, hit, the, ball).

A simple parse tree

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, hit, the, and ball are all leaf nodes. (To better understand what "S", "VP", "NP" etc. mean, see [1]) Image File history File links This is a lossless scalable vector image. ...

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.

See also

• Computational linguistics
• Parsing
• Sentence diagram
• X-bar theory

Computational linguistics is an interdisciplinary field dealing with the statistical and logical modeling of natural language from a computational perspective. ... An example of parsing a mathematical expression. ... A sentence diagram of the unusual sentence Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo. ... X-bar theory is a component of linguistic theory which attempts to identify syntactic features common to all languages. ...

External links

• Linguistic Tree Constructor
• phpSyntaxTree — Online parse tree drawing site
• Qtree — LaTeX package for drawing parse trees
• Syntax Tree Drawer in SVG
• TreeForm Syntax Tree Drawing Software
• Trees Player

This linguistics article is a stub. You can help Wikipedia by expanding it.