1、Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春第二章第二章 詞法分析詞法分析本章主要討論詞法分析程序的設計原則，單詞的描述技本章主要討論詞法分析程序的設計原則，單詞的描述技術、識別機制及詞法分析程序的自動構造原理。術、識別機制及詞法分析程序的自動構造原理。1.詞法分析的功能詞法分析的功能 2.程序語言的單詞符號種類及詞法分析輸出程序語言的單詞符號種類及詞法分析輸出 3.詞法分析程序的設計與實現詞法分析程序的設計與實現4.正規表達式與有窮自動機正規表達式與有窮自動機5.詞法分析程序的自動生成詞法分析程序的自動生成P

2、rinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春本章重點本章重點 單詞的描述工具單詞的描述工具 單詞的識別系統單詞的識別系統 設計和實現詞法分析程序設計和實現詞法分析程序 首先需要描述和刻畫程序設計語言中的原子單位首先需要描述和刻畫程序設計語言中的原子單位單詞，其次需要識別單詞和執行某些相關的動作。單詞，其次需要識別單詞和執行某些相關的動作。 描述程序設計語言的詞法的機制是正規表達式，識別描述程序設計語言的詞法的機制是正規表達式，識別機制是有窮自動機機制是有窮自動機。Principle of Compiling長春工

3、業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春詞法分析程序詞法分析程序功能：功能：逐個讀入源程序字符并按照構詞規則切分成一系列單詞逐個讀入源程序字符并按照構詞規則切分成一系列單詞主要任務：主要任務：讀入源程序，輸出單詞符號讀入源程序，輸出單詞符號其他任務：其他任務： 濾掉空格，跳過注釋、換行符濾掉空格，跳過注釋、換行符 追蹤換行標志，指出源程序出錯的行列位置追蹤換行標志，指出源程序出錯的行列位置 宏展開，宏展開，關鍵：關鍵：找出單詞的分割符找出單詞的分割符Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院

4、20112011春春l 詞法分析是編譯過程中的一個階段，在語法分析前詞法分析是編譯過程中的一個階段，在語法分析前進行。可以作為一個獨立的子程序。進行。可以作為一個獨立的子程序。優勢表現為：優勢表現為：簡化設計簡化設計改進編譯效率改進編譯效率增加編譯系統的可移植性增加編譯系統的可移植性 l 可以和語法分析結合在一起作為一遍，由語法分析可以和語法分析結合在一起作為一遍，由語法分析程序調用詞法分析程序來獲得當前單詞供語法分析使程序調用詞法分析程序來獲得當前單詞供語法分析使用。用。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院2011201

5、1春春單詞符號單詞符號是程序設計語言中具有獨立意義的最小單位，程序設計是程序設計語言中具有獨立意義的最小單位，程序設計語言基本組成成分。語言基本組成成分。五類：五類：關鍵字（保留字關鍵字（保留字/基本字）基本字）:if while 標識符：常量名標識符：常量名 變量名變量名常數：常數：34 56.78運算符：運算符：+ - / =，、,!,= /=*結束結束組合標識符組合標識符查保留字查保留字 保留字保留字 輸出保留字輸出保留字 輸出標識符輸出標識符組合整數組合整數 輸出整數輸出整數 輸出單分符輸出單分符 讀字符讀字符 讀字符讀字符讀字符讀字符輸出雙分符輸出雙分符 讀字符讀字符輸出單分符輸出單

6、分符/ 注釋處理注釋處理 輸出單分符輸出單分符 錯誤處理錯誤處理 YYYYYYYYYYNNNNNNNNNNPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春正規表達式與有限自動機正規表達式與有限自動機要求要求正規式與正規集的定義正規式與正規集的定義有窮自動機的定義及表示有窮自動機的定義及表示NFANFA確定化為確定化為DFADFA掌握掌握DFADFA的化簡的化簡掌握用正規式構造掌握用正規式構造DFADFA掌握正規文法與有窮自動機間的轉換掌握正規文法與有窮自動機間的轉換 Principle of Compiling長春

