CParseC

Parsing on C has problems:

• Handwritten parsers (recursive descent, state machine, etc) are hard to maintain.
• Flex or Bison generated code is also hard to maintain plus it complicates builds.

CParseC (C Parser Combinators) offers a solution to parsing that is flexible and performant:

• Composable, expressive parsers written in plain C99 (inspired by Haskell's Parsec)
• Single header library, freestanding (no libc assumed)
• Zero-copy parsing
• No hidden allocations, user-supplied arena
• Inlining-friendly, macros instead of function pointers in hot paths
• SIMD specialized combinators
• Used on PostgreSQL extensions (see pg_csv)

Demo

A CSV parser looks like this:

#include <stdio.h>
#include <stdlib.h>

#define CPC_USE_STRING_H
#include "cparsec.h"

CPC_TAKE_QUOTED(quotedField, '"', '"')
CPC_TAKE_TILL_ONE_OF(unquotedField, ",\r\n")
CPC_ALT(field, quotedField, unquotedField)
CPC_STRING(comma, ",")
CPC_SEP_BY_1(record, field, comma)
CPC_ALT(lineEnd, CPC_END_OF_LINE_, CPC_EOF_)
CPC_LEFT(csvRow, record, lineEnd)

int main(void) {
  CpcArena arena;
  CpcValue arena_storage[8192];
  cpc_arena_init(&arena, arena_storage, sizeof(arena_storage) / sizeof(arena_storage[0]), NULL);

  const char csv[] = "alpha,\"beta\",\"ga,mm,a\",d\"\"elta\n";
  CpcSlice   input = cpc_slice_from_cstr(csv);
  CpcResult  result = CPC_PARSE(csvRow, input, &arena);

  for (size_t i = 0; i < result.out.as.list.len; ++i) {
    const CpcValue *cell = cpc_val_list_at(&arena, &result.out, i);
    CpcSlice        slice = cell->as.slice;
    printf("%.*s  ", (int)slice.len, slice.ptr);
    //alpha  "beta"  "ga,mm,a"  d""elta
  }

  return EXIT_SUCCESS;
}

When parsing 1 million CSV rows the above parser is ~1.3 times faster than BurntSushi/rust-csv and ~20 times faster than attoparsec-csv. See the continuous benchmarking on CI to confirm the results.

API

Basic combinators

All the macros basically generate inlinable functions that take other inlinable functions as parameters. They return CpcValue, which can be a slice (CpcSlice) or a list (CpcList, which requires CpcArena for storage).

SIMD combinators

These parsers are specialized versions that make use of memchr to be SIMD enabled ¹. They require <string.h> support, so you have to #define CPC_USE_STRING_H to use them.

Unnamed combinators

For convenience some parsers can be unnamed and applied inline. For example instead of doing this:

CPC_STRING_(p_comma, ",")
CPC_SEP_BY_1(record, field, p_comma)

You can do:

CPC_SEP_BY_1(record, field, CPC_STRING_(","))

To do this use #define CPC_USE_UNNAMED since unnamed combinators require non-standard C99 behavior (Nested Functions, Statement Exprs and __COUNTER__). Reallistically, they only work on GCC and not on other compilers like clang.

Currently this only works for CPC_STRING_, CPC_EOF_ and CPC_ANY_ but support can be added for every combinator.

Helpers

Haskell Comparison

Differences with Haskell

• Do or do not, there is no try. Unlike Haskell's Parsec we don't need a try since it's cheap to backtrack due to working with slices. Parsers like CPC_STRING do not consume input if they fail.
• CParseC parsers always terminate. Unlike many, manyTill, sepby, sepby1 which can infinite loop in Haskell. If for example you do a combination of CPC_TAKE_WHILE with CPC_MANY, you'll get CPC_ERR_NO_PROGRESS error instead of an infinite loop.
• There's no equivalent for >> as this can be already expressed with *>, which is CPC_RIGHT.

Similarities with Haskell

All the functions are inspired by Haskell Parsec or AttoParsec. Here's a table with some equivalences:

Footnotes

1. memchr is not inherently SIMD. This depends on the implementation provided by the target libc. For example on glibc and BSD libc it is SIMD enabled but not on musl. ↩