3

次の構造を含むテキストドキュメントがあります

{1,"StructEx",
[{1,"Element_1",[{2,"name","exampleName"},{3,"exampleValue",1},{2,"exampleComment","foo"}]},
[{1,"Element_2",[{2,"name","exampleName2"},{3,"exampleValue",2},{2,"exampleComment","bar"}]}]}

括弧内の最初の値はデータ型です。StructExのすべての要素を（数回の反復を通じて）返す正規表現が必要なので、このようなものにパックできます

["StructEx"]=>
array(2) {
["Element_1"]=>
array(3) {
  ["name"]=>
  string(11) "exampleName"
  ["exampleValue"]=>
  int(1)
  ["exampleComment"]=>
  string(3) "foo"
}
["Element_2"]=>
array(3) {
  ["name"]=>
  string(12) "exampleName2"
  ["exampleValue"]=>
  int(2)
  ["exampleComment"]=>
  string(3) "bar"
}
}
4

1 に答える 1

1

ネストが任意の深さであると仮定すると、答えはノーです。この種のテキスト ドキュメントを正規表現で解析することはできません。深さが限られている場合、それは苦痛ですが、実行可能です。

なぜそれが一体なのですか？

アルファベット

あなたの質問にさらに詳しく答えるために、いくつかのすばらしい乾式理論を紹介しましょう。

アルファベット Σ を空でない記号の集合として定義しましょう (より技術的に正しい定義は、アルファベットを空でない自由オブジェクトとして扱う圏論から得られますが、議論のためにはこの定義で十分です。

アルファベット Σ では、アルファベット上のすべての有限文字列 (読み方: 単語) のセットを定義できます。つまり、次のようになります。

Σ = {s 1 , s 2 , ... ,s n }

Σ* = {ε} ∪ {s i1 s i2 ...s im | s ik ∈ Σ, m > 0, 1 ≤ k ≤ n}、ε は空文字列

例として、アルファベットがある場合Σ = {a, b, c}、Σ* の一部の単語は , になりますがaaaaaa、それが存在することさえ知らないため、 ではありませabababaん。abdd

正規表現と言語

アルファベット Σ を考えると、 のような正規表現がありab*|cます。混乱を避けるために正規表現の正式な定義をスキップしているので、それが私たちの単純な古い「実用的な」正規表現であると仮定しましょう。

各正規表現定義は、正規言語を定義します。たとえば、この例では、言語は単語a、ab、cで構成されていますが、 でabbbbbcはありませんabc。

有限オートマトン

各正規言語は、正規表現を認識できるデバイスである有限オートマトンとして表現できます。前述の正規表現ab*|cの場合、オートマトンは次のようになります。

ab*|c

0 は開始状態、二重丸は受け入れ状態です。つまり、オートマトンは状態 0 で開始し、単語の各文字を消費し、遷移矢印に従って移動します。最終的に受け入れ状態になった場合、文字列を受け入れると言います。それ以外の場合は、それを拒否すると言います。

したがって、この場合、abbマシンに文字列をフィードします。

  1. 状態 0 で開始
  2. を消費aし、状態 1 に移動
  3. 消費bし、状態 3 に移動
  4. 消費bし、状態 3 に移動
  5. 文字列は空で、状態 3 は受け入れ状態であるため、このマシンは文字列を受け入れます。つまり、正規表現パターンが文字列と一致します。

abcマシンにフィードするとどうなるか見てみましょう。

  1. 状態 0 で開始
  2. を消費aし、状態 1 に移動
  3. 消費bし、状態 3 に移動
  4. 消費c、移動する場所がない、文字列が拒否された

したがって、正規表現は一致しませんabc。これらはすべて、理論を追加した実用的な正規表現と基本的に同じです。

等価

各正規言語は有限オートマトン認識可能であるという定理があります。つまり、目的のパターンに一致する正規言語 (および基礎となる正規表現) が存在する場合、同等の有限オートマトンが存在するはずです。

では、なぜですか？

しかし、あなたのパターンの入れ子には無限の深さがあります。したがって、有限オートマトンの定義と矛盾する、通常の言語と同等の無限大の有限オートマトンが必要になります。

参照

  1. 正規表現とオートマトン

免責事項

ご覧のとおり、正規表現の帰納的定義、圏論の観点からの有限オートマトン、操作の下のクロージャ、およびその他の正式なものはスキップしました。前述の参照リンクでそれについて読むことを歓迎します。

于 2013-07-16T03:54:26.290 に答える