7、工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春字母表和符號串的基本概念字母表和符號串的基本概念字母表字母表：元素的：元素的非空有窮非空有窮集合。記為集合。記為。 字母表包含了語言中所允許出現的一切字母表包含了語言中所允許出現的一切符號符號。 例如：例如： = 0，1符號串符號串(字字)：字母表中的符號所組成的：字母表中的符號所組成的有窮有窮序列。序列。 一個語言的句子總是它的字母表的符號串。這個符號一個語言的句子總是它的字母表的符號串。這個符號串的組成必須是按照文法規則組合而成的。串的組成必須是按照文法規則組合而成的。 語法分析的一個重要任務就是：判斷一個符號

8、串的組語法分析的一個重要任務就是：判斷一個符號串的組成是否滿足某個文法的規定。成是否滿足某個文法的規定。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春字母表和符號串的基本概念字母表和符號串的基本概念(續續)空串：不包含任何符號的串，記為。*：表示上所有符號串的全體。空集：，不包含任何元素。 在本課程中，語言被認為是句子的集合。所以，一個語言就是對應于它的字母表上的一個符號串集合。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春符號串的

9、運算符號串的運算符號串的長度符號串的長度：指符號串：指符號串x中所含符號的個數，記為中所含符號的個數，記為|x|。符號串相等符號串相等：若：若x、y是字母表是字母表上的兩個符號串，那么當且僅當組成上的兩個符號串，那么當且僅當組成x的各符號與組成的各符號與組成y的各符號依次相等時，則符號串的各符號依次相等時，則符號串x與符號串與符號串y相相等，記作等，記作x=y。 連接連接(并置并置)：若：若x、y是兩個符號串，則是兩個符號串，則xy表示連接，是將符號串表示連接，是將符號串y連連接在符號串接在符號串x的后面。若的后面。若x、y是字母表是字母表上的兩個符號串，則上的兩個符號串，則xy也也是字母表是

10、字母表上的符號串。上的符號串。 注意：連接沒有交換率律，即注意：連接沒有交換率律，即 xy yx 而對于空串而對于空串有有 x=x=xPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春方冪方冪：x的的n次方冪即將次方冪即將n個個x連接。連接。x0 = , x1 = x, x2 = xx, xn=xxx=xx n-1=x n-1 x 乘積乘積：令：令A、B為兩個符號串集合，為兩個符號串集合，A和和B的乘積的乘積AB定義定義為：為：AB = xy | x A且且y B A=A =A A= A =方冪方冪：A的的n次方冪就

11、是將次方冪就是將n個個A相乘。相乘。 A0= A1=A A2=AA An=AAA=AA n-1 =A n-1 A Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春符號串集合的運算符號串集合的運算集合的正則閉包和集合的閉包集合的正則閉包和集合的閉包： 設設A為一個集合，則集合為一個集合，則集合A的正則閉包用的正則閉包用A+表示，定義為：表示，定義為： A+ =A1 A2 . A n 表示表示A上的所有的非空符號串的集合。上的所有的非空符號串的集合。 集合集合A的閉包用的閉包用A*表示，定義為：表示，定義為： A* =

12、A 0 A+ 表示表示A上的所有符號串（包括空字符串）的集合。上的所有符號串（包括空字符串）的集合。 例如：例如：A =a，b， 則則A+ =a,b,aa,ab,ba,bb,aaa,aab, A* = ,a,b,aa,ab,ba,bb,aaa,aab,Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春定義（正規式和正規集）定義（正規式和正規集）設字母表為設字母表為 ，輔助字母表，輔助字母表 = ， ， ， ， ， ， 。1、 和和 都是都是 上的正規式，表示的正規集分別為上的正規式，表示的正規集分別為 和和 ；2、對

