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 file (cparsec.h) with no dependencies (no libc assumed by default)
• Zero-copy parsing
• No hidden allocations, user-supplied arena
• Inlining-friendly, macros instead of function pointers in hot paths
• SIMD specialized combinators

Demo

A CSV parser looks like this:

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

#define CPC_USE_MEMCHR
#define CPC_USE_UNNAMED
#include "cparsec.h"

CPC_TAKE_QUOTED(quotedField, '"', '"')
CPC_TAKE_TILL_ONE_OF(unquotedField, ",\r\n")
CPC_ALT(field, quotedField, unquotedField)
CPC_SEP_BY_1(record, field, CPC_STRING_(","))
CPC_ALT(lineEnd, CPC_END_OF_LINE_, CPC_EOF_)
CPC_LEFT(parse_csv_row, 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 = parse_csv_row(input, &arena, NULL);

  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.25 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).

Macro	Description	Unnamed
CPC_STRING(name, lit)	Parses the exact string literal lit and returns it as a slice.	CPC_STRING_ *
CPC_ALT(name, x, y)	Tries parser x, and if it fails, tries parser y on the same input.	N/A
CPC_RIGHT(name, x, y)	Runs x then y, returning only the output of y.	N/A
CPC_LEFT(name, x, y)	Runs x then y, returning only the output of x.	N/A
CPC_APPLY(name, x, y)	Runs x then y, returning both outputs as a list.	N/A
CPC_TAKE_WHILE_1(name, pred)	Consumes one or more characters while pred is true and returns the consumed slice.	N/A
CPC_MANY(name, parser)	Runs parser zero or more times and returns the outputs as a list.	N/A
CPC_MANY_1(name, parser)	Runs parser one or more times and returns the outputs as a list.	N/A
CPC_MANY_TILL(name, parser, end)	Repeats parser until end succeeds, returning the collected outputs as a list.	N/A
CPC_SEP_BY(name, item, sep)	Parses zero or more item values separated by sep, returning a list.	N/A
CPC_SEP_BY_1(name, item, sep)	Parses one or more item values separated by sep, returning a list.	N/A
CPC_PURE(name, value)	Succeeds without consuming input and returns value.	N/A
CPC_MAP(name, parser, fn)	Runs parser and transforms its output with fn.	N/A
CPC_TAKE_WHILE(name, pred)	Consumes zero or more characters while pred is true and returns the consumed slice.	N/A
CPC_TAKE_TILL(name, pred)	Consumes input until pred becomes true and returns the consumed slice.	N/A
CPC_BETWEEN(name, open, parser, close)	Parses open, then parser, then close, returning only the output of parser.	N/A
CPC_MATCH(name, parser)	Runs parser and returns the exact consumed input as a slice instead of its parsed value.	N/A
CPC_ONE_OF(name, chars)	Succeeds if the next character is one of the characters in chars, returning it as a slice.	N/A
CPC_END_OF_LINE(name)	Parses \\n or \\r\\n and returns the matched slice.	CPC_END_OF_LINE_
CPC_ANY(name)	Consumes and returns any single character as a slice.	CPC_ANY_
CPC_EOF(name)	Succeeds only at end of input.	CPC_EOF_
CPC_LABEL(name, parser, label)	Wraps an existing parser and changes its fallback error message. It does not override internal errors like arena surpassed or no progress.	N/A

For convenience some parsers can be unnamed to reduce the overhead of naming every function. The ones that are marked with * like CPC_STRING_, need #define CPC_USE_UNNAMED since they require non-standard C99 behavior (Nested Functions, Statement Exprs and __COUNTER__).

SIMD combinators

These parsers are specialized versions that make use of memchr to be SIMD enabled. Since memchr is not available everywhere, they require #define CPC_USE_MEMCHR.

Macro	Description	Anonymous
CPC_TAKE_TILL_ONE_OF(name, stops)	A combination of CPC_TAKE_TILL + CPC_ONE_OF. Returns a slice.	N/A
CPC_TAKE_QUOTED(name, quote, escape)	Parses a quoted string, handling escaped content. Returns a slice.	N/A

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 an error of no progress 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:

CParseC	Haskell
CPC_ALT	<|>
CPC_RIGHT	*>
CPC_LEFT	<*
CPC_APPLY	<*>
CPC_MAP	<$>
CPC_PURE	pure