Resolving Left Recursion in Top Down Parsing

This direction is merged into another direction: left-recursion elimination. Its last version stays readable and citable here.

Version 1 of 113 papers20 conceptsfrozen 2026-10-04

In the study of formal grammars, left recursion is a classic "infinite loop" trap. If a grammar rule defines a category by starting with that same category—for instance, a "Noun Phrase" starting with a "Noun Phrase"—a standard top-down parser will search for the first Noun Phrase, which requires finding a Noun Phrase, and so on, forever.

To build parsers that are both computationally efficient and linguistically accurate, researchers have developed a suite of strategies to transform these recursive "traps" into manageable, terminating structures.

The Geometry of the Infinite Loop

The core problem arises when the leftmost child of a node in a derivation tree is of the same type as the parent. In An Exploration of Left-Corner Transformations, Andreas Opedal and colleagues describe this as a vertical chain of recursive rules. To a top-down parser, this looks like a bottomless pit.

The solution is often a "left-corner transformation." This process identifies the leftmost leaf of a deep derivation and "hoists" it to become the root of a new, shallower structure. By repositioning the leaf, the parser effectively converts a left-leaning tree (which causes infinite descent) into a right-leaning tree. This right-leaning structure is compatible with standard top-down algorithms because the parser can consume a terminal symbol before recurring.

From Recursion to Iteration

Another way to avoid the recursion trap is to stop treating the grammar as a set of nested calls and start treating it as a loop. This is the "iterative" approach.

Shamim A. Naqvi and Lawrence J. Henschen demonstrated in Synthesizing Least Fixed Point Queries Into Non-Recursive Iterative Programs that left-recursive assertions in logic can be synthesized into non-recursive iterative programs. By decoupling the logical definition from the execution mechanism, they showed that self-referential rules don't have to lead to non-termination; they can simply be processed as a sequence of updates until a "fixed point" is reached.

Similarly, Kenneth Ward Church argued in On Parsing Strategies and Closure that human parsing mimics a Finite State Machine. By using tail-recursion optimization, a system can treat successive right-branching attachments as iterative steps. This allows the parser to reuse the same memory slots for nested phrases, maintaining a constant memory state regardless of how long the sentence becomes.

Compiling Away the Problem

Rather than changing the parser, some researchers focus on changing the grammar itself before the parser ever sees it. In Modular Logic Grammars, Michael C. McCord introduced a "shift operator." During the compilation of the grammar, this operator automatically transforms right-recursive rules into left-embedded forms (and vice versa). This ensures that the underlying logic engine—usually Prolog—doesn't fall into an infinite loop while still correctly capturing the nesting of structures like possessive chains ("the dog's owner's friend").

This "cleanup" approach has historical roots in early OCR systems. Stephen C. Darden in A Contextual Recognition System for Formal languages showed that by eliminating recursion and adjacent non-terminals from formal grammars, a system could use high-confidence symbols as "anchors." These anchors allow the parser to orient itself within a messy string of characters, using the rigid structure of the grammar to correct errors without getting lost in recursive ambiguity.

Tabling and Global Decisions

When transformations aren't enough, parsers can use "memory" to break the cycle. Mark Johnson 0001 and Jochen Dörre explored this in Memoization of Coroutined Constraints. By using a "Lemma Table," the parser records every sub-problem it has already solved. If it encounters the same Noun Phrase goal again at the same position, it simply looks up the result in the table instead of recurring. This "tabling" mechanism guarantees termination even on grammars that would otherwise cause infinite loops.

In modern transition-based parsing, the focus has shifted toward global awareness. Yue Zhang and Stephen Clark in Transition-Based Parsing of the Chinese Treebank using a Global Discriminative Model introduced explicit termination actions. This allows a shift-reduce parser to perform final unary reductions on the root node before finishing. By considering the entire sequence of actions globally, the parser can handle complex nested structures without the "greedy" local errors that often trigger recursive failures.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_resolving_left_recursion_in_top_down_par_c9ed350a,
  title = {Resolving Left Recursion in Top Down Parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/resolving-left-recursion-in-top-down-parsing/rdr_c9ed350af40e4a44958707d4a04530d0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_resolving_left_recursion_in_top_down_par_c9ed350a_v1,
  title = {Resolving Left Recursion in Top Down Parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/resolving-left-recursion-in-top-down-parsing/rdr_c9ed350af40e4a44958707d4a04530d0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}