3

正規表現を表す文字列を受け入れるプログラムを作成しようとしています。例えば：

10(0U1)*

U はユニオン演算子で、* は Kleene スターです (暗黙の連結も見られます)。

文字列のアトムをトークン化し、演算子とオペランドに基づいてマシンを構築することを検討しました。これに似たルールで各アトムをアルゴリズム的に操作したかった: http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

このタイプの入力をインテリジェントな方法で解析して、プログラムで NFA を構築できるようにする方法がわかりません。

私のプログラムの目標は、上記の入力を取り込んで、対応する NFA を出力することです。その目標を達成するためのアドバイスは大歓迎です。

4

1 に答える 1

2

外部ライブラリを使用できる場合は、ANTLRなどの最新のパーサー ジェネレーターにすべての解析作業を実行させ、正規表現の抽象構文ツリーを渡した方がよいでしょう (たとえそれが比較的単純な言語であっても)。

それ以外の場合、ゼロから作成する必要がある場合は、最初にトークナイザー (または「字句解析器」) が必要かどうかを判断する必要があります。言語が1文字のトークンで構成されている場合(例のように)、トークナイザーの作成を安全にスキップして、文字列内の文字をループすることができます。次に、トークン リストをスキャンして構文ツリーを構築する大きなループであるパー​​サーを作成する必要があります。

いずれにせよ、あなたの例では、次のような構文ツリーになるはずです10(0U1)*:

構文木

構文ツリーでは、すべての括弧と暗黙の優先規則がなくなり、ツリーの構造に置き換えられていることに注意してください。

その後、ツリーを再帰的に NFA グラフに変換する必要があります。

これは、進行する可能性のある方法の 1 つの大まかなスケッチです。

構文ノードの種類ごとに変換方法を記述します。このメソッドは、NFA の開始状態と終了状態を引数として呼び出されます。後者はオプションです。このメソッドは、グラフの独自の部分を描画し、必要に応じて子の変換メソッドを呼び出し、終了状態を返します (パラメーターとして省略されている可能性があるため、呼び出し元には不明です)。

  • 開始状態を作成し、構文ツリーのルート ノードの変換メソッドを呼び出して、開始状態を開始状態として渡します。
  • リテラル構文ノード (この例では 0 と 1) は、開始状態から終了状態まで矢印を描画し、指定されていない場合は新しい終了状態を作成します。
    ここに画像の説明を入力
  • スター ノードは、子ノードの変換メソッドを呼び出して、独自の開始状態を子ノードの開始状態と終了状態の両方として指定します (NFA がこの状態を必要な回数だけ「ループ」できるようにするため)。
  • 連結ノードは最初の子を呼び出し、開始状態を与えますが、終了状態は与えません。次に、2 番目の子を呼び出し、1 番目の子の終了状態を開始状態として渡します。子ごとに 1 つずつ、サブグラフの一方向のシーケンスを構築します。

あなたはその考えを得る必要があります。

状態のリンクされた構造として NFA グラフを構築した後 (デバッグやドキュメントの目的で実際のグラフとして表示した後)、それを正式なタプルに変換して出力することができます。

于 2013-02-23T20:43:19.353 に答える