skip to content

How does an EBNF repetition group expand back into plain BNF productions?

level: middleimportance: should knowfreq 38%

answer

  1. brackets are shorthand, not new power
  2. invent one helper nonterminal
  3. recursion replaces the braces
  4. one alternative consumes, one is empty
  5. zero or more needs the empty production

basics

~10 s

A repetition group becomes a fresh nonterminal with two productions: one that consumes a single occurrence and recurses, and one empty alternative that ends the chain. The sugar disappears, the language stays the same.

solid answer

~50 s

Backus-Naur Form gives you productions, alternation and nothing else, so every repeated element has to be written as recursion. **Extended BNF** adds bracket sugar — `{ X }` for zero or more, `[ X ]` for optional, `( ... )` for grouping — and each form has a mechanical expansion into plain BNF that introduces one new nonterminal. For a filter rule `FILTER = TERM , { and , TERM }`, the expansion is `FILTER -> TERM MORE` together with `MORE -> and TERM MORE` and an empty alternative for `MORE`. The sugar is notation only: it does not let you describe any language that plain BNF could not, and the empty alternative it introduces is a real production that downstream analysis has to account for. Note also that the flat repetition says nothing about how a three-element chain groups, whereas the recursive rule commits to a shape.

code

pseudocode · 12 lines
pseudocode
EBNF (repetition in braces):
  FILTER = TERM , { and , TERM } ;

expanded to plain BNF (MORE is the fresh helper):
  FILTER -> TERM MORE
  MORE   -> and TERM MORE
  MORE   -> empty

trace for: status is open and owner is me
  FILTER -> TERM MORE
         -> TERM and TERM MORE      (MORE takes the first alternative)
         -> TERM and TERM           (MORE takes the empty alternative)

go deeper

for a junior

Recall what the bracket forms mean: braces are zero or more of the enclosed fragment, square brackets are optional, and both are shorthand for ordinary rules.

for a middle

Perform the expansion on request: invent a helper nonterminal, give it a consuming alternative and an empty one, and check the result generates the same strings.

for a senior

Point out what the expansion exposes — an empty production downstream analysis must handle, and a nesting decision the flat form left open — and keep the document and the expanded rules from drifting apart.

for a principal

Decide which artefact is authoritative when a readable specification and an expanded rule set both exist, and who is accountable for keeping them in agreement.

## Two notations for the same idea **Backus-Naur Form** is the minimal notation for writing productions down: a left-hand side, a rewriting symbol, a right-hand side, and a vertical bar for alternation. Anything repeated has to be expressed by a rule that refers to itself, because BNF offers no other way to say *more of the same*. **Extended BNF** adds operators that make specifications readable. The dialects differ in punctuation — some write repetition with braces, some with a trailing star, some separate the elements of a right-hand side with commas and terminate rules with a semicolon — but the operator set is stable and so are the expansions. | EBNF form | Meaning | Plain BNF expansion | |---|---|---| | `{ X }` | zero or more X | `R -> X R` and `R -> empty` | | `[ X ]` | X or nothing | `R -> X` and `R -> empty` | | `( X \| Y )` | grouping of alternatives | `R -> X` and `R -> Y` | | one or more X | X repeated at least once | `R -> X R` and `R -> X` | In every row, `R` is a **fresh nonterminal** invented for the expansion; it has no meaning of its own beyond standing for the bracketed fragment. ## The worked expansion The saved-filter rule in EBNF says a filter is one comparison followed by any number of further comparisons joined by a keyword: ``` FILTER = TERM , { and , TERM } ; TERM = FIELD , is , VALUE ; ``` Expanding the braces gives plain BNF: ``` FILTER -> TERM MORE MORE -> and TERM MORE MORE -> empty ``` Walk it for `status is open and owner is me`: `FILTER` becomes `TERM MORE`, `MORE` takes the first alternative to consume `and TERM`, and the second `MORE` takes the empty alternative to stop. For a single comparison with no keyword, `MORE` takes the empty alternative immediately. The expansion generates exactly the strings the braces described. ## Three things the expansion makes visible 1. **Nothing was gained in power.** EBNF is sugar over BNF: every EBNF rule has a plain-BNF expansion, so the two notations describe exactly the same family of languages. A spec written in EBNF has not smuggled in extra capability, and a tool that consumes only plain productions loses nothing by expanding first. 2. **An empty alternative appears.** Repetition and option both introduce a production with an empty right-hand side. That empty production is real: it can be taken, and analyses that reason about what a nonterminal can start with have to account for the case where it produces nothing at all. Getting rid of such productions, where a particular tool wants them gone, is a separate transformation subject. 3. **The bracket form is flat; the expansion is not.** `{ and , TERM }` describes a sequence and says nothing about how three comparisons joined by two keywords group together. The expanded rule, by contrast, nests each tail inside the previous one and therefore commits to a shape. Whoever writes the expansion is making a decision the EBNF left open, and that decision is worth being deliberate about rather than accidental. ## Reading and writing specs in practice When a team writes its filter language down, EBNF is usually the better document: `{ and , TERM }` is read correctly at a glance, while a chain of recursive helper rules has to be traced. When a rule set is fed to machinery that expects bare productions, the expansion is applied first, by hand or by the tool. Both artefacts describe the same language, and the risk in keeping two of them is the usual one — they drift, and the document stops matching what is enforced. Two small hygiene points round it out: - **Name the fresh nonterminals meaningfully.** An expansion that produces `R1`, `R2` and `R3` is correct and unreadable; naming them after the fragment they stand for keeps error messages and reviews intelligible. - **Do not nest sugar deeper than you can expand aloud.** A right-hand side with braces inside brackets inside a group is legal and is a warning sign that the rule is doing several jobs at once. ## What the interviewer is checking That you treat the notation as notation. A candidate who believes EBNF is a more powerful formalism, or who cannot produce the two-production expansion of a repetition group on request, has learned the brackets as syntax rather than as shorthand for rules.

  • How does the optional bracket form expand, and how does it differ from repetition?
    An optional fragment becomes a fresh nonterminal with two productions: one that is the fragment itself and one that is empty. Repetition needs the same empty alternative but its non-empty alternative refers back to the helper, so it can be taken any number of times. Option allows at most one occurrence; repetition allows unboundedly many.
  • Does writing a spec in EBNF let it describe languages plain BNF cannot?
    No. Every EBNF operator has a mechanical expansion into ordinary productions, so both notations describe exactly the same family of languages. EBNF buys readability in the document, not reach. A tool that expands the sugar before analysing the rules loses nothing by doing so.
  • What does the flat repetition form leave undecided that its expansion decides?
    How a chain of three or more elements groups. The braces describe a sequence and say nothing about nesting, while the expanded recursive rule nests each tail inside the previous one. Whoever writes the expansion picks a shape, so that choice should be made deliberately rather than falling out of how the helper rule was typed.

saying these in an interview costs you the question

  • Claims EBNF describes languages plain BNF cannot.
  • Expands a repetition group without an empty alternative.
  • Thinks the braces themselves fix how a chain groups.
  • Reuses an existing nonterminal instead of inventing a helper.
  • Treats the empty production as a notational nothing.
  • Assumes every dialect spells repetition with the same punctuation.