Scott Vokes on An Efficient Context-Free Parsing Algorithm

Mini
Ori Berenstein on The Slab Allocator https://www.usenix.org/legacy/publications/library/proceedings/bos94/full_papers/bonwick.a

Ori's Bio
Ori was once evicted from the womb. The experience was unpleasant, and he has never forgiven the world for it. Today, he spends most of his time waving fingers over keyboards in order to inject magic into microwaves. Follow Ori at https://twitter.com/oribernstein

---
Main Talk
Scott Vokes on "An Efficient Context-Free Parsing Algorithm" by Jay Earley (Communications of the ACM, 1970)
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.1808

Scott tells us: This paper introduces the Earley algorithm, which is a fully general parsing algorithm: it's able to parse any context-free grammar, including many too ambiguous or recursive for other parsers to handle without careful restructuring. Instead, it takes ambiguity in stride, and is even able to handle many realistic grammars in linear time.

I’ll provide a quick overview of parsing terminology along the way, present the main ideas of the paper (and warn about an infamous bug), and show how it also supports use cases like syntax auto-completion and error messages.

Finally, I'll introduce some other important papers that build on it -- understanding the core algorithm unlocks a whole family tree of parsing approaches. There will be a few resources for people who want to learn more about parsing in general, not just generalized parsing.

Scott's Bio
Among other things, Scott Vokes is the author of theft, a property-based testing library for C. He works on the Compiler Engineering team at Fastly, where he helps make fast things safe, and safe things fast. He's previously worked on embedded systems, compilers, distributed storage systems, and architectural design software, but has always built testing tools along the way. Outside of computers, Scott loves cooking, bicycling, and electronics. He lives in Grand Rapids, MI. Follow Scott at https://twitter.com/silentbicycle

---