How does a leftmost derivation of a string differ from a rightmost derivation of the same string?

## Sentential forms: the lines of a derivation A derivation is written as a sequence of lines joined by a rewriting arrow. Each line is a **sentential form**: a string of terminals and nonterminals mixed together, reachable from the start symbol. The first sentential form is the start symbol alone; the last contains no nonterminal and is the generated string, which is why an all-terminal sentential form is called a **sentence** of the grammar. At each step there may be more than one nonterminal in the line, so the derivation has a choice of *where* to apply a rule, quite separate from the choice of *which* rule to apply. Fixing that first choice by a rule of thumb gives the two named orders. ## The same sentence, twice Take the four-rule saved-filter grammar with start symbol `FILTER`: ``` FILTER -> TERM and FILTER | TERM TERM -> FIELD is VALUE FIELD -> status | owner VALUE -> open | me ``` The rightmost derivation of `status is open and owner is me` rewrites the rightmost nonterminal every time: ``` FILTER => TERM and FILTER => TERM and TERM => TERM and FIELD is VALUE => TERM and FIELD is me => TERM and owner is me => FIELD is VALUE and owner is me => FIELD is open and owner is me => status is open and owner is me ``` The leftmost derivation of the same sentence is in the code example beside this answer. Both are eight steps long, and both apply exactly the same eight productions to exactly the same symbol occurrences. What differs is the shape of the intermediate lines: the leftmost order finishes the first comparison into words before it ever touches the tail, while the rightmost order leaves `TERM` standing on the left until the final three steps. | | Leftmost derivation | Rightmost derivation | |---|---|---| | Which nonterminal is rewritten | the leftmost one in the line | the rightmost one in the line | | Early sentential forms | terminals accumulate on the left | terminals accumulate on the right | | Number of steps for a given structure | identical | identical | | Multiset of productions applied | identical | identical | | What it fixes | the order of rewriting only | the order of rewriting only | ## Why the derivation length is not a free variable One step rewrites exactly one nonterminal occurrence, so the number of steps equals the number of nonterminal occurrences that ever appear — which is one per rule application. Reordering the steps cannot change that count. If two derivations of the same sentence have different lengths, they are not reorderings of each other: they used different rules, and the grammar therefore offers more than one way to build that sentence. Spotting that is the doorway to the ambiguity question, which belongs to its own subject and is not what this one asks. ## What the choice of order does not change It is tempting to think the two orders describe different structures, because the lines on the page look so different. They do not. The rewriting relation only ever replaces a single nonterminal by the right-hand side of one of its own productions, and that replacement is independent of what surrounds it: rewriting the tail first cannot affect which rules are available for the head. So when the same rule applications are available in both orders, both orders describe the same nesting — the same parent-child relationships between rule applications. The practical consequences are worth stating plainly: - **A derivation is evidence, not a plan.** Exhibiting any derivation of a string shows it is in the language; you are free to write down whichever order is easiest to read. - **The two orders have names because tools are built around them.** Prediction-driven and reduction-driven parser families each correspond naturally to one of the two, which is why interview questions about parser families assume this vocabulary. - **A mixed order is still a derivation.** Nothing forbids rewriting the middle nonterminal one step and the leftmost the next; such a derivation is perfectly valid, just not canonical. Leftmost and rightmost are singled out because they are deterministic conventions, not because other orders are illegal. - **The sentential forms of a leftmost derivation have a useful shape**: everything to the left of the rewritten nonterminal is already terminal, which is exactly the prefix a left-to-right reader has consumed. ## What an interviewer is listening for A weak answer treats the two orders as two different meanings. A strong one separates the *choice of rule*, which is about what the language contains, from the *choice of position*, which is only about bookkeeping — and then says what it takes for that separation to be safe: the same rules applied to the same occurrences. That sentence is what the follow-up about parse trees is built on.