在執行lex時將多個正則表達式轉換爲DFA

Question

我正在學習根據正式表達式編寫一個詞法分析生成器（lex的克隆），以便根據「Dragon Book」中描述的DFA直接轉換算法。

現在我可以成功地轉換正則表達式DFA，但我被困在有多個規則，例如：

abc { printf("abc"); } 
a* { printf("a*); } 

我可以轉換abc和a*兩個DFA圖形，而是如何combile這兩個DFA圖只有一個？

Answer 1

幾年前，我實際上做了這個練習 - 我用C++編寫了一本集成的詞法分析器和LALR解析器，並以此書爲指導。這本書實際上告訴你如何直接將正則表達式轉換爲NFA，然後使用算法將NFA轉換爲DFA，我不記得現在的名稱。要支持多個規則，您只需爲每個規則創建一個NFA。然後，您創建一個新的開始狀態，並從您的開始狀態創建一個從每個規則創建的每個NFA的開始狀態的epsilon轉換。至少，這就是我不記得我的代碼就能記住的事情。