13、任何、對任何a ，a是正規式，它所表示的正規集為是正規式，它所表示的正規集為a；3、假定、假定e1和和e2都是都是 上的正規式，它們所表示的正規集分別為上的正規式，它們所表示的正規集分別為L(e1)和和L(e2)，那么，那么，(e1), e1 e2, e1 e2, e1 也都是正規式也都是正規式,它們所表示的正規集它們所表示的正規集分別為分別為L(e1), L(e1) L(e2), L(e1)L(e2)和和(L(e1) 。4、僅由有限次使用上述三步驟而定義的表達式才是、僅由有限次使用上述三步驟而定義的表達式才是 上的正規式，僅由上的正規式，僅由這些正規式所表示的集合才是這些正規式所表示的集合才

14、是 上的正規集。上的正規集。 或或； 連接；連接； 閉包閉包 規定優先順序為規定優先順序為“ ”、“ ”、“ ” ， 左結合左結合Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春例：令例：令 =a，b， 上的正規式和相應的正規集有：上的正規式和相應的正規集有：正規式正規式正規集正規集aaba*所有以所有以b開頭后跟任意多個開頭后跟任意多個a的字的字a ba,babab(a b)(a b)aa,ab,ba,bba ,a,aa, 任意個任意個a的串的串(a|b)*(aa|bb)(a|b)*所有含有兩個相繼的所有含有兩個

15、相繼的a或兩個相繼的或兩個相繼的b的字的字(a b) ,a,b,aa,ab 所有由所有由a 和和b組成的串組成的串Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春程序設計語言的單詞都能用正規式來定義。程序設計語言的單詞都能用正規式來定義。例例：令：令 =l，d，則，則 上的正規式上的正規式: r=l(l d) 定義的正規集為定義的正規集為: l,ll,ld,lll,ldd,就是標識符的詞法規就是標識符的詞法規則。其中則。其中l代表字母代表字母,d代表數字代表數字, 正規式正規式 ：字母：字母(字母字母|數字數字)

16、,它表示每個元素的模式是它表示每個元素的模式是“字字母打頭的字母數字串母打頭的字母數字串”,例例：令令 d， ，e，則，則 上的正規式上的正規式:d*(.dd*| )(e(+|-| )dd*| )表示的是無符號數。表示的是無符號數。 其中其中d為為09中的數字。中的數字。 比如：比如：2,12.59,3.6e2,471.88e-1等都是正規式表示集合中的等都是正規式表示集合中的元素。元素。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春正規式的等價正規式的等價若兩個正規式若兩個正規式e1和和e2所表示的正規集相同所

17、表示的正規集相同,則說則說e1和和e2等價等價,寫作寫作e1=e2。設設r,s,t為正規式，正規式服從的代數規律有：為正規式，正規式服從的代數規律有：lr s=s r “或或”的交換律的交換律lr (s t)=(r s) t“或或”的可結合律的可結合律l(rs)t=r(st)“連接連接”的可結合律的可結合律lr(s t)=rs rt (s t)r=sr tr 分配律分配律 l r=r =r 是是“連接連接”的恒等元素的恒等元素le*e+le+=e*e=ee*l(e*)*=e*Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院201120

18、11春春有限自動機有限自動機研究詞法分析器的重要理論基礎研究詞法分析器的重要理論基礎lDFA，NFA的基本概念和理論的基本概念和理論 DFA:確定的有限自動機確定的有限自動機 (Deterministic Finite Automata) NFA:非確定的有限自動機非確定的有限自動機 (Nondeterministic Finite Automata)l正規文法、正規表達式與有限自動機之間的關系。正規文法、正規表達式與有限自動機之間的關系。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春DFA的定義的定義一個確定的

19、有限自動機一個確定的有限自動機(DFA) M是一個五元組：是一個五元組： M=(S，s0，F),),其中其中: : 1. 1.S S是一個有窮集，它的每個元素稱為一個狀態；是一個有窮集，它的每個元素稱為一個狀態； 2.2.是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱稱為輸入符號表；為輸入符號表； 3.3.是在是在SS上的單值映射，即，如上的單值映射，即，如 (s，a)=s，(sS，sS)就意味著，當前狀態為就意味著，當前狀態為s，輸入符為，輸入符為a時，將轉換為下一個狀態時，將轉換為下一個狀態s，我，我們把們把s稱作稱作s s的

