Ensuring Termination in Recursive Feature Based Grammars

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 266 papers80 conceptsfrozen 2026-10-04

In computational linguistics, there is a fundamental tension between the expressive power of human language and the mechanical limits of the machines that process it. Human language is inherently recursive—we can nest possessive phrases ("my mother's friend's car") or add an infinite number of adjectives. To model this, researchers use powerful formalisms like Unification Grammars and Definite Clause Grammars (DCGs).

However, these grammars often lead to a "halting problem" in disguise. Without careful constraints, a parser might enter an infinite loop, attempting to build a tree of infinite depth for a sentence of finite length. This research direction focuses on identifying why these loops happen and how to mathematically guarantee that a parser will always finish its job.

The Trap of Left Recursion

The most common cause of non-termination is left recursion. In a top-down parser, if a rule defines a category in terms of itself at the very beginning—such as saying a "Noun Phrase" can be a "Noun Phrase" followed by a "Prepositional Phrase"—the parser will try to find a Noun Phrase by looking for a Noun Phrase, which requires looking for a Noun Phrase, and so on.

As Michael C. McCord and Edward P. Stabler Jr. observed, the standard top-down backtracking search used in logic programming (like Prolog) is fundamentally incompatible with these structures. Even in more modern toolkits like NLTK, basic recursive descent algorithms will spin forever when they encounter these patterns.

While bottom-up parsers are generally more robust to left recursion, they face their own "infinite" problems. Masaru Tomita and Fred Popowich pointed out that cyclic rules (where a symbol eventually derives itself) and null productions (rules that result in empty strings) can create loops where the parser keeps adding new nodes to a graph without ever consuming a word from the input.

The Complexity of Feature Structures

The problem becomes significantly harder when we move from simple labels (like "NP") to complex feature structures. In unification-based grammars, categories are not just atomic symbols; they are bundles of information (like person, number, and gender).

Stuart M. Shieber identified a subtle form of non-termination in these systems: the infinite prediction loop. Even if a grammar isn't strictly left-recursive in its labels, the "prediction" step in a parser might generate an endless sequence of increasingly specific categories. For example, a rule might keep adding a new layer of "subcategorization" features to a verb, creating a unique category that the parser has never seen before, preventing it from ever realizing it is repeating itself.

As Andrew R. Haas demonstrated, general unification grammars are actually Turing-complete. This means that, in the worst case, it is mathematically impossible to write a program that can tell if any given grammar will terminate on any given string.

Mechanisms for Guaranteed Termination

To make parsing practical, researchers developed several "circuit breakers" to stop the infinite search.

Subsumption and Memoization

One of the most powerful solutions is subsumption checking, popularized by Fernando Pereira 0003 and David H. D. Warren in their "Parsing as Deduction" framework. Before the parser adds a new hypothesis to its "chart" (a table of intermediate results), it checks if a more general version of that hypothesis already exists. If it does, the new hypothesis is redundant and is discarded. This ensures that the parser only explores a finite number of truly distinct structures.

Restriction

Stuart M. Shieber introduced restriction, a technique that masks out certain parts of a feature structure during the prediction phase. By ignoring the "messy" details that cause infinite growth and only looking at a "safe" subset of features, the parser can group similar predictions together and terminate.

Offline Parsability

To provide a formal safety guarantee, researchers defined a class of "safe" grammars known as offline parsable grammars. As explored by Andrew R. Haas, a grammar is offline parsable if its "context-free backbone" (the basic rules without the features) does not allow for infinite derivations of the same string. This constraint ensures that for any finite sentence, there are only a finite number of possible tree structures to check.

Beyond Linear Strings

The challenge of termination extends beyond simple sentence parsing. Gertjan van Noord showed that grammars which are perfectly safe for linear strings can still fail when the input is a cyclic word lattice (common in speech recognition). In these cases, the combination of a recursive grammar and a cyclic input creates a "second source of infinity," requiring even stricter controls to prevent the parser from following a loop in the speech graph forever.

Similarly, in natural language generation, the goal is to turn a meaning representation into a string. Shieber et al. and Claire Gardent noted that top-down generators are highly susceptible to infinite loops when they encounter "gaps" or empty categories that provide no semantic information to guide the search. This led to the development of "semantic-head-driven" algorithms that anchor the search in actual lexical words rather than abstract grammatical categories.

Papers in this version

Showing 60 of 66 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 132 papers
  2. Version 1 · 2026-10-04 · 66 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_left_recursion_elimination_a0624db4,
  title = {left-recursion elimination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/left-recursion-elimination/rdr_a0624db454274d4ba1a448ecf03cde4f},
  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_ensuring_termination_in_recursive_featur_a0624db4_v1,
  title = {Ensuring Termination in Recursive Feature Based Grammars},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ensuring-termination-in-recursive-feature-based-grammars/rdr_a0624db454274d4ba1a448ecf03cde4f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}