Paper: Left-To-Right Parsing And Bilexical Context-Free Grammars

ACL ID A00-2036
Title Left-To-Right Parsing And Bilexical Context-Free Grammars
Venue Annual Conference of the North American Chapter of the Association for Computational Linguistics
Session Main Conference
Year 2000
Authors

We compare the asymptotic time complexity of left-to-right and bidirectional parsing techniques for bilexical context-free grammars, a grammar formal- ism that is an abstraction of language models used in several state-of-the-art real-world parsers. We pro- vide evidence that left-to-right parsing cannot be re- alised within acceptable time-bounds if the so called correct-prefix property is to be ensured. Our evi- dence is based on complexity results for the repre- sentation of regular languages.