Scaladays '15: Meerkat Parsers

June 9, 2015

Meerkat Parsers

An expression language

It’s common to formulate grammars in BNF-like formats and let the combinator generate the parser out of it.

Parsing as a search problem.

Parsing is like trying to get through a a maze: there is dead ends.

Head recursion

Methods: Backtracking schemes

Nondeterminism and Ambiguity

Being non ambiguous does not always require being deterministic

Objective: Near-linear performance on near-deterministic grammars

Separation of Lexing and Parsing


Combines the power of general parsing with disambiguational parsing and combinational filters. The best of both worlds: parser generators and parser combinators.

Paper: Faster, Practical GLL Parsing, CC'15

Shared packed parse forest

Build parsing trees and share subtrees. We need to make it binary.


Discussion, links, and tweets

I care about lots other interesting things as well. Follow me on Twitter to get an impression of that. Or contact me directly on another channel or come along to visit me.