steve-chavez/CParseC

Source: https://github.com/steve-chavez/CParseC

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(&arena, input);

  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"  delta
  }

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

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

The _LABEL variants take an extra label parameter to change the builtin error message.

The internal error messages that show the conditions of arena size surpassed and no progress (in case of badly written parsers with infinite loops) cannot be overridden.

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.

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.
• There’s no equivalent for >> as this can be already expressed with *>, which is CPC_RIGHT.
• Only the parsers that can fail and have a builtin error message can have their error message overriden with a _LABEL variant of the parser.
  • Why? It was found on https://github.com/steve-chavez/CParseC/pull/2 that wrapping non-leaf parsers in functions hurt performance severily since they prevented inlining.

Similarities with Haskell

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