Introduction
Natural language is notoriously ambiguous, often yielding an exponential number of valid syntactic structures for a single sentence. In computational linguistics, explicitly enumerating every possible parse tree is computationally infeasible. To address this "explosion" of possibilities, researchers utilize "shared forests"—compact data structures that store common sub-trees only once. In their 1989 paper, Sylvie Billot and Bernard Lang provide a foundational framework for understanding the efficiency and structure of these forests across various parsing strategies.
The Uniform Framework
The authors introduce a unified model for parsing algorithms based on two key components: Push-Down Transducers (PDT) and Dynamic Programming Simulation. By modeling strategies like Earley, LR, and LL as non-deterministic PDTs, they demonstrate that any context-free parsing process can be executed with $O(n^3)$ space and time complexity.
A novel contribution of this work is the formalization of the shared forest as a Context-Free Grammar (CFG) itself. In this view, the forest is not merely a complex graph but a grammar that generates the set of all valid parse strings. This abstraction allows for a clear distinction between "AND-nodes" (representing the right-hand sides of grammar rules) and "OR-nodes" (representing points of ambiguity where multiple rules apply to the same non-terminal).
The Look-ahead Paradox
One of the paper's most significant findings is the "Look-ahead Paradox." In deterministic parsing for programming languages, look-ahead (e.g., moving from LR(0) to LR(1)) is a standard technique to resolve choices and improve efficiency. However, in ambiguous natural language parsing where the goal is to find all valid structures, look-ahead can be counter-productive.
The authors demonstrate that adding look-ahead features causes "state splitting." This splits the parser's internal states based on context, which often prevents the parser from recognizing that different paths have reached the same sub-problem. Consequently, instead of merging these paths into a single shared sub-tree, the parser performs redundant work, leading to larger, less efficient forests. In tests with the "SBBL" grammar, increasing look-ahead directly led to a loss of efficiency and a larger forest representation.
Forest Topology and Sharing Quality
The physical "shape" of a shared forest is not universal; it depends heavily on the chosen parsing strategy. For instance, bottom-up parsers tend to share the rightmost constituents of a rule, whereas top-down parsers are better at sharing leftmost constituents.
Experimental results using various grammars—including a picogrammar of English and the Ada programming language grammar—confirmed these insights. Simpler schemata like LR(0) often produced more compact forests than more "sophisticated" ones like LR(1). For the Ada expression grammar, while look-ahead provided a 25% speedup in raw computation, it did not improve the compactness of the resulting forest.
Conclusion
Billot and Lang's work provides a rigorous theoretical basis for shared forests, proving that cubic complexity is achievable for any context-free grammar without requiring conversion to Chomsky Normal Form. Their discovery of the Look-ahead Paradox remains a crucial lesson for designers of natural language parsers: more complex features do not always lead to better performance in the face of ambiguity.
Summary updated