Non-terminal function

A non-terminal function is a function (node) in a parse tree which is either a root or a branch in that tree.

Background

A parse tree is made up of nodes and branches. In the picture below the parse tree is the entire structure, starting from S and ending in each of the leaf nodes (John,ball,the,hit).

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, 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.

Nodes as Functions

Each of these nodes can also be called a function. However, this type of function (i.e. a node in a parse tree) is not the same as a function in mathematics or computer programming. A function in mathematics takes in zero or more inputs and returns a value.

In parse trees, a function can be a true mathematical function which "uses" its child nodes as inputs, and returns a single output to its parent. More often, however, a node in a parse tree is a static symbol such as a number, letter, or word.

The use of parse tree functions is highly dependent on the area which is using it. In the branch of evolutionary computation called genetic programming, for instance, tree functions are quite often (but not exclusively) used as mathematical-style function. In linguistics and linguistic theory, tree functions are never mathematical functions, except in certain areas of computational linguistics.

See also

• Terminal function