哪一個是關鍵字，哪個是關鍵字散列表的項目？

Question

我需要實現一個詞法分析器，我需要一個數據結構來保存關鍵字。 我被建議使用散列表來保持關鍵字，一個建議是使用C＃哈希表格形式System.Collections。但我有一個問題：使用這個散列表我需要一個鍵和一個項目。我只有關鍵字。我應該使用關鍵字作爲關鍵字還是作爲項目，還是作爲兩者？ 由於關鍵字不同，我可以使用其他數據結構，例如二叉樹？ 我的真正興趣是：編譯器如何實現這個問題？

Answer 1

一般來說，關鍵字只有語法值，所以在大多數編譯器中，它們只用於選擇合適的語法規則。他們的「價值」就這樣立即消耗掉了。由於他們的身份是唯一有用的信息，因此使用HashSet比HashMap更合適。

但是，可能有一組關鍵字在語法上是相同的，形成了實際上枚舉類型。在這種情況下，枚舉值可能是與關鍵字關聯的值。

對於手工構建的詞法分析器，使用哈希集或其他類似的數據結構可能很簡單，但大多數編譯器實際上會將關鍵字和其他詞法記號模式一起編譯爲有限狀態自動機。這允許在詞法掃描期間識別關鍵字，而不需要任何外部數據結構。

無論如何，在幾乎所有語言中，關鍵字集都是固定的，因此使用編譯到詞法掃描程序的高效數據結構是最合適的。例如，代替二叉樹，使用可以二進制搜索的排序後的靜態字符串是合理的。或者，可以使用預建的系統;這幾乎等同於上面提到的有限狀態自動機。