Parse tree
Encyclopedia : P : PA : PAR : Parse tree
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.
Basic Description
A parse tree is made up of nodes and branches. The picture below is a linguistic parse tree representing an English sentence. 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.
See also
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]
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.