状態図！=グラフ図。
すでに述べたように、状態図はソフトウェアアルゴリズムを記述するためのより便利な代替形式です。 さらに、状態図は動的プロセスを記録する自然な形であり、アルゴリズムのグラフ図は、明白であり、それらを個別に示したり、理解を損なったりする必要のない実装機能を既に含んでいる人工的な構造です。ただし、技術的には必要なアクションのシーケンスを正しく説明しています。
ただし、状態図は、グラフ図を記録するための単なる別のグラフィカル表記ではなく、いくつかの優れた機能を備えています。 図1（b、c）は、図1の記事である初期のグラフ方式に対応する同じオートマトンの状態図を示しています。 1（a）。
図1 a）。 ソースグラフチャート
図1 b）、c）。 アルゴリズムを実装する同等のオートマトンの状態図
（a）。
図1（c）は、状態図と遷移の誤った記録の例を示しています。 不正確な点は、赤い長方形で強調表示された遷移は、入力イベントだけでなく、この状態では同じ名前の元のグラフダイアグラムのフラグに対応するフラグによっても決定されることです（図 1（a）は、入力文字のみを考慮してプロセスの状態を監視することができなくなったため、フラグcを変更するロジックを何らかの形で考慮する必要があります。 問題はフラグc自体にもありませんが、このフラグを変更するロジックが状態s1だけに結び付けられていないという事実にあります。 このフラグの変更に関連付けられたイベントがs1のみに関連付けられる場合、そのような問題は存在しません。 赤で強調表示された遷移はs1に到達したパスに依存します 。これはオートマトンの定義と矛盾し、反応は入力シンボルと現在の状態のみに依存します。 本文でさらに言及するために、これを自動化の原則と呼びます。
図のアルゴリズムの顕著な非手動実装のグラフ方式 1（a）は、状態が明示的に定義されておらず、したがって状態間の遷移が定義されていないため、正しい状態図の形式で記述するのはそれほど簡単ではありません。 図の図を描くには 1（b）図のアルゴリズムによる 1（a） 同等のオートマトンを取得する必要がありました。 グラフスキームの同等のオートマトンを取得する手法は、次のいずれかの記事で検討対象になります。「非自動」プログラムを含むデジタルデバイスはすべて、これらの状態は明示的に記述されていないにもかかわらず、 数学的な意味での状態です。 このような状態は、量子電気力学の量子光子に似ており、簡単に説明することができます。それらはどこにでもあり、どこにも特定ではありませんが、存在し、作用します。
この例では、偶然、グラフ図の各ブランチが1つの状態に対応しています。 つまり、各出力シンボルは1つの状態でのみ取得されます。 ただし、フラグを変更するロジックが異なる場合、1つの出力シンボルが複数の異なる状態で取得されるか、言い換えると、グラフ図の同じブランチが複数の異なる状態に対応することがわかります。 これは、わかりやすさの点でさらに複雑なケースです。
州について話しているので、完全に自然な質問が発生します：「いくつの州に対処しなければなりませんか？」 自動実装では、必要に応じて、状態の数をある程度まで任意に設定します。
非手動アプローチの場合、同等のオートマトンの潜在的な状態の数は次のとおりです。
$$表示$$ 2 ^ \テキスト{total_digit_of all_variable_variables_being、ビット。 } $$表示$$
つまり、 boolなどの動作を決定する変数を1つでも追加すると、「構造」変数の数が2倍になり、条件付きで「回路可能」状態と呼びます。 これらの状態の多くは到達不能な状態です。 到達不能な状態はすべて、動作を決定する変数に対するアクションの特別に選択されたロジックによって自動的に除外され、これらのアクションが互いに重なり合って望ましい結果が得られると想定されます。 心理学の観点から、これは結果として望ましい結果をもたらす一連の多方向アクションとしての動的プロセスであることを思い出します。 前述のように、理解するのは非常に複雑な形式です。 動的プロセスのオートマトン記述（状態図）とアルゴリズム記述（グラフ図）の違いの良い類似性は、その導関数のグラフのグラフ関数の代わりに調べることができます。
行動を決定する変数が少ない場合、アルゴリズムの記述の複雑さはそれほど顕著ではありませんが、そのような変数の数が増えると、アルゴリズムの知覚の複雑さは指数関数的に増大し、精神を抑圧します。
動作を定義する変数という用語を明確にする必要があります。 非手動実装の場合、これは実質的にアルゴリズム分岐を作成する変数です。 自動実装の場合、これは内部状態変数です。 変数として、 内部状態は、すべての状態がリストされている列挙型変数（=ちょうどint）、または2つの状態しかない場合は単なるbool変数です。 次に、オートマトンのソフトウェア実装のさまざまなオプションを示します。
すでに記事の冒頭で述べたように、グラフ図はオートマトンの記録形式であるだけでなく、従来のアルゴリズムの記録形式でもあります。 条件付き遷移操作が遷移矢印で表されているという事実は、驚くことではありませんが、サイクルをどのように表現するのでしょうか？ 私たちのマシンが長方形のテーブルを通過するとしましょう。つまり、垂直サイクルと水平サイクルの変数の組み合わせの合計数はm * nです。 結果のオートマトンには同じ数の状態がありますか？つまり、オートマトンスタイルでループを記述する方法はありますか？
ループを考えてみましょう：
for(i = 5; i--; ){}
このサイクルの条件の観点から、カウンター5,4,3,2,1の値は同じ値です。 はい、ループ本体iの内部でこれはパラメーターです。プログラムの動作はこのパラメーターの異なる値によって異なりますが、forループ操作の観点から、カウンター変数は0ではなく2つの値を取ることができます。変数iはいわば擬似フラグ変数です。
テーブルトラバースオートマトンに戻ると、このオートマトンには2つの状態と2つの擬似フラグ変数があることに注意してください。
- 水平サイクルカウンター 、ステータスを決定します。
{0}-垂直ループ、
{1、...、5、...}-水平サイクル、 - 垂直サイクルカウンターが終了条件を決定します。
図2.状態図を使用したネストされたループの記録。
図に示す「はじめに」の例のOut_textオートマトン 3は、オートマトンの状態の変化を引き起こすイベントの観点から興味深いものです。
図3.「テキストブロックの自動表示」、状態図。
外部とみなせる唯一のイベントは行末です。このオートマトンの他のすべてのイベントは純粋に内部であり、アルゴリズム自体の動作によって生成されます。 ただし、これは、前述の自動化の原則に違反しません。特定の状態からの遷移に影響するすべてのイベントは、同じ状態自体によって生成されるためです。つまり、オートマトンの動作は、この状態への到達方法に依存しません。
自動実装されたプログラムはグラフ図として表すことができ、自動的に実装されたままになります。 図 4.対応する状態図のグラフ図と、記事の冒頭に示した遷移の例を示します。
図4.図3で説明したオートマトンに対応するグラフ図 1（b）
ご覧のように、自動的に実装されたプログラムを記録すると、コンパクトさに関してグラフ図は状態図よりも著しく失われます。
ここで、自動プログラミングと自動回路を区別するものを検討してください。
自動回路のアーチファクト。
危機にwhatしているものをよりよく理解するために、ソフトウェアマシンの2つのカテゴリ（シンボリックと機能）を紹介します。 キャラクターマシンは、入力で一連の文字を受け入れ、出力で一連の文字を発行するマシンです。 これは、古典的な抽象オートマトン 、離散数学で実際に考慮されるオートマトンの完全な類似物です。 文字オートマトンは、コードの認識、正規表現の解析、言語分析、機能オートマトンの最適化、および一般的なアルゴリズムに使用されます。 それらの実装方法については、今日の記事の後半で説明し、次のいずれかの記事で詳細に説明します。
機能的なソフトウェアマシンは、これらのマシンとは反対です（本文ではプログラムと呼びます）-コンピューターまたはマイクロコントローラーのアプリケーションと制御プログラムの完全な類似体です。 これらは、同じモジュール、周辺機器のマイクロコントローラを制御するサブルーチン、またはいくつかの有用な作業を実行するサブルーチン、またはユーザーとのインタラクティブな作業を実装するサブルーチンですが、自動的に設計および実装されます。
自動回路では、抽象オートマトンの開発後の次のステップは構造合成です。抽象信号と状態が「ライブ」ビットでエンコードされ、エンコード方法が選択されると、すでにエンコードされたビットで動作する論理回路が構築されます。 機能的なソフトウェアマシンは、構造マシンに類似したソフトウェアです。
回路の観点からのみ機能的オートマトンを検討し、それらに構造的オートマトン以上のものが見えない場合、そのような狭い外観は干渉する可能性が高くなります。 このアプローチは、自動回路からのトレーシングペーパーであり、自動設計されたモジュールの配置方法のテンプレートを提供します。
図5.ソフトウェアマシンの実装の一般的なパターン
これは、設計プロセスが面倒になるという事実につながり、ほとんどの場合、このテンプレートで規定されている不必要な正式な手順が含まれます。
しかし、実際のプロセスを形式化されたシグナルのセットに変えたり、ある種の「自動化された」APIを使用しないことは、自動プログラミングの利点をもたらします。 利点は、状態図のカテゴリに動的プロセスを記録することです。これにより、プログラミングがより予測可能になります。 オートマトンを操作オートマトンと制御オートマトンに適切に分割します。この分割の一部として、操作オートマトンを正しく合理的に選択することにより、ソリューションが効果的になり、次の記事で説得力を持って示されます。
回路自動機の開発者の動作を機械的にコピーします。これは、アーティファクトという言葉が意味するものです。自動プログラミングは、自動回路の揺りかごを残して、プログラムを処理します。 このプログラムは非常に便利でプラスチック素材であり、この素材の可塑性が人気を集めました。 通常の方法でプログラミングすることにより、デジタル回路を設計するルーチンを省くことができます。 アクションを実行する必要がある場合、条件を確認して実行します。特別なトリガー関数を作成する必要はありません。 私は何について話しているのですか？ このように書くことができます：
if(IO_latch->Data_1_received && IO_latch->Permission) { State = 5; }
でもできる
typedef bool paTrigger(); typedef void paAction(); struct tLink_Trigger_Action { paTrigger * Trigger; paAction * Action; int Next_state; }; bool Trigger_X(){return(IO_latch->Data_1_received && IO_latch->Permission);}; void Action_X(){State = 5;}; tLink_Trigger_Transition Table[States_max][ Triggers_max] = { /*State_0*/{}, /*State_1*/{ …,{ Trigger_X, Action_X }, … }, /*State_2*/{}, /*State_3*/{}, /*State_4*/{}}; uint Engine (uint Message) { if(State->Trigger()) { State->Action(); State = State->Next_state; } … }
違いを感じますか？
超形式主義の支持者が異議を唱えることができるのは、通常のプログラミングでは会計処理が少なく、自動回路方式ではすべてのビットがカウントされるということだけです。 これに対して、パラメータを考慮することに問題がある場合、アカウンティングを考慮してメインマシンをルーチンから解放するサブマシンを作成する価値があると答えます。 これは、建設的な分解のヒントです。
プログラムに関連する状況のドラマは、動的プロセスのモデリングと分析のための便利なツールを提供する自動メンタルテンプレートが同時に重い開発者を支配し、通常のプログラミングの単純な喜びを奪うという事実にあります。 私の意見では、これは自動プログラミング技術がエキゾチックな好奇心以上に上昇できない最も深刻な理由の1つです。
ご想像のとおり、この論争の的となっている状況を克服するための自然な方法は、両方のパラダイムを最大限に活用することです。 この場合、内部状態は次の着信イベントの処理方法を示すものではなく、一種の動作モードになります。 これは重要です。 むしろ、状態は、アルゴリズムがしばらくの間使用されているサブルーチンと見なされる必要があります。 同時に、彼は入力信号を処理し、週末にどこにでも行かずに放送することができます。 ある状態では、プログラムが同じタイプの作業を実行し、同じタイプの範囲を超えるすべてのものが別の状態に転送されることが理解されます。 状態から状態への遷移は、信号によって行われるのではなく、このアルゴリズムにとって重要なイベントによってのみ行われます。 そして、選択した条件に基づいて、これらのイベントを自分で選択します。 したがって、各状態モードには埋め込みプログラムを含めることができます。
図6. 状態が動作モードである設計パターン。
しかし、プログラムは移行するまで関数モードだけではありません。 短い反復を実行し、その間に状況を制御します。 さらに、アプリケーション全体は次のようになります。
図7.プログラムのコミュニティ。
つまり、プログラムを使用すると、 企業のマルチタスクの概念になります。これは、 企業のマルチタスクの古典的なアルゴリズムとは対照的に、何らかの理由で通常のアプリケーション自体が何らかの理由でOSを参照し、システムに制御を返す場合、プログラムは最初に設計されます制御を1ステップだけ受け取るプログラムとして、それを実行し、制御を次の反復に渡します。 企業のマルチタスクとプログラムの違いは正式に条件付きですが、プログラムを自動的に見ることはその反復性を意味するため、プログラムが制御を戻すことを「忘れる」ような問題はありません。
図に示すように、プログラムはマルチスレッドOSの制御下でも問題なく動作します。 同時に、もちろん、企業のマルチタスクは不要のようですが、モジュールの自動デバイスは、自動設計に関連する上記のすべての利点を保持しています。
図8.マルチスレッド環境のプログラム。
プログラムは、移行中に発生する単一のアクションを実行でき、同じ状態（動作モード）で拡張アクティビティを実行できるため、その状態図は機能とMiles and Moorsを取得します。 たとえば、パーキングメーターは状態図で表されます。
図9.プログラム「パーキングメーター」、説明はマシンマイルズとムーアの機能を組み合わせたものです。
パーキングメーターの例はまだ検討されていませんが、状態図を見ると、何が危険なのかを理解するのは簡単です。 状態図によるこのカウンタの説明は、テキストを使用して作成された同じマシンの説明よりもはるかに有益であることに注意してください。
理論の観点からは、ミーリーオートマトンとムーアオートマトンの機能を1つの状態図に組み合わせることで間違いを犯しません。 そのようなオートマトンで数学演算を実行する必要がある場合、それはミーリー・オートマトンと見なすことができます。 同じ機能を備えた抽象オートマトンの場合、Mealyオートマトンはより少ない状態で結果を出すことができます。 マイルをムーアマシンに、またはその逆に変換するための数学的手法があります。
上記はプログラムが何であるかについて少し光を当てます。それらを実装する方法に移りましょう。
機能的なソフトウェアを実装する方法。
前に説明した、図の便宜上のグラフ図から始めましょう。 10。
図10.実装するグラフ図。
グラフ図から直接続く最も明白な「直接的な」解決策は、switchステートメントを使用して、複数Cの代替の状態を決定することです。 次の入力シンボルを受け取ると、プログラムは現在の状態を判別し、状態ごとに入力シンボルが分析され、入力シンボルごとに特定の状態への遷移だけでなく出力シンボルも設定されます。
#define mStep ((uword) (-2))// . uint Automaton (uint Input) { static uint State = 3; uint Out; {, , }; switch (State) { //////////////////////////////////////////// case 1: switch (Input) { /////////// case 0: { , }; State = 2; Out = 2; break; /////////// case 1: { , }; State = 3; Out = 3; break; /////////// case 2: { , }; State = 6; Out = 6; break; /////////// case mStep: break; } break; //////////////////////////////////////////// case 2: ... //////////////////////////////////////////// case 3: ... //////////////////////////////////////////// case 4: ... //////////////////////////////////////////// case 5: ... //////////////////////////////////////////// case 6: ... default: // Error }; return(Out); }
Automataは、 SwitchテクノロジーとIAR visualStateで同様の方法で実装されます。
プログラマーステートの概念は、移行を行わずにしばらく機能するが、同時に「小さなアクティビティ」を継続できるプログラム操作モードとして解釈するため、プログラムを新しい状態に移行することが保証されていない入力シンボルがあるはずです（内部的な理由で彼が独りで行かない限り）、しかし、彼はそれを毎回アクティブにします。 ステップ記号はmStepです。
2番目の実装オプションは根本的に異なります。リストに示すように、各イベントのハンドラーを作成します
uint Message_i0_handler(uint &State) { uint Out; switch (State) { //////////////////////////////////////////// case 1: { , }; State = 2; Out = 2; break; //////////////////////////////////////////// case 2: { , }; State = 1; Out = 1; break; ... }; return(Out); } uint Message_i1_handler(uint &State) { ... } uint Message_i2_handler(uint &State) { ... } void Message_Step_handler(uint &State) { switch (State) { //////////////////////////////////////////// case 1: {, , }; break; //////////////////////////////////////////// case 2: {, , }; break; //////////////////////////////////////////// case 3: {, , }; break; }; return(mStep); } typedef uint (*paMessage_handler)(uint &State); paMessage_handler Reactions[3] = { Message_i0_handler_for_s1, Message_i1_handler_for_s1, Message_i2_handler_for_s1}; uint Automaton (uint Input) { Reactions [Input]; }
上記のオプションは、基本的な考え方を反映した基本的なオプションですが、かなり面倒で時間がかかります。 ただし、それらは、かさばりを減らす（相対的）および作業を高速化する（実際の）方向に問題なく変更されます。
リストオプション2に示すコードを変更します。各Message_ixx_handlerイベントハンドラーを、各状態に対応する一連の関数に分割します。
uint Message_i0_handler_for_s1(uint &State) { { , }; State = 2; Out = 2; return(Out); } uint Message_i0_handler_for_s2(uint &State) { { , }; State = 1; Out = 1; return(Out); } ... uint Message_Step_handler_for_s1(uint &State) { {, , }; return(mStep); }
合計すると、 States * Messages機能が必要であることが理解されますが、一部は繰り返される場合がありますが、さらに、ごく少数しかありません。
ここで取得したすべてのメソッドを配列に結合すると、マシンはルートエンジン関数から動作し、エンジンはフォームに記述できます。
typedef uint (*paMessage_handler)(uint &State); paMessage_handler Reactions[6][3] = { { Message_i0_handler_for_s1, Message_i1_handler_for_s1, Message_i2_handler_for_s1}, ... { Message_i0_handler_for_s6, Message_i1_handler_for_s6, Message_i2_handler_for_s6}, }; paMessage_handler Reactions_for_Step [6] = { Message_mStep_handler_for_s1, ..., Message_mStep_handler_for_s6 }; uint Engine(uint Input = mStep) { uint State = 3; if(Input == mStep) return(Reactions_for_Step [State] (State)); else return(Reactions[State][Input] (State)); }
このオプションを使用すると、割り込みハンドラーでのイベントディスパッチスキームと単一エンジンからの処理が適切に実装されます。
同様の方法が、 boost.statechartテンプレートの実装の基礎となります。
前の2つのオプションの主な欠点は、自動回路のアーティファクトです。つまり、この方法でプログラミングすると、「プログラマーのスタイル」のプログラミングを維持することができず、過度に肥大化した表形式のプログラミングスタイルを使用する必要があります。
表形式のプログラミングが提供するものを検討してください。
- 「+」は、各状態のすべてのイベントに対する反応をリストします（未処理のイベントにはスタブがあります）。 完全な説明があります。
- 「-」しかし、同時に、すべてが非常に面倒に認識されているため、一部のタイプミスの可能性は非常に大きいか、空白を残しています。 つまり、自動プログラミング自体がより信頼性の高い開発方法論であるという事実にもかかわらず、信頼性の向上については言及していません。
IAR社がvisualStateオートマトンのグラフィックプログラミングの道を進んだことは驚くことではありません。プログラミングの自動テキストベースのプログラミングスタイルは人向けではないことを考慮してください。
リストのバリアント1は、受け入れられた状態操作モードの概念によって拡張されている場合、変更の可能性の点ではるかに有益であると思われます。
各状態の入力信号ハンドラー（外部スイッチ）を個別の関数（関数モード）に配置します。
uint State_1 (uint &State, uint Input) { {, , }; switch (Input) { /////////// case 0: { , }; State = 2; Out = 2; break; /////////// case 1: { , }; State = 3; Out = 3; break; /////////// case 2: { , }; State = 6; Out = 6; break; /////////// case mStep: // }; uint State_2 (uint &State, uint Input){...};
状態関数をインデックスで示すことができるように、新たに分離された状態関数はすべて配列に配置されます。 変数内部状態はインデックスであり、タイプuintの値であり、エンジンは次の形式を取ります。
typedef uint (*paState)(uint &State, uint Input); paState States[6] = { { State_1, ..., State_6}, }; uint Engine(uint Input = mStep) { static uint State = 3; return(States [State] (State, Input)); }
オプション3と一見類似しているため、これは、一連の変更モードとしてのプログラマーの概念とより一致しています。 各状態関数はモード関数であり、それ自体が必要なすべての周辺機器、または周辺機器からの同期データフレームをポーリングし、入力文字だけでなくこれに基づいて遷移します。
入力シンボルには、すべてのプログラムに対して同じタイプのシステムメッセージが含まれる場合があります。 これは、特に、状態関数自体を従来の最も馴染みのある方法で記述できることを意味します。
このオプションは、 内部状態変数の各値がこの状態を処理する関数に一意に関連付けられているため、 オプション1よりも優れたパフォーマンスを示し、状態関数を呼び出すと、目的の関数へのポインター。 同時に、 オプション1を実装する場合 、 内部状態変数は状態番号に対応する値と繰り返し比較されます。
このオプションは高速ですが、ルーチンの量は減りません。 この実装の主な欠点は、状態テーブルを持ち、ヘッダーとコードファイルに状態の並列記録を保持する必要があり、いわば、二重記述の問題をコピー/貼り付けしないことです。 ただし、この問題は非常に簡単に解決されます。指定された例を変更します。定数テーブル内のポインターのインデックスである内部状態変数の代わりに、それ自体が状態関数へのポインターである内部状態変数を使用できます。
typedef uint (*paState)( void * argState, uint Input); uint State_1 (paState * State, uint Input) { {, , }; switch (Input) { /////////// case 0: { , }; State = (paState*) State_2; Out = 2; break; /////////// case 1: { , }; State = (paState*) State_3; Out = 3; break; /////////// case 2: { , }; State = (paState*) State_6; Out = 6; break; /////////// case mStep: // }; uint State_2 (paState *State, uint Input){...}; uint Engine(uint Input = mStep) { static paState *State = (paState*) State_3; return(State(State, Input)); }
説明されているオプションは、「自然な」プログラミングとほとんど変わりません。これは、スイッチの内部構造と、それらの代わりに次のタイプの構造を使用できると想像するとさらに明白になります。
if(IO_latch->Data_1_received && IO_latch->Permission) { State = 5; }
このオプションは、個々の状態モードが別々の機能で取り出されるという点でのみ「自然な」プログラミングと異なります。ただし、タスクを単純なサブタスク機能に分割することは、プログラミングの主な手法の1つです。ここでは、ソースコードの機械的で素朴な断片化を回避する、プログラムを分割するための建設的な基準（個別の状態は個別の関数）があるという事実についてのみ話しています：この関数は大きくなり、たとえば、 . , , ( — ), , , « » .
«», tDisplay::Out_text, «». .
11.
この例からわかるように、すべての状態は単一の関数として実装できます。この例では、goto演算子を使用する必要はありませんが、既存の古典的な構造体である分岐とループに追加しました。これ自体は、プログラミングの別の構造的構成であり、オートマトンの状態への移行です。この構造設計について詳しく説明します。
一般的な場合、各状態はラベルでマークされ、状態間の遷移はgoto構造state_nameを使用して実行されます。
状態は常にラベルで始まり、プログラムはそのエントリポイント以外から状態に入ることはできません。括弧{}で囲むこともでき、1つの関数（！）内にオートマトンをネストできます。しかし、これはすでに多すぎます。これにより、単一の関数内で作業する場合でも、モジュール性の原則への準拠が保証されるため、gotoステートメントの使用を前提とする信頼できるプログラミングの原則に違反するものはありません。すべての遷移は、状態図に完全に従って行われます。これにより、複雑さを増すことなく変更を加えることができ、すべてが棚で整理され、それ以上のことはありません。
このソリューションの唯一の欠点は、マシンが作業を開始すると、ストール状態に切り替わるまでマシン内に残ることです。ディスプレイの場合、これは歓迎されますが、オートマタのコミュニティとして実装されたシステムの機能プログラム図7は、この方法で機能する能力がない場合があります。この場合、例6のように、各状態は個別の関数によって記述される必要があります。プログラムコードの実装の便宜上、遷移はマクロによって実行されます。
typedef uint (*paState)( void * argState, uint Input); #define mGoto(argState,argOut){\ State = (paState*)argState;\ return(argOut);\ } #define mStall_code ( (uword)(-1) ) #define mStall(){\ return(mStall_code);\ } // uint Engine(paState *State, uint Input = mStep) { return(State(State, Input)); }
この単純なAPIを使用すると、同じオートマトンの状態関数からオートマトンの動作を制御できます。
このようなコマンドは、実行すると機能が終了するため、このオートマトンの外側にあるオートマトンに対して呼び出すことはできません。
説明されているコマンドシステムの使用は、スキームに従って実行されます。
paState *Display_state; void tDisplay::Out_text (int arg_x0, int arg_y0, int arg_x1, int arg_y1, int arg_x_shift, int arg_y_shift, unsigned char * argText, TMemo * argDebug) { // Display_state = (paState*) state__Inside_text_block; // while(Engine (Display_state, 0) != mStall_code); return; }//void tDisplay::Out_text (int arg_x0, int arg_y0, //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// uint state__Inside_text_block(paState * State, uint Input) { if(Input == mForce_Out_text_block) mGoto(state__Out_text_block, 0); while(1) { switch(*Text_end) { case '\0': case '\n': mGoto(state__Out_text_block, 0); } Text_end++; } }// uint state__Inside_text_block(paState * State, uint Input) //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// uint state__Out_text_block(paState * State, uint Input) { if(Text != Text_end) { // . Out_text_block(); // Execute_script Line_width x_rel += Line_width; } // Text = Text_end; mGoto(state__Control_processing, 0); }// uint state__Out_text_block(paState * State, uint Input) //////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// uint state__Control_processing(paState * State, uint Input) { if(*Text_begin == 0) { mStall(); } // esc mGoto(state__Control_processing, 0); }
この実施形態では、オートマトンエンジンは、関数本体ではなく、別のスレッド、いわゆる「ステップ実行」で起動されてもよい。表示の場合、この必要性は明らかではありませんが、各ブロックを表示した後、新しいデータが処理されてから次のバッチを転送するのに時間がかかることを想像してください。自動的に、これはマルチタスク環境がない場合でも効率的に実装されます。この例は、オートマトン実装の有用性を紹介する機会を提供します。この場合、Out_textを呼び出すとプロセスが充電され、そのエンジンは、計算量が許す限り、バックグラウンドのスーパーループまたは割り込みハンドラーで定期的に起動されます。
説明されているシンプルなAPIは非常に便利で非常に機能的です。これを使用して、例4を変更すると、次のようになります。エンジンはオプション4と同じです。
uint State_1 (paState * State, uint Input) { {, , }; switch (Input) { /////////// case 0: { , }; mGoto(State_2,2); /////////// case 1: { , }; mGoto(State_3,3); /////////// case 2: { , }; mGoto(State_6,6); /////////// case mStep: // . return (0); };
このAPIは、自動合成のニーズの大部分をカバーする単純さにもかかわらず、実用に便利です。
以下、このオプションを基本的な構造実装と呼びます。建設的という言葉は、この実装方法が最も受け入れられるように、実際の経験に直接従うことを意味します。
一部の例では、内部状態変数はエンジン関数の本体で静的として宣言されていますが、これは慣例です。実際、オートマトンはクラスによって記述され、この変数はオートマトンの記述子クラスの一部です。ステートマシン記述子とこのマシンの作業変数をマシンコンテキストという用語と呼ぶことに同意します。オートマトンのコンテキスト、具体的な構造がオートマトンを説明するものの問題には、多くのニュアンスがあります。この問題については別の記事が取り上げられます。
シンボリックソフトウェアマシンを実装する方法。
最後に、単純なシンボリックオートマトンを実装する方法を検討します。上記のように、それらは別個のファミリーを形成し、その概念は機能的オートマトンとは大きく異なり、古典的な抽象オートマトンであり、2つのオートマトンファミリーを実装する方法は異なりますが、共通の機能を備えています。オートマトンがあり、その入力が文字のシーケンスa、b、cを受け取り、指定されたシーケンスを検出した場合に1を、他のすべての場合に0を与えるとします。
希望のbacabシーケンスをしましょう。このオートマトンの状態図を図に示します。 12
図12. bacab入力シーケンス決定マシン。
次のいずれかの記事で、このようなマシンの自動コンパイルのアルゴリズムを示します。次に、このマシンを最も効率的に実装する方法を検討します。 2次元配列を作成する最も簡単な方法
uint FSM[States_amount][Alphabet_size];
ネストされた各配列は状態に対応し、ネストされた配列の各要素には、各入力文字の次の状態のインデックスが含まれます。一般的な場合、各入力文字は0からAlphabet_Size-1のインデックスに関連付けられています。この配列は、古典的なオートマトン遷移テーブルです。出力シンボルは常に「コードが認識される」場合を除いて常に0であるため、出力テーブルは作成できませんが、コードが認識される場合、次の状態ではなく、値0、1、2、...に数字0xffが含まれます。 ff。この場合、エンジン1からの戻りコード、および次の状態のインデックスは0です
。このようなオートマトンのエンジンは、コメントなしの単純な関数によって記述されます。
uint FSM[States_amount][Alphabet_size]; uint Engine(uint Input) { static uint State = 0; State = FSM[State][Index_for(Input)]; if(State == (uint)(-1)) { State = 0; return 1; } else return 0; } // while(!terminate) { if(Engine(Stream++)) goto Found; }; Stopped: // , Found: // }
オートマトンを実装する基本的な方法を説明しました。実装方法のさらなる開発は、マシンの接続に関連しています。これは別の大きなトピックであり、別のシリーズの記事がそれに専念します。
今日のレビューは終わりました。次の記事では、効率について、つまり測定可能なプラスについて説明します。