字句解析ツールのリテラル抽出ポリシー

Question

私はC言語のような字句解析ツールを構築しました。例えば、この入力を与えると次の結果が得られます。上記の例では

入力

int i = 0 ; int j = i + 3; 

出力

int KEYWORD 
i  IDENTIFIER 
=  OPERATOR 
;  PUNCTUATION 
int KEYWORD 
j  IDENTIFIER 
=  OPERATOR 
i  IDENTIFIER 
+  OPERATOR 
3  INTEGER_CONSTANT 
;  PUNCTUATION 

あなたは、与えられた入力を気づいているかもしれませんが、私はそれにそれが失敗した下のようなものを与えるとき、文法的に正しかったです。

私が唯一の目的（私はそれが正しい用語であるかどうかを知りません、リテラルそれらを呼び出す）ことができ、小さな部分に上記の文字列を破るためにあるクラスを作った

int i = "1.2.2222.+\<++++ 

入力正規表現とマッチするか、DFAで検証されます。

+のようなあいまいな状況で問題が発生します。+は、加算演算子、または今後登場する整数リテラルの一部、またはインクリメント演算子の一部でもかまいません。私の先生の要求は次の段落で説明されています。

+が+の前にある場合は、インクリメント演算子として処理する必要があります。簡単な言葉で、プログラムはすべての可能性を探してベストを選択しようとする必要があります。つまり、プログラムに有効な入力がある場合、何らかの無効な入力が再び有効な入力となり、無効な入力で停止してはならず、正しいリテラルが見つかることを意味します。私には反対だが、私のために。私の主張は、プログラム文字列が特定のインデックスで無効になった場合、システムがエラーチェックをしていないため処理を停止する必要があるということです。

私は複雑な（私にとっては）ネストされたif else構造を使ってすべての可能性をコード化しようとしましたが、部分的な成功を収めました。あなたのお陰で、よりシンプルで洗練されたソリューションを提案できますか？ステートマシンにこの問題を構造化することも考えましたが、パターンマッチングのためにyesまたはnoと答えるDFA以外のステートマシンを実装することはなかったので、私はあまり確信していません。

これは宿題に関する質問ですが、私はちょうどコードを求めていません。

Answer 1

字句解析の通常の手法は、"maximal munch"アルゴリズムを使用することです。入力ストリームは、単一のトークンである可能性のある最長プレフィックスを繰り返し取ることによってトークンに分割されます。 1つのアルゴリズムについては、this answerを参照してください。

（<::は通常、<に::をレクサー処理され、例えば、C++で）このルールに例外を作るために時折必要であるが、全体的に、最大のムンクのルールは、より重要なのは、読むために実装するのは簡単です。