查找'最有效的方法'關鍵詞

好吧，我正在寫一個函數作爲詞法分析器的一部分，它查找或搜索與關鍵字匹配的內容。我的詞法分析器捕獲所有顯而易見的標記，例如單字符和多字符運算符（+ - */> < = == etc）（同時註釋和空白已被取出），因此我在將一串只包含字母數字字符（包括下劃線）的流收集到一個string ，那麼該字符串需要被匹配爲已知關鍵字或標識符。查找'最有效的方法'關鍵詞

所以我想知道如何去識別它？我知道我基本上需要將它與某些列表或數組或其他所有內置關鍵字進行比較，並且如果它匹配一個與它對應的枚舉值相匹配的返回值;否則，如果沒有匹配，那麼它必須是一個函數或變量標識符。那麼我應該如何尋找比賽？我在某處讀到，稱爲二進制搜索樹的東西是一種有效的方法，或者使用哈希表，問題是我從未使用過，因此我不確定它是否是正確的方式。我可以使用MySQL數據庫嗎？

來源

2010-09-21 Dooms101

http://stackoverflow.com/questions/479919/searching-fast-through -a-sorted-list-of-strings-in-c可能對你有幫助 – vrdhn 2010-09-21 04:21:46

使用MySQL在C++中進行關鍵字查找就像調用一個Web服務來執行兩個整數的加法一樣。 – pascal 2010-09-21 04:22:24

如果您的關鍵字集是固定的，則可以爲O（1）查找構建perfect hash。檢查出gperf或cmph。

來源

2010-09-21 04:26:15 ergosys

您仍然會與非關鍵字產生散列衝突，所以我不認爲這比其他方法更有效。這也不是O（1），真正的複雜性不取決於關鍵字的數量，但它取決於每個關鍵字的長度。 – 2010-09-21 04:41:16

查找後的驗證是字符串比較，但這不可能是性能的重要因素。由於哈希值是完美的，因此不存在哈希衝突懲罰，輸入或者匹配哈希槽或者不匹配，不需要額外的搜索。 – ergosys 2010-09-21 04:56:02

完美的散列函數實際上對編譯器詞法分析器來說並不有用;計算單個散列並將其用於各種範圍散列表中的關鍵字查找和符號查找會更好。通過增加關鍵字散列表的大小，您可以便宜地保證沒有關鍵字查找的衝突，甚至更好的是在添加其他任何內容之前將關鍵字添加到全局散列表中，因此只需要一次查找就可以解析關鍵字和符號。或者考慮在一個全局哈希表中實施所有的idents（包括關鍵字），以便編譯器中其他地方的超便宜的指針比較。 – 2013-09-18 17:05:28

A "trie"肯定是最有效的方法。

來源

2010-09-21 04:21:39

不管你使用的是std::map，你可能已經足夠了。

來源

2010-09-21 05:16:59

或者'std :: tr1 :: unordered_map'，如果你的編譯器支持它，最新的VC++和GCC都可以。 :) – 2010-09-21 05:42:21

對於單字符關鍵字查找表將是完美的。對於多字符（特別是如果長度不同）：一個哈希表。如果您需要性能，您甚至可以使用源代碼生成來創建哈希表（使用簡單的哈希函數，根據您的語法，能夠或不能忽略大小寫）。

所以我會用一個LUT和一個哈希表來實現它：首先用LUT檢查第一個字符（如果它是一個簡單的運算符，它將以非字母數字值開始），並且if未找到，請檢查哈希表。

來源

2010-09-21 06:22:08 ruslik

這是針對一種語言，具有永不改變的特定關鍵字集合，而且它們並不是很多？

如果是這樣，它可能無所謂你使用。你會有更大的魚來炒。

然而，由於該表不發生變化，這將是很難被擊敗這樣的硬編碼搜索：

// 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-21 20:58:06

查找'最有效的方法'關鍵詞

回答

相關問題