derivation tree


Given a formal grammar G=(Σ,N,P,σ), recall that a derivation from words u to v over Σ can be visualized as a finite sequencePlanetmathPlanetmath of words over Σ, connected by the binary relationMathworldPlanetmath :

u0u1un (1)

where u=u0 and v=un. Each uiui+1 is a derivation step, which means that there is a production in P which, when applied to ui, yields ui+1. In other words, there is AB in P such that ui=xAy and ui+1=xBy, where x,y are words over Σ.

When the formal grammar G is context-free, a derivation can be represented by an ordered treeMathworldPlanetmath, revealing the structureMathworldPlanetmath behind the derivation that is usually not apparent in the linear representation (1) 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, G is context-free, and any derivation of G begins with σ, the starting non-terminal.

Definition. A parse tree of G is an ordered tree T such that

  1. 1.

    the nodes of T are labeled by elements of Σ, or the empty wordPlanetmathPlanetmathPlanetmath λ,

  2. 2.

    if a node with label A has children N1,,Nk such that N1<<Nk, and that each Ni has label Ai, then AA1Ak is a production of P.

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 G is context-free, in a parse tree, any node that is not a leaf is labeled by a non-terminal symbol.

For example, if Σ={σ,a,b,X,Y}, N={σ,X,Y}, and the productions of P are

σaXY,XbYb,YXa,Ya,

then

represents a derivation tree of G. The tree represents the following derivations

  • σaXYabYbYabXabYabXabb

  • σaXYabYbYabYbbabXabb

  • σaXYaXbabYbbabXabb

Definition. If 1,,m are the leaves of a parse tree T, with 1<<m, then the result of T is the word B1Bm, where BiΣ is the label of i. 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 abXabb.

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 RelationMathworldPlanetmath 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