Why can a parsing expression grammar's ordered choice never produce two different parse trees for one input?
answer
- order is part of the meaning
- first success wins at a position
- no alternative reconsidered later
- every decision is forced
- a recognizer, not a description
basics
~20 sOrdered choice commits to the first alternative that succeeds at a position, so each rule yields at most one result there. The grammar defines one recognizer rather than a set of permitted derivations, so a second parse tree cannot exist.
solid answer
~40 sThe choice operator `/` is read operationally: at a given input position, try the alternatives left to right and take the first one that succeeds; the rest are never consulted. The other operators are equally directed — a sequence runs left to right, a repetition is greedy and never gives characters back so that whatever follows can succeed. So every expression, at every position, has exactly one outcome: fail, or succeed consuming a fixed number of characters. A parse tree is just the record of those forced decisions, so a successful parse has exactly one tree. The price is that overlap between alternatives is resolved silently rather than reported: the written order is part of the grammar's meaning, and rearranging it can change which inputs are accepted.
go deeper
Recall that alternatives in this style of grammar are tried in the order written and the first one that succeeds wins. The order on the page is not a formatting detail.
Explain why that leaves exactly one outcome per expression per input position, and therefore exactly one tree: choice, sequence and repetition are all forced, so no second derivation is available to build.
Show what the guarantee costs in a grammar you maintain: overlap is resolved silently, a dead alternative is legal, and only a test corpus will tell you that an input takes a branch you did not intend.
Weigh a formalism that cannot be ambiguous against one whose tooling reports conflicts at build time. You are trading a loud failure during development for a quiet behavioural difference found in production.
## What ordered choice actually says A **parsing expression grammar (PEG)** is a set of rules whose right-hand sides are *parsing expressions*: not descriptions of strings, but instructions for a recognizer. The choice operator, written `/`, has an operational reading. To match `e1 / e2` at input position `p`: try `e1` at `p`; if it succeeds, the whole choice succeeds with that result and `e2` is never consulted; only if `e1` fails does the parser return to `p` and try `e2`. There is no state in which *both* alternatives have matched, because the second one is not attempted once the first has succeeded. The other operators are equally directed: - a **sequence** `e1 e2` runs left to right, and `e2` starts from wherever `e1` stopped; - a **repetition** `e*` is greedy and possessive: it consumes as many copies as it can and never hands characters back so that what follows can succeed; - the **predicates** `&e` and `!e` test whether `e` would match at the current position and consume nothing either way. ## Why a second parse tree cannot exist Work up the structure of an expression. A literal at a position either matches or it does not — one outcome. A choice takes the first alternative that succeeds, so given one outcome per alternative it has one outcome. A sequence composes two single outcomes into one. A repetition is fixed by how many times its body succeeds, which is itself fixed. By induction, **every expression at every position has exactly one outcome**: fail, or succeed consuming a definite number of characters. A parse tree is nothing more than the record of which alternatives were taken and how far each reached. If every one of those decisions is forced, the record is forced too, so a successful parse yields exactly one tree. This is a property of the formalism rather than of a particular grammar: you cannot write a PEG with two trees for one input, in the way you can write an unordered rule set that permits two derivations of the same string. ## Commitment is stronger than 'try them in order' The subtle part is what happens *after* a choice has succeeded. In `A <- (a1 / a2) b`, suppose `a1` succeeds and `b` then fails. The sequence fails, and the failure travels **outward** to the nearest enclosing choice — it does not travel **back** into the choice that already returned a result, so `a2` is never tried at that position. Backtracking exists, but only inside an alternative that has not yet succeeded. | Aspect | Unordered rule set | Ordered choice | |---|---|---| | Two alternatives match | both derivations exist in the formalism | the first written one wins | | Order of alternatives | not part of the meaning | part of the meaning | | A later element fails | another derivation may still apply | the sequence fails outright | | Overlap between alternatives | a generator for a deterministic parser class can flag it | the grammar is well formed; nothing must be flagged | ## What the guarantee costs - **Overlap is resolved silently.** Two alternatives that can both match are legal and produce no diagnostic; implementations differ in whether they warn that an alternative is unreachable. - **An alternative can be dead.** If an earlier alternative always succeeds where a later one would, the later one is never reached, and the grammar still looks correct on the page. - **Reordering is a semantic edit.** Moving a line for readability can change the accepted set — it is a breaking change, not a cosmetic one. - **The language is defined by the recognizer.** There is no independent description of the accepted set to check the grammar against; a test corpus takes that role. - **Boundaries need predicates.** Because nothing prefers a longer match, `!` is how you insist that a matched name is not the prefix of a longer one. - **Failure messages are weak.** The parser reports where the last attempt died, which is often far from the alternative you meant to take. ## Reading a grammar with this rule in mind 1. Find every choice whose alternatives can match at the same position — in practice, alternatives sharing a prefix. 2. Check that the more specific alternative is written **above** the more general one; if a general one comes first, everything below it is unreachable at that position. 3. Check what follows the choice in the sequence: if the committed alternative leaves the input in a state the rest cannot match, the whole rule fails and the other alternative will not rescue it. 4. Write a test for each alternative, because the grammar itself will not tell you that one is dead. The property worth remembering is that determinism is bought at the grammar level, not at the tooling level: the formalism removes the possibility of two trees, and hands you, in exchange, the duty of getting the order right.
- If two alternatives of one ordered choice can both match at the same position, what does the grammar tool report?Nothing is required of it: the grammar is well formed, and overlap is a legal way to express a preference. Some implementations warn that an alternative looks unreachable, others do not, so the overlap is normally found by a test that exercises the alternative you expected to be taken.
- Does backtracking still happen under ordered choice, and how far back does it reach?Yes, but only within an alternative that has not yet succeeded: if it fails partway, the position resets to where the choice started and the next alternative runs from there. Once an alternative has succeeded, a later failure in the enclosing sequence propagates outward instead of re-entering that choice.
- What does greedy-and-possessive repetition mean for a rule written as `Item* End`?`Item*` consumes every `Item` it can and will not surrender the last one so that `End` can match. If `End` overlaps with `Item`, the rule fails rather than backing off by one repetition, which is the same commitment rule applied to repetition instead of choice.
Think of a clerk working down a checklist and stopping at the first line that applies: there is never a tie to break, but a line placed too high quietly hides every line beneath it.
saying these in an interview costs you the question
- Says two alternatives matching means the parse is ambiguous
- Thinks ordered choice prefers the longest matching alternative
- Claims the parser explores all alternatives and keeps the best
- Expects a conflict report whenever alternatives overlap
- Assumes reordering alternatives cannot change the accepted language