Derivation tree is a graphical representation for the derivation of the given production rules for a given CFG. It is the simple way to show how the derivation can be done to obtain some string from a given set of production rules. The derivation tree is also called a parse tree.
Parse tree follows the precedence of operators. The deepest sub-tree traversed first. So, the operator in the parent node has less precedence over the operator in the sub-tree.
A parse tree contains the following properties:
E = E + E E = E * E E = a | b | c
a * b + c
Note: We can draw a derivation tree step by step or directly in one step.
Draw a derivation tree for the string "bab" from the CFG given by
S → bSb | a | b
Now, the derivation tree for the string "bbabb" is as follows:
The above tree is a derivation tree drawn for deriving a string bbabb. By simply reading the leaf nodes, we can obtain the desired string. The same tree can also be denoted by,
Construct a derivation tree for the string aabbabba for the CFG given by,
S → aB | bA A → a | aS | bAA B → b | bS | aBB
To draw a tree, we will first try to obtain derivation for the string aabbabba
Now, the derivation tree is as follows:
Show the derivation tree for string "aabbbb" with the following grammar.
S → AB | ε A → aB B → Sb
To draw a tree we will first try to obtain derivation for the string aabbbb
Now, the derivation tree for the string "aabbbb" is as follows: