課題とスコープ
算術式と変数宣言のための小規模なパーサーを設計してください。入力に複数の構文エラーが含まれている場合でも、パーサーは位置を報告し、後続の文の処理を継続し、IDE向けの部分ASTを提供する必要があります。
これは、字句解析、構文解析、エラー回復、およびデータ構造の間の境界をテストするものです。Bisonは同期ポイントまで入力を破棄して続行することを推奨しています。また、IDEにはエラーノード、安定した範囲情報、そして最初のエラー以降の回復処理も必要です。
面接官が評価するポイント
候補者は、再帰下降構文解析またはLRを選択する前にトークンと文法を定義し、字句エラーと構文エラーを区別し、安全な同期ポイントを選択し、連鎖エラーを抑制し、部分ASTを保持し、ネストされた区切り文字、欠落したセパレーター、終了していない文字列をテストできる必要があります。
30秒の回答フレームワーク
「私はレキサー、パーサー、診断機能を分離します。パーサーはトークンカーソルとソース範囲を追跡します。エラー発生後は、期待されるトークンと実際のトークンを記録し、セミコロン、閉じ区切り文字、またはEOFまでスキップしてErrorNodeを挿入し、処理を継続します。回復処理では、いくつかのトークンが正常に処理されるまで重複を抑制します。ASTノードは欠落した範囲を保持するため、呼び出し側は厳格モードまたは寛容モードを選択できます。」
ステップバイステップの詳細な回答
ステップ1：トークンと文法を定義する
レキサーは、識別子、数値、演算子、区切り文字、セミコロン、無効な文字について、種類、テキスト、オフセット、行および列の位置を出力します。文法によって優先順位と結合性を固定し、回復処理が式解析関数全体に散らばらないようにします。
ステップ2：パーサー構造を選択する
小規模な文法には再帰下降構文解析が読みやすく、式の処理にはprecedence climbingが適しています。より大規模な文法では、明示的なエラー戦略を持つジェネレーターを使用する場合があります。いずれの方法でも、パーサーには先読み（lookahead）、有界なトークン回復、およびソース範囲が必要です。
ステップ3：字句エラーと構文エラーを分離する
無効な文字や終了していない文字列は字句エラーです。エラートークンを出力してスキャンを続行します。オペランド、区切り文字、セミコロンの欠落は、パーサーによってコンテキスト内で報告される構文エラーです。すべての問題に「Unexpected token」というラベルを付けないでください。
ステップ4：同期ポイントを選択する
文レベルの同期ポイントは、セミコロン、閉じ波括弧、またはEOFです。式内では、カンマ、閉じ丸括弧、または演算子の境界で同期します。スキップ処理では常にカーソルを進めるかEOFに達する必要があり、そうでなければ同じエラーで無限ループに陥ります。
ステップ5：部分ASTを構築する
ノード上にエラー範囲を保持します。欠落した子ノードはMissingNodeで表し、回復不能なスパンは元のトークンを含むErrorNodeで表します。フォーマット、ハイライト、補完の各機能は、完全なツリーを前提とするのではなく、これらのノードを適切に処理する必要があります。
ステップ6：連鎖診断を抑制する
1つの回復処理によって、表面的なエラーが多数発生する可能性があります。最後の同期ポイントと成功したトークン数を追跡し、別の診断を報告する前にいくつかのシフト成功を待ちます。ログやUIの使いやすさを維持するために、ファイルごとのエラー数に上限を設けます。
ステップ7：インクリメンタルパースをサポートする
エディタのテキストが変更された場合、変更されていないサブツリーを再利用しながら、影響を受けるトークン範囲とその周辺の文法コンテキストを再パースします。ノード範囲とトークンIDを安定させ、文字オフセット単独ではなく、親の境界とパーサーの状態によってキャッシュを無効化します。
ステップ8：テストと測定を行う
有効な入力、単一のエラー、多数のエラー、ネストされたエラー、長い文字列、および非常に大きな式をテストします。位置、カウント、エラーノード、および終了性をアサートします。長い入力に対して、線形スキャン、再帰深度、メモリ、および最悪ケースの回復コストを測定します。
トレードオフと境界
高速フェイル（Fail fast）対 継続
バッチコンパイラは、より適切なフィードバックのために診断後も処理を続行する場合があります。設定の検証では最初のエラーで拒否することがあります。乖離を防ぐためにレキサー、トークン、診断を共有しながら、これをモードとして切り替え可能にします。
多数の同期ポイント 対 少数の同期ポイント
ポイントを増やすとエラーの影響範囲は限定されますが、回復可能なトークンをスキップしてしまう可能性があります。ポイントを減らすとコンテキストは保持されますが、連鎖エラーが増加します。文や区切り文字に基づいてポイントを定義し、代表的なコーパスでテストします。
再帰下降 対 ジェネレーター
再帰下降を使用するとカスタム診断が容易になります。ジェネレーターは大規模で安定した文法に適しています。回復処理は、テストされていないジェネレーターのデフォルトに頼るのではなく、明示的なインターフェースにする必要があります。
障害訓練と発展
閉じ丸括弧が欠落している場合
次の文を追加し、そのセミコロンまたはEOFでの同期、1つの区切り文字欠落の診断、および後続の文が保持されることを検証します。
無効な文字と終了していない文字列
レキサーがエラートークンを出力し、パーサーが1つの文字で立ち往生することなく、行末または文字列の終端に達することを検証します。
連続エラーの多発
すべてのトークンが無効な入力を与えます。カーソルが進み、エラー数が制限され、CPU使用率が二次関数的に増加しないことを確認する必要があります。
よくある間違いとフォローアップ
間違い1：最初のエラーでnullを返す
IDEがハイライトや補完をどのように継続するかを質問します。代わりに範囲情報を持つErrorNodeまたはMissingNodeを返します。
間違い2：回復中にカーソルを進めない
同じトークンでのループを排除する終了性の論拠を求めます。
間違い3：パーサーですべてのエラーを報告する
終了していない文字列や無効な文字がレキサー診断とパーサー診断のどちらに属するかを質問します。
間違い4：連鎖エラーの抑制を無視する
1つのセミコロン欠落によって重複したエラーが10個も出力されるべきではない理由を質問します。
間違い5：オフセットのみでインクリメンタルパースをキャッシュする
1つの区切り文字を挿入した後に、どの親ノードとパーサー状態が無効になるかを質問します。
拡張フォローアップと模範回答
なぜエラーノードを保持するのか？
フォーマット、補完、ハイライトには依然として構造と範囲が必要です。エラーノードを使用することで、ダウンストリームのツールはクラッシュすることなく、不完全な入力を明示的に処理できます。
回復が確実に終了することをどのように保証するか？
最大エラー数と再帰制限を設けた上で、すべての回復処理でトークンを1つ消費するかEOFに到達させます。
診断の品質をどのように検証するか？
複数の独立したエラーを含むコーパスを使用し、最初のエラーのみをテストするのではなく、位置、カウント、後続のAST、および実行時間をアサートします。