Kat parser to convert tokens to productions.

This is a recursive descent parser, providing unlimited lookahead capabilities to allow arbitrary context-free grammars to be parsed. The implementation of memoization makes it a packrat parser which runs in linear time at the expense of potentially unlimited memory use. In practice memory use is limited by the simplicity of typical kat scripts (e.g. expressions don’t tend to have many subexpressions).

This is inspired by Python’s PEG parser, used as of 3.9. Some introductory information can be found in this series of blog posts.

Sean Leavey <>



Kat script parser.