HN 日本語サマリー

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

パーサーは複雑である必要はない

Parsers don't have to be complicated (bkaradzic.github.io)

46 pointsby signa1132 コメント

要約

著者は、パーサー生成ツール(Lemon)や手書きのパーサーの経験から、それぞれに不満を感じていました。パーサー生成ツールはコードが読みにくく、手書きパーサーは繰り返しが多く、バグを生みやすいという問題がありました。そこで、これらの問題を解決するために、依存関係や複雑さを排除し、再利用可能なプリミティブ(基本要素)で構成された、ゼロコピー・アロケーションフリーでデバッガでも読みやすい「bx::Scanner」というライブラリを開発しました。

全文翻訳

パーサーは複雑である必要はない

はじめに

数年前、bgfx用の本格的なシェーダーフロントエンドパーサーを書き始め、Lemonパーサー生成ツールを使用しました。それは小さく、機能しましたが、生成されるコードは好きではありませんでした。生成された出力は読みにくく、パーサーを生成するコード自体も私には馴染みのないものでした。文法が変わるたびに、結果として得られるコードの形状を再学習する必要がありました。問題は解決しましたが、最終的には断念しました。

一方で、Lemonのようなものを使うには大げさすぎるような、より小さなものに対しては、アドホックなパーサーを書き続けました。ポインタ演算、文字に対する手動ループ、少数のstrchr/strncmpスタイルの呼び出し、いくつかの状態変数、そしてエッジケースを見落としていないという希望。これらは高速で依存関係もありませんでしたが、常に同じパターンを繰り返していました。空白のスキップ、識別子の収集、エラーメッセージのための行番号の追跡、入力が完璧に整形されていない場合の避けられないオフバイワンエラーの処理です。新しいパーサーごとに、独自の小さなバグの地雷原となり、解析が必要な新しいものごとに、それらのプライベートコピーが作成されました。

このアドホックな解析コードのほとんどは、大まかに次のようでした。

 1const char* pos = input.getPtr();
 2const char* end = input.getTerm();
 3
 4while (pos < end
 5   &&  bx::isSpace(*pos) )
 6{
 7    ++pos;
 8}
 9
10const char* start = pos;
11while (pos < end
12   && (bx::isAlphaNum(*pos) || *pos == '_') )
13{
14    ++pos;
15}
16
17bx::StringView ident(start, pos);

このパターンをトークンタイプごとに繰り返し、手動での行数カウントを追加し、\r\nと\nの処理を追加すると、古典的なアドホックスキャナーになります。これは機能し、高速です。同じロジックが、誰かが「モダン」にする必要があると判断し、Boost.Spiritで書き直した場合、どのように見えるかは読者の想像に任せます。

私が求めていたのは、その中間にあるものでした。ジェネレーターや依存関係グラフを持ち込むことなく、繰り返し発生するスキャン部分を処理する、小さな再利用可能なプリミティブのセットです。ゼロコピー、割り当てフリー、デバッガで読みやすいものです。それがbx::Scannerです。これはパーサー生成ツールでも、Parsing Expression Grammars (PEG) ライブラリでもなく、どちらかになろうともしていません。

設計

bx::Scannerは、意図的に設計されたいくつかの制約に基づいて構築されています。

  • ゼロコピー、非所有型。 スキャナーはメモリを割り当てず、テキストをコピーしません。すべての結果は、空の結果も含め、元の入力に直接指し示すStringViewであり、空の結果は何も指すのではなくカーソルを指します。

  • 単一カーソル、自己移動しない。 単一の現在位置。accept / acceptWhile / acceptUntilがそれを前進させます。peekはカーソルを移動せずに同じテストを実行します。seekとresetは存在しますが、暗黙的に後退するものはありません。

  • 組み込みの行と列の追跡。 改行を横切る移動は、逆方向のseekも含めて、行番号を更新します。getLineとgetColumnは常に利用可能で、どちらも1から始まるため、まともなエラーメッセージがほぼ無料で得られます。

  • ミニ言語ではなく文字クラス。 いくつかのクラス(Class::Space、Class::NonSpace、Class::Identifier、Class::EndOfLine、Class::NewLine)は、ほとんどの日常的なスキャンをカバーします。それ以上に具体的なものは、accept / acceptWhileに渡される通常のbool(*)(char)述語です。学習すべきパターン言語はなく、自分の関数以外にデバッグするものはありません。

  • 非常に小さな表面積。 公開インターフェース全体が、1つの小さなヘッダーファイルに収まります。

