私はコンパイラを書くのがまったく初めてです。だから私は現在プロジェクトを開始しています（Javaでコーディングされています）。コーディングする前に、字句解析の部分についてもっと知りたいです。Web で調べたところ、ほとんどがトークナイザーを使用していることがわかりました。
このプロジェクトでは、それら (トークナイザー) を使用せず、代わりに有限状態オートマトンを使用する必要があります。混乱しています。リンクされたリストを使用して実装する必要がありますか? または単純な入れ子になった switch ケースで十分です。私は有限オートマトンの実装にあまり詳しくありませんが、利点は何ですか?
トークナイザーの人工的な禁止を考えると、これは割り当てであると思います。
「有限状態オートマトンを用いた字句解析」はグーグルマッチが多いです。これらは何が欠けていますか？
字句解析に有限状態オートマトンを使用する方法を理解するのに問題がありますか? それとも自分でオートマトンを書いていますか？それらが有限状態マシン（FSM）としても知られていることを知っておくと役立つ場合があります
トークナイザーはその内部で FSM を使用する可能性があるため、トークナイザーではなく FSM を使用する必要があると言う理由がわかりません。これは、自分で作成したトークナイザーを使用できず、自分で作成する必要があるという意味ですか
正規表現マッチャーの実装も通常は有限状態マシンであるため、これは考慮すべき領域である可能性があります。
lex (およびその最近の関連flex ) は、ソースが利用可能な字句解析器です。あなたはアイデアのためにそれらを見ることができます
Russ Cox による正規表現マッチングはシンプルかつ高速であり、有限ステート マシンを使用した認識エンジンの構築に関する優れた入門書です。彼は、正規表現から非決定論的有限オートマトン、さらに決定論的有限オートマトンへと移行する方法を示しています。彼の参照実装では、有向グラフ(連結リストに似ていますが、各ノードは複数の「アウト」参照を持つことができ、それ自体を含む他のノードを参照することができます) と連結リストを使用します。ステート マシンをモデル化する方法は他にもあります。
いくつかのレコグナイザーを組み合わせてレクサー/スキャナーを構築します。たとえば、正規表現で定義された次のトークンを持つ代入のみの言語を想像してください。
入力を左から右にスキャンしながら、現在のシンボルに基づいて各トークンのマシンの遷移を移動します。シンボルに有効な遷移がない場合は、受け入れ状態にある最後のマシンを選択します。その状態までスキャンされたすべてのシンボルは、トークンの一部です。スキャンは、最後に受け入れられたシンボルの後のシンボルから再開されます。新しいトークンの有効な遷移がない場合、入力は無効であり、レクサーはエラーを報告する必要があります。受け入れ状態のマシンが複数ある場合は、優先ルールによって、使用するトークンを決定する必要があります。
注: これらの手順は、可能な限り最長の一致を常に返すレクサーについて説明しています。マシンの 1 つが受け入れ状態になるとすぐにトークンを返すレクサーを設計することもできます。
サンプル入力の結果:
字句解析は単にトークンを返すことに注意してください。トークンが適切に使用されているかどうかはわかりません。「25=xyz」は意味をなさないかもしれませんが、解析段階まで待たなければなりません。
追加のリソースとして、Dick Grune はParsing Techniques - A Practical Guide の初版をPostscript および Pdf として提供しています。