接受正則表達式並生成NFA（Java）

Question

我正在嘗試編寫一個程序，該程序將接受描述正則表達式的字符串。例如：

10(0U1)* 

當U是聯合運營商和*是克林星（我們也看到隱含的連接）。

我考慮將字符串的原子標記化並根據運算符和操作數構造機器。我想用與以下規則相似的算法對每個原子進行操作：http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

我不知道如何以智能方式最好地解析這種類型的輸入，以便可以通過編程方式構造NFA。

我的程序的目標是接受上述輸入並輸出相應的NFA，它將通過其5-touple來描述。任何有關達成這一目標的建議非常感謝。

Answer 1

如果您可以使用外部庫，那麼最好使用現代解析器生成器（例如ANTLR）執行所有解析工作，併爲您的正則表達式提供一個抽象語法樹，即使它是一種相對簡單的語言。否則，如果您需要從頭開始編寫它，您需要首先弄清楚是否需要標記器（或「詞法分析器」）。如果你的語言是由一個字符標記構成的（如你的例子），那麼你可以安全地跳過寫一個標記器，只是循環字符串中的字符。然後你必須編寫解析器，這是一個掃描記號列表並構建語法樹的大循環。

在你應該結束了一個語法樹尚且如此，對於你的例子10(0U1)*任何情況下：

注意的是，在語法樹中的所有括號和隱含的優先規則都消失了，它們被替換由樹的結構。

之後，您必須遞歸地將樹轉換爲NFA圖。

下面是的一個粗略草圖繼續進行的一種可能方式。

爲每種語法節點類型編寫一種翻譯方法。該方法將以其開始和結束NFA狀態作爲參數進行調用，後者是可選的。該方法會得出自己的一片圖形，調用它的孩子適當的翻譯方法，並返回它的結束狀態（這可以作爲一個參數被省略了，因此未知其調用程序。）

• 創建一個起始狀態，併爲語法樹的根節點調用翻譯方法，將起始狀態作爲起始狀態傳遞。
• 一個文字語法節點（0，在你的例子1）將利用其初始狀態的箭頭，其截止狀態，創造一個新的結局狀態，如果沒有提供：
  
• 星形節點將調用其子節點的翻譯方法將其自身的起始狀態作爲子節點的起始和結束狀態（以便NFA將能夠根據需要多次「遍歷」該狀態。）
• 一個CONCAT節點將調用的第一個孩子，給它它的起始狀態，但沒有結束的狀態;那麼它會調用第二個孩子，將第一個孩子的結束狀態作爲開始狀態;等等，建立​​一個單向的子圖序列，每個孩子一個。

你應該明白我的意思。

你已經建立了NFA圖形作爲狀態的鏈接結構之後（也許顯示它作爲一個實際的圖形，用於調試或文檔目的），你可以把它翻譯成正式的元組和輸出。