編譯原理中的正則表達式、NFA和DFA

這點知識，貌似也是編譯原理課程的一個考點…………

（直接從正則表達式構造DFA的）

正則表達式，接觸得已經不少，各種語言都會有些正則表達式的庫來增強字符串處理功能，這裡就編譯原理的詞法分析要用到的內容淺析下下。

嗯，我很懶……還是課件截圖：

這裡用遞歸定義來定義正則的，原因是簡潔方便，方便以後進一步學習，比如NFA。如果要說正則表達式的術語定義，又得找維基了，鏈接%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F

“在計算機科學中，是指一個用來描述或者匹配一系列符合某個句法規則的字符串的單個字符串”

簡單點講，就是用一種方便點的表達式來描述一個復雜的語言。

舉個例子：a(a|b)*b這個正則表達式表示的意義就是a開頭，b結尾的，由a和b構成的字符串的集合。

NFA，Nondeterministic Finite Automata，不確定的有限狀態自動機。

要先理解FA先，也就是有限狀態自動機，其實就是個識別器，只能對每個可能的輸入串簡單地回答“是”或“否”。

然後NFA是一種FA，其特點是在某個狀態S下輸入某個字符a，可以進入多個不同狀態，還有就是空串ε也可以作為輸入字符標號。

這裡繼續舉例說明：