Efficient parsing with large sparse grammars

 

During work with a moderate-sized, application-specific natural language grammar taken from the BeRP speech system [Jurafsky et al. 1994] we had opportunity to optimize our implementation of the algorithm. Below we relate some of the lessons learned in the process.

• Speeding up matrix inversions
• Linking and bottom-up filtering