This post provides a complete tour of Valiant’s parsing along with and extraction of parse trees from the recognition matrix. Previously, I covered CYK parsing with the extraction of trees using back-links from the parse matrix. This is part of my ongoing effort to document various parsing algorithms including GLL, Earley, PEG, and Parsing Combinators.

I am looking for feedback on structure as well as content as before. The implementation prioritizes clarity over speed.

Note: Pyodide takes a little time to initialize, but it should be faster to initialize than spinning up the binder service from Jupyter (but slower to execute).