C言語向け単一ヘッダーパーサーコンビネーター

C言語での構文解析には問題があります。手書きのパーサー（再帰下降、ステートマシンなど）は保守が困難です。FlexやBisonによって生成されたコードも保守が困難であり、さらにビルドを複雑にします。 CParseC（C Parser Combinators）は、柔軟で高性能な構文解析ソリューションを提供します。それは、C99で記述された合成可能で表現力豊かなパーサー（HaskellのParsecに触発されています）、依存関係のない単一のヘッダーファイル（cparsec.h）（デフォルトではlibcを想定していません）、ゼロコピー解析、隠れたアロケーションなし、ユーザー指定のアリーナ、インライン化に優しいホットパスでの関数ポインターの代わりにマクロ、SIMD特化コンビネーターです。 デモ CSVパーサーは次のようになります。 ```c #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; } ``` 100万行のCSVを解析する場合、上記のパーサーはBurntSushi/rust-csvよりも約1.25倍、attoparsec-csvよりも約20倍高速です。結果を確認するには、CIでの継続的なベンチマークを参照してください。 API 基本的なコンビネーター すべてのマクロは基本的に、他のインライン可能な関数をパラメーターとして取るインライン可能な関数を生成します。それらはCpcValueを返します。これはスライス（CpcSlice）またはリスト（CpcList、ストレージにCpcArenaが必要）になります。 | マクロ | 説明 | ラベル | 無名 | | :------ | :------ | :------ | :------ | | CPC_STRING(name, lit) | 正確な文字列リテラルlitを解析し、それをスライスとして返します。 | CPC_STRING_LABEL | CPC_STRING_ * | | CPC_ALT(name, x, y) | パーサーxを試行し、失敗した場合は同じ入力でパーサーyを試行します。 | N/A | N/A | | CPC_RIGHT(name, x, y) | xを実行してからyを実行し、yの出力のみを返します。 | N/A | N/A | | CPC_LEFT(name, x, y) | xを実行してからyを実行し、xの出力のみを返します。 | N/A | N/A | | CPC_APPLY(name, x, y) | xを実行してからyを実行し、両方の出力をリストとして返します。 | N/A | N/A | | CPC_TAKE_WHILE_1(name, pred) | predがtrueである限り1つ以上の文字を消費し、消費されたスライスを返します。 | CPC_TAKE_WHILE_1_LABEL | N/A | | CPC_MANY_1(name, parser) | パーサーを1回以上実行し、出力をリストとして返します。 | CPC_MANY_1_LABEL | N/A | | CPC_SEP_BY_1(name, item, sep) | sepで区切られた1つ以上のitem値を解析し、リストを返します。 | CPC_SEP_BY_1_LABEL | N/A | | CPC_PURE(name, value) | 入力を消費せずに成功し、valueを返します。 | N/A | N/A | | CPC_MAP(name, parser, fn) | パーサーを実行し、その出力をfnで変換します。 | N/A | N/A | | CPC_MANY(name, parser) | パーサーを0回以上実行し、出力をリストとして返します。 | N/A | N/A | | CPC_SEP_BY(name, item, sep) | sepで区切られた0個以上のitem値を解析し、リストを返します。 | N/A | N/A | | CPC_TAKE_WHILE(name, pred) | predがtrueである限り0個以上の文字を消費し、消費されたスライスを返します。 | N/A | N/A | | CPC_MANY_TILL(name, parser, end) | endが成功するまでパーサーを繰り返し、収集された出力をリストとして返します。 | N/A | N/A | | CPC_TAKE_TILL(name, pred) | predがtrueになるまで入力を消費し、消費されたスライスを返します。 | N/A | N/A | | CPC_MATCH(name, parser) | パーサーを実行し、解析された値の代わりに消費された正確な入力をスライスとして返します。 | N/A | N/A | | CPC_ONE_OF(name, chars) | 次の文字がchars内の文字の1つである場合に成功し、それをスライスとして返します。 | CPC_ONE_OF_LABEL | N/A | | CPC_END_OF_LINE(name) | \nまたは\r\nを解析し、マッチしたスライスを返します。 | CPC_END_OF_LINE_LABEL | CPC_END_OF_LINE_ | | CPC_ANY(name) | 任意の単一文字を消費し、スライスとして返します。 | CPC_ANY_LABEL | CPC_ANY_ | | CPC_EOF(name) | 入力の終端でのみ成功します。 | CPC_EOF_LABEL | CPC_EOF_ | | CPC_BETWEEN(name, open, parser, close) | openを解析し、次にparserを解析し、次にcloseを解析し、parserの出力のみを返します。 | N/A | N/A | 便宜上、すべての関数に名前を付けるオーバーヘッドを減らすために、一部のパーサーは無名にすることができます。CPC_STRING_のように*でマークされているものは、非標準のC99動作（ネストされた関数、ステートメント式、__COUNTER__）を必要とするため、#define CPC_USE_UNNAMEDが必要です。 _LABELバリアントは、組み込みのエラーメッセージを変更するための追加のラベルパラメーターを受け取ります。 注意 アリーナサイズ超過や（無限ループのある不適切に記述されたパーサーの場合の）進捗なしの状態を示す内部エラーメッセージはオーバーライドできません。 SIMDコンビネーター これらのパーサーは、memchrを使用してSIMDを有効にするための特殊なバージョンです。memchrはどこでも利用できるわけではないため、#define CPC_USE_MEMCHRが必要です。 | マクロ | 説明 | ラベル | 無名 | | :------ | :------ | :------ | :------ | | CPC_TAKE_TILL_ONE_OF(name, stops) | CPC_TAKE_TILL + CPC_ONE_OFの組み合わせです。スライスを返します。 | N/A | N/A | | CPC_TAKE_QUOTED(name, quote, escape) | 引用符で囲まれた文字列を解析し、エスケープされたコンテンツを処理します。スライスを返します。 | CPC_TAKE_QUOTED_LABEL | N/A | Haskellとの比較 Haskellとの違い やるか、やらないか、試すことはない。 HaskellのParsecとは異なり、スライスで動作するためバックトラックが安価なため、`try`は必要ありません。CPC_STRINGのようなパーサーは、失敗した場合に入力を消費しません。 CParseCパーサーは常に終了します。Haskellの多くの`many`, `manyTill`, `sepby`, `sepby1`は無限ループになる可能性がありますが、これとは異なります。 `>>`に相当するものはありません。これはすでに`*>`、つまりCPC_RIGHTで表現できるためです。 失敗する可能性があり、組み込みのエラーメッセージを持つパーサーのみが、パーサーの_LABELバリアントでエラーメッセージをオーバーライドできます。なぜか？非リーフパーサーを関数でラップすると、インライン化が妨げられ、パフォーマンスが著しく低下することが#2で判明したためです。 Haskellとの類似点 すべての関数はHaskell ParsecまたはAttoParsecに触発されています。以下にいくつかの同等性を示す表を示します。 | CParseC | Haskell | | :------ | :------ | | CPC_ALT | <\|> | | CPC_RIGHT | *> | | CPC_LEFT | <* | | CPC_APPLY | <*> | | CPC_MAP | <$> | | CPC_PURE | pure |