ワークフローは常に同じです。StringViewでScannerを構築し、peekとacceptを繰り返して完了します。

1bx::Scanner scanner(input);
2
3// 先頭の空白をスキップします。
4scanner.accept(bx::Scanner::Class::Space);
5
6// 識別子を読み取ります。
7const bx::StringView ident = scanner.accept(bx::Scanner::Class::Identifier);

acceptは一致したテキストを消費し、StringViewとして返します。期待されるトークンが存在しない場合、空のビューを返し、カーソルをそのままにするため、次の代替手段を試すことができます。peekはカーソルを移動せずに同じテストを実行します。

StringViewにはoperator boolがないため、一致した場合は!scanner.accept('=').isEmpty()のように読み取ります。ブール値を返すよりも冗長ですが、一致したテキストは、取得するためにもう一度呼び出す必要なく、回答とともに返されます。

これは、今日のbxで実際にどのように使用されているかです。

LineReader、最もシンプルなヘルパー

LineReaderは入力を行に分割し、\nと\r\nを処理し、不正な入力が残しがちな末尾の\rをトリムします。

1for (bx::LineReader lr(fileContents); !lr.isDone(); )
2{
3    const bx::StringView line = lr.next();
4
5    // `line`は終端文字を含まず、lr.getLine()はその行番号です。
6}

ループ条件に注意してください。明白に見えるwhile (!lr.next().isEmpty() )は間違っています。ファイルには空行が含まれる可能性があり、その空行は有効な結果です。空とは「この行に文字がない」という意味であり、「これ以上行がない」という意味ではないため、終了テストはisDoneである必要があります。

INI解析とサブスキャナー

これはサードパーティのINIライブラリを完全に置き換えました。ScannerはStringViewから構築され、acceptUntilはStringViewを返すため、単一の行を独自のスキャナーにすることができます。

 1bx::Scanner scanner(data);
 2
 3while (!scanner.isDone() )
 4{
 5    scanner.accept(bx::Scanner::Class::Space);
 6
 7    // 1行を、独自の Сканнер として扱います。以下のコードは、
 8    // 行がどれほど不正であっても、行の終わりを超えて実行されることはありません。
 9    bx::Scanner line(scanner.acceptUntil(bx::Scanner::Class::EndOfLine) );
10
11    if (!line.accept(';').isEmpty() )   // 行コメント。
12    {
13        continue;
14    }
15
16    if (!line.accept('[').isEmpty() )   // [セクション] ヘッダー。
17    {
18        line.accept(bx::Scanner::Class::Space);
19        const bx::StringView name = bx::strRTrimSpace(line.acceptUntil("]") );
20
21        if (!line.accept(']').isEmpty()
22        &&  !name.isEmpty() )
23        {
24            section = addSection(name);
25        }
26
27        continue;
28    }
29
30    const bx::StringView name = bx::strRTrimSpace(line.acceptUntil("=") );
31
32    if (line.accept('=').isEmpty()
33    ||  name.isEmpty() )
34    {
35        continue;
36    }
37
38    line.accept(bx::Scanner::Class::Space);
39    setProperty(section, name, bx::strRTrimSpace(line.acceptAll() ) );
40}

サブスキャナーがここで実際の作業を行っています。アドホックバージョンでは、あなたが書くバグは常に同じです。]または改行が欠落している不正な行があり、パーサーは次の行を探して喜んで進んでしまいます。内部スキャナーを単一行に制限することで、「不正な行の終わりを超える」ことを、単に可能性が低いのではなく、表現不可能にします。

URL解析と「空」の意味

一致がboolではなくStringViewとして返されるため、「何も一致しなかった」と「一致しなかった」は同じ値として到着します。acceptUntilでこれが最も顕著です。_findが入力に全く存在しない場合と、_findが既にカーソルにある場合の両方で空を返し、どちらの場合もカーソルは移動しません。

ほとんどの場合、その収縮は回避すべきものではなく、望ましい結果です。空のトークンは正当なトークンです。http://example.comにはパスがなく、ほとんどのURLにはユーザー情報がありません。空のビューはカーソルを指したままなので、入力のゼロ長の Сlice であり、穴ではないため、結果に直接入れることができます。

1const bx::StringView authority = scanner.acceptWhile(isNotSlash);

