lexer - 非決定性有限オートマトンを構築する

Question

手書きの字句解析を行います。以前に作成した3つの有限自動化を含む1つの非決定論的有限自動を描画する必要があります。飛行機、雲、滑走路などのキーワードで作りました。この3つのオートマタに共通のオートマタを構築する方法について、助けが必要です。それを行う方法の例が必要ですか？あなたが知っているなら私を助けてください??

Answer 1

飛行機、雲、滑走路のオートマトンを描画して、開始状態の前にいくらかの部屋を残します。ここで、最初の状態を消去します。それらの前に新しい単一の状態を描画します。「a」トランジション/エッジ、「r」エッジを「unway」、「c」エッジを「loud」にして、「irplane」オートマトンに接続します。それでおしまい。終わり。

より一般的なケースの場合、それはより複雑です。まず、各オートマトン（飛行機、雲、滑走路など）を描画し、開始位置までに空きスペースを残します。次に、開始する前の状態を描画し、それを飛行機、雲、滑走路オートマトンの古い開始状態の先頭にフリーエッジで接続します。（フリーエッジは、εエッジ、イプシロンエッジ、λエッジ、またはラムダエッジとも呼ばれます）。

次に、それらに対してサブセット構築アルゴリズムを実行します。これは、YouTubeでのビデオチュートリアルを見つけることができます。非決定性有限オートマトンを決定性有限オートマトン（DFA）に変換するオンラインサブセット構築アルゴリズムツールもあります。そのプロセスは決定化と呼ばれます。

DFAを入手したら、それを使用して、スキャナーを駆動する状態、アクション、およびルックアップテーブルを作成します。それはそれ自身のワームの缶です。人々は通常、LexやFlexなどのスキャナージェネレーターを使用してそれを自動化します。オンラインで使用できる同様のユーザーフレンドリーなツールは、OnlineScannerGeneratorです。次の入力を提供することにより、グラフを作成するために使用できます。

airplane:airplane
cloud:cloud
runway:runway

次のように、そのためのDFAが提供されます。