skip to content

A readable published rule set is left recursive and your top-down generator rejects it — do you rewrite the rules or change parser family?

level: principalimportance: should knowfreq 40%

answer

  1. the rewrite is free, the readability is not
  2. ask who reads the rules
  3. different families need different rewrites
  4. normative source plus generated copy
  5. guard the pair with differential parsing

basics

~20 s

Decide by who reads the rules. If the rule set is a published specification, keep it as authored and let a parser family that accepts left recursion consume it; if it is an internal input to one tool, rewrite it and treat the transformed form as generated output.

solid answer

~50 s

The rewrites are cheap mechanically and expensive socially: left-recursion elimination and left factoring both preserve the language, but they replace named constructs with primed helpers, flip the tree from left-leaning to right-leaning, and multiply alternatives when the recursion is indirect. So the question is what the rule set is *for*. A rule set that ships as the specification of a format has readers other than the parser, and rewriting it for one tool's convenience taxes every one of them forever. A bottom-up or general parser accepts left recursion as written and needs no factoring, so changing family removes the cost rather than paying it. The third option is usually the best: keep the authored rules as the normative document, generate the transformed copy as build output, and guard the pair with differential parsing over a corpus so they cannot drift apart.

go deeper

for a junior

Recall that rewriting rules for a parser does not change which inputs are valid — it changes the document people read and the shape of the tree.

for a middle

Be able to say which parser families need left recursion removed and which need shared prefixes factored, and that a bottom-up family needs neither.

for a senior

Argue the operational case: generated rules versus authored ones, diagnostics that leak helper names, tree consumers broken by the flipped associativity, and a corpus that keeps the two copies honest.

for a principal

Own the framing — a rule set with external implementers is an interface, so optimising it for one tool transfers cost to every consumer, and the decision belongs with whoever owns the format, not the build.

## The decision, stated honestly The two rewrites — eliminating left recursion and factoring shared prefixes — are language preserving. Nothing about what the format *is* changes. What changes is the artefact people read, and that is the whole of the trade: - **The tree flips.** A left-recursive rule encodes left associativity in the structure. After the rewrite the repetition hangs off a tail rule and leans right, so associativity has to be reimposed in the semantic action. - **Named constructs are replaced by helpers.** Every primed or factored nonterminal is a name no author chose, and it shows up in generated code, in error messages, and in any railroad diagram produced from the rules. - **Indirect recursion multiplies alternatives.** Substituting one nonterminal into another replaces one alternative with one copy per production of the inlined nonterminal, and a chain does this repeatedly. - **None of it buys expressive power.** The same strings are accepted before and after. ## What each option actually costs | option | what you pay | what you get | |---|---|---| | rewrite the rules in place | readability of the normative document, forever, for every reader | one rule set, one tool, no build step | | change parser family | learning curve, different diagnostics, different performance profile | the authored rules stay as written; no factoring either | | keep both, generate the transformed copy | a build step and an equivalence test | readable specification plus a working tool | | keep the grammar readable and parse it by hand | ongoing maintenance of hand-written code | total control of structure and diagnostics | ## The questions that decide it 1. **Who reads this rule set?** If the answer includes implementers outside your team, the rules are documentation and the rewrite is a tax on all of them. 2. **Is there one implementation or several?** A format with independent implementations must publish rules that any family can consume; a rule set rewritten for one family quietly privileges it. 3. **How much does the tree shape matter downstream?** A pipeline that walks the tree positionally is broken by both rewrites; one that walks by name survives factoring and struggles with the flipped associativity. 4. **How good do the diagnostics need to be?** Generated helper names surface in error messages, and if the format is user-facing, that cost is visible to end users rather than to you. 5. **Is the recursion direct or indirect?** Direct elimination is a local edit a reader can follow; indirect elimination rewrites whole neighbourhoods and is effectively unreadable output. ## Which family needs which rewrite This is the technical half of the judgement, and it is small enough to hold in your head: - **Predictive top-down with fixed lookahead** — needs left recursion removed *and* shared prefixes factored. - **Backtracking or ordered-choice top-down** — still loops on left recursion in the standard formulations, though some implementations add explicit support for it; factoring is a performance and rule-ordering concern rather than a correctness one. - **Bottom-up shift-reduce families** — accept left recursion as written, and prefer it, since the left-recursive form keeps the stack shallow on long lists; factoring is unnecessary. - **General chart parsers** — accept any context-free rule set as authored. - **Table-filling cubic parsers** — need neither rewrite, but do need the rule set in Chomsky normal form, which is a heavier transformation than either. So "change parser family" is not one option but a small menu, and the honest answer names which member and why. ## The shape most teams land on Treat the authored rule set as the **normative source** and the transformed one as **build output**, exactly as you would treat generated code. Then: - Keep the transformation scripted, never hand-edited, so it is reproducible. - Guard the pair with **differential parsing**: run both over a corpus of accepted and rejected inputs and assert the same verdict, so a drift is caught at build time rather than by a consumer. - Name generated helpers deliberately if the tool lets you, so diagnostics stay legible. - Revisit the decision when the recursion turns indirect — that is usually the point at which the generated rule set stops being reviewable and the case for changing family gets stronger. ## What a strong answer sounds like A weak answer picks a side. A strong one asks what the rule set is for, states that the rewrites are free in language terms and expensive in human terms, names which parser families need which rewrite, and proposes the generated-copy arrangement with an equivalence test — while being explicit that if there is exactly one implementation and no external reader, rewriting in place is the simpler and correct choice.

  • What test keeps an authored rule set and its transformed copy from drifting apart?
    Differential parsing over a corpus: run both rule sets across the same accepted and rejected inputs and assert identical verdicts, ideally identical token sequences too. Add every bug report to the corpus. It cannot prove equivalence in general, but it catches the clerical errors — a dropped alternative, a misattached helper — that the transformations actually produce.
  • If the rules must stay as authored, which parser families can consume them unchanged?
    Bottom-up shift-reduce families accept left recursion and need no factoring, and general chart parsers accept any context-free rule set as written. A table-filling cubic parser needs neither rewrite but does require Chomsky normal form, which is a heavier transformation than the two you were trying to avoid.
  • When is rewriting the published rules in place clearly the right call?
    When the rule set has exactly one implementation, no external readers, and the recursion is direct. The rewrite is then a local edit any reviewer can follow, and the build step, the equivalence corpus and the two-artefact discipline would all be overhead bought for nobody.
  • Why does indirect recursion shift the balance toward changing family?
    Because elimination by substitution stops being a local edit: it inlines whole neighbourhoods of rules and multiplies alternatives, so the output is no longer something a reviewer can read against the original. Once the transformed rule set is unreviewable, the argument that it is merely a mechanical variant of the authored one loses its force.

saying these in an interview costs you the question

  • Rewrites a published specification for one tool's convenience.
  • Treats the transformed rule set as the normative document.
  • Assumes every parser family needs the same rewrites.
  • Ships both rule sets with no equivalence test.
  • Claims the rewrite changes what the format accepts.
  • Hand-edits generated rules instead of rerunning the transformation.