Left-To-Right Parsing and Bilexical Context-Free Grammars

Mark-Jan Nederhof, Giorgio Satta

In: Sergei Nirenburg , Douglas Appelt , Fabio Ciravegna , Robert Dale (Hrsg.). Proceedings of the 6th Applied Natural Language Processing Conference and 1st Meeting of the North American Chapter of the Association for Computational Linguistics (ANLP-NAACL'00), April 29 - May 3. Applied Natural Language Processing Conference (ANLP) Seattle, Washington, USA Seiten 272-279 2000.


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

Weitere Links

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence