Derivations and Parse Trees
What You'll Learn
You'll learn how to derive strings step-by-step from a context-free grammar and how to visualize those derivations as tree structures called parse trees.
Core Idea
Once you have a context-free grammar (variables, terminals, productions, and a start symbol), you can derive strings by repeatedly replacing variables with the right-hand side of productions until only terminal symbols remain.
A derivation is a sequence of substitution steps. Starting from the start symbol, you apply productions one at a time. For example, if your grammar has S → aSb | ε, you might derive the string "aabb" like this:
S ⇒ aSb ⇒ aaSbb ⇒ aabb
Each ⇒ represents one replacement step.
A parse tree is a graphical representation of this derivation. The root is the start symbol, internal nodes are variables, and leaves are terminals (or ε). Each internal node's children correspond to the symbols on the right-hand side of the production used to expand that variable.
Think of it like a family tree: the start symbol is the ancestor, and each production "gives birth" to its children symbols until you reach terminal symbols at the leaves.
For the derivation above, the parse tree would have S at the root, with children a, S, and b at the first level. The middle S then expands to a, S, b again, and the innermost S becomes ε.
Reading the leaves left-to-right gives you the derived string.
Key Takeaway: Derivations show the step-by-step process of generating strings from a grammar, while parse trees visualize the hierarchical structure of that derivation, making the syntactic structure explicit and unambiguous.