archives

C++ Parser Combinator Library

I have put a C++ parser combinator library on GitHub https://github.com/keean/Parser-Combinators. There is an example to show how it is used, and there is a simple recursive decent parser for comparison. The parser-combinators benchmark 20% faster than the simple parser. I would appreciate comments on the code, the choice of combinators (I want to keep the number to a minimum without compromising usefulness), and the comparative readability of code using the combinators vs the simple parser, or any other thoughts.

There are two basic string recognisers ('accept', 'expect'), two nullary parsers ('succ', 'fail'), and two parser-constructors ('all', 'any') that take a user supplied functor and a variadic argument list of parsers or recognisers. The functor for the parser constructors is variadic, so it is passed one result argument for each parser, 'all' only calls the functor if all the parsers succeed and provides all arguments, 'any' calls the functor as soon as the first parser from the left succeeds with an index number indicating which argument has the valid result (the remaining arguments are initialised with the default constructor). Finally there are four combinators that can be used on both recognisers and parsers '&&', '||' which behave as they do in boolean logic (with short-circuit evaluation), 'many' and 'discard'.

Edit: The latest version of this library supports full backtracking parser combinators, and is different from other C++ parser combinator libraries because it separates static and dynamic polymorphism. By limiting dynamic polymorphism to only where actually needed, the compiler can inline the combinators (which are function-objects) resulting in performance better than the non-combinator hand-written recursive descent parsers.