20、一個后繼狀態；的一個后繼狀態； 4.4. s0 SS是唯一的一個初態；是唯一的一個初態； 5.5.F S是一個終態集，也稱可接受狀態或識別狀態集。是一個終態集，也稱可接受狀態或識別狀態集。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春DFA映射的表示映射的表示直接給出：直接給出： (s，a)=s狀態轉換矩陣：狀態轉換矩陣： 行表示狀態，列表示輸入符號行表示狀態，列表示輸入符號狀態轉換圖：狀態轉換圖：結點：狀態，用結點：狀態，用表示；終態，用表示；終態，用表示表示有向弧有向弧 箭頭箭頭弧標記弧標記 輸入字符輸入字符

21、Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春例：有例：有DFA M =(0,1,2,3,a,b, ,0,3) 為：為：(0,a) = 1 (0,b) = 2(1,a) = 3 (1,b) = 2(2,a) = 1 (2,b) = 3(3,a) = 3 (3,b) = 3狀態狀態 輸入輸入ab0121322133*33Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春(0,a) = 1 (0,b) = 2(1,a) = 3 (1,b)

22、= 2(2,a) = 1 (2,b) = 3(3,a) = 3 (3,b) = 3aaab0123ba，bbPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春DFA的確定性表現在：的確定性表現在： 對任何狀態對任何狀態s S，在讀入了輸入符號，在讀入了輸入符號a 之后，之后，能夠唯一地確定下一個狀態。能夠唯一地確定下一個狀態。 從狀態轉換圖來看，若字母表從狀態轉換圖來看，若字母表含有含有n個輸入字符，個輸入字符，那末任何一個狀態結點最多有那末任何一個狀態結點最多有n條弧射出，而且每條弧射出，而且每條弧以一個不同的輸入

23、字符標記。條弧以一個不同的輸入字符標記。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春DFA識別的字識別的字一個字一個字可為可為DFA M所接受：對于所接受：對于* 中的任何字中的任何字，若存在一，若存在一條從初態結點到終態結點的條從初態結點到終態結點的通路通路，且這條通路上所有弧的，且這條通路上所有弧的標記符號連接成的字等于標記符號連接成的字等于。若若M的初態結點又是終態結點，則空字的初態結點又是終態結點，則空字可為可為M所識別。所識別。DFA M所能識別的符所能識別的符號號串的全體記為串的全體記為L(M)。

24、對于任何兩個有窮自動機對于任何兩個有窮自動機M和和M，如果，如果L(M)=L(M)，則稱，則稱M與與M是等價的。是等價的。 Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春每讀入一個符號，讀每讀入一個符號，讀頭向后移動一個位置，頭向后移動一個位置，有窮控制器控制狀態有窮控制器控制狀態轉移到下一個狀態轉移到下一個狀態在初始時，讀頭處于輸在初始時，讀頭處于輸入帶的開始位置，表示入帶的開始位置，表示準備讀入，狀態處于初準備讀入，狀態處于初始狀態始狀態整個模型由三部分組成：整個模型由三部分組成： 輸入帶：存放輸入符號輸入帶

25、：存放輸入符號 讀頭：可以在輸入帶上向后移動讀頭：可以在輸入帶上向后移動 有窮控制器：控制狀態發生變化有窮控制器：控制狀態發生變化如果讀頭移動到最后一個符號后面，如果讀頭移動到最后一個符號后面，狀態正好是終結狀態，則輸入帶上狀態正好是終結狀態，則輸入帶上的符號組成的字能被該有限自動機的符號組成的字能被該有限自動機所識別所識別Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春能接受偶數個能接受偶數個0和偶數個和偶數個1組成的串的有窮自動機。組成的串的有窮自動機。SABC11010010Principle of Comp

26、iling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春NFA的定義的定義一個非確定的有限自動機一個非確定的有限自動機(NFA) M是一個五元組：是一個五元組： NFA M=(S， ，s0，F ) 其中其中: :1.1.S為狀態的有窮非空集為狀態的有窮非空集；2.2.是有窮輸入字母表；是有窮輸入字母表；3.3.為一個為一個S * 到到S的子集的映射的子集的映射；4.4. s0 S是初始狀態集是初始狀態集；5.5.F S為終止狀態集為終止狀態集。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院201

