Lex保留字規則與查找表

Question

This網頁建議如果您的lex程序「有大量保留字，讓lex簡單匹配字符串並在您自己的代碼中確定它是否是變量或保留字。「

我的問題是：更高效的地方，爲什麼？如果這意味着編譯詞法分析器的速度更快，我並不關心這個問題，因爲它是從使用詞法分析器分析輸入的程序中刪除的。

這似乎是，lex只是用你的描述來建立一個狀態機，一次處理一個字符。似乎並不合乎邏輯的是，增加狀態機的大小必然會導致它比使用一個標識符規則更慢，然後進行幾次字符串比較。

此外，如果事實證明有一些合乎邏輯的理由使其作爲優化有意義，那麼會認爲是大量保留字？我有大約20個，而大約30個其他規則適用於各種事情。這會被視爲大量的保留字嗎？我是否應該嘗試對其他一些符號使用相同的策略？

我試圖谷歌的結果，但我發現的唯一相關文章陳述這一戰略，就好像它是衆所周知的沒有任何理由。

如果它是相關的，我使用flex 2.5.35。

編輯：Here是另一個參考，它聲稱，當被要求匹配幾個長文字串時，lex產生低效率的掃描器。它也沒有給出理由。

Answer 1

根據the flex manual的規定，「掃描儀的速度與規則的數量無關，或......規則對於諸如'*'和'|'等運算符的複雜程度。」

主要表現損失是由於回溯。這可以通過（除其他之外）使用全部規則來避免，所述規則將匹配從「開始」違規令牌的令牌。例如，如果您有一個由[a-zA-Z_]組成的保留字列表，然後是用於匹配[a-zA-Z _] [a-zA-Z_0-9] *格式標識符的規則，則匹配標識符的規則將捕獲任何以保留字的名稱開頭的標識符，而不必備份並嘗試再次匹配。

根據the faq，flex生成確定性有限自動機，它「同時並行地完成所有匹配」。如上所述，其結果是掃描儀的速度與規則的數量無關。另一方面，字符串比較在規則數量上是線性的。

因此，保留字規則實際上應該比查找錶快得多。