CD Notes
Complete guide to derivations in compiler design covering leftmost and rightmost derivations, derivation sequences, sentential forms, and the relationship between derivations and parse trees.
What is a Derivation?
A derivation is a sequence of production rule applications that transforms the start symbol into a string of terminals. Each step replaces one non-terminal with the right-hand side of one of its productions. The derivation proves that a string belongs to the language defined by the grammar.
Types of Derivations
| Grammar: E | E + E | E * E | ( E ) | id |
| String to derive | id + id * id |
| ⟹_lm id + E (expand leftmost E | id) |
| ⟹_lm id + id * E (expand leftmost E | id) |
| ⟹_lm id + id * id (expand E | id) |
| ⟹_rm E + E * id (expand rightmost E | id) |
| ⟹_rm E + id * id (expand rightmost E | id) |
| ⟹_rm id + id * id (expand E | id) |
Derivation and Parse Tree Correspondence
Sentential Forms
A sentential form is any string in (V ∪ T)* derivable from S.
Left-sentential form: obtained via leftmost derivation steps
Right-sentential form: obtained via rightmost derivation steps
Example derivation steps and their sentential forms:
E ← start (sentential form)
E + T ← sentential form (left-sentential)
T + T ← sentential form
F + T ← sentential form
id + T ← sentential form
id + T * F ← sentential form
id + F * F ← sentential form
id + id * F ← sentential form
id + id * id ← sentence (no non-terminals)
Handles and Reductions
| Rightmost derivation | Reverse (reductions): |
| ⟹ E + T * F ← reduce id to F (handle | id) |
| Actually following the grammar E | E+T|T, T→T*F|F, F→id: |
| id + id * id handle: first "id" | reduce to F |
| F + id * id handle: "F" | reduce to T |
| T + id * id handle: "T" | reduce to E |
| E + id * id handle: "id" | reduce to F |
| E + F * id handle: "F" | reduce to T |
| E + T * id handle: "id" | reduce to F |
| E + T * F handle: "T * F" | reduce to T |
| E + T handle: "E + T" | reduce to E |
Multiple Derivations and Ambiguity
| Ambiguous grammar: E → E + E | E * E | id |
|---|---|---|
| / | \ / | \ |
| / | \ / | \ |
Removing Ambiguity
| E → E + T | T (addition, lower precedence) |
|---|---|
| T → T * F | F (multiplication, higher precedence) |
| F → ( E ) | id (atoms) |
| / | \ |
Derivation Length and Complexity
Interview Questions
- Q: Why do bottom-up parsers use rightmost derivation in reverse?
A: Bottom-up parsers read input left-to-right and build the parse tree from leaves to root. At each step, they identify a "handle" (RHS of a production) and reduce it to the LHS. This reduction sequence, when reversed, gives a rightmost derivation. The rightmost non-terminal is always the one being reduced because handles appear at the top of the stack.
- Q: Can two different grammars produce the same derivation for a string?
A: No — a derivation is defined relative to a specific grammar's productions. However, two different grammars can generate the same language (produce the same set of strings). Their derivations will differ because they use different production rules, but the derived strings are identical.
- Q: How does derivation length relate to parser efficiency?
A: Each derivation step corresponds to one parser action (shift/reduce or expand). Linear-time parsers (LL(1), LR(1)) perform O(n) actions for n tokens — one constant-time action per token. The derivation length is proportional to parse tree size, which is O(n) for most practical grammars.
- Q: What is a canonical derivation?
A: A canonical derivation has a fixed strategy for choosing which non-terminal to expand. Leftmost canonical derivation always expands the leftmost non-terminal; rightmost always expands the rightmost. These are the derivations constructed by LL parsers (leftmost) and LR parsers (rightmost in reverse).
- Q: How do you determine if a grammar is ambiguous?
A: In general, grammar ambiguity is undecidable. However, specific grammars can be checked by finding a string with two distinct parse trees. Common symptoms include: two productions applicable to the same prefix, or constructs like "dangling else." LL(1) and LR(1) conflicts in the parsing table also indicate potential ambiguity.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Derivations in Syntax Analysis.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, syntax, analysis, derivations, derivations in syntax analysis
Related Compiler Design Topics