シーケンス処理または解析のための優先言語/技術

Question

私は過去に数回同様の問題を抱えていて、類似の問題を解決するためにどの言語（方法論）が使用されているかを知りたい（私はJ2EE/Java開発者です） ：

問題：考えられるルールのセット（言葉はAとXの組み合わせで、常にXで始まり、各単語はスペースで区切られていると言います）では、単語のシーケンスを読み込み、入力を解析して、どの単語が構文的に正しいかを判断する。要するに、これらは構文解析技術を伴う問題です。 Javaの自動販売機のロジックをシミュレートします。

私が知りたいことは、入力を解析することに関連する問題を解決するための技術/最良のアプローチは何かを知りたいと思います。 Googleのコードのジャムで外国人の言語処理問題

Google code jam problem

のように、我々はJavaでANTLRのようなものや、いくつかのライブラリを使用しています。

私はこの質問が少し一般的だと知っていますが、それを表現する他の方法はありませんでした。

P.S：私は解決策が欲しくない、私はそのような繰り返し問題を解決する最善の方法を探している。

Answer 1

JavaCCを複雑な解析に使用できます。

比較的簡単な解析とイベント処理のために、私はenumを状態マシンとして使用します。 espをプッシュパーサーとして使用します。非常に簡単な構文解析のために

、あなたはイコール、スイッチまたはのstartsWith

Answer 2

でのindexOfまたはスプリット（」「）を使用することができますが、基本的に有限状態の自動化である何かのロジックをシミュレートしたい場合は、単純にすることができます手でFSAをコード化する。これは標準的なコンピュータサイエンスソリューションです。あまり分かりにくい方法は、イベントの有効なシーケンスの記述からFSAを生成するためにレクサージェネレータを使用することです（レクサージェネレータではこれらを「文字」と呼びますが、文字の代用イベントの発生）。

マッチングに関する複雑な再帰的なルールがある場合は、より伝統的なパーサが必要です。 文法が複雑でない場合は、これらを手作業でコーディングすることもできます。私の?SO answer on "how to build a recursive descent parser"を見てください。あなたの文法が複雑であるか、あるいは素早く変化するならば、標準のパーサージェネレータを使いたいでしょう。他の答えは、特定のものを示唆していますが、選ぶべきものがたくさんあります。

[FWIW、私はパーサージェネレータを、TRW POS端末のMay Company社の百貨店で1974年に有効なトランザクションシーケンスを認識するために適用しました。

Answer 3

あなたはANTLRを使うことができますが、それは複雑な問題に役立ちますが、正規表現を使用することもできます：spilled（ "\\ s +"）。