27、12011春春NFA映射的表示映射的表示直接給出直接給出狀態轉換矩陣狀態轉換矩陣狀態轉換圖狀態轉換圖Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春矩陣表示矩陣表示(S，0)=P (S，1)=S，Z(Z，0)=P(Z，1)=P(P，1)=Z狀態狀態 輸入輸入01SPS,ZPZZ*PPPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春狀態轉換圖狀態轉換圖(S，0)=P (S，1)=S，Z(Z，0)=P(Z，1)=P(P，1)=ZSPZ00,

28、1111Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春NFA識別的字識別的字l對于對于*中的任何一個串中的任何一個串t，若存在一條從某一初態結點到，若存在一條從某一初態結點到某一終態結點的道路，且這條道路上所有弧的標記字依序某一終態結點的道路，且這條道路上所有弧的標記字依序連接成的串等于連接成的串等于t，則稱，則稱t可為可為NFA M所識別所識別(讀出或接受讀出或接受)。l若若M的某些結點既是初態結點又是終態結點；或者存在的某些結點既是初態結點又是終態結點；或者存在一條從某個初態結點到某個終態結點的道路一條從某個

29、初態結點到某個終態結點的道路,其上所有弧的其上所有弧的標記均為標記均為，那么空字，那么空字可為可為M所接受。所接受。lNFA M所能接受的符號串的全體記為所能接受的符號串的全體記為L(M)。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春021ba,bab Sab0211(1,2)2*22Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春DFA 與與NFA的區別的區別: DFA是是NFA的特例。的特例。 對每個對每個NFA N存在著與之等

30、價的存在著與之等價的DFA M。DFA與與NFA的關系的關系DFA： S為狀態的有窮非空集為狀態的有窮非空集； 是有窮輸入字母表；是有窮輸入字母表； 為一個為一個S 到到S的單值的單值映射映射； s0 S是初始狀態是初始狀態； F S為終止狀態集為終止狀態集NFA： S為狀態的有窮非空集為狀態的有窮非空集； 是有窮輸入字母表；是有窮輸入字母表； 為一個為一個S * 到到S的子集的的子集的映射映射； s0 S是初始狀態集是初始狀態集； F S為終止狀態集為終止狀態集Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春解決

31、的問題解決的問題： 1. 初態集初態集 2. 輸入字輸入字 3. 弧弧 4. 轉換的目標狀態集轉換的目標狀態集Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春NFA的確定化的確定化1.增加狀態增加狀態X,使之成為新的唯一的初態。從使之成為新的唯一的初態。從X引引弧到原初態結點。弧到原初態結點。2.對狀態圖進一步進行如下形式的改變對狀態圖進一步進行如下形式的改變ijABikAjBijA|BiAjBijA*ikjAPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學

