derivation tree
Given a formal grammar , recall that a derivation from words to over can be visualized as a finite sequence of words over , connected by the binary relation :
(1) |
where and . Each is a derivation step, which means that there is a production in which, when applied to , yields . In other words, there is in such that and , where are words over .
When the formal grammar is context-free, a derivation can be represented by an ordered tree, revealing the structure behind the derivation that is usually not apparent in the linear representation above. This ordered tree is variously known as a derivation tree or a parse tree, depending how it is being used.
In the foregoing discussion, is context-free, and any derivation of begins with , the starting non-terminal.
Definition. A parse tree of is an ordered tree such that
-
1.
the nodes of are labeled by elements of , or the empty word ,
-
2.
if a node with label has children such that , and that each has label , then is a production of .
A parse tree such that the root has label is called a derivation tree, or a generation tree. Every subtree of a derivation tree is a parse tree.
Remark. Since is context-free, in a parse tree, any node that is not a leaf is labeled by a non-terminal symbol.
For example, if , , and the productions of are
then
represents a derivation tree of . The tree represents the following derivations
-
•
-
•
-
•
Definition. If are the leaves of a parse tree , with , then the result of is the word , where is the label of . A word over is said to correspond to a parse tree if it is the result of the tree.
In the example above, the result of the tree is .
Remark. A derivable word may correspond to several derivation trees. See the entry ambiguous grammar for more detail.
References
- 1 H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
- 2 A. Salomaa, Formal Languages, Academic Press, New York (1973).
- 3 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (1969).
Title | derivation tree |
---|---|
Canonical name | DerivationTree |
Date of creation | 2013-03-22 19:00:17 |
Last modified on | 2013-03-22 19:00:17 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 10 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 68Q42 |
Classification | msc 68Q45 |
Synonym | generation tree |
Defines | parse tree |
Defines | result of a derivation tree |