Packrat Parser
Introduction I was tweaking my functional language’s parser one evening, and I became frustrated with the messiness of my code. It wasn’t something I intended, but a natural occurrence which happens from writing parsers like this, I really couldn’t do much to fix it without sacrificing hours into rewriting it. The most annoying issue I was facing was the constant consumption of ignored tokens such as parenthesis, I would call “consume” every single line which added onto the pile of mess the parser created already - it distracted me from reading the grammar flow of the parse function. And just like any other programmer, I decided to fix this; and i didn’t go the easy route I spent a weekend learning about different parsing algorithms, ones I’ve never heard of before, that’s when I came across Earley parsing - an algorithm for context free grammars. ...