32、院20112011春春例：例：(a|b)*(aa|bb)(a|b)*S S12Z(a|b)*(aa|bb)(a|b)*例：例：(a|b)*(aa|bb)(a|b)*SZ(a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*S312Z4ababaabbS312Z4aabba45abbPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春 3.定義定義I I的的-閉包閉包-closure(I I)，v任何狀態任何狀態q I，則，則q -closure(I)；v任何狀態任何狀態q I，則，則q經任意條經任

33、意條 弧而能到達的狀態的弧而能到達的狀態的q -closure(I) 。例：例：I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2；12534687aaaNFA的確定化的確定化Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春12534687aaa定義狀態集合定義狀態集合I I的的a弧轉換弧轉換，I Ia = -closure(J J) ,其中其中J J是所有那是所有那些可從些可從I I中的某一狀態經過一條中的某一狀態經過一條a a弧而到達的狀態的全體。弧而到達的狀態的全體。Pr

34、inciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春確定化的算法確定化的算法v首先置該表的首行首列為首先置該表的首行首列為 : closure(X),X為開始結點。為開始結點。v對對 = a1ak, 構造一個構造一個k+1列的表。列的表。若某行的第一列的若某行的第一列的狀態已確定為狀態已確定為I I，則第，則第i+1(i = 1,2,k)列的值為列的值為I Iai，然后，然后檢查該行上的所有狀態子集，看它是否已在第一列出現。檢查該行上的所有狀態子集，看它是否已在第一列出現。若未出現，將其填加到后面的空行上。重復此過程，直若

35、未出現，將其填加到后面的空行上。重復此過程，直到所有狀態子集均在第一列中出現。到所有狀態子集均在第一列中出現。v得到一個確定的有限自動機：將每個狀態子集視為新的得到一個確定的有限自動機：將每個狀態子集視為新的狀態，初態就是首行首列的狀態，終態是含有原終態的狀態，初態就是首行首列的狀態，終態是含有原終態的集合。集合。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春例子例子4f35621iaaaabbbbSABACBBADCCEDFDEFDFCEPrinciple of Compiling長春工業大學計算機科學與工程學

36、院長春工業大學計算機科學與工程學院20112011春春等價的等價的DFAaCDBAEFSbaaaaabbbbbabFPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春小結小結DFA與與NFA的相關概念的相關概念DFA與與NFA的關系的關系重點：重點：DFA與與NFA定義及關系定義及關系難點：難點：NFA的確定化的確定化Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春正規表達式與正規表達式與FA的等價性的等價性正規表達式和有限自動機的表達能

37、力是相同的。具體表正規表達式和有限自動機的表達能力是相同的。具體表現在：現在： 給定一個正規表達式給定一個正規表達式R，可以構造出相應的有限自，可以構造出相應的有限自動機動機A。該自動機接受的符號串的集合恰巧是正規。該自動機接受的符號串的集合恰巧是正規表達式的值，即表達式的值，即L（R）=L（A） 給定一個有窮狀態自動機給定一個有窮狀態自動機A，可以構造出相應的正，可以構造出相應的正規表達式規表達式R。該正規表達式的值恰巧是該自動機接。該正規表達式的值恰巧是該自動機接受的符號串的集合，即受的符號串的集合，即L （ A ） =L（ R ）Principle of Compiling長春工業大學計

38、算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春從正規表達式到從正規表達式到FA具體步驟：對于任意的一個正則表達式具體步驟：對于任意的一個正則表達式e，從，從 e開始，按照變換規則，逐步擴弧、擴結，直到轉換圖上開始，按照變換規則，逐步擴弧、擴結，直到轉換圖上所有的弧上都是所有的弧上都是中的單個符號為止。中的單個符號為止。對于引入的每一個新狀態，應該賦予一個獨有的名字。對于引入的每一個新狀態，應該賦予一個獨有的名字。 Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春從正規表達式到從正規表達式到F

39、A的替換規則的替換規則替換規則：替換規則：sze1e2Ase1ze2sze1|e2Zse1e2sz e*szeAPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春例子例子e = (A|B)（A|B|0|1)*sze1sAA|B2z(A|B|0|1)*BAsA3zA|B|0|1BPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春例子例子a*|(a|b)a)*SZa*|(a|b)a)*SZa*(a|b)a)*SZa(a|b)aSZaa|baPr

40、inciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春NFA 到正規表達式到正規表達式1、轉換圖拓廣，新設置一個唯一的開始狀態、轉換圖拓廣，新設置一個唯一的開始狀態S和唯和唯一的終態一的終態Z，通過，通過弧連接到原弧連接到原FA。2、運用、運用替替換規則消弧消結點，直到只剩下開始狀態換規則消弧消結點，直到只剩下開始狀態和接受狀態。此時，唯一的邊上的標記就是所要和接受狀態。此時，唯一的邊上的標記就是所要的表達式。的表達式。SZ M Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科

41、學與工程學院20112011春春NFA 到正規表達式替換規則到正規表達式替換規則c.321R1R2R331R1R2*R3a.123R1R213R1R2b.12R1R221R1|R2Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春例：例： L(M)如右圖：如右圖：求正規式求正規式R，使，使L(R)=L(M).因此：因此：L(R)= (a|b)(a|b)*y(a|b)(a|b)*xya|ba|bx-+aba,b-+aba,bxyPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算

