finite automaton generator, mkfa reference document programmed and written by 1995-1996 S.Hamada □仕様説明 A g2faとの機能上の相違点 n 1 末尾再帰の正規言語(正則)を扱うことができる。これにより例えばフレー ズの有限系列が扱える。左再帰は扱えない。λ遷移を処理しないためであ る。しかし現在必要とされている文法では全く問題がない。もしもっと一 般性をもたせたいとすれば、それに対応することを考えるよりLRを用いて CFLを受理することを考えるべきだろう。 2 g2faは文の受理フラグのみ準備するという仕様であったが、これを変更し て、文法ファイル内の任意のクラスの受理フラグを選択的にFAに埋め込む ことにした。これによりそれぞれのクラスの還元にアクションを施すこと ができる。受理フラグの登録数は32個以内という制限がある。それはint 内のビットフィールドとして表現されているからである。 3 クラス開始フラグを新規に設けた。このフラグと受理フラグから、例えば 解析木を構築するといった利用が可能であろう。 4 g2faでは状態1が最終状態と保証されていたが、mkfaでは決まっていない。 B 入出力ファイルの仕様 * 文法ファイル BNFライクに書き換え規則を記述することはg2faと同じ。ただし受理フラグ の拡張を表現するため、文法ファイルの文法が拡張された。 1 受理フラグはデフォルトで上から新しいクラスが発見されるたびに割付ら れる。開始フラグも同様。以下開始フラグは省略。 2 受理フラグは@{\n}\nで書き換え規則定義行(これを実体宣言と 呼ぶ)をくくることにより、複数のクラスに同じ受理フラグを割り当てる ことができる。またこのブロック内ではクラス名のみ書いておき、ブロッ クの後続行でクラスを定義をすることも可能(これをプロトタイプ宣言と 呼ぶ)である。ブロックのメンバーとして割り当て指定するクラスは、そ れより以前に割り当てが行なわれていないものに限られる(2重割り当てチェッ クを1パスで済ませるための都合)。また複数の定義のあるクラスをメンバー としてくくるとflag-reassignedのエラーが出るので、そのときはプロト タイプ宣言を用いるできである。 3 受理フラグの割り当ては選択的に行なうことも可能である。その行以降の クラスに割当を行なう(行なわない)という制御命令として%ASSIGN,%IGNORE が用意されている。またクラスまたはタグの初めての定義の行頭に!を付 けるとその定義単位に関してのみモードを逆転させることができる。また 初めての定義でない行で!を付けた場合は無視される。ブロック内のクラ スには付けられない。またIGNOREされたブロック内のプロトタイプ宣言さ れたメンバーが、実体宣言部でASSIGNされた場合はASSIGNされる。 4 クラス名は英数字とアンダースコアのみ許される。 5 クラス名の直前に*を付けると、そのクラスを開始記号とする。 6 #以降行末までは注釈とみなされる。 * 語彙ファイル 仕様変更なし。 * FAファイル 次の点で仕様変更された。(-cオプションで受理フラグの仕様をg2faと同じ にできる) 1 第4フィールドの受理フラグが拡張された。ただし受理フラグは16進数で 表現されている。g2faでは1か0かを扱うので下位互換である。 2 クラス開始フラグが設けられた。これは受理フラグと同形式である。これ は第5フィールドである。すなわち{受理状態、入力、遷移先、受理フラグ、 開始フラグ}である。 3 g2faでは状態1は必ず受理状態だと固定されていたが、mkfaでは保証され ない。そこで受理状態は{受理状態:? 入力:-1 遷移先:-1 受理フラグ:? 開始フラグ:?}というふうに明示される。(g2faと非互換) 4 g2faではNFAファイルとDFAファイルを両方出力するが、mkfaではNFA->DFA 変換をメモリ上で行なうので、-NFA,-DFAオプションで選択的に出力する。 * ヘッダファイル mkfaは受理フラグをパーサが利用するためのCのヘッダファイルを提供する。 このヘッダファイルをインクルードすれば、クラスの受理フラグを"ACCEPT_ "というラベルと論理和することにより受理判定可能である。 このためクラス名は英数字とアンダースコアのみ許される。ただしブロック 化されたクラスに関してはタグ名がラベルに与えられる。 C 支援機能 mkfaには文法作成のための支援機能が強化されている。それらには次の項目 がある。 1 エラーチェックが厳しい。受理フラグの2重定義、未使用クラスのチェッ ク、曖昧さのチェック、正則からの逸脱などが主な点である。 2 (未実装)特定のクラスの内容の文字列表示。 3 (未実装)パージングのシミュレートモード。 4 (未実装)二つの文法の等価性のチェック。 D その他 g2faと入力ファイルの互換性を保ちたかったので、あきらめた文法仕様があ る。一つは、文法ファイルを改行フリーで";"で区切らせること、クラス定義 は"|"を用いて1ステートメントに固定させることと、FAファイルの第4フィー ルドは遷移先の受理フラグにすること(現在は遷移前の受理フラグ、このため ダミー行が1行増える)である。 □バージョン履歴 ~v.1.00 grammarファイルから非終端の構成を、vocaファイルから終端の種類と番号を 調べる。それらから非終端のクラス毎に構成する非終端のリストを作成し(構 成する非終端はクラスのリストへのポインタを持つ)、そのグラフ構造の開始 記号であるクラスから、left-to-rightに再帰的に他のクラスのリストへもぐ り込んで行き、終端を見つけたらFAの状態遷移をするというようにしてNFAを 作成する。次にNFA->DFAであるが、開始記号からトポロジー順にコンフリク トしているアークを融合して、その先は融合対象先の状態それぞれから出て いるアークをすべてコピーする。またその元の融合対象であるアークを消去 する。この時アークを消すことによりその融合対象先を指すアークがなくなっ たら、その状態は消滅させる。その後、三つ組リストを作成する。 v.1.01(95.12.31) +> 0 -(a)-> 1* | | | (a) +--+ というNFAからDFAに変換する時、今までは仮に新しい融合状態2を作り、融合 対象それぞれ順に、そこからの遷移を融合状態へコピーしては0からの遷移を 切って消滅判定をしていた。そしてすべて終ったら融合状態群をリストに加 える。 大抵のループではこの処理で構わないが、上記のような自己ループ上で、か つ自己ループが融合されるとき、融合の中間処理中にコピーが行なわれるた め不具合が起こる。 具体的には下の通り。 右線形のみという制約から1が先現れる。そして1からの遷移をコピーした後、 1は0からの遷移しかないから消滅する。その次、次の融合対象である0からの 遷移のコピーとなるが、現在の状態は0から0へのアークのみ存在するため、 それがコピーされる。 0 -(a)-> 2* 2 -(a)-> 0 となるわけである。 そこで0のアークの処理が完全に終っているか、まだ全く始められていない状 態の時にコピーをする必要があるのだが、アークの処理を完全に終らせてか らコピーをするようにした。具体的には融合対象の中に自分がいたら(すなわ ち自己ループ)、reservedというフラグを立てて枝を切るのみにしておく。自 分のアークの処理が完全に終ってから、reservedフラグが立っている全ての 融合状態を順に処理していく。 これにより上記の問題は解決された。 v.1.02(96.1.1) 今までは、NFA新規作成時にFAに番号を振り、DFA作成時に消滅した状態に対 しては欠番登録をした上で、3つ組作成時に欠番のない番号列に写像していた。 しかし良く考えるとNFAやDFAの作成時はノードへのポインタで処理している ので状態番号は不要である。そこでNFA作成時は状態を-1としておき、3つ組 作成時に参照されたノードに対して番号を振っていくという処理に変更した。 これによりg2faの暗黙ルールであった状態#1は受理状態という規則は守られ なくなった一方、欠番処理が不要になった分、最も処理が遅かった3つ組作成 が大分速くなった。 v.1.03(96.1.1) 今まで3つ組の探索順序を深さ優先で行なっていたため、3つ組を作成する時 はバッファを用意して、ノードに立ち寄るたびに実体コピーをして適正位置 に挿入(すなわちソート)していた。そこでキューを用意して幅優先探索にし た。これだとソートを行なわなくてもそのまま出力するだけで良い。この結 果g1の処理において、3つ組作成処理は、v.1.02では全体の時間の94%占めて いたのに対して、v.1.03では0.5%に下がった。またこの結果今までg2faより 3倍以上遅かったのが、4倍以上速くなった(適正位置への挿入はデータベース におけるインデックスファイルみたいなことをしていて結構大変だったのに…)。 次に浮上してきた律速段階は18%を占めるappendNextArcだ。その他、画面表 示での改行問題などを解決した。 v.1.04(96.1.2) パーザはscanfを使ってDFAファイルを読み込んでいるので第4フィールドの0x という文字列を出力しないように変更した。またテストのためg2faと互換の 出力が出来るオプションを新設した。この出力ファイルでパージングした結 果、オリジナルのDFAの結果と全く同じになったので(ただし状態1は受理でな いのに受理とされてしまうので、その影響が偶然なかったわけだが)mkfaは正 しいDFAを出力していることが確かめられた。 v.1.10(96.1.4) yaccのソースを大幅に書き換え、文法ファイルの仕様を大きく拡張した。主 に受理フラグの設定に関するものであり、ついでにエラーチェックを強化し た。ドキュメントを整備した。技術的なこととして他のモジュールで文字配 列として定義されたものをexternでポインタとして参照したら落ちるという バグに長時間悩まされた。なぜだめなのか分からない(レベルとしては同じな のに)。またこの改変の際、今まではNFA作成時にヘッダファイルを作成して いたが、文法ファイル読み込時に行なうことにした。また未使用クラスチェッ ク時にクラス情報をすべてフリーすることにした。 v.1.11(96.1.8) 開始記号を指定する*を新設。その他、プログラムを機能毎にモジュール分け した。 v.1.11a(96.1.11) v.1.11でエンバグしていた-cの出力(第5フィールドが出力される)を訂正。 v.1.11b(96.1.11) 再帰定義の際、ループ内でのreservedフラグの立て方がおかしかったのを修 正した。 v.1.11c(96.1.11) DFAで再帰が深くなると落ちるのがstack overflowによるものと判明。再帰関 数内の文字列をstaticに変更し、ある程度深くまでの探索が可能になった。 将来的にそれでも不足ならばgccのコンパイルオプションなどで回避する必要 がある。 v.1.20(96.1.13) BNFを終端レベルまで落としてNFAを作成した後DFAを作ると状態数が爆発する ことがある。その一つとしてあるクラスの定義が同じクラスから始まる場合、 そのクラスそれぞれの終端列の解釈ごとに独立して問題解決するため、無駄 に状態数を作るということがある。このことははじめから分っていたが、最 終的に最小化すれば同じになるので気にしなかった。しかしこれが原因で96M を食い付くして落ちるということが起こったので対処することにした。 TOPレベル(文法レベル)で状態を押さえられるならば文法を書き換える処理を 行うことにした。具体的には次のパターンを考えている。 s : a b c s : a b d s : a b tmp tmp : c tmp : d しかし下のような文法の場合、イプシロン定義が現れる(すなわちラムダ遷移 を処理する必要がある)ので、それを避けるためにabortフラグを用意した。 s : a b c s : a b 具体的にはbにabortフラグを立てておき、NFA作成中に注目中のトークンに abortフラグが現れたら、現在処理中のクラスの出口FAに直接つなぐというも のである。すなわち、上で言えば、bの出口が二つ用意されたと考えて良い(c の前とcの後ろ)。 しかし現在これを行うために発生するバグが分っている。すなわち、sの出口 である"..c"に"..b"を接続するように作っているため、その出口FAでは経路 が違うのにcもdも受理することになる。これを回避するためには入り口を二 つ用意する方法が考えられる(他の回避方法も無くはない)。ちなみにクラ ス定義は文字列の配列として表現されていたのを、文字列のリストに変更し ている(楽するために配列にしていたものはこれで全滅した)。 注:これは後から考えるとアーク上に受理フラグを設けていないための仕様の バグである。逆に言えばアーク上にフラグを乗せれば問題は解決する。 v.1.21(96.1.13) DFAが完全にDFAになっていないバグが前から確認されていた。この原因は、 NFAからDFAに変換する際、どの遷移元と遷移先でアークを指定するようになっ ていたため、例えばAからBへa,bの入力で遷移する場合区別が付かなかったた め、不定の結果となっていたことである。また後ろ向き(前状態へ)のアーク は実は不要で、本数のみ登録すれば良いことに今頃気付いたので、その修正 を同時に行った。これにより、手元にある文法ファイルは完全なDFAファイル を出力するようになり、また高速化、プログラムの簡潔化が実現された。ま た以前はこれが原因で状態爆発していたようで、これによって状態がある程 度抑制されるようになった。 v.1.22(96.1.15) NFAからDFAへの変換において入力コンフリクトを解決する際に、問題となる 入力の遷移先が全く同じである場合、別々に新規の状態を作るのではなく、 同じ状態へ遷移するようにした。例えばつぎの場合、 0 -(a,b)->1 +--(a,b)->2 の場合aもbも1,2へ遷移するので、 0-(a,b)->(1,2) とする。今までは、 0 -a->(1,2) +--b->(1,2') としていた。(1,2)も(1,2')も全く同じであるが、実体を二つ持っていたこと になる。 言い換えればこの処理は、v.1.20でグラマレベルの融合をしていたのを終端 のレベルで行ったと言える。すなわち(a,b)という入力を擬似的に一つの入力 (トークン)と見るわけである。このためにグラマレベルでの融合は無くても 同じ結果となるわけだが、やはりなるべく早期に融合を行っていくことで処 理が早くなる利点があることは確かである(だって処理効率で言うならこの処 理も最後に最小化を行うとしたら結果は同じなので不要となってしまうから)。 またv.1.21までは、 A : a A : a A (ただしaは終端) という文法を無限ループするものとしてはねるバグがあったのを修正した。 v.1.30(96.1.15) 今までは、DFAの作成のアルゴリズム自体を勘違いしていて、ある場所での例 えば0と1の融合状態と、別の場所での0と1を融合状態は別物として扱ってい た。これにより下記の文法では無限に状態を作成することが確認されていた。 S : A S : B A : C D B : C D C : a C : b D : c D : c D そこで融合状態辞書を、ローカルなものからグローバルに変えたら(ちょっと の変更で済んだ)、何と涙が出るほど状態数は減り(NFAよりDFAの方が状態数 が少なくなる!)、上記文法もコンパイルできるようになった。 v.1.31(96.1.16) v.1.30よりFAの総数とFAの処理数が最終的に一致しなくなった。これは複合 的な原因を持っていて、次の通りである。 ・DFA変換の際、新しい非終端に入る度に経過表示していたが、最後全てが終 わったあとに表示をしていないために、最後の処理が表示に反映されてい なかった。 ・ループとアボートが同時に起こったときのNFAの処理がおかしかった。具体 的には、DFA処理関数への引数を逆にしたら解決された。 ・孤立ループ島ができてしまうため、だれからも指されていなければ消去す るというノード消去判定にかからなかった(ただしこれは出力結果に支障を 来たさない。単に不要となったノードをfreeできないだけである) 上2つは原因が分った時点ですぐに直せたが、3つめは構造的に難しかった。 アークを切断するときにこの状態に落ちるかをチェックする関数を作ったの だが(指されているアークが一つになったなら、そのノードが消滅すると仮定 して自分にその影響が返ってくるかとすればよい)、これを用いると、状態融 合処理過程などに一旦この状態に陥ることがあり、このチェックにかかるた めに消滅すべきでないノードまでが消去される場合があるのである(これに気 付くのにもたいへん時間がかかった)。そこで作業中のノードに対して volatiled属性を立て消去不能と見なすことによって解決を試みたところ、帳 じりの合わない文法ファイル(loop_recurse2など)は合うようになったが、g1 などではチェック関数の中でBusErrorをどうしても起こしてしまう。という ことでこの件に関しては1日頑張ってだめだったので保留とすることにした。 またv.1.30では状態融合において、すでに存在する融合状態へのリンクの処 理をエンバグさせていたので、これを修正した。 v.1.32(96.1.16) v.1.20で文法書き換えを行うようになってから今まで、DFA変換において abortFAとexitFAを等価に扱っていなかった。そのため、abortFAがちゃんと 接続されないという現象が起きていた。そこで変換の再帰関数が呼ばれたと き、exitFAがNULLならabortFAを見て、入っているならその値をexitFAへ移す というようにしたところ正常動作した。これにともない、{exitFA,abortFA} を{exitFA1,exitFA2}と名称変更した。 v.1.33(96.1.17) v.1.30から『涙が出るほど』状態数が少なくなったが、少し問題があった。 それは普通のNFA->DFA変換と同じように融合された元の状態要素が同じであ れば同じ状態とするというアルゴリズムだったが、経路によって受理される クラスが違うので、受理(開始)フラグが同じであるときのみ許されるとしな ければならない。その変更をした。しかし恐れていたほど状態が膨らむとい うことはなかった。 v.1.34(96.1.18) ループする時、その先のノードへ受理フラグを立てるのを忘れていたのを直 した。また状態を減らすための文法書き換え時にできる状態の名前を# から#に変更した。文法チェック時のエラーメッセー ジに含まれる可能性があり、その場合分かりにくいからである。 v.1.35(96.1.19) v.1.31でループとアボートを同じと捕らえたが、それは間違いだった。それ らは別物で、再帰は正式の出口と等価であり、置き換わるものである。また アボートは子供に次々継承されていくため蓄積していくものなので、リスト で扱うよう変更された。今までは孫にアボートが継承されていなかったこと になる。このリストの使い方は普通のオート変数とは異なるため注意が必要。 親のリストはそのまま子供に渡され、子供はそれを冒頭でコピーして使用す るとなっているので引数としてもらったリストはfreeしてはならない。普通 のオート変数と同じ寿命にするためには、親がコピーして渡せば良いのだが、 3個所で子供を呼んでいるので、それぞれコピーをするのがめんどくさいのた め、このような形となった。 v.1.36(96.1.20) 今までのアルゴリズムでは、たまに永久ループする文法があった。その理由 は融合状態辞書(プログラムではGROUPと呼んでいる)を単純に構成されるFAへ のポインタとしていたからである。しかし例えば状態1と状態2が融合された 状態(1,2)とさらにそれに状態1を融合した状態(1,(1,2))は全く同じものであ る。そこで辞書に書き込むFAのポインタは融合された状態である場合はその もとの構成FAへのポインタのリストを書き込むようにした。これにより完全 にNFAのパワーセットであることが保証されるため、理論的に永久ループはな くなった。またv.1.35までは辞書内ソートの位置判定の条件がタイプミスし ていたのを直したので、それにより状態がさらに半分になった。後、今まで 融合したときフラグを付け忘れている個所があったのも修正された。 v.1.37(96.1.22) g2fa互換の場合文受理のフラグだけなので、状態融合判定のif文内でフラグ が一致しているかどうかの判定をしないとしていたつもりがうっかり間違っ ていたために-cではいつまでも新しい状態を作るとなっていたのを修正。 v.1.40(96.1.23) 仕様上のバグと考えられているフラグの仕様を変更した。すなわちノード上 に記録するのではなくアーク上に記録する。これにより、分岐それぞれでこ となるフラグを表現できるし、またループなどによるフラグの混乱もなくな る。このフラグの記録方式は、開始フラグ受理フラグそれぞれに関して指定 できる。fbsでの利用としては文受理判定をノード上のフラグで行っているた め受理フラグはノード上で行い、開始フラグは単語シーケンス上に取り込む つもりなのでアーク上に記録する予定である。 このフラグ処理の実現方法は次の通りである。 開始フラグは、NFAの再帰関数のボディの先頭毎に一旦FAの仮フラグ記録バッ ファに書き込んでおくとしておきアーク接続時に接続元のFAの仮フラグ記憶 バッファの内容をコピーしてFAの仮フラグバッファを消す方法を取る。 受理フラグに関してはさらに複雑な処理が要求される。開始フラグより難し いのは、あるクラスの最終ボディが非終端である場合複数のアークに自分の フラグを立てなければならないがどのアークかという情報をどう受け渡すか と言うことである。そこでおそらくこの問題に関しては考え方を大きく変え て自分の受理フラグを自分で付けるのではなく子孫(最終的には終端接続時) に付けさせるようにする方法が良いと思われる。その情報伝搬はexitFAを用 意するときに履歴情報内にフラグを立てることによって行えばよい。 受理フラグに関してはfbsで現在必要とされていないので先のバージョンに譲 ることにした。 v.1.41(96.2.1) 今まで末尾再帰があった場合は単純に、そのクラスの開始ノードへ接続する としていたが、これでは例えば次のような文法で本来受理すべきでない系列 も受理してしまう。 A : a A : B B : b B これだと(b)*aになってしまう。 これを避けるためにはクラスの開始ノードへ接続するのをやめて、カレント クラス以下のレベルに属する開始ノードからの遷移を記録した上で、再帰個 所に達したときには、開始ノードにつなぐのではなく新たなノード(プログラ ムではcloneFAと呼んでいる)に飛ぶようにして、そのノードからは記録して あった遷移を継承するようにするのが手っ取り早い。 この情報の記録の取り方にはいろいろ考えられるが、最もスマートと思われ る方法はNFA作成の再帰関数の履歴バッファにそのリストを組み込むことであ る。終端を実際に接続する際に履歴バッファ(自分のみでなく親のバッファも) を調べ、接続元のFAと履歴内のFAが一致した場合は、そこへ終端記号と遷移 先FAのリストに追加するとする。こうすれば例えば上記の場合、Bを処理して いる際にはBの履歴にはbのみが登録されるためaでの遷移はなくなるので、A とBとで区別されていることになる。 これにより再帰の問題は解決された。しかしリンクの構造上、DFA作成時に大 量に孤立ループができてしまうようになった。すなわちcloneFAのもとのFAが 消滅してもその先のFAはcloneFAから指されているので消滅しないわけである。 またもう一つ大きなバグフィックスがある。v.1.20以来文法書き換えのため に導入されたabortフラグの扱いがNFA処理関数の中で一カ所間違っていた。 具体的には、あるクラスのボディに非終端が現れると、そのクラスが持って いる副出口(extraFAs)を必ずそのまま渡していた。しかしそのボディ内の非 終端がボディの最後尾でなければ脱出するわけではないので渡してはだめで ある。これにより坂倉の宿泊案内の文法のDFAが正常になった。 v.1.42(96.2.1) 履歴バッファからのアークを結ぶ際の遷移先のFAのpsNumの付け方が少しおか しかったので修正した。ただDFA処理中どうせ0にならないで孤立ループになっ てしまうのであまり影響はないし問題もなかったのだが。 v.1.43(96.2.1) abortフラグによる副出口に受理フラグを付け忘れていたのを修正した(それ にしてもabortフラグがらみはバグが多いな)。またエラー関数などを可変長 関数として書き直した。 v.1.44(96.2.3) 左再帰性によって処理の永久ループを防ぐためのチェックが今まで過剰だっ たのを適切にした。またこれに伴い、そのエラーメッセージとクラスが無限 定義になるときのエラーメッセージを改善して、関与するクラスのリストを 含めるようにした。またyacc内で発覚したエラーで行がずれるもののうち、 簡単に直せるもののみ補正して表示するようにした。また今までクラスのビッ トフィールドはunsigned intとしていたが、gccのlong long型に将来的に変 更する可能性があるので、typedefで定義してそれを用いるようにした。また r_makeNFAの処理を2重ループで表現することにより若干見やすくした。また -qオプションを拡張して静的経過表示もできるようにした。 □将来の拡張 1 出来上がったDFAに最終的な状態最小化をする。状態最小化にはO(nlog(n)) で処理できるHopcroftのアルゴリズムというものがあるらしい。 1. Hopcroft の原著 J.~Hopcroft, An $n \log n$ Algorithm for Minimizing States in a Finite Automaton, Theory of Machines and Computations, Academic Press, New York, pp.189--196, 1971. 2. Hopcroft のアルゴリズムを解説した文献 D.~Gries, Describing an Algorithm by Hopcroft, Acta Informatica 2, pp.97--109, 1973. 2 状態数が大きくなると、融合FAの辞書を引くのにとても時間がかかるよ うになったのを高速化する。これにはハッシュテーブルを用いるのが最適 であろう。 3 受理フラグもエッジ上に乗せられるようにする。 4 開始記号のフラグを最下位ビットに固定する。 5 左再帰の文法を読み込み時に末尾再帰に書換えて処理可能にする。 □バグその他問題点 次の仕様上の問題点がある。 S : P P : A P : A B とあったときに、DFAでは入力ABに対してPの受理フラグはAの後でもBの後で も立つため、Pの実体が間違って判断される可能性がある。 S : P P : A P P : A の場合も同様、Aの前に開始フラグが、Aの後に必ず受理フラグが立ってしま う問題がある。 これらは経路履歴を情報としないDFAにおいて回避困難な問題である。入力を 決定的にするには融合が必要だが、融合するとフラグの区別ができなくなる からである。NFAならばBNFをそのままネットワークにした形状になっており、 違う還元経路同士が異なるノードの実体を持ったままで融合されないので、 この問題は発生しない。 また再開パージングの実現形を考えた時も、もしフレーズ音節連接で失敗地 点から再開するとしたときNFAになるのでパーザはNFAの方が都合が良い気が する。 こう考えたとき、文生成器としてのパーサにDFAを渡す必要はないような気が する(ということは最小化に対する努力は無駄だった!?)。