正規表現を解析中にオートマトンを作成する

Question

正規表現をNFAに変換しようとしていますが、問題が発生しています。あなたがその件名を知らないなら、これは私が言っているものへのリンクですhere。

ここで問題となるのは、文字列が与えられた場合、まずそれを後置に変換することです。彼はリアルタイムで、R.Eを解析しながらNFAを描く方が良いと述べていますが、そのような方法はありません。.....

私はこれを始める際に問題があります。誰もが最初に行われるはずの括弧が大きな問題であるため、文字列の解析中にNFAを作成するアルゴリズムを教えてください。

PS：私は実際にはありませんこれに他のタグを置くべきであることを確かめてください....また、これは宿題ではありません。

Answer 1

ここでは、a combined parser, NFA builder, and NFA interpreterがPythonの1ページにあります。私はあなた自身のためにそれを理解することの楽しさを台無しにしていないことを望む - あなたは、リンクをたどる前にハッキングを待つことを好むかもしれない。

これはdeinstの提案と似ていますが、「後方」です。 deinstが言うように、パーサーは正規表現の各サブ式に対してNFAを構築して、あなたが行くにつれてそれらをフックすることができます。たとえば、(a|b)*cの場合は、(a|b)*を解析してNFA＃1を取得し、次にcを解析してNFA＃2を取得し、NFA＃1の最終状態をクローバーして＃2の開始状態に変更します。そして再帰的に。これは従来の答えです。

代わりに、私のコードでは、受け入れ状態だけで簡単なNFAが作成されます。次に、cを解析し、NFAを拡張します。これで、cをチェックし、それを受け入れるNFAがあります。次に、(a|b)*を再帰的に解析し、依然としてNFAを拡張します。文字列reとNFA kを与えられたパーサの契約は、文字列を解析して、kの開始点で終了する結果NFAを生成し、reが一致すると解釈します。このアプローチは、部分的なNFAのビットを互いに繋ぎ合わせてそれらを引っ掛ける必要性を回避する。

Answer 2

かっこ内の正規表現を別個のNFAと見なすことができます。あなたが気にするのは、入力状態と受け入れ状態があることだけです。あなたは括弧内のものをNFAに再帰的に解析し、その入力と受け入れ状態を、構築中のNFA内の適切な場所に挿入します。中置式を解析するという手間のかかる部分は、演算子の優先順位を正しく設定していることです。これは、後置に変換するだけの労力がかかります。

私は、後で出力するのではなく、後で出力する準備ができているように、後置出力を出力する代わりに（後でshunting yard algorithmから）、後置修飾を再解析することをお勧めします。