3

正規表現から NFA へのコンバーターを実装しようとしています。ほとんどのコードを記述しましたが、状態 (ノード) とエッジの表現を考慮して、サイクルを使用してグラフを作成する方法を見つけるのに苦労しています。

私のグラフ表現は次のとおりです。

type state =
| State of int * edge list (* Node ID and outgoing edges *)
| Match (* Match state for the NFA: no outgoing edges *)
and edge =
| Edge of state * string (* End state and label *)
| Epsilon of state (* End state *)

正規表現を NFA に変換する私の関数は、基本的に正規表現のタイプのパターン マッチであり、正規表現のタイプと「最終状態」(NFA のすべての発信エッジが移動する場所) を取り込み、「開始状態」を返します。その正規表現の（部分的に構築された）NFAの。NFA フラグメントは、発信エッジ リストで構築された State を返すことによって構築されます。各エッジの終了状態は、再帰呼び出しによって構築されます。

ほとんどのコードは簡単ですが、グラフでサイクルを必要とする Kleene スターと + の NFA を構築するのに苦労しています。私の表現を考えると、次のような結果になります。

let rec regex2nfa regex final_state =
  match regex with
  ... (* Other cases... *)
  | KleeneStar(re) ->
      let s = State(count, [Epsilon(regex2nfa r s); Epsilon(final_state)]) in
      s

この時点で s が未定義であるため、明らかにこれはコンパイルされません。ただし、型チェッカーはそのような再帰的に定義された型を (正当に) 拒否するため、"rec" キーワードも追加できません。そしてまた...）。基本的に、ここには鶏が先か卵が先かという問題があります。完全に構築される前に、「状態」参照を別の状態に渡す必要があります。再帰呼び出しで。

参照/可変レコードを使用せずにこれを行う方法はありますか? これを可能な限り機能的に保ちたいのですが、状況を考えるとこれを回避する方法がわかりません...誰か提案がありますか?

4

1 に答える 1

1

遅延型または関数を使用して、明示的な参照なしでサイクルを持つデータ構造を作成できます。実際、どちらも何らかの形の可変性を隠しています。

リストよりも複雑な、最も単純な遅延構造の例を次に示します。

type 'a tree = 'a tr Lazy.t
and  'a tr = Stem of 'a * 'a tree * 'a tree

let rec tree_with_loop : int tree =
  lazy (Stem (42,tree_with_loop,tree_with_loop))

しかし、この種の構造 (つまり、サイクルを含むもの) では、すべてのトラバース関数が発散するため、無限の脆弱な地面に足を踏み入れていることを理解する必要があります。

そして、これは同じ例ですが、遅延はありません:

type 'a tree = unit -> 'a tr
and  'a tr = Stem of 'a * 'a tree * 'a tree

let rec tree_with_loop : int tree =
  fun () -> Stem (42,tree_with_loop,tree_with_loop)

そして、これは少し少ない無限ツリーの例です:

type 'a tree = 'a tr Lazy.t
and  'a tr =
  | Node of 'a
  | Tree of 'a tree * 'a tree

let rec tree_with_loop : int tree =
  lazy (Tree (tree_with_loop,
              lazy (Node 42)))
于 2014-05-07T06:27:44.693 に答える