To capture the rich, ambiguous nature of natural language, computational grammars often expand to unmanageable sizes. Whether extracted automatically from treebanks, engineered for speech recognition systems, or scaled for machine translation, grammars face a combinatorial explosion. A maximalist grammar tries to account for every linguistic variation by adding more rules, more nonterminals, and finer-grained labels.
However, this precision comes at a steep cost: massive memory footprints and sluggish parsing speeds. The core insight of grammar optimization is that much of this complexity is redundant. By analyzing the underlying structural properties of formal and statistical grammars, we can drastically shrink their size without sacrificing their coverage or accuracy.
Post-Processing Compaction and Structural Merging
One way to reduce grammar size is to take an over-engineered grammar and prune away its hidden redundancies. This is often done as a post-processing step after a grammar has been compiled or extracted from a corpus.
Consider a rule-based grammar where some rules are implicitly covered by combinations of other rules. In Compacting the Penn Treebank Grammar, A V Krotov et al. introduce an iterative algorithm that identifies and removes these redundant rules. If the right-hand side of a rule can be successfully parsed using the remaining rules in the grammar, that rule is discarded. By repeating this process until no more rules can be eliminated, the authors achieve over a 93% reduction in grammar size while maintaining parsing performance.
Another source of bloat is the presence of structurally identical pathways in a grammar's search graph. In Equivalent node-based speech grammar optimization, Min Zhang et al. show that identifying and merging equivalent nodes prunes the search space losslessly, preserving the exact set of valid sentences while accelerating processing. Similarly, the optimization algorithm designed by Horacio Franco et al. in Fast hierarchical grammar optimization algorithm toward time and space efficiency selectively expands subgrammars and aggressively reduces graph structure, achieving a 66% reduction in nodes. For high-level linguistic frameworks, John Dowding et al. in Practical Issues in Compiling Typed Unification Grammars for Speech Recognition apply post-processing transformations to merge duplicate nonterminals and eliminate unit rules, slashing the rule count of expanded grammars by over 60%.
We can also compress grammars by refactoring how rules are structured or labeled:
- Factorization: Mark Johnson et al. in Compact non-left-recursive grammars using the selective left-corner transform and factoring employ top-down and left-corner factorization to target commonalities in rule productions, compressing the grammar's representation.
- Label Coarsening: When labels themselves are too granular, Greg Hanneman et al. in Improving Syntax-Augmented Machine Translation by Coarsening the Label Set show that collapsing thousands of fine-grained bilingual labels into dozens of coarse categories yields a highly compact grammar that mitigates data sparsity.
- Generic Components: For large, flat grammars, Ea-Ee Jan et al. in Improving large scale alphanumeric string recognition using redundant information demonstrate that substituting generic grammar components for predictable or highly variable elements (like the final character in a string) yields significant compression with minimal impact on recognition accuracy.
Grammar Induction and the Minimum Description Length Principle
Instead of cleaning up a bloated grammar after the fact, we can design induction algorithms that favor compact representations from the start. This is often framed as the Smallest Grammar Problem: finding the most compact context-free grammar capable of generating a given sequence, treating linguistic structure as a form of data compression (Laura Alonso Alemany et al. in Data-driven computational linguistics at FaMAF-UNC, Argentina). As Rafael Carrascosa et al. explain in The Smallest Grammar Problem as Constituents Choice and Minimal Grammar Parsing, solving this efficiently requires decoupling the selection of structural building blocks (constituents) from the optimization of the overall grammar structure.
To guide this search, researchers rely on the Minimum Description Length (MDL) principle. The intuition behind MDL is a balancing act between two competing costs:
$$\text{Total Bits} = \text{Grammar Cost} + \text{Derivation Cost}$$
- The Grammar Cost: The number of bits needed to store the rules themselves.
- The Derivation Cost: The number of bits needed to encode how the corpus sentences are derived from those rules.
If your grammar is too specific, you have a massive rule set but short, trivial derivations. If your grammar is too broad, you have a tiny rule set but incredibly long, complex derivations.
Overly Specific Grammar (High Grammar Cost, Low Derivation Cost):
Rule 1: S -> "the quick brown fox jumps over the lazy dog"
Rule 2: S -> "a quick brown dog jumps over the lazy cat"
Overly Broad Grammar (Low Grammar Cost, High Derivation Cost):
Rule 1: S -> Word S | Word
Rule 2: Word -> "the" | "quick" | "brown" | ...
Optimal MDL Grammar (Balanced):
Rule 1: S -> NP VP
Rule 2: NP -> Det Adj Adj N
...
Tai-Hung Chen et al. in Automatic Learning of Context-Free Grammar use an iterative MDL objective to find this optimal middle ground, automatically discovering meaningful phrases like noun and verb phrases. This scalable MDL-based induction is also leveraged by Linlu Qiu et al. in Improving Compositional Generalization with Latent Structure and Data Augmentation to induce grammars from large-scale semantic parsing datasets, making structural learning techniques computationally viable for data augmentation.
A compelling insight into why MDL works so well in this domain comes from Payam Siyari in The Generalized Smallest Grammar Problem. By generalizing the problem to allow for controlled ambiguity (branching rules), the author demonstrates that introducing ambiguity can drastically reduce grammar size. The added cost of specifying which branch to take during reconstruction is heavily outweighed by the bits saved from a more compact, shared representation.
Parsimonious Selection in Statistical Parsing
The tension between grammar size and accuracy is particularly acute in Data-Oriented Parsing (DOP). Traditional DOP models are maximalist: they store all possible subtrees from a training treebank to ensure maximum linguistic coverage. This causes a combinatorial explosion of fragments, leading to severe memory constraints.
To solve this, Willem H. Zuidema introduces Parsimonious Data-Oriented Parsing (P-DOP) in Parsimonious Data-Oriented Parsing. Instead of keeping every fragment, P-DOP uses a "push-n-pull" estimation algorithm to identify and retain only the most statistically informative subtrees. By filtering out redundant fragments that have negligible impact on performance, the author compresses the grammar by orders of magnitude while maintaining or even improving parsing accuracy.
A similar approach is detailed by the author in What are the Productive Units of Natural Language Grammar? A DOP Approach to the Automatic Identification of Constructions, where identifying the most productive subtrees reduces the rule count by 25% compared to standard DOP.
Complementing this, Khalil Sima'an in Explanation-Based Learning of Data-Oriented Parsing applies Explanation-Based Learning to identify "safe" linguistic chunks before full parsing occurs. This reductive learning strategy produces highly compact statistical grammars, mitigating memory constraints and accelerating complex stochastic models by focusing computational resources only on the structural variations that matter.
Key Foundational Work
Compacting the Penn Treebank Grammar (1998) — contributed 3 concept elements to this direction.
Explanation-Based Learning of Data-Oriented Parsing (1997) — contributed 1 concept elements to this direction.