Skip to content

Latest commit

 

History

History
16 lines (8 loc) · 1.09 KB

README.md

File metadata and controls

16 lines (8 loc) · 1.09 KB

This visualizer is available here.

I've discussed one aspect of the implementation of this algorithm in a public gist. In this gist, I propose a change to the parsing algorithm to simplify the implementation.

Description

This is a tool that implements the Earley parsing algorithm as given by Elizabeth Scott and Adrian Johnstone in Recognition is not parsing — SPPF-style parsing from cubic recognisers.

Traditional Earley parser algorithms are based on adding links between items and walking the links post-parse to construct some form of derivation. This algorithm instead builds a derivation graph during parsing.

Useful Links

Earley Parsing Explained. This is a particularly approachable description of the Earley algorithm.

A Pint-sized Earley Parser. Another implementation of the SPPF-building algorithm (with explanation).