When parsing natural language, a system attempts to map a linear sequence of words into a structured tree or graph. However, human language is inherently ambiguous. A single sentence can contain multiple words with multiple parts of speech, complex coordination, and uncertain modifier attachments (such as prepositional phrases).
When these local uncertainties interact, the number of potential parse trees doesn't just increase—it multiplies. As Helmut Schmid et al. observe in Parse Forest Computation of Expected Governors, a broad-coverage grammar can yield millions or even billions of valid syntactic interpretations for a single long sentence. If a parser attempts to evaluate each tree as an independent entity, it quickly triggers a combinatorial explosion that exhausts computational memory and time, as noted by Philip J. Hayes in A Construction-Specific approach to Focused Interaction in Flexible Parsing.
To make deep linguistic parsing practical, researchers have developed three core strategies to manage this search space explosion: packed representations, early structural pruning, and constraint propagation.
Packed Representations: Sharing the Forest
The fundamental intuition behind packed representations is structure sharing. If two different interpretations of a sentence share an identical sub-phrase, the parser should not compute or store that sub-phrase twice.
Masaru Tomita pioneered this approach in An Efficient Context-Free Parsing Algorithm for Natural Languages by introducing the Graph-Structured Stack (GSS) and the shared-packed forest. Instead of maintaining separate stacks for every possible derivation path, a GSS allows parsing branches to merge when they enter identical states and split when new ambiguities arise. The output is a compact graph that represents an exponential number of parse trees in polynomial space.
Unpacked Trees (Exponential Growth):
Tree 1: (VP (V saw) (NP (NP the man) (PP with the telescope)))
Tree 2: (VP (VP (V saw) (NP the man)) (PP with the telescope))
Packed Forest (Shared Structure):
[VP] ---> [V: saw] + [NP: the man]
---> [VP] + [PP: with the telescope]
This concept scales directly to highly complex, unification-based formalisms like Head-driven Phrase Structure Grammar (HPSG). High-coverage HPSG grammars often assign numerous detailed feature structures to a single word to account for various syntactic roles. To prevent this lexical ambiguity from overwhelming the chart, Yusuke Miyao et al. introduced a packing method in Packing of feature structures for optimizing the HPSG-style grammar translated from TAG. By merging nearly-identical lexical entries into a single structure with internal "choice points" (disjunctions), the parser tracks fewer total constituents.
In Probabilistic Disambiguation Models for Wide-Coverage HPSG Parsing, Yusuke Miyao demonstrated that these packed feature forests make it computationally tractable to apply probabilistic models over wide-coverage grammars without ever unpacking the underlying search space. Similarly, Hae-Chang Rim et al. showed in Transforming Syntactic Graphs into Semantic Graphs that maintaining a syntactic graph with an "exclusion matrix" allows a system to evaluate and prune hundreds of incompatible interpretations simultaneously, rather than checking individual trees sequentially.
Early Pruning and Supertagging
While packing compresses ambiguity during chart construction, an orthogonal strategy is to prevent the ambiguity from entering the chart in the first place. This is particularly vital for strongly lexicalized grammars like Combinatory Categorial Grammar (CCG), where words are assigned rich, syntactically informative categories.
Because assigning multiple categories per word causes an exponential increase in hypothetical sub-analyses, systems use supertagging—a form of localized sequence labeling—to predict and restrict the valid categories before parsing begins. In Efficient CCG Parsing: A* versus Adaptive Supertagging, Michael Auli et al. demonstrated that while exact algorithms like A* search reduce the number of chart edges explored, combining exact search with adaptive supertagging yields a massive real-world CPU speedup by narrowing the grammar constants early.
However, aggressive pruning introduces a risk: if the supertagger discards the correct category, the downstream parser can never recover it. To solve this error propagation problem, Michael Auli et al. developed an integrated framework in A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing. By utilizing Dual Decomposition, they allowed the supertagger and the parser to iteratively negotiate constraints, ensuring efficiency without sacrificing accuracy.
Pruning can also leverage simpler syntactic signals:
- CFG Filtering: Takuya Matsuzaki et al. demonstrated in Efficient HPSG Parsing with Supertagging and CFG-Filtering that a simplified Context-Free Grammar filter can eliminate impossible HPSG tag sequences early, leaving a lightweight shift-reduce parser to handle the remaining heavy constraints.
- Chunking Constraints: Elliot Glaysher et al. showed in Speeding Up Full Syntactic Parsing by Leveraging Partial Parsing Decisions that a fast, shallow chunker can pre-identify phrase boundaries, preventing a full CYK parser from exploring paths that cross those boundaries.
- POS Blazing: In High Precision Treebanking-Blazing Useful Trees Using POS Information, Takaaki Tanaka et al. used Part-of-Speech tags to "blaze" the search space, automatically filtering out invalid grammatical permutations before deep evaluation occurs.
Reframing Parsing as Constraint Satisfaction
A third approach abandons generative tree-building entirely, reframing parsing as a process of eliminating impossible relationships within a network.
Hiroshi Maruyama formalized this in Structural Disambiguation with Constraint Propagation via Constraint Dependency Grammar (CDG). Instead of combining smaller trees into larger ones, CDG initializes a network representing all theoretically possible word-to-word dependencies. The parser then applies structural constraints iteratively. When a dependency edge is found to violate a rule, it is deleted, which triggers a cascade of further edge eliminations across the network. This constraint propagation resolves complex structural ambiguities, like prepositional phrase attachments, in polynomial time without ever explicitly enumerating a single tree.
Generative Parsing: Combine elements -> Check validity -> Backtrack if failed
Constraint Parsing: Start with all possible edges -> Prune invalid edges -> Remaining network is the parse
This constraint-driven reduction is equally effective for managing feature-based unification grammars. When a parser unifies complex, disjunctive feature descriptions, the number of feature combinations can explode. Mikio Nakano addressed this in Constraint Projection: An Efficient Treatment of Disjunctive Feature Descriptions by introducing Constraint Projection (CP). CP strategically discards feature information that is no longer relevant to the current parsing goal. By dropping these spent constraints, CP prevents "argument explosion" and keeps the unification process highly efficient.