【正文】 110 ? ??? ??? ??? ??? ??? ??? ??? ??bbabbaa青島大學信息工程學院 編譯原理與技術 57 有限自動機 – 兩個 NFA N1和 N2稱為等價的，當且僅當它們識別同一個語言，即 L(N1)=L(N2)。 青島大學信息工程學院 編譯原理與技術 55 有限自動機 ? 不確定的有限自動機 NFA – 定義：一個不確定的有限自動機 NFA M是五元組 S, ?, T, s0, F，其中： （ 1） S是非空的有限的狀態(tài)集合； （ 2） ?是非空的輸入字母表； （ 3） T是 S?(??{?})→ 2S （ S的冪集），它可以把一個狀態(tài)映射到一組狀態(tài) ； – T(s1, a)= s2表示輸入符號 a時，把狀態(tài) s1轉換到 s2，成為當前狀態(tài)； （ 4） s0?S，是唯一的起始狀態(tài)； （ 5） F?S，是非空的終結狀態(tài)。 EEDBA ? ??? ??? ??? ??? ?? ? 82.EEECCCBA ? ??? ??? ??? ??? ??? ??? ??? ?? ? EEDA ? ??? ??? ??? ?? .03青島大學信息工程學院 編譯原理與技術 54 有限自動機 – 定義 (a)：兩個有限自動機 M1和 M2是等價的，當且僅當它們識別相同的語言，即L(M1)=L(M2)。 DFA M所能識別的所有字的集合稱為 M識別的語言，記做 L(M)。 青島大學信息工程學院 編譯原理與技術 52 有限自動機 定義 ：對于有限自動機 M的 ?*中的任何一個符號串 α，若存在一條從起始狀態(tài)到某一終結狀態(tài)的通路，且這條通路上所有弧的標記符連成的串等于 α，則稱 α被 M識別（讀出或接受）。 d d d +, ? + ? )＝ E T(C, d)=C T(D, d)＝ E T(E, d)＝ E 狀態(tài) A是起始狀態(tài)， E是終結狀態(tài)。)=C T(A, d)=D T(B, 被 M接受或識別的語言，記做 L(M)，定義為字符串c1c2...的集合，其中每個 ci??，并且存在狀態(tài)序列s1=T(s0, c1), s2=T(s1, c2), ... , sn=T(sn1, )， sn ?F。 – 但是，實現(xiàn)這兩類有限狀態(tài)機的效率不同，用它們構造的詞法分析器在識別語言中單詞記號的效率方面也有顯著的差別。 – 由于正規(guī)表達式的重要而廣泛的應用， Java語言通過包 接支持。這個模板決定什么樣的字符串屬于某一個集合。小數(shù)和指數(shù)部分是可選的，其中指數(shù)標記 E后面可以有 +或 ?，再跟上一個或多個數(shù)字，而小數(shù)點之后必須至少有一個數(shù)字。這樣，正規(guī)式 r的名字 name就可以像 ?中的符號一樣，在以后構造 ?上正規(guī)式的時候使用。帶符號的整數(shù)可以寫成 (+|?)?[19][09]* 青島大學信息工程學院 編譯原理與技術 43 正規(guī)表達式 – 如果正規(guī)式很長，可以給它命名，使它們可以像普通的符號一樣，在隨后的正規(guī)式中使用這些名字來引用相應的正規(guī)式，以便得到簡潔的正規(guī)式。標識符是字母打頭的字母數(shù)字串，可以表示成 [AZaz][ AZaz09]*。更簡潔的方式是用方括弧，用連接線表示范圍，這樣，上面的字母或數(shù)字就可以分別表示成 [az]和 [09]。這樣， (0|1)+表示所有二進制數(shù)字的集合，而 (0|1)*同時還包含了可串。 – 正規(guī)式等價的例子如a|(ba)*= (ba)*|a，(a|b)=(b|a)。 – (a|c)*b(a|c)* b表示的集合是什么呢？它表示只含兩個b的符號串的集合。 青島大學信息工程學院 編譯原理與技術 40 正規(guī)表達式 例 ：令字母表 ?={a, b, c}，那么 – (a|b)(a|b)＝ {aa, ab, ba, bb}； – (a|c)*表示所有 a和 c組成的符號串，其中包含空串 ?； – (a|c)*b(a|c)*表示只包含一個 b的字母表 ?上的所有符號串，例如 b， abc， baaac， caccb， ccbaaa。 – 定義 ：字母表 ?上的正規(guī)表達式（簡稱正規(guī)式）按照下列規(guī)則遞歸地定義： （ 1） ?是 ?上的正規(guī)式，它表示的正規(guī)集是 {?}； （ 2） ?是 ?上的正規(guī)式，它表示的正規(guī)集是 ?； （ 3） ?中的任意符號 a都是 ?上的正規(guī)式，它表示的正規(guī)集是 {a}（ 4）若 r和 t都是正規(guī)式，它們所表示的正規(guī)集分別是 L(r)和L(t)，那么 (r)、 r|t 、 rt和 r*都是正規(guī)式，表示的正規(guī)集分別是L(r)、 L(r)∪ L(t)、 L(r)L(t)、 ( L(r)) *。 青島大學信息工程學院 編譯原理與技術 38 正規(guī)表達式 例 ：令字母表 L={A, B, ..., Z, a, b, ..., z}，D={0, 1, ..., 9}，那么 – L∪ D是字母和數(shù)字的集合； – LD4表示以字母開頭、跟隨 4個數(shù)字的串的集合； – L(L∪ D)15表示長度為 16的標識符，即以字母開始的 16位的字母和數(shù)字串的集合； – D*表示不含空的數(shù)字串的集合。 – ?+實際上就表示了該字母表所構成的語言，句子就是其中的符號串。 – 顯然， ?*＝ ?0∪ ?+， ?+= ?*? = ??*。 青島大學信息工程學院 編譯原理與技術 37 正規(guī)表達式 – 定義 ：字母表 ?的閉包 ?*＝ ?0∪ ?1∪ ...∪ ?n...，正閉包 ?+＝ ?1∪ ?2∪ ...∪ ?n... 。由于對于任何符號串 x都有 x?＝ ?x＝ x，所以 {?}A=A{?}=A，但是，對于空集 ?，卻有等式 ?A=?A=?。 – 定義 ：兩個符號串集合 A和 B的乘積 AB定義為： AB={uv | u?A并且 v?B}。 – 字母表上的符號集合通常用大寫字母 A、 B、 C等表示。顯然， uun1 = un1u= un。 – 例如， u1=u， u2=uu， u4=uuuu。 – 顯然，對于任何符號串 α，都有 α?＝ ?α＝ α。顯然， |αβ|=|α|+|β|。 ?例如，若我們只關心符號串 x=αtγ中的符號 t，也可以用 x=...t...表示；同樣， x=tα和 x=t...這兩種表示都只關注符號的頭時符號 t。 青島大學信息工程學院 編譯原理與技術 34 正規(guī)表達式 ?如果 x=uv是一個符號串，則稱 u是 x的頭，稱 v是 x的尾。符號 α的長度表示成 |α|，例如 |abba|=4。符號串中符號的排列順序十分重要，上面的 ab和 ba表示不同的符號串。 ?例如，對于字母表 ?＝ {a, b}， a、 b、 aa、 ab、 ba和 abba都是 ?上的符號串。 青島大學信息工程學院 編譯原理與技術 33 正規(guī)表達式 – 定義 ：由字母表中的符號所組成的任何有限序列稱為符號串。 青島大學信息工程學院 編譯原理與技術 32 正規(guī)表達式 ?符號、符號串與符號集合 – 定義 ：字母表是有限的非空的符號集合，字母表中的元素稱作符號。 case “/”: getchar(ch)。 case “?”: getchar(ch)。 case “?”: getchar(ch)。 } case “+”: getchar(ch)。 return(3, “=”)}。 } case “GE”: { getchar(ch)。 return(3, “= =”)}。 } case “EA”: { getchar(ch)。 return(3, “=”)}。 return(3, “”)}。 } // 返回標識符的單詞記號 } case “LNE”: { getchar(ch)。 // 返回關鍵字的單詞記號 else {value=insert(token, identifierTable)。 code = lookup(token, keywordsTable)。 } 青島大學信息工程學院 編譯原理與技術 31 詞法分析器的一種手工實現(xiàn) case “inID”: { while ((isletter(ch) || isdigit(ch)) { token = token+ch。 } case “number”: { value = insert (token, identifierTable)。 else {code = 11。 token = token+ch。 else reporterror ()。 token = token+ch。 code=10}。 getchar(ch)}。 case ch = = ?.? : { state = “2”。 // 過濾掉無用的符號 } } 青島大學信息工程學院 編譯原理與技術 30 詞法分析器的一種手工實現(xiàn) case “inNum”: { while (state屬于 {inNumber, 2, 3}) { // 處理數(shù) switch state { case “inNum”: { switch ch // 處理整數(shù) case isdigit(ch): { token = token+ch。 token = ch。 token = ch。 token = ch。 token = ch。 getchar(ch) }。 case ch = =?? : { state = “GE”。 token = ch。 getchar(ch) }。 case ch = =?? : { state = “LNE”。 case ch = =?{? : { state = “ment”。 token = ch。 getchar(ch) }。 switch ch { case isletter(ch): { state = “inID”。 getchar(ch) }。 state_sets表示所有狀態(tài)名的集合 青島大學信息工程學院 編譯原理與技術 29 詞法分析器的一種手工實現(xiàn) while (state屬于 state_sets) { switch state { case “ment”: getchar(ch)。 char state = “start”。 else reporterror()。 getchar(ch) 。 getchar(ch) 。 // 還是在狀態(tài) 2 case 3: getchar(ch)。 getchar(ch) }。 case 2: getchar(ch)。 getchar(ch) }。 case 1: getchar(ch)。 getchar(ch) }。 while (state = 0, 1, 2, 3 ) { switch state { case 0: getchar(ch)。狀態(tài) 2中的標記 other是除’ *’之外的其它符號，而從狀態(tài) 3到狀態(tài) 2的標記 other是除’ *’和’ /’之外的其它符號。 // 把 token插入標識符表 ， 返回入口地址 return (2, value) // 返回標識符的單詞記號 ， 假如標識符種別是 2 } 青島大學信息工程學院 編譯原理與技術 25 詞法分析器的一種手工實現(xiàn) ?根據(jù)狀態(tài)棧圖編寫詞法掃描器的方法二 – 采用一個變量來記錄當前的狀態(tài)，把狀態(tài)轉換嵌入到一個循環(huán)體內的分支語句中，其中的第一個分支測試當前狀態(tài)，而嵌入內層的第一個分支語句則對給定的狀態(tài)測試輸入符號，以決定轉移進入的狀態(tài)。 // 在關鍵字表中查詢 token， 若它是關鍵字就返回 1 if (code= =1) return(1, token)。 // 不斷讀入字母或數(shù)字 ， 合并成一個標識符 getchar(ch)。 char token[] =””。 – 多個轉移就對應分支語句； – 如果轉移返回自身，形成一個圈，對應程序段的就是循環(huán)語句。 3 digit digit other digit digit digit 9 ． 8 1 4 5 6 2 +, － E 7 +,? digit E digit other other * 青島大學信息