如何編寫一個詞法分析器，其標識符可以以關鍵字開頭？

Question

假設您有一種語言，其標識符可能以關鍵字開頭。例如，假設「case」是關鍵字，但「caser」是有效的標識符。假設詞法分析器規則只能處理正則表達式。然後，似乎我不能將關鍵字規則放在詞法分析器中的標識符規則之前，因爲這會將「caser」解析爲「case」，後跟「r」。由於標識符規則與關鍵字匹配，並且關鍵字規則永遠不會觸發，所以我也不能在關鍵字規則之後放置關鍵字規則。

因此，我可以在詞法分析器中制定keyword_or_identifier規則，並讓解析器確定keyword_or_identifier是關鍵字還是標識符。這是通常完成的嗎？

我意識到「使用具有前瞻性的不同詞法分析器」是一種答案（類型），但我也對如何在傳統的基於DFA的詞法分析器中完成這項工作感興趣，因爲我目前的詞法分析器似乎工作正常那樣。

Answer 1

大多數詞法分析器，從原來的lex，比賽方案如下：

1. 使用最長匹配。

2. 如果有兩個或更多的替代項匹配最長匹配，請使用詞法分析器定義中的第一個替代項。

這使得以下樣式：

"case"     { return CASE; } 
[[:alpha:]][[:alnum:]]* { return ID; } 

如果輸入模式是caser，然後將使用第二個選擇，因爲它是最長的匹配。如果輸入模式爲case r，那麼將使用第一個替代方案，因爲它們都匹配case，並且通過上面的規則（2），第一個贏得勝利。

雖然這看起來有些武斷，但主要與DFA方法保持一致。首先，DFA在第一次達到接受狀態時不會停止。如果確實如此，那麼諸如[[:alpha:]][[:alnum:]]*這樣的模式將是無用的，因爲它們在第一個字符（假設它是字母）上進入接受狀態。相反，基於DFA的詞法分析器將繼續執行，直到從當前狀態出現不可能的轉換，然後再備份直到最後接受狀態。 （請參閱下面的內容。）

由於兩種不同的規則，給定的DFA狀態可能會接受，但這也不是問題;只記錄第一個接受規則。公平地說，這與DFA的數學模型稍有不同，DFA的數學模型在每個狀態下對每個符號都有一個過渡（儘管它們中的許多可能會過渡到「下沉」狀態），並且與DFA完成輸入，取決於讀取輸入的最後一個符號時自動機是否處於接收狀態。詞法分析模型略有不同，但也可以很容易地形式化。

理論模型中唯一的困難是「回到最後接受狀態」。在實踐中，這通常是在每次達到接受狀態時記住狀態和輸入位置來完成的。這確實意味着可能需要倒回輸入流，可能是任意數量。

大多數語言不需要經常備份，而且很少需要無限期備份。如果沒有備份狀態，某些詞法分析器可以生成更快的代碼。（如果你使用-Cf或-CFflex會做到這一點。）

導致無限期備份一個常見的情況是未能提供對字符串文字的適當的錯誤返回：

["][^"\n]*["] { return STRING; } 
/* ... */ 
.    { return INVALID; } 

這裏，第一圖案會如果在同一行上有匹配的"，則匹配以"開頭的字符串文字。 （爲簡單起見，我省略了\ -escapes。）如果字符串文字未終止，則最後的模式將匹配，但輸入將需要倒回至"。在大多數情況下，通過忽略無與倫比的"來繼續詞法分析是毫無意義的;只需忽略整條線的其餘部分就會更有意義。因此，不僅備份效率低下，還可能導致虛假錯誤消息的大量增加。一個更好的解決方案可能是：

["][^"\n]*["] { return STRING; } 
["][^"\n]*  { return INVALID_STRING; } 

這裏，如果字符串是無端接第二個選擇，只能成功，因爲如果字符串被終止，第一種選擇將匹配一個或多個字符。因此，這些替代方案出現的順序並不重要，儘管我認識的每個人都會按照我所做的順序進行排列。