有限状態マシンパーサー

Question

FSMのようなパーサーで自己設計されたファイル形式を解析したい C ++で （これは teach-myself-c++-the-hard-way-by-doing-something-big-and-difficult プロジェクトの種類:)）。 euh ... lineの終わりを意味するニューラインを含むトークン化された文字列があります。見る 入力例については、こちら. 。すべてのコメントとジャンクは除外されているので、私はこのようなstd ::文字列を持っています：

global \n { \n SOURCE_DIRS src \n HEADER_DIRS include \n SOURCES bitwise.c framing.c \n HEADERS ogg/os_types.h ogg/ogg.h \n } \n ...

構文の説明：

• {}はスコープであり、大文字の単語は、オプション/ファイルのリストが従うことを意味します。
• nは、オプション/ファイルのリストでのみ重要であり、リストの最後を示します。

だから私は、FSMは私のニーズ/知識のために十分に単純/拡張可能だと思った。私が伝えることができる限り（そして私のファイルのデザインを望んでいます）、私は同時の状態やそのような派手なものを必要としません。いくつかの設計/実装の質問：

1. 使用する必要があります enum または要約 class +私の州の派生物？ 1つ目はおそらく小さな構文の方が良いですが、後で醜くなる可能性があり、2つ目は正反対です。私はそのシンプルさのために、最初に傾いています。 enum 例 と クラスの例. 。編集：どうですか この提案 にとって goto, 、私は彼らがC ++で悪だと思ったのですか？
2. リストを読むとき、私は無視する必要がありません \n. 。使用する私の好みの方法 string 経由 stringstream, 、無視します \n デフォルトで。だから私は簡単な伝える方法が必要です（同じ！） stringstream 特定の状態が有効になっている場合、ニューラインを無視しないこと。
3. シンプルになります enum マルチレベルの解析には状態で十分です（スコープ内のスコープ {...{...}...}）それともハッキーな実装が必要ですか？
4. これが私が念頭に置いているドラフト状態です：
   • upper: ：グローバル、exe、lib+ターゲット名を読み取ります...
   • normal: ：スコープ内で、ソースを読むことができます...、ユーザー変数を作成します...
   • list: ：新しいラインに遭遇するまで、アイテムをリストに追加します。

各スコープには、一種の条件付き（win32：global {gcc：cflags = ...}）があり、まったく同じファッションで（どこでも）処理する必要があります。 list 状態、アイテムごと）。

ご意見をお寄せいただきありがとうございます。

Answer 1

ネストスコープがある場合、有限状態マシンは いいえ 適切な方法で、コンテキスト無料の文法パーサーを見る必要があります。 an LL（1）パーサー 再帰的なファンシトンのセットとして書くことができます。 lalr（1）パーサー Bisonなどのパーサージェネレーターを使用して書くことができます。

FSMにスタックを追加すると、 プッシュダウンオートマトン 地域。非決定的プッシュダウンオートマトンは、コンテキストフリーの文法と同等です（ただし 決定論的プッシュダウンオートマトン 厳密には強力ではありません。）LALR（1）パーサージェネレーターは、実際に決定論的なプッシュダウンオートマトンを内部で生成します。優れたコンパイラデザインの教科書は、プッシュダウンオートマトンが文法から構築される正確なアルゴリズムをカバーします。 （このように、スタックを追加することは「ハッキー」ではありません。） このウィキペディアの記事 また、文法からLR（1）プッシュダウンオートマトンを構築する方法についても説明していますが、IMO、この記事は可能な限り明確ではありません。

あなたのスコープの巣の巣が有限にしか深くない場合（つまり、あなたは持っています upper, normal と list レベルですが、あなたはネストされていません listsまたはネスト normals）、スタックなしでFSMを使用できます。

Answer 2

解析用のテキスト入力ストリームを分析する2つの段階があります。

語彙分析： これは、入力ストリームが語彙ユニットに分割される場所です。一連の文字を見て、トークンを生成します（話し言葉や書かれた言語では単語に類似しています）。有限状態マシンは、語彙構造について良い設計上の決定を下した場合、語彙分析に非常に優れています。上記のデータから、個々の語彙素は、キーワード（「グローバル」）、識別子（「ビットワイズ」、「ソース」など）、シンボリックトークン（「 "" "}"、 "、"、 "/"など）のようなものになります。 ）、数値、エスケープ値（「 n」など）など。

構文 /文法分析： トークンのシーケンスを生成すると（またはそうしている間）、構造を分析して、トークンのシーケンスが言語デザインと一致しているかどうかを判断できる必要があります。言語構造がそれほど複雑でない場合は、代わりに有限状態マシンでそれを行うことができるかもしれませんが、通常、これには何らかのパーサーが必要です。一般的に（そして、特にあなたのケースではネスト構造が必要なので）、Ken Bloomが説明するテクニックの1つを使用する必要があります。

だからあなたの質問に応えて：

状態には列挙または抽象クラス +デリバティブを使用する必要がありますか？

小さなトークンザーの場合、状態 /遷移値のマトリックスが適切であり、 next_state = state_transitions[current_state][current_input_char]. 。この場合、 next_state と current_state いくつかの整数タイプ（列挙されたタイプを含む）です。無効な状態に移行すると、入力エラーが検出されます。トークンの終わりは、次の入力文字が与えられた別の状態に利用可能な有効な遷移がない有効なエンドステートの状態識別に基づいて識別されます。スペースが心配な場合は、代わりにマップのベクトルを使用できます。州のクラスを作ることは可能ですが、それはおそらくあなたが必要とするよりも難しいものをもっと難しくしていると思います。

リストを読むときは、 nを無視する必要はありません。

「 n」と呼ばれるトークンを作成するか、より一般化するエスケープトークン（バックスラッシュの前に識別子があります。ソース内のラインブレークの識別について話している場合、それらは単にトランジションを作成する必要がある文字です状態遷移マトリックスでは（UNIXラインの破損とWindowsラインの破損の違いに注意してください。どちらでも動作するFSMを作成できます）。

単純な列挙状態は、マルチレベルの解析に十分であるでしょうか（スコープ内のスコープ{... {...} ...}）、またはハッキーな実装が必要ですか？

ここでは、ネストが特定のレベルを超えないことを保証できない限り、文法またはプッシュダウンオートマトンが必要になります。それでも、FSMが非常に複雑になる可能性があります。

これが私が念頭に置いているドラフト州です：...

上記の語彙分析と文法分析に関する私のコメントを参照してください。

Answer 3

解析のために、私は常にすでに動作することが証明されているものを使用しようとします： antlr と antlrworks これは、文法を設計およびテストするのに非常に役立ちます。 c/c ++のコードを生成できます（および 他の言語）しかし、それらの言語のANTLRランタイムを構築する必要があります。

もちろん見つけたら フレックス また バイソン 使いやすい（それらを使用することもできます（CとC ++のみを生成することはわかっていますが、しばらく使用しなかったので間違っている可能性があります）。