3

さて、私は字句解析器の一部として、キーワードとの一致を「検索」または検索する関数を作成しています。私のレクサーは、単一文字および複数文字の演算子（+ - * / > < = == etc）などのすべての明白なトークンをキャッチします（コメントと空白もすでに削除されています）ので、英数字（アンダースコアを含む）のみのストリームを収集した後、関数を呼び出しますstring。次に、文字列は既知のキーワードまたは識別子として一致する必要があります。

それで、私はそれをどのように特定するのか疑問に思いましたか？基本的に、リストや配列、またはすべての組み込みキーワードの何かと比較する必要があることを知っています。それが1つのリターンに一致する場合は、対応する列挙値に一致します。それ以外の場合、一致するものがない場合は、関数または変数の識別子である必要があります。では、どのように一致を探す必要がありますか？二分探索木と呼ばれるものがそれを行うための効率的な方法であるか、ハッシュテーブルを使用することによってどこかで読んだことがあります。問題は私も一度も使用したことがないので、それが正しい方法かどうかわかりません。MySQLデータベースを使用できますか？

4

5 に答える 5

4

キーワードのセットが固定されている場合、O（1）ルックアップ用の完全なハッシュを構築できます。gperfまたはcmphを確認してください。

于 2010-09-21T04:26:15.753 に答える
2

std :: mapの実装が何であれ、おそらく十分でしょう。

于 2010-09-21T05:16:59.760 に答える
2

これは、決して変わらない特定のキーワードのセットを備えた言語用であり、それらの数はそれほど多くありませんか？

もしそうなら、それはおそらくあなたが何を使うかは問題ではありません。あなたは揚げるより大きな魚を持っているでしょう。

ただし、リストは変更されないため、次のようなハードコードされた検索に勝るものはありません。

// search on first letter
switch(s[0]){
  case 'a':
    // search on 2nd letter, etc.
    break;
  case 'b':
    // search on 2nd letter, etc.
    break;
  ........
  case '_':
    // search on 2nd letter, etc.
    break;
}
于 2010-09-21T20:58:06.340 に答える
1

「トライ」は確かに最も効率的な方法です。

于 2010-09-21T04:21:39.300 に答える
0

単一の文字キーワードの場合、ルックアップテーブルが最適です。複数文字の場合（特に長さが異なる場合）：ハッシュテーブル。パフォーマンスが必要な場合は、ソースコード生成を使用してハッシュテーブルを作成することもできます（構文に応じて、大文字と小文字を無視できる、または無視できない単純なハッシュ関数を使用します）。

したがって、LUTとハッシュテーブルを使用して実装します。最初に、LUTを使用して最初の文字をチェックし（単純な演算子の場合は、英数字以外の値で開始します）、見つからない場合はチェックします。ハッシュテーブル。

于 2010-09-21T06:22:08.857 に答える