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

目次 はじめに 何年も前に、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); このパターンをトークンタイプごとに掛け合わせ、手動の行カウントを追加し、 と の処理を追加し、入力が完璧に整形されていない場合のオフバイワンエラー処理を追加すると、古典的なアドホックスキャナーになります。それは機能し、高速です。同じロジックが「モダン」にする必要があると誰かが決定し、Boost.Spiritで書き直したときにどのように見えるかは、読者の想像に任せます。 私が求めていたのは、その中間にあるものでした：生成器や依存関係グラフを持ち込まずに、繰り返し部分を処理する、再利用可能なプリミティブの小さなセットです。ゼロコピー、アロケーションフリー、デバッガで読みやすいもの。それがbx::Scannerです。これはパーサー生成器でもなく、Parsing Expression Grammars (PEG) ライブラリでもなく、どちらかになろうともしていません。 デザイン bx::Scannerは、意図的に設計されたいくつかの制約を中心に構築されています。 ゼロコピーおよび非所有。 スキャナーは決してアロケーションを行わず、テキストをコピーしません。すべての結果は、空の結果であっても、カーソルを指すものであり、何もないところを指すものではなく、元の入力に直接指すStringViewです。 1つのカーソル、そしてそれは自分自身では動きません。 単一の現在位置。accept / acceptWhile / acceptUntil はそれを前進させます。peek は移動せずに同じテストを実行します。seek と reset は存在しますが、暗黙的にバックトラックするものはありません。 組み込みの行と列の追跡。 改行を横断するどんな移動も行番号を更新します。後方シークも含まれます。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() のように読み取られます。ブール値を返すよりも冗長ですが、一致したテキストは、取得するために2回目の呼び出しを必要とせずに、回答とともに返されます。 これが bx で実際にどのように使用されているかを示します。 LineReader、最もシンプルなヘルパー LineReader は入力を行に分割し、 と を処理し、不正な入力が残したがる余分な末尾の をトリミングします。 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にはユーザー情報がありません。空のビューはカーソルを指したままなので、入力のゼロ長の切り抜きであり、穴ではないため、結果に直接入れることができます。 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 は完全な範囲をキャプチャします。 合計