Linguistic and computational advantages of bidirectional bottom-up parsing with top-down predictions

Abstract

This paper compares two parsing strategies: bidirectional bottom-up parsing with top-down predictions (BBP) and standard chart parsing. We demonstrate that BBP is superior to classical chart parsers from a linguistic and computational points of view. The efficiency of BBP results from two factors: first, top-down predictions bring about an algorithmic improvement, and, second, the memory model, the data structures and the programming techniques incorporate notable computational improvements.