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.