parsing - 大きなファイル用のライブ構文強調表示パーサー

Question

私は、パーサージェネレーターと、ストリームを最初から最後まで一度に処理するパーサーの基本に精通しています。

私の質問は、構文を強調表示するテキストエディターのような状況についてです。ユーザーが非常に大きなファイルに 1 文字ずつ変更を加えると、ファイル全体を再解析して再強調表示するために多くの計算を実行する必要があります。

私が考えることができる簡単な最適化：

しかし、ファイルの先頭から開始せずに「ローカル」テキストのみを再処理するための一般的に適用可能な手法はありますか?

考え:

アップストリームの変更の影響は、ダウンストリームの変更よりも影響が少ないように思われるため、アルゴリズムが許可する先読みトークンの数によっては、その多くのトークンからファイルの末尾まで再処理できるのではないでしょうか?
ほとんどの再処理要求時にカーソルがどこにあるかを知っているので、その時点での状態のスナップショットをキャプチャして、そこから再開することができます (それが役立つ場合)。

しかし、私はこれが解決されたか、それが機能しないことを誰かが知っていること、および一般的な文法にはファイル全体の解析が常に必要であることを前提としています。

ありがとう！

score 3 · Accepted Answer

構文の強調表示は正確である必要はありません。実際、正確な構文の強調表示が煩わしい場合があります (ファイルの先頭のどこかに構文エラーが発生したために画面全体が灰色になる場合など)。通常、次の方法で回避できます。

トークンクラスを色付けするだけで、ほとんどの作業を実行できます。
中かっこ、大かっこ、およびかっこ (BBP) を一致させるには、画面に表示されている BBP の最初に一致する BBP までさかのぼってスキャンするだけです。これはバックグラウンドで実行できます。これは、通常、ユーザーが一致を探すまで何の影響もないためです。
トークンを逆方向に認識しにくい場合があります (ブロックコメント、正規表現)。この場合、一定の距離だけ戻り、前方にスキャンします。数百行でオーバーヘッドが増えることはありません。代わりに (これは #2 でも機能します)、下位のネストレベルで BBP で終了する行など、戦略的なポイントで字句状態をキャッシュします。

これらはほんの一部の提案です。Vim および Emacs リポジトリには、成功した蛍光ペンの例が多数あり、特定の言語の実用的なアイデアを参照できます。

1 に答える 1