編譯原理第三章

• 3.1_正規文法和狀態轉換圖
• • （1）構造狀態轉換圖
  • （2）狀態矩陣
• 3.2_有限自動機
• • 3.2.1_確定的有限自動機DFA
  • 3.2.2_非確定的有限自動機NFA
• 3.3_NFA轉換為DFA（NFA確定化）
• • 3.3.1_無ε動作的NFA確定化
  • 3.3.2_有ε動作的NFA確定化
• 3.4_DFA最小化
• 3.5_正規表達式和正規集

3.1_正規文法和狀態轉換圖

（1）構造狀態轉換圖

1、對于G中每一個形如A——>aB的產生式，從結點A引一條矢線到結點B，并用符號a標記這條矢線
即A—^a—>B

2、對于G中每一個形如A——>a的產生式，從結點A引一條矢線到結點F，并用符號a標記這條矢線
即A—^a—>F

（2）狀態矩陣

狀態矩陣：Bij=B[Si，aj]，其中Si為狀態圖中各狀態，aj為各輸入符號，總元素個數＝|VN|×|VT|

3.2_有限自動機

3.2.1_確定的有限自動機DFA

3.2.2_非確定的有限自動機NFA

3.3_NFA轉換為DFA（NFA確定化）

3.3.1_無ε動作的NFA確定化

3.3.2_有ε動作的NFA確定化

3.4_DFA最小化

DFA狀態數最小化算法:
(1)將狀態集K劃分為終態子集Z和非終態子集K-Z， 記為π={Z, K-Z}。
(2)對當前中的每個子集，檢查其中每個狀態對識別相同字符是否具有同樣的映射（即是否能夠映射到π中的同一個集合），將映射到不同狀態子集的稱為可以區分的，將其按映射關系進行分裂，產生新的狀態子集集合，記為πnew。 .
(3)若πnew <> π， 重復(2)，直至各子集都不能繼續劃分。
(4)對最終劃分II的每個狀態子集，取其中任一狀態作為該子集的代表狀態，將原來射入該子集的所有矢線改為射入此代表狀態。取含有原任一終態的子集作為新的終態。

3.5_正規表達式和正規集

（1）正規式:將文法的終結符號用以上三種運算符連接起來組成的正規文法的表達式，是另- -種用于描述正規文法的直觀表示。
例如語法范疇<標識符>的正規表達式為:字母(字母|數字) *
（2）正規集:正規式所描述的字符串的集合。

總結

以上是生活随笔為你收集整理的编译原理第三章的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。