Rahul Gopinath | #parsing

This action will delete this post on this instance and on all federated instances, and it cannot be undone. Are you certain you want to delete this post?

No

Yes

This action will block this actor and hide all of their past and future posts. Are you certain you want to block this actor?

No

Yes

This action will block this object. Are you certain you want to block this object?

No

Yes

Are you sure you want to delete the OAuth client [Client Name]? This action cannot be undone and will revoke all access tokens for this client.

No

Yes

Are you sure you want to revoke the OAuth token [Token ID]? This action cannot be undone and will immediately revoke access for this token.

No

Yes

You are currently offline.

#parsing 1 hashtag

Rahul Gopinath posted Mar 17, 2023

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.

https://rahul.gopinath.org/post/2023/03/16/valiant-parser/

#parsing #context-free