The computational complexity of parsing is a central concern in computational linguistics, because it determines which grammar formalisms can be used in practical systems. Complexity results establish the inherent difficulty of parsing problems as a function of input length and grammar size, distinguishing formalisms that admit efficient polynomial-time algorithms from those whose parsing problems are intractable. These results have shaped the development of grammar formalisms, guided the search for efficient parsing algorithms, and motivated the study of mildly context-sensitive languages as the sweet spot between expressiveness and tractability.
Complexity by Grammar Class
The parsing complexity landscape is well mapped for the major grammar formalisms in the Chomsky hierarchy and beyond. Regular language membership can be decided in O(n) time by a DFA. Context-free grammar parsing requires O(n³) time in the general case (CYK, Earley), O(n²) for unambiguous grammars, and O(n) for deterministic context-free languages (LR parsing). Tree-adjoining grammar parsing takes O(n⁶) time. Context-sensitive language membership is PSPACE-complete, and unrestricted grammar membership is undecidable.
Unambiguous CFG: O(n²) (Earley)
General CFG: O(n³) (CYK / Earley)
TAG: O(n⁶) (Earley for TAG)
LCFRS / MCFG: O(n^(3·fan-out))
CSG / LBA: PSPACE-complete
Unrestricted: Undecidable
The Cubic Barrier and Beyond
The O(n³) complexity of general CFG parsing has been a practical target for decades. Valiant's 1975 result showed that CFG recognition can be reduced to Boolean matrix multiplication, achieving O(n^2.373) with the best known matrix multiplication algorithms. While theoretically important, the constant factors make sub-cubic algorithms impractical. In practice, the cubic-time algorithms CYK and Earley remain the workhorses, with optimizations like grammar binarization, cell pruning, and coarse-to-fine parsing making them practical for sentences of moderate length.
Complexity results for parsing can be stated with respect to the input string alone (data complexity, with grammar fixed) or with respect to both string and grammar (combined complexity). The distinction matters: CYK parsing is O(n³) in data complexity but O(n³ · |G|) in combined complexity, where |G| is the grammar size. For large-scale grammars, combined complexity becomes the practical bottleneck, motivating grammar factoring, rule indexing, and supertagging approaches that reduce the effective grammar size.
Implications for Grammar Design
Complexity results have directly influenced the design of grammar formalisms for NLP. The motivation for mildly context-sensitive formalisms — TAG, CCG, LCFRS — is precisely that they extend context-free power to capture specific natural language phenomena while maintaining polynomial-time parsability. The recognition that natural language likely requires slightly more than context-free power, but far less than context-sensitive power, has guided the search for the right level of expressiveness.
In the era of neural NLP, complexity considerations have taken on new forms. Neural parsers typically run in O(n) or O(n²) time for dependency parsing and O(n³) for constituency parsing, with the grammar effectively encoded in the neural network weights. Understanding the formal relationship between these empirical systems and the theoretical complexity landscape remains an active area of research, connecting traditional parsing complexity to modern questions about the computational expressiveness of attention mechanisms and recurrent architectures.