parse tree

A Dictionary of Computing | 2004 | 700+ words | Copyright

parse tree (syntax tree) A tree defining the syntactic structure of a sentence in a context-free language. The interior nodes are labeled by nonterminals of the context-free grammar; the descendants of a node labeled by A, say, spell from left to right the right-hand side of some production having left-hand side A. The leaf nodes of a parse tree may be terminals or nonterminals. If all the leaves are terminals then they spell from left to right a sentence of the language.

An example of a parse tree is shown in the diagram. It is assumed that the grammar in question has productions A → BC, B → b, C → cc

Note that it is conventional for the top of the tree to be its root and the bottom to be its leaves.

An early stage in compiling a program usually consists of generating a parse tree in which the constructs that make up the program are expressed in terms of the syntax of the programming language.

Cite this article
Pick a style below, and copy the text for your bibliography.

MLA
Chicago
APA

JOHN DAINTITH. "parse tree." A Dictionary of Computing. 2004. Encyclopedia.com. 27 May. 2012 <http://www.encyclopedia.com>.

JOHN DAINTITH. "parse tree." A Dictionary of Computing. 2004. Encyclopedia.com. (May 27, 2012). http://www.encyclopedia.com/doc/1O11-parsetree.html

JOHN DAINTITH. "parse tree." A Dictionary of Computing. 2004. Retrieved May 27, 2012 from Encyclopedia.com: http://www.encyclopedia.com/doc/1O11-parsetree.html

Learn more about citation styles