HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Single header Parser Combinators for C (github.com)

49 pointsby steve-chavez7 コメント

要約

CParseCは、C言語における構文解析の問題を解決するために設計された、単一ヘッダーのパーサーコンビネーターライブラリです。手書きのパーサーやFlex/Bisonのようなツールに比べて、メンテナンスが容易でビルドを複雑にせず、さらに非常に高いパフォーマンスを提供します。HaskellのParsecに触発された、C99で書かれた合成可能で表現力豊かなパーサーが特徴です。

全文翻訳

CParseC

C言語でのパーシングには問題があります。

  • 手書きのパーサー(再帰下降、ステートマシンなど)はメンテナンスが困難です。
  • FlexやBisonで生成されたコードもメンテナンスが難しく、ビルドを複雑にします。

CParseC (C Parser Combinators) は、柔軟で高性能なパーシングソリューションを提供します。

  • C99で記述された、コンポーザブルで表現力豊かなパーサー(HaskellのParsecにインスパイアされています)。
  • シングルヘッダーライブラリ、スタンドアロン(libcは想定していません)。
  • ゼロコピーパーシング。
  • 隠れたアロケーションなし、ユーザー提供のアリーナを使用。
  • インライン化に最適化、ホットパスでは関数ポインタの代わりにマクロを使用。
  • SIMD最適化されたコンビネータ。
  • PostgreSQL拡張で使用されています(pg_csv を参照)。

デモ

CSVパーサーは以下のようになります。

#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;
}

100万行のCSV行を解析した場合、上記のパーサーはBurntSushi/rust-csv より約1.3倍、attoparsec-csv より約20倍高速です。結果を確認するには、CIでの継続的なベンチマーク を参照してください。

API

基本的なコンビネータ

すべてのマクロは、基本的に他のインライン関数をパラメータとして受け取るインライン関数を生成します。これらは CpcValue を返します。CpcValue はスライス (CpcSlice) またはリスト (CpcList、ストレージに CpcArena が必要) のいずれかです。

マクロ説明
CPC_STRING(name, lit)文字列リテラル lit を正確に解析し、スライスとして返します。
CPC_ALT(name, x, y)パーサー x を試行し、失敗した場合は同じ入力でパーサー y を試行します。
CPC_RIGHT(name, x, y)x を実行してから y を実行し、y の出力のみを返します。
CPC_LEFT(name, x, y)x を実行してから y を実行し、x の出力のみを返します。
CPC_APPLY(name, x, y)x を実行してから y を実行し、両方の出力をリストとして返します。
CPC_TAKE_WHILE_1(name, pred)pred が真である間、1つ以上の文字を消費し、消費したスライスを返します。
CPC_MANY(name, parser)parser を0回以上実行し、出力をリストとして返します。
CPC_MANY_1(name, parser)parser を1回以上実行し、出力をリストとして返します。
CPC_MANY_TILL(name, parser, end)end が成功するまで parser を繰り返し実行し、収集した出力をリストとして返します。
CPC_SEP_BY(name, item, sep)sep で区切られた item の値を0個以上解析し、リストとして返します。
CPC_SEP_BY_1(name, item, sep)sep で区切られた item の値を1個以上解析し、リストとして返します。
CPC_PURE(name, value)入力を消費せずに成功し、value を返します。
CPC_MAP(name, parser, fn)parser を実行し、fn でその出力を変換します。
CPC_TAKE_WHILE(name, pred)pred が真である間、0個以上の文字を消費し、消費したスライスを返します。
CPC_TAKE_TILL(name, pred)pred が真になるまで入力を消費し、消費したスライスを返します。
CPC_BETWEEN(name, open, parser, close)open、次に parser、次に close を解析し、parser の出力のみを返します。
CPC_MATCH(name, parser)parser を実行し、解析された値の代わりに消費された正確な入力をスライスとして返します。
CPC_ONE_OF(name, chars)次の文字が chars のいずれかの文字である場合に成功し、それをスライスとして返します。
CPC_END_OF_LINE(name)\n または \r\n を解析し、一致したスライスを返します。
CPC_ANY(name)任意の単一の文字を消費し、スライスとして返します。
CPC_EOF(name)入力終了時のみ成功します。
CPC_LABEL(name, parser, label)既存のパーサーをラップし、フォールバックの解析エラーメッセージを変更します。
SIMDコンビネータ

これらのパーサーは、memchr を利用してSIMD化された特殊なバージョンです1。これらは <string.h> のサポートが必要なため、使用するには #define CPC_USE_STRING_H を定義する必要があります。

マクロ説明
CPC_TAKE_TILL_ONE_OF(name, stops)CPC_TAKE_TILL + CPC_ONE_OF の組み合わせ。スライスを返します。
CPC_TAKE_QUOTED(name, quote, escape)エスケープされたコンテンツを処理し、引用符で囲まれた文字列を解析します。スライスを返します。
名前なしコンビネータ

便宜上、一部のパーサーは名前なしでインライン適用できます。例えば、以下のように書く代わりに:

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

以下のように書くことができます。

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

これを行うには #define CPC_USE_UNNAMED を定義してください。名前なしコンビネータは、非標準のC99動作(ネスト関数、ステートメント式 および __COUNTER__)を必要とします。現実的には、これらはGCCでのみ機能し、clang のような他のコンパイラでは動作しません。

現在、これは CPC_STRING_、CPC_EOF_、CPC_ANY_ のみに対応していますが、すべてのコンビネータでサポートを追加できます。

ヘルパー
マクロ説明
CPC_PARSE(parser, input, arena)input と arena を使用して parser を実行します。
CPC_USER(type, field)arena に格納されている user ポインタから field を読み取ります。これは、パーサーの実行時値を指定するのに役立ちます。

Haskellとの比較

Haskellとの違い
  • やるかやらないか、try はありません。HaskellのParsecとは異なり、スライスを扱うためバックトラックが安価なので try は必要ありません。CPC_STRING のようなパーサーは、失敗した場合に入力を消費しません。
  • CParseCパーサーは常に終了します。Haskellの many、manyTill、sepby、sepby1 のように無限ループする可能性があります。例えば、CPC_TAKE_WHILE と CPC_MANY を組み合わせた場合、無限ループの代わりに CPC_ERR_NO_PROGRESS エラーが発生します。
  • >> に相当するものはありません。これは *>(CPC_RIGHT)で既に表現できます。
Haskellとの類似点

すべての関数は、Haskell ParsecまたはAttoParsecにインスパイアされています。いくつかの等価性を示す表を以下に示します。

CParseCHaskell
CPC_ALT<|>
CPC_RIGHT*>
CPC_LEFT<*
CPC_APPLY<*>
CPC_MAP<$>
CPC_PUREpure

フットノート

  1. memchr は本質的にSIMDではありません。これは、ターゲットlibcの実装に依存します。例えば、glibc や BSD libc ではSIMD化されていますが、musl ではされていません。 ↩