Valiant's general context free parser is one of the few very well known general context free parsers. Its claim to fame is that given any context-free grammar, it can parse any strings in that grammar in less than O(N^3) time, by leveraging advances matrix multiplication. Unfortunately, lucid explanations of what Valiant's algorithm does is somewhat hard to find. I have just written a live notebook post that explains the Valiant's parser, and lets you play with the algorithm directly.

#parsing #context-free