Introduction
In the early 1980s, the dominant view in cognitive science was that humans parse language using a "depth-first" approach. The logic was straightforward: because we rarely notice the inherent ambiguities in sentences and seem to process speech in linear time, our brains must be picking a single path and sticking to it unless forced to backtrack. In his 1983 paper, John Bear of the University of Texas challenged this orthodoxy, proposing that a breadth-first model might actually be a more elegant and efficient explanation for how we process language.
The Challenge of Ambiguity
The central challenge in computational linguistics is ambiguity. A single word can often be a noun or a verb, and a phrase can often attach to multiple parts of a sentence. At the time, most models focused on depth-first algorithms that relied on heuristics—like Minimal Attachment or Right Association—to guess the correct path. However, these guesses often fail, requiring the parser to "backtrack," a process that is computationally expensive and doesn't always align with how humans experience "garden path" sentences. Bear argues that instead of guessing and backtracking, a parser should track all possibilities but use immediate context to filter out those that are syntactically impossible.
The Breadth-First Architecture
Bear’s model is a variation of a chart parser that maintains efficiency through aggressive pruning. Key technical components include:
- Active Edges: The parser stores "active" (incomplete) constituents on a chart. For example, if it identifies a determiner, it creates an edge representing a Noun Phrase ($NP$) that is currently awaiting a Noun ($N$).
- Reachability (Pre-computation): This is the model's "secret sauce." Before parsing begins, the system computes a table of which categories can start which phrases. If the grammar says a Sentence ($S$) can start with a Noun Phrase ($NP$), then $NP$ is "reachable" from $S$.
- Look-ahead Buffers: The model uses a word buffer (W-buffer) and a category buffer (M-buffer). Before the parser attempts to build a new edge or extend an old one, it checks the W-buffer. If the next word is not "reachable" from the expected next part of the phrase, that path is killed immediately.
Psychological and Computational Implications
The model suggests that "linear time" parsing isn't achieved by picking one path, but by having a grammar smart enough to realize that the vast majority of paths are dead ends the moment the next word is seen. Bear argues that the fact that humans only perceive one reading of a sentence is perfectly consistent with a breadth-first model that uses contextual filtering. We might be tracking multiple paths at a sub-conscious level, but the filter kills alternatives so fast we never realize they existed.
Furthermore, by dispensing with "inactive edges" (completed phrases) once they have been used to extend an active edge, the parser keeps its workspace lean. This avoids the "parallel processing explosion" typically associated with breadth-first algorithms.
Conclusion
John Bear's breadth-first model provides a compelling alternative to the depth-first paradigms of the early 80s. By replacing error-prone heuristics with pre-computed reachability and immediate look-ahead filtering, the model offers a framework that is both computationally efficient and psychologically plausible. While the paper acknowledges limitations in handling broader semantic context, it remains a landmark proposal in the evolution of parsing theory.
Summary updated