Skip to content

Grammar Derivation & Word Complexity

← Back to Domain-Specific Families

Abstractions about how strings and sentences are generated, parsed or measured — context-free, recursive, LL and operator-precedence grammars, left recursion in top-down parsing, factor complexity counting distinct subwords, and breaks or substitutions in written form (anacoluthon, typographic approximation).

8 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

  • Anacoluthon — Break an expected grammatical construction within a sentence by continuing under an incompatible syntax, functioning either as spontaneous disfluency or as a deliberate rhetorical figure.
  • Context-Free Grammar — Generate recursively nested strings with productions that replace one nonterminal at a time regardless of its surrounding symbols, yielding parse trees and exactly the languages recognized by nondeterministic pushdown automata.
  • Factor Complexity Function — The length-indexed count of distinct contiguous factors in a finite or infinite word—equivalently the density function of its factor language—whose growth separates periodicity, low-complexity aperiodicity, and entropy-bearing pattern diversity.
  • Left Recursion — A grammar nonterminal can derive itself again as the leftmost symbol before consuming input, a useful associativity idiom that naive top-down parsers cannot terminate on without transformation or special handling.
  • LL Grammar — A context-free grammar whose next production in a leftmost derivation is uniquely determined while scanning input left-to-right with a fixed amount of lookahead.
  • Operator-precedence grammar — A context-free grammar in operator form whose production-derived terminal-pair precedence matrix is conflict-free.
  • Recursive Grammar — A generative grammar in which a nonterminal can return to itself through a nonempty chain of productions, directly or indirectly.
  • Typographic Approximation — A repertoire-constrained substitution uses available characters or marks to make an unavailable written sign recognizable, with a possible loss of exact identity or form.