【文章內(nèi)容簡(jiǎn)介】 C等表示。例如，字母表 ?＝ {a, b, 0, 1}上長(zhǎng)度為 2的符號(hào)串集合 A={α | α=xy，并且x和 y是 ?中的一個(gè)符號(hào) }；字母表 ?上單詞 B={β | β是 {a, b}中的符號(hào)串 }。 – 定義 ：兩個(gè)符號(hào)串集合 A和 B的乘積 AB定義為： AB={uv | u?A并且 v?B}。 – 例如，設(shè) A={a, b}， B={0, 1}，那么 AB={a0, a1, b0, b1}，BA={0a, 1a, 0b, 1b}， AA={aa, ab, ba, bb}。由于對(duì)于任何符號(hào)串 x都有 x?＝ ?x＝ x，所以 {?}A=A{?}=A，但是，對(duì)于空集 ?，卻有等式 ?A=?A=?。 – 類似于符號(hào)串的方冪，可以定義符號(hào)串集合的方冪，特別地，定義字母表 A的方冪為 – A0= {?}， A1=A， An= An1 A ( n 0 )， 顯然，若 u ?An，則 | u | = n。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 37 正規(guī)表達(dá)式 – 定義 ：字母表 ?的閉包 ?*＝ ?0∪ ?1∪ ...∪ ?n...，正閉包 ?+＝ ?1∪ ?2∪ ...∪ ?n... 。 – 例如，對(duì)于字母表 ?＝ {a, b}， ?+={ a, b, aa, bb, ab, ba, aaa, bbb, aab, bba, aba, bab, abb, baa, ...}。 – 顯然， ?*＝ ?0∪ ?+， ?+= ?*? = ??*。 – ?*表示字母表 ?上所有長(zhǎng)度的符號(hào)串的集合，包括空符號(hào)串； ?+表示長(zhǎng)度至少為 1的符號(hào)串的集合。 – ?+實(shí)際上就表示了該字母表所構(gòu)成的語(yǔ)言，句子就是其中的符號(hào)串。 – 對(duì)于 C語(yǔ)言，可以說(shuō)， C語(yǔ)言是其字母表，也即基本符號(hào)正閉包的真子集。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 38 正規(guī)表達(dá)式 例 ：令字母表 L={A, B, ..., Z, a, b, ..., z}，D={0, 1, ..., 9}，那么 – L∪ D是字母和數(shù)字的集合； – LD4表示以字母開(kāi)頭、跟隨 4個(gè)數(shù)字的串的集合； – L(L∪ D)15表示長(zhǎng)度為 16的標(biāo)識(shí)符，即以字母開(kāi)始的 16位的字母和數(shù)字串的集合； – D*表示不含空的數(shù)字串的集合。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 39 正規(guī)表達(dá)式 ? 正規(guī)式與正規(guī)集 – 字母表 ?上的正規(guī)表達(dá)式用來(lái)描述一種稱為正規(guī)集的語(yǔ)言。 – 定義 ：字母表 ?上的正規(guī)表達(dá)式（簡(jiǎn)稱正規(guī)式）按照下列規(guī)則遞歸地定義： （ 1） ?是 ?上的正規(guī)式，它表示的正規(guī)集是 {?}； （ 2） ?是 ?上的正規(guī)式，它表示的正規(guī)集是 ?； （ 3） ?中的任意符號(hào) 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)) *。 – 根據(jù)顯然定義有下列等式： L(a)={a}， L(?)={?}， L(?)={}， L((r))= L(r)， L(rt)= L(r)L(t)，L(r|t)= L(r)∪ L(t)， L(r*)= ( L(r)) *。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 40 正規(guī)表達(dá)式 例 ：令字母表 ?={a, b, c}，那么 – (a|b)(a|b)＝ {aa, ab, ba, bb}； – (a|c)*表示所有 a和 c組成的符號(hào)串，其中包含空串 ?； – (a|c)*b(a|c)*表示只包含一個(gè) b的字母表 ?上的所有符號(hào)串，例如 b， abc， baaac， caccb， ccbaaa。 – 最多包含一個(gè) b的字母表 ?上的符號(hào)串的集合可以表示成 (a|c)*| ((a|c)*b(a|c)*)，或者 (a|c)*(b|?)(a|c)*。 – (a|c)*b(a|c)* b表示的集合是什么呢？它表示只含兩個(gè)b的符號(hào)串的集合。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 41 正規(guī)表達(dá)式 – 定義 ：如果兩個(gè)正規(guī)式 r與 t表示的正規(guī)集相同，則稱它們的等價(jià)的，記做 r=t。 – 正規(guī)式等價(jià)的例子如a|(ba)*= (ba)*|a，(a|b)=(b|a)。 定理 解釋 r|t = t|r | 的交換律 r|(s|t) = (r|s)|t r(st) = (rs)t 結(jié)合律 r(s|t) = rs | rt (r|s)t = rt | st 分配律 ?r = r? = r ?r = r? = r r | ? = r 吸收律 r* = (r | ?)* 閉包運(yùn)算和 ?之間的關(guān)系 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 42 正規(guī)表達(dá)式 ? 擴(kuò)展的正規(guī)式 （ 1）一個(gè)或多次重復(fù)：一元后綴算符“ +”表示一個(gè)或多次重復(fù)，即正規(guī)式 r+表示一個(gè)或多個(gè) r的串的集合。這樣， (0|1)+表示所有二進(jìn)制數(shù)字的集合，而 (0|1)*同時(shí)還包含了可串。 （ 2）字符集的范圍：對(duì)于字母或數(shù)字的集合，可以使用 a|b|...|z或0|1|...|9。更簡(jiǎn)潔的方式是用方括弧，用連接線表示范圍，這樣，上面的字母或數(shù)字就可以分別表示成 [az]和 [09]。類似的，a|b|c|d可以寫成 [ad]或者 [abcd]。標(biāo)識(shí)符是字母打頭的字母數(shù)字串，可以表示成 [AZaz][ AZaz09]*。 （ 3）零個(gè)或一個(gè)：一元后綴算符“ ?”表示零個(gè)或一個(gè)， r?是 r|?的縮寫。帶符號(hào)的整數(shù)可以寫成 (+|?)?[19][09]* 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 43 正規(guī)表達(dá)式 – 如果正規(guī)式很長(zhǎng)，可以給它命名，使它們可以像普通的符號(hào)一樣，在隨后的正規(guī)式中使用這些名字來(lái)引用相應(yīng)的正規(guī)式，以便得到簡(jiǎn)潔的正規(guī)式。 – 如果 r如是字母表 ?上的正規(guī)式，那么正規(guī)定義的形式是： name → r 。這樣，正規(guī)式 r的名字 name就可以像 ?中的符號(hào)一樣，在以后構(gòu)造 ?上正規(guī)式的時(shí)候使用。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 44 正規(guī)表達(dá)式 例 ： Pascal語(yǔ)言的標(biāo)識(shí)符集合是字母開(kāi)頭的字母數(shù)字串，下面就是這個(gè)集合的正規(guī)定義： letter → [A Zaz] digit → [0 9] identifier → letter( letter| digit )* 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 45 正規(guī)表達(dá)式 例 ： Pascal語(yǔ)言的數(shù)是 2022， +1998， ?，?6這樣的串，即由整數(shù)、小數(shù)和指數(shù)三個(gè)部分組成。小數(shù)和指數(shù)部分是可選的，其中指數(shù)標(biāo)記 E后面可以有 +或 ?，再跟上一個(gè)或多個(gè)數(shù)字，而小數(shù)點(diǎn)之后必須至少有一個(gè)數(shù)字。下面就是 Pascal語(yǔ)言的數(shù)的集合的正規(guī)定義： digit → [0 9] digits → digit digit* signed → + | ? fraction → (.digits)? exponent → (E(signed)?digits)? number → signed? digits fraction exponent 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 46 正規(guī)表達(dá)式 ? 正規(guī)表達(dá)式的實(shí)現(xiàn)和應(yīng)用 – 正規(guī)表達(dá)式實(shí)際上是描述和識(shí)別一組字符串的模板（模式），它包含字符、元符號(hào)（如表示重復(fù)的 *和選擇符 |）和一些具有特殊意義的符號(hào)。這個(gè)模板決定什么樣的字符串屬于某一個(gè)集合。 – 正規(guī)表達(dá)式在處理文本方面具有強(qiáng)大的能力，它在計(jì)算機(jī)領(lǐng)域的應(yīng)用不僅僅局限于構(gòu)造編譯器的詞法掃描器，其它著名的應(yīng)用還包括 UNIX操作系統(tǒng)的命令工具如 grep，處理復(fù)雜文本分析與操作的腳本語(yǔ)言 Perl， Tcl， Python， PHP和 awk以及通用程序開(kāi)發(fā)編輯器 emacs。 – 由于正規(guī)表達(dá)式的重要而廣泛的應(yīng)用， Java語(yǔ)言通過(guò)包 接支持。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 47 有限自動(dòng)機(jī) ?為什么引入有限自動(dòng)機(jī) – 確定的有限自動(dòng)機(jī)和不確定的有限自動(dòng)機(jī)都能識(shí)別正規(guī)集，即它們識(shí)別的語(yǔ)言正好就是正規(guī)式所能表達(dá)的語(yǔ)言，而且在識(shí)別語(yǔ)言的能力上，它們完全等價(jià)。 – 但是，實(shí)現(xiàn)這兩類有限狀態(tài)機(jī)的效率不同，用它們構(gòu)造的詞法分析器在識(shí)別語(yǔ)言中單詞記號(hào)的效率方面也有顯著的差別。 正規(guī)式 不確定的有限自動(dòng)機(jī) 確定的有限自動(dòng)機(jī) 詞法分析器 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 48 有限自動(dòng)機(jī) ?確定的有限自動(dòng)機(jī) DFA – 定義 ：一個(gè)確定的有限自動(dòng)機(jī) DFA M是五元組S, ?, T, s0, F，其中： （ 1） S是非空的有限的狀態(tài)集合； （ 2） ?是非空的輸入字母表； （ 3） T是部分單值映射 S??→ S ，又稱轉(zhuǎn)移函數(shù)；T(s1, a)= s2表示輸入符號(hào) a時(shí)，把狀態(tài) s1轉(zhuǎn)換到 s2，成為當(dāng)前狀態(tài)； （ 4） s0?S，是唯一的起始狀態(tài)； （ 5） F?S，是非空的終結(jié)狀態(tài)。 被 M接受或識(shí)別的語(yǔ)言，記做 L(M)，定義為字符串c1c2...的集合，其中每個(gè) ci??，并且存在狀態(tài)序列s1=T(s0, c1), s2=T(s1, c2), ... , sn=T(sn1, )， sn ?F。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 49 有限自動(dòng)機(jī) 例 ：一個(gè)有限自動(dòng)機(jī) DFA N= {A, B, C, D, E}, {+, ?, ., d}, T, A, {E}，其中 T的定義如下 : T(A, +)=B T(A, ?)=B T(A, )=C T(A, d)=D T(B, )=D T(B, d)=C T(C, )＝ E T(C, d)=C T(D, d)＝ E T(E, d)＝ E 狀態(tài) A是起始狀態(tài)， E是終結(jié)狀態(tài)。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 50 有限自動(dòng)機(jī) – 轉(zhuǎn)換函數(shù)可以用狀態(tài)轉(zhuǎn)換矩陣或狀態(tài)轉(zhuǎn)換表來(lái)表示，該表的行表示狀態(tài)，列對(duì)應(yīng)輸入的符號(hào)，表元素表示狀態(tài)轉(zhuǎn)移的狀態(tài)，空白元素對(duì)應(yīng)的二元組 狀態(tài)，符號(hào) 沒(méi)有定義。 + ? d A B B C D B D C C E C D E E E 例 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 51 有限自動(dòng)機(jī) – 一個(gè) DFA也可以表示成一個(gè)確定的狀態(tài)轉(zhuǎn)換圖，狀態(tài)轉(zhuǎn)換函數(shù) T(s1, a)=s2對(duì)應(yīng)了連接兩個(gè)結(jié)點(diǎn) s1和 s2，標(biāo)記為 a的有向弧。 +, ? C E d A D B d d d d 例 從狀態(tài) A到 B的轉(zhuǎn)換上的標(biāo)記“ +, ?”表示兩條從 A到 B的弧的標(biāo)記 +和 ?， 這是常用的簡(jiǎn)化方式。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 52 有限自動(dòng)機(jī) 定義 ：對(duì)于有限自動(dòng)機(jī) M的 ?*中的任何一個(gè)符號(hào)串 α，若存在一條從起始狀態(tài)到某一終結(jié)狀態(tài)的通路，且這條通路上所有弧的標(biāo)記符連成的串等于 α，則稱 α被 M識(shí)別（讀出或接受）。若起始狀態(tài)也是一個(gè)終結(jié)狀態(tài)，則空串 ?可以為 M接受。 DFA M所能識(shí)別的所有字的集合稱為 M識(shí)別的語(yǔ)言，記做 L(M)。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 53 有限自動(dòng)機(jī) 例如，考慮上述的有限自動(dòng)機(jī)，如果 d代表任意一個(gè)數(shù)字 0， 1， ...， 9，它能否接受符號(hào)串 30.、+.28和 ?？對(duì)于它們，可以分別給出從狀態(tài) A到終結(jié)狀態(tài) E的路徑： – 因而它們都是這個(gè) DFA N可以接受的數(shù)。 EEDBA ? ??? ??? ??? ??? ?? ? 82.EEECCCBA ? ??? ??? ??? ??? ??? ??? ??? ?? ? EEDA ? ??? ??? ??? ?? .03青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 54 有限自動(dòng)機(jī) – 定義 (a)：兩個(gè)有限自動(dòng)機(jī) M1和 M2是等價(jià)的，當(dāng)且僅當(dāng)它們識(shí)別相同的語(yǔ)言，即L(M1)=L(M2)。 – 定義 (b)：兩個(gè)有限自動(dòng)機(jī) M1和 M2是等價(jià)的，當(dāng)且僅當(dāng)對(duì)于每個(gè) M1接受的符號(hào)串 γ，M2接受 γ。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 55 有限自動(dòng)機(jī) ? 不確定的有限自動(dòng)機(jī) NFA – 定義：一個(gè)不確定的有限自動(dòng)機(jī) NFA M是五元組 S, ?, T, s0, F，其中： （ 1） S是非空的有限的狀態(tài)集合； （ 2） ?是非空的輸入字母表； （ 3） T是 S?(??{?})→ 2S （ S的冪集），它可以把一個(gè)狀態(tài)映射到一組狀態(tài) ； – T(s1, a)= s2表示輸入符號(hào) a時(shí)，把狀態(tài) s1轉(zhuǎn)換到 s2，成為當(dāng)前狀態(tài)； （ 4） s0?S，是唯一的起始狀態(tài)； （ 5） F?S，是非空的終結(jié)狀態(tài)。 被 M接