2

次のような数式を含む n (〜50000) 行の長いリストがあります。

A(1, 2) = 54353
A(1, 2, 3) = 89327
A(1, B(1, 2)) = 8372
A(7, B(1, 3, 5)) = 6311
A(7, B(C(1, 3, 7), 2, C(1, 3), 5)) = 28490
B(A(1, C(5, 3)), 3, 8, D(1, 2)) = 39783

等

これらの式には、リテラル ( 1、2、3、5など) と関数呼び出し (A(x, y)またはA(x, y, z)またはB(x, y)) が含まれます。関数の引数は、リテラルまたは他の (ネストされた) 関数呼び出しのいずれかにすることもできます。機能 ( A、B、Cなど) は固定されており、その数はそれほど多くありません (12 程度の場合もあります)。

これで、完全な式または*グロブ文字として機能するパターンのいずれかを使用してクエリを実行しました。

A(1, 2) => [54353]
A(1, *) => [54353, 89327, 8372]
A(*, 3) => [89327]
A(*, B(*)) => [8372, 6311, 28490]
A(*, B(*, 3, *)) => [6311]

基本的に、2 つの質問があります。

  1. それを行う方法: 実際、私は良い基本的なパターン マッチング アルゴリズムを知りません。* を含む式を正規表現に変換しようとしましたが、単純な例では機能しますが、残念ながら、より複雑なものでは失敗します。

    Converting:
'A(*, B(*, 3, *))' => /^A\(.*, B\(.*, 3, .*\)\)$/

True positive:
'A(7, B(1, 3, 5))' =~ /^A\(.*, B\(.*, 3, .*\)\)$/

False positive:
'A(7, B(C(1, 3, 7), 2, C(1, 3), 5))' =~ /^A\(.*, B\(.*, 3, .*\)\)$/

    これらのブレース式を逆ポーランド記法に変換してから、通常の正規表現アプローチを適用すると役立つと思いますが、よくわかりません。

  2. How to do it fast : すべてのクエリに対して ~50000 の一致を実行するよりも速く実行する方法についてのアイデアは大歓迎です。ここである種の FSM を使用することは可能ですか?

4

1 に答える 1

2

Context Free Languageを記述している間、正規表現は（もともと）正規言語用に設計されています。

あなたの言語は Deterministic Push-Down Automataによって解析可能です。

考え方は FSM に似ていますが、それに加えて、可能なスタックpush()とpop()要素 があります。
FSM での状態の変更も、スタックのヘッドに依存します。

于 2013-01-31T15:28:03.900 に答える