In the conclusion, raph writes: > I am even more convinced than before that efficient parsing is possible on GPU. IMO, the place to start looking for GPU-frie

In the conclusion, raph writes: > I am even more convinced than before that efficient parsing is possible on GPU. IMO, the place to start looking for GPU-friendly parsing algorithms is Valiant's algorithm, which is asymptotically the fastest known general CFG parsing algorithm, and is implemented in terms of Boolean matrix multiplication. The intuition is that bottom-up parsing is basically a transitive closure computation, which is basically the same as solving systems of linear equations over a Boolean ring, which can be sped up using Strassen's algorithm. A bit of Googling suggests that people have looked at optimising Boolean matrix multiplication on GPUs, but I have no idea what the state of the art here is.