この話は2008年に始まりました。 XSS攻撃に対抗する私のプロジェクトの1つで、BBコードを使用することに決め、適切なJavaライブラリを探し始めました。 よくググリングして、何も見つかりませんでした。 もちろん、BBコードをHTMLに変換するための多くのライブラリがありましたが、1つの基準（タグを追加または削除できないこと）に応じて、すべてが私に合っていませんでした。 コース「プログラミング言語と翻訳方法」（古典教育の利点！）を思い出して、私はBBコードを解析するための独自のライブラリの実装に取りかかりました。 その結果、私の最も長命のKefirBBプロジェクトが登場しました 。
KefirBBは、マークアップ言語の構成可能な翻訳者になりました。 ライブラリには、BBCode変換、HTMLフィルタリング、テキスタイル、部分的マークダウンの設定がすでに含まれています。 また、ユーザーは独自のマークアップ言語を実装できます。 構成は、XMLファイルまたはプログラムで指定できます。
2つの主要なエンティティがあります：コードとスコープ。 このコードは、BBコードを解析するためのサンプルと、HTMLを生成するためのテンプレートです。
<code name="bold"> <pattern ignoreCase="true">[b]<var inherit="true"/>[/b]</pattern> <template><b><var/></b></template> </code>
コード内のテキストの解析には、外部の解析に使用されるものとはまったく異なるコードを使用できます。 これを行うために、いくつかのコードを含むスコープがあります。 異なるスコープには同じコードが含まれる場合があります。 この例では、スコープは親コードから継承されます。 ROOTのデフォルトスコープがあります。
これらの詳細については、ドキュメント- ユーザーガイドをご覧ください。
ここで、この翻訳者の開発中に得た経験を共有したいと思います。
最初に遭遇した問題はエラー処理です。 私はもともと、文脈依存文法の翻訳者を作成しました。 しかし、私はすでに後でわかった。 つまり 彼はステートマシンでは動作しません。 パーサーは再帰的なアルゴリズムです。 もちろん、大学でのミスとミスと戦うのは貧弱ですが、彼らは私たちに教えてくれましたが、プログラマーがプログラムでミスをすることを期待して教えてくれました。 翻訳者の最初のバージョンでは、単純なテキストから瞑想を残しました。
[b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b]
これは、タグ[b]が検出されると、パーサーがそれをタグ[b] [/ b]として認識し、既にタグ[b]内にあるかのように内部の解析を開始したために発生しました。 その後、2番目、3番目、4番目など テキストの最後と最後に到達したとき、パーサーは自分がだまされていたことを理解しました。 その後、彼は最後のタグが間違っていると判断し、最後から2番目のタグに戻しました。 最後から2番目のタグが間違っていることをすぐに理解し、最後から2番目のタグのコンテキストで最後のタグを解析し始めました。 最初、彼は自分が正しいと判断し、次に間違っていると判断し、その後戻ってきました。 プロセスはどこかで永遠に終わりました。 アルゴリズムの複雑さはO(2^N)
です。
そして私は言わなければならない、それは深刻な問題だった。 私はほとんど必死で、やめる準備ができていました。 幸いなことに、同級生で世界プログラミングチャンピオンのRenat Mullakhanov氏は、残念なことに、もはや私たちと一緒ではないので、解決策を提案しました。 すでにエラーが発生した場所を覚えておいて、再度解析する必要はありません。 この例では、翻訳者が最後のタグに誤りがあることを理解した後、最後から2番目のタグのコンテキストでそれを解析しようとしませんが、すぐにエラーを返します。 アルゴリズムの複雑さはO(N)
急激に減少しました。 その後、翻訳者はまだ可視領域を持っていなかったため、外観を変更してアルゴリズムを書き直す必要がありましたが、主なアイデアは保持されていました。
その後、翻訳者が開発し、その機能が拡張され、すべてのプロジェクトにしっかりと入りました。 かつてそれを翻訳するためにも使用されました。 そして、ある晴れた日、あるサイトでテキストの翻訳が非常に深刻な問題を引き起こすことに気づきました。 中規模のテキストのブロードキャストには2秒かかりました。 これは受け入れられませんでした。 長い最適化が始まりました。
コードを最適化するときに最初に学ぶべきことは、ヒューリスティックな推測に注意を払わないことです。 プロファイラーのみがパフォーマンスの問題を特定するのに役立ちます。 しかし、これでも私を救いませんでした。 プロファイラーを見てみると、ほとんどの時間は、現時点でどのコードを解析に使用すべきかを決定するメソッドによって奪われていることがわかりました。 私はそれを長期間最適化し、何百回も加速しました。 しかし、判明したように、ほとんどの場合、テキストはコードなしで解析されます。 つまり 最適化する必要があるのはコードの解析ではなく、コードなしのテキスト解析です。実際のテキストでは10倍大きいためです。
どうやってやるの？ 最初のステップで、KefirBBはコードを開始できる文字を定義します。 これらのキャラクターは通常それほど多くありません。 たとえば、BBコードの場合は[
、HTMLの場合は<
です。 次に、これらの文字を比較するためだけにチェックが行われます。 驚くべきことに、この最適化はワードプロセッシングを10倍高速化しました。
KefirBBの開発、新しい機能の追加、新しいマークアップ言語の追加を続けています。 どんな批判やコメントも歓迎します。