parsing - テキスト エディターでの構文解析

Question

テキストエディタはどのようにシンタックスハイライトを実行しますか? vim は特別な拡張機能を備えた単純な正規表現を使用して、構文要素を区別するためにより強力にすることを知っていますが、TextMate のような他のテキスト エディターでは完全なパーサーを定義できることも知っています。TextMate が大きなファイルでうまく機能することは知られていませんが、Sublime Text はおそらく大きなファイルで vim よりも優れたパフォーマンスを発揮し、さらに従来の TextMate 構文パーサーをサポートしています。ファイルの上から下への解析の実行を回避するために採用している興味深いハックはありますか、それとも非常に効率的な解析アルゴリズムを採用しているだけですか?

Answer 1

私はかつてテキストエディタを書きました。私は他の人よりもうまくやれると思っていました。それから私は Vim を学び、私が間違っていたことに気付きました:P 私の強調表示エンジンの一部はまだ GitHub に存在します。

いくつかのアプローチが可能です。実際の字句解析 (または浅い解析) ルーチンを作成することもできますが、正規表現を効果的に使用し、ソース解析理論の専門家でない場合は、正規表現の方が実際には高速になる可能性があります。2つを混ぜて使いました。

優れたパフォーマンスを得るために、編集者がファイル全体を強調表示することはほとんどありません。代わりに、ファイルの可視領域を強調表示するだけで、作業を最小限に抑えることができます。もちろん、ユーザーが途中で編集を開始したときに何が起こるかを考慮する必要があります。その可視領域の。私のアプローチは、レクサー状態のスナップショット (つまり、すべてのトークンと字句状態の配置) を常にメモリに保持し、カーソルから 1 つまたは 2 つのトークンを逆方向に歩き、その時点でレクサー状態を使用することでした (つまり、トークンと状態は左にスタックされ、右にあるものは破棄されます)、その時点から可視範囲の終わりまでハイライターを再起動します。すべての (私が思うに) ソース言語は左から右に読み取られるため、編集された領域のさらに左側にあるトークンの強調表示は決して変更されるべきではありません。

編集 | ソースを読み直したところ、途中で行った他の最適化がいくつかありました。キーワードの長いリスト (組み込み関数名など) は、チェックするのにコストがかかります。それらを基数ツリーに組み込み、パフォーマンスが大幅に向上しました。