構造が区切り文字が存在したかどうかに依存する場合にのみ重要になります。その場合、トークンは尋ねるべきものではありません。入力に尋ねてください。区切り文字を消費したい場合はacceptを、そうでない場合はpeekを使用します。

 1bx::Scanner scanner(url);
 2
 3const bx::StringView scheme = scanner.acceptUntil("://");
 4
 5// `scheme`は、`"/tmp/file"`と`"://host"`の両方で空になるため、
 6// スキームが存在したかどうかという質問は別途行われます。
 7const bool hasScheme = !scanner.accept("://").isEmpty();
 8
 9const bx::StringView authority = scanner.acceptWhile(isNotSlash);
10
11const bool hasPath = !scanner.peek('/').isEmpty();

経験則:戻り値はトークンです。peekまたはacceptは「区切り文字が存在したか?」という構造的な質問に答えます。単一の戻り値で十分でない場合(トークンが複数のacceptから組み立てられる場合)、getCursorとbetweenが完全な範囲をキャプチャします。

URLを解析するための合計75行のコードであり、23k行のC++ヘッダーファイルではありません…

[画像: https://x.com/bkaradzic/status/2077995321175794008]

ファイルパスの正規化

パス処理は、ドライブレター、/と\の混在、.と..の折りたたみに対応する必要があります。区切り文字は、accept("/\\")がリテラルの2文字シーケンス/ を探してしまうため、文字列ではなく述語で一致させます。

 1bx::Scanner scanner(src);
 2
 3if (2 <= src.getLength()
 4&&  ':' == src.getPtr()[1])       // Windowsドライブレター。
 5{
 6    size += write(&writer, toUpper(src.getPtr()[0]), &err);
 7    size += write(&writer, ':', &err);
 8    scanner.seek(2);
 9}
10
11const bool rooted = !scanner.accept(isPathSeparator).isEmpty();
12
13while (!scanner.isDone()
14&&     err.isOk() )
15{
16    if (!scanner.acceptWhile(isPathSeparator).isEmpty() )
17    {
18        trailingSlash = scanner.isDone();
19        continue;
20    }
21
22    const bx::StringView component = scanner.acceptWhile(isNotPathSeparator);
23
24    // `.`はスキップされ、`..`はライターを前の区切り文字に戻します。
25}

..処理は、入力ではなく出力を巻き戻し、..がエスケープできないプレフィックスを示すウォーターマークを使用します。スキャナーの仕事は、一度に1つのコンポーネントを引き渡すことだけであり、これはまさに以前は厄介だった部分です。

スタックトレースのシンボリゼーション

atosまたはaddr2lineの出力行を関数名とファイルおよび行に変換することは、strstr呼び出しとポインタ演算のクラスターを置き換えます。

 1for (bx::LineReader lr({atosBuffer, bytes}); !lr.isDone(); )
 2{
 3    bx::Scanner scanner(lr.next() );
 4
 5    functionName = scanner.acceptUntil(" (");
 6
 7    if (functionName.isEmpty() )
 8    {
 9        break;
10    }
11
12    scanner.accept(" (");
13
14    filePath = scanner.acceptUntil(":");
15
16    if (filePath.isEmpty() )
17    {
18        filePath = "<Unknown?>";
19        break;
20    }
21
22    scanner.accept(':');
23
24    const bx::StringView lineStr = scanner.acceptUntil(")");
25
26    if (!lineStr.isEmpty() )
27    {
28        bx::fromString(&line, lineStr);
29    }
30}

これは前のセクションの収縮が有利に働いている例です。空の関数名は有効な結果ではないため、「欠落」と「空」が区別できないことはまさに望ましいことであり、単純な戻り値が唯一のテストで十分です。

結論

私は最初にこれを、もう一つのアドホックパーサー、今回はaddr2line出力用のものを書いていたときに必要としました。それが(現在は削除された)strConsumeToを生成し、後にbx::Scannerのコアとなりました。

bx::Scannerを使用することで、INIライブラリの依存関係を削除し、URL解析、パス正規化、スタックトレースシンボリゼーションで、同じ空白と識別子のループの手作業によるコピーを3つ削除することができました。

もしあなたが空白をスキップして識別子を収集するために、またポインタを追うループを書いていたら、代わりにこれのようなものを検討してみてください。パーサーは本当に複雑である必要はありません。