Skip to content

Nostracodus/earley

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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).

About

A visualization of SPPFs generated during Earley parsing

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published