In
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
, the terminal yield (or fringe) of a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
is the sequence of leaves encountered in an ordered walk of the tree.
Parse trees and/or derivation trees are encountered in the study of
phrase structure grammar
The term phrase structure grammar was originally introduced by Noam Chomsky as the term for grammar studied previously by Emil Post and Axel Thue ( Post canonical systems). Some authors, however, reserve the term for more restricted grammars in ...
s such as
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be ...
s or
linear grammar In computer science, a linear grammar is a context-free grammar that has at most one nonterminal in the right-hand side of each of its productions.
A linear language is a language generated by some linear grammar.
Example
An example of a linear gr ...
s. The leaves of a derivation tree for a
formal grammar
In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe ...
''G'' are the
terminal symbol
In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. ''Terminal symbols'' are the elementary symbols of the language defined by a formal grammar. ...
s of that grammar, and the internal nodes the
nonterminal
In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. ''Terminal symbols'' are the elementary symbols of the language defined by a formal grammar. ...
or variable symbols. One can read off the corresponding terminal string by performing an ordered
tree traversal
In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. ...
and recording the terminal symbols in the order they are encountered. The resulting sequence of terminals is a string of the language ''L''(''G'') generated by the grammar ''G''.
Formal languages
{{Formalmethods-stub