How can one sentence have many derivations from a grammar yet only one parse tree?
answer
- order is presentation, structure is content
- each rule application becomes one internal node
- the leaves read out the sentence
- swapping independent steps changes no edge
- different rules means a second tree
basics
~20 sA parse tree records which production was applied to which symbol occurrence, not the order the rewrites happened in. Many derivations that differ only in ordering describe the same parent-child structure, so they draw one tree.
solid answer
~50 sBuild the tree from a derivation like this: the start symbol is the root, and every time a production rewrites a nonterminal, that occurrence gets the right-hand side's symbols as its children, left to right. Reading the leaves left to right gives back the sentence, which is called the tree's **yield**. Two derivations that apply the same productions to the same occurrences produce exactly the same parent-child edges, so they collapse to one tree — the leftmost and rightmost orders are two ways of walking it. The order is genuinely lost: given the tree you can reconstruct either canonical derivation, but not which one was written first. When a grammar admits two derivations that use *different* rules for one sentence, you get two trees instead of one, and that is the ambiguity question rather than this one.
go deeper
Recall the construction: the start symbol is the root, each rule application hangs its right-hand side beneath the symbol it replaced, and reading the leaves left to right gives the text back.
Explain which information the tree keeps and which it drops, and state the condition under which many derivations really do collapse to one tree rather than asserting it unconditionally.
Show why downstream work is written against the tree and not the derivation, and where the boundary sits between the full parse tree and the trimmed structure a later stage carries.
Discuss what a team gives up by having no explicit tree at all — validating text with ad hoc checks — and when that shortcut stops paying.
## From a derivation to a tree A derivation is a list of lines; a **parse tree** is a picture of the same event, and the construction is mechanical: 1. Draw the start symbol as the root. 2. Each time a step rewrites an occurrence of nonterminal `A` using the production `A -> X Y Z`, attach `X`, `Y` and `Z` to that occurrence as children, in that left-to-right order. 3. Stop when every leaf is a terminal. Reading the leaves from left to right gives the sentence, which is the tree's **yield**. Every internal node is therefore one rule application, and every leaf is one terminal of the generated string. A tree with 8 internal nodes came from a derivation of exactly 8 steps. ## What the tree keeps and what it throws away | Recorded in the tree | Not recorded in the tree | |---|---| | Which production was applied | In what order the applications happened | | Which occurrence it was applied to | Which canonical convention was used | | The left-to-right order of children | The intermediate sentential forms as text | | The nesting of one structure inside another | Which nonterminal was rewritten first | That asymmetry is the whole answer. The choice of *position* — leftmost, rightmost, or something in between — is what the tree discards, because the edges it draws are the same whichever step drew them. The choice of *production* is what the tree keeps, because a different production means different children. ## Why the order can be dropped safely Rewriting is **context free** in the literal sense: a production `A -> alpha` may be applied to any occurrence of `A`, no matter what surrounds it, and applying it does not change which productions are available anywhere else in the line. So two steps that rewrite different occurrences never interfere, and swapping them yields the same set of parent-child edges. The one ordering constraint that survives is the obvious one: an occurrence cannot be rewritten before the step that introduced it. Any ordering of the rule applications that respects that constraint is a valid derivation of the same tree, and there are usually many of them. Leftmost and rightmost are two such orderings, chosen because each is deterministic. ## The condition, stated exactly It is wrong to say that every sentence has one tree. The precise statement is: - Derivations that apply **the same productions to the same occurrences** always describe **one** tree. - A sentence for which the grammar admits derivations using **different** productions has **more than one** tree, and the rule set is then ambiguous for that sentence. Deciding whether some sentence like that exists is a separate subject with its own hard results, and it is not this one. A useful corollary follows immediately: for an unambiguous grammar there is exactly one leftmost derivation and exactly one rightmost derivation of any sentence it generates, and both describe the same tree. That is why tooling can quote either without ambiguity of its own. ## Why an engineer cares A derivation cannot be computed over; a tree can. Once a saved-filter expression has a tree, the structure is addressable: the root says the expression is a conjunction, the children say which comparisons it joins, and a walk over the tree can be turned into a query, a validation report or a highlighted rendering. Everything downstream of syntax is written against the tree, never against the list of lines. Two boundaries are worth stating aloud so you do not overclaim: - The parse tree keeps **every** symbol of every right-hand side, including punctuation and keywords that carry no information once the structure is known. The trimmed structure a compiler actually carries forward is a different object with a different name, and it is a separate subject. - Walking the tree — the traversal orders and how recursion changes when a node has a list of children — is likewise its own subject. Here the tree is a record of a derivation, not a data structure being iterated. ## The answer in one breath The derivation says *how you wrote it down*; the tree says *what you built*. Order is presentation, structure is content, and the collapse from many derivations to one tree is exactly the removal of the presentation.
- What is the yield of a parse tree, and why does it matter?The yield is the string obtained by reading the leaves left to right. It matters because it is the link back to the input: a tree is a parse tree *for a given sentence* only if its yield is that sentence and its root is the start symbol. Any tree failing either condition describes something else.
- Given only a parse tree, can you recover the derivation that produced it?You can recover the rule applications and their positions, and therefore reconstruct the leftmost or the rightmost derivation exactly. You cannot recover which order was originally written, because the tree never stored it. That is precisely the information the tree discards.
- How many internal nodes does a parse tree have relative to its derivation?One per step, since each rewriting step attaches one right-hand side to one occurrence. A derivation of eight steps yields a tree with eight internal nodes, which is a quick consistency check when you write both out by hand.
Two cooks can chop the onions before or after the carrots and still plate the same layered dish. The derivation is the order the steps were taken in; the parse tree is the layering that survives on the plate.
saying these in an interview costs you the question
- Says each derivation order produces a differently shaped tree.
- Thinks the tree records the sequence of rewriting steps.
- Believes every sentence of every grammar has exactly one tree.
- Assumes the tree drops keywords and punctuation.
- Cannot say what reading the leaves left to right gives.