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.
", "mediaType":"text/html", "attachment":[], "tag":[ {"type":"Hashtag","name":"#parsing","href":"https://gopinath.org/tags/parsing"}, {"type":"Hashtag","name":"#context-free","href":"https://gopinath.org/tags/context-free"} ], "type":"Note", "id":"https://gopinath.org/objects/jztU6hQGihA" }