42、機科學與工程學院20112011春春確定有窮自動機的化簡確定有窮自動機的化簡一個有窮自動機是化簡了的，即是說：一個有窮自動機是化簡了的，即是說： 它沒有多余狀態；它沒有多余狀態； 它的狀態中沒有兩個是互相等價的。它的狀態中沒有兩個是互相等價的。一個有窮自動機可以通過消除多余狀態和合并等價狀一個有窮自動機可以通過消除多余狀態和合并等價狀態而轉換成一個最小的與之等價的有窮自動機。態而轉換成一個最小的與之等價的有窮自動機。所謂有窮自動機的所謂有窮自動機的多余狀態多余狀態，是指這樣的狀態：從自，是指這樣的狀態：從自動機的開始狀態出發，任何輸入串也不能到達的那動機的開始狀態出發，任何輸入串也不能到達的那

43、個狀態；或者從這個狀態沒有通路到達終態。個狀態；或者從這個狀態沒有通路到達終態。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春確定有窮自動機的化簡確定有窮自動機的化簡一個有窮自動機是化簡了的，即是說：一個有窮自動機是化簡了的，即是說： 它沒有多余狀態；它沒有多余狀態； 它的狀態中沒有兩個是互相等價的。它的狀態中沒有兩個是互相等價的。狀態狀態S和和T等價的條件等價的條件 一致性條件一致性條件 狀態狀態S和和T必須同時為可接受狀態或必須同時為可接受狀態或不可接受狀態。不可接受狀態。 蔓延性條件蔓延性條件 對于所有輸入

44、符號，狀態對于所有輸入符號，狀態S和狀態和狀態T必須轉換到等價的狀態里。必須轉換到等價的狀態里。DFA的最小化的方法（分割法）的最小化的方法（分割法）方法：將方法：將DFA的狀態分割成一些互不相交的子集。的狀態分割成一些互不相交的子集。Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春分割法分割法DFA的最小化算法的核心 把一個把一個DFA的狀態分成一些不相交的子集，使得任何不同的狀態分成一些不相交的子集，使得任何不同的兩子集的狀態都是可區別的，而同一子集中的任何兩個的兩子集的狀態都是可區別的，而同一子集中的任何兩個

45、狀態都是等價的狀態都是等價的.算法：將所有狀態分成兩個子集將所有狀態分成兩個子集終態集終態集和和非終態集非終態集運用判定狀態等價原則分別對兩個子集的狀態進行分析和運用判定狀態等價原則分別對兩個子集的狀態進行分析和劃分，把互相等價的狀態構成一個子集，若發現不等價，劃分，把互相等價的狀態構成一個子集，若發現不等價，繼續劃分，這樣繼續劃分，這樣FA的狀態被分成互不相交的若干子集。的狀態被分成互不相交的若干子集。從每個子集中選出一個狀態做代表，即可構成簡化的從每個子集中選出一個狀態做代表，即可構成簡化的FAPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科

46、學與工程學院20112011春春注意：注意：a a、由于一個子集中，各狀態射出的弧均相同，故只需要將原、由于一個子集中，各狀態射出的弧均相同，故只需要將原進入各子集中各狀態的弧都改為進入所選的狀態。進入各子集中各狀態的弧都改為進入所選的狀態。b b、含有原來初態的子集仍為初態，各終態的子集仍為終態、含有原來初態的子集仍為初態，各終態的子集仍為終態Principle of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春例：化簡下圖，使其最小化例：化簡下圖，使其最小化。CDBAEFSbaaaaabbbbbabFaPrinciple of Co

47、mpiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春DBASaaabbbbaCDBAEFSbaaaaaabbbbbba00: S,A,B C,D,E,F1:1: 2:2:aA，S,BbS,BS,A,BPrinciple of Compiling長春工業大學計算機科學與工程學院長春工業大學計算機科學與工程學院20112011春春詞法分析器生成工具詞法分析器生成工具LexLex：Unix(Linux)系統的一個標準實用程序。系統的一個標準實用程序。詞法分析器自動構造示意圖詞法分析器自動構造示意圖Lex源文件源文件 （.l）Lex詞法分析程序詞法分析程序（lex.yy.c）輸入的輸入的Lex源文件（源文件（.l），主要定義了一些詞法規則。），主要定義了一些詞法規則。輸出的詞法分析程序輸出的詞法分析程序(lex.yy.c)，包含，包