サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
体力トレーニング
makenowjust-labs.github.io
正規表現マッチングの実装手法の1つとしてPike VMと呼ばれるものがあります。 これはGo言語の正規表現実装やRustのregex crateで使われている手法であり、正規表現rrrと入力文字列wwwに対してO(∣r∣×∣w∣)O(|r| \times |w|)O(∣r∣×∣w∣)の計算量でマッチングができるのが特徴です。 Earley法はJay Earleyの提案した文脈自由文法 (CFG) の構文解析手法の1つです。 すべてのCFGを構文解析できる手法で最悪計算量はO(∣w∣3)O({|w|}^3)O(∣w∣3)ですが、無曖昧であればO(∣w∣2)O({|w|}^2)O(∣w∣2)で、決定的であればO(∣w∣)O({|w|})O(∣w∣)で構文解析ができます。 実装してみると分かりますが、Pike VMとEarley法には類似している点があり、Earley法をPike VMの発展系の
Practical Regular Expressionsrecheck supports practical regular expression features including backreferences and look-around operations. State-of-the-Artrecheck implements the state-of-the-art algorithm to detect ReDoS vulnerability, which contains the fuzzing with static analysis. Just a Libraryrecheck is published as just a library, so you can embed this into your application easily.
Copyright © 2020-2024 TSUYUSATO "MakeNowJust" Kitsune. Built with Docusaurus.
このページを最初にブックマークしてみませんか?
『makenowjust-labs.github.io』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く