Introducing Glush: a robust, human readable, top-down parser compiler

Glush is a new parser compiler based on Glushkov’s construction algorithm – . It offers a human readable grammar, is naturally top-down and maintains worst case cubic performance for even the most ambiguous grammars.

It’s been 45 years since Stephen Johnson wrote Yacc (Yet another compiler-compiler), a parser generator that made it possible for anyone to write fast, efficient parsers. Yacc, and its many derivatives, quickly became popular and were included in many Unix distributions. You would imagine that in 45 years we would have further perfected the art of creating parsers and would have standardized on a single tool. A lot of progress has been made, but there are still annoyances and problems affecting every tool out there.

We’re happy to announce that there’s now another tool for all our toolboxes: Glush is a parser toolkit that lets you create efficient parsers in multiple languages (currently JavaScript, Go, and Ruby) in a declarative and expressive grammar format. Glush focuses on supporting every type of grammar you can throw at it. This means you can write a grammar that’s easy for humans to read and that can function as a readable specification as well. While supporting a wide range of grammar features Glush maintains best-in-class performance.

In this article we will go into the philosophy behind Glush and its reason for existence. We’re going to start by explaining exactly the type of parser we’re interested in creating. We’ll look at the major parser techniques and tools that exist today and discuss how well they fit into our requirements. In the final section we’ll explain the inner workings of the algorithm behind Glush.

Leave a Comment