1

独自の正規表現ライブラリを実装する方法の正式なドキュメントはありますか？既存の正規表現ライブラリの作成者は、コードのベースになっている正式なドキュメントはありますか？

4

4 に答える 4

1

オートマトン理論および/またはコンパイラー構築に関する優れた教科書（HopcroftやUllmanなど）には、正規表現と、それらをコンパイルできる有限状態オートマトンとの関係が記載されています。したがって、自然言語処理に関するいくつかの教科書も同様です。たとえば、ジュラフスキーやマーティンなど、有限状態の方法が一般的に使用されています。

（CourseraにはUllman自身によるコースもありましたが、新しいセッションはまだ発表されていません。）

現在のREライブラリがどのドキュメントに基づいているかという質問については、私が引用したような教科書と既存の実装に基づいています。私が知っている最初のRE実装は、ケン・トンプソンのバージョンのQEDの実装です。1967年。残念ながら、QED Webサイトの技術レポートには、参考文献がほとんどなく、RE/FA理論に関連するものはありません。このアイデアは、最終的には1950年代に開発されたKleeneの正規言語の理論にまでさかのぼると確信しています。

于 2012-12-03T12:30:03.120 に答える
1

私は、正規表現のサポートを含む JavaScript パーサーを作成しました (そして放棄しました)。私は ECMAscript 定義に基づいており、それ自体は Perl5 正規表現を使用しています。これは ECMA 262 です。私は 1999 年 12 月の第 3 版を使用しました。

于 2012-12-03T12:29:35.617 に答える
0

正規表現は正規表現と呼ばれます。これは、正規表現が表すステート マシンのプロパティであるためです。簡単に言えば、考えられる実装では、単なるテーブルであるステート マシンを使用する可能性があります。正規表現パーサーは、正規表現のいくつかの状態と遷移を作成し、それを実行すると、遷移に従って状態を通過します。

例えば ​​/ab+/ は次のようなものを生成します:

state \ next char:  a       b       $       *
[initial state]     goto 1  fail    fail    fail
1                   fail    goto 2  fail    fail
2                   fail    goto 2  match   fail

($ は文字列の末尾、* はその他の文字)

于 2012-12-03T12:32:38.960 に答える