編譯原理第15章-參考資料

1、編譯原理 文法文法/ /正規(guī)式正規(guī)式/ /有限自動(dòng)機(jī)有限自動(dòng)機(jī) 基礎(chǔ)知識(shí)基礎(chǔ)知識(shí)課外材料課外材料(未未修過(guò)相關(guān)課程者參考修過(guò)相關(guān)課程者參考)編譯原理 形式語(yǔ)言概念形式語(yǔ)言概念 正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述文法文法/ /正規(guī)式正規(guī)式/ /有限自動(dòng)機(jī)有限自動(dòng)機(jī)基礎(chǔ)知識(shí)基礎(chǔ)知識(shí) 上下文無(wú)關(guān)文法及語(yǔ)言上下文無(wú)關(guān)文法及語(yǔ)言編譯原理形式語(yǔ)言概念形式語(yǔ)言概念 字母表字母表 （Alphabet）- 形式符號(hào)的集合形式符號(hào)的集合- 常用常用 表示表示 - 舉例舉例 英文字母表英文字母表 a, b, , z, A, B , , Z 漢字表漢字表 , 自自, , 動(dòng)動(dòng) , , 機(jī)機(jī), 化學(xué)元素表化學(xué)元素表 H,

2、 He, Li, ,Une = a, n, y, 任任,意意 編譯原理形式語(yǔ)言概念形式語(yǔ)言概念 字符串字符串 （String）- 字母表字母表 上的一個(gè)上的一個(gè)字符串字符串（串串），或稱為），或稱為 字字（word），為），為 中字符構(gòu)成的一個(gè)有限中字符構(gòu)成的一個(gè)有限 序列。序列。 空串空串（empty string）, 常用常用 表表 示，不包含任何字符。示，不包含任何字符。 - 字符串字符串 w 的的長(zhǎng)度長(zhǎng)度，記為，記為 w ，是包含在，是包含在 w 中字符的個(gè)數(shù)中字符的個(gè)數(shù) 舉例舉例 = 0， bbaba = 5編譯原理形式語(yǔ)言概念形式語(yǔ)言概念 字符串的字符串的連接連接（concaten

3、ation ）運(yùn)算）運(yùn)算- 設(shè)設(shè) x, y為串為串, 且且 x a1a2 am, y b1b2 bn, 則則 x 與與 y 的的連接連接 x y a1a2 am b1b2 bn- 連接運(yùn)算的連接運(yùn)算的性質(zhì)性質(zhì) ( x y ) z x（ y z ） x x x x y x + y 編譯原理形式語(yǔ)言概念形式語(yǔ)言概念 字母表上的運(yùn)算字母表上的運(yùn)算- 冪運(yùn)算冪運(yùn)算 設(shè)設(shè) 為字母表，為字母表，n 為任意自然數(shù)，為任意自然數(shù)， 定義（定義（1） 0 = （2）設(shè)）設(shè) x n-1，a ， 則則a x n （3） n 中的元素只能由（中的元素只能由（1）和）和（2） 生成生成- 閉包閉包 * * = = 0

4、0 1 1 2 2 - 閉包閉包 + + = = 1 1 2 2 3 3 編譯原理形式語(yǔ)言概念形式語(yǔ)言概念 語(yǔ)言語(yǔ)言 （Languages）- 概念概念 設(shè)設(shè) 為字母表，則任何集合為字母表，則任何集合 L * 是是字字 母表母表 上的上的一個(gè)一個(gè)語(yǔ)言語(yǔ)言 - 舉例舉例 , English, , words , any, 任意任意 - 比較比較 空語(yǔ)言空語(yǔ)言 與與僅含空字的語(yǔ)言僅含空字的語(yǔ)言 編譯原理形式語(yǔ)言概念形式語(yǔ)言概念 語(yǔ)言上的運(yùn)算語(yǔ)言上的運(yùn)算- 兩個(gè)語(yǔ)言兩個(gè)語(yǔ)言 L 和和 M 的的聯(lián)合聯(lián)合（union） L M = w w L w M - 兩個(gè)語(yǔ)言兩個(gè)語(yǔ)言 L 和和 M 的的連接連接（c

5、oncatenation） L M = w1w2 w1 L w2 M - 語(yǔ)言語(yǔ)言 L 的的閉包閉包（closure） L* = L0 L1 L2 = i 0 Li , 其中其中 L0 = ， L1 = L, L2 = LL, Ln = Ln-1L編譯原理形式語(yǔ)言概念形式語(yǔ)言概念 程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言- C 源程序的集合源程序的集合用用 * 表示表示 （ 為為 ASCII字符集）字符集）- L 表示由滿足表示由滿足 C 語(yǔ)言語(yǔ)言詞法規(guī)則詞法規(guī)則的單詞構(gòu)成的語(yǔ)的單詞構(gòu)成的語(yǔ)言言 - M表示由滿足表示由滿足 C 語(yǔ)言語(yǔ)言語(yǔ)法規(guī)則語(yǔ)法規(guī)則的源程序構(gòu)成的的源程序構(gòu)成的語(yǔ)語(yǔ) 言言 - S 表示由正確

6、的表示由正確的C語(yǔ)言源程序構(gòu)成的語(yǔ)言語(yǔ)言源程序構(gòu)成的語(yǔ)言 - 四者之間的關(guān)系四者之間的關(guān)系L *，M *，S *M L*, S L* S M編譯原理形式語(yǔ)言概念形式語(yǔ)言概念 幾個(gè)重要的幾個(gè)重要的形式語(yǔ)言類形式語(yǔ)言類編譯原理正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述 描述正規(guī)語(yǔ)言的形式工具描述正規(guī)語(yǔ)言的形式工具- 3 型（正規(guī)）文法型（正規(guī)）文法- 有限自動(dòng)機(jī)有限自動(dòng)機(jī)- 正規(guī)表達(dá)式正規(guī)表達(dá)式編譯原理 有限自動(dòng)機(jī)的有限自動(dòng)機(jī)的五要素五要素- 有限狀態(tài)集有限狀態(tài)集 - 有限輸入符號(hào)有限輸入符號(hào)集集 - 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù) - 一個(gè)開始狀態(tài)一個(gè)開始狀態(tài) - 一個(gè)終態(tài)集合一個(gè)終態(tài)集合q0q1q2q3Start01

7、101100正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 有限狀態(tài)集有限狀態(tài)集 - 有限輸入符號(hào)有限輸入符號(hào)集集 - 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù) - 一個(gè)開始狀態(tài)一個(gè)開始狀態(tài) - 一個(gè)終態(tài)集合一個(gè)終態(tài)集合 一個(gè)確定有限狀態(tài)自動(dòng)機(jī)一個(gè)確定有限狀態(tài)自動(dòng)機(jī) DFA (deterministic finite automata) 是一個(gè)五元組是一個(gè)五元組 A = (Q, , , q0 , F ). : Q Q q0 Q F Q 確定有限自動(dòng)機(jī)的形式定義確定有限自動(dòng)機(jī)的形式定義正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- Q = q0 , q1 , q2 , q3 - = 0, 1 - (q0 ,0) = q2 ,

8、(q0 ,1) = q1 (q1 ,0) = q3 , (q1 ,1) = q0 (q2 ,0) = q0 , (q2 ,1) = q3 (q3 ,0) = q1 , (q3 ,1) = q2 - q0 - F = q0 , q3 q0q1q2q3Start01101100 轉(zhuǎn)移圖表示的轉(zhuǎn)移圖表示的 DFA 正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 q0q1q2 q301q2q1q3q0q0q3q1q2- Q = q0 , q1 , q2 , q3 - = 0, 1 - (q0 ,0) = q2 , (q0 ,1) = q1 (q1 ,0) = q3 , (q1 ,1) = q0 (q2 ,0

9、) = q0 , (q2 ,1) = q3 (q3 ,0) = q1 , (q3 ,1) = q2 - q0 - F = q0 , q3 轉(zhuǎn)移表表示的轉(zhuǎn)移表表示的 DFA 正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q1q2q3q0 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q2q3q0q1 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q2q0q1q3 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q2q3q0q1 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其

10、描述編譯原理q1q2q3q0 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q1q3q0q2 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q1q0q2q3 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q1q2q3q0 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q1q3q0q2 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q1q2q3q0 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其

11、描述編譯原理q1q2q3q0 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q2q3q0q1 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q2q0q1q3 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q1q3q0q2 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q1q2q3q0 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q2q3q0q1 DFA如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其

12、描述編譯原理- 設(shè)一個(gè)設(shè)一個(gè) DFA A = (Q, , , q0 , F ) : Q Q - 擴(kuò)充定義擴(kuò)充定義 : Q * Q 對(duì)任何對(duì)任何q Q，定義：定義： 1 (q , ) = q 2 若若w = xa, 其中其中 x *, a , 則則 ( q , w) = ( ( q , x) , a) 擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串?dāng)U展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 q0q1q2 q301q2q1q3q0q0q3q1q2- 舉例舉例 (q0 , ) = q0 (q0 , 0) = (q0 , 0) = q2 (q0 , 00) = (q2 , 0) = q0 (q

13、0 , 001) = (q0 , 1) = q1 (q0 , 0010) = (q1 , 0) = q3Start01101100 擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串?dāng)U展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 設(shè)一個(gè)設(shè)一個(gè) DFA A = (Q, , , q0 , F ) - 定義定義 A 的語(yǔ)言：的語(yǔ)言： L(A) = w ( q0 , w) F - 可以證明，可以證明，如果存在如果存在一個(gè)一個(gè) DFA A = (Q, , , q0 , F )，滿足，滿足L = L(A) ， 則則 L 是一個(gè)正規(guī)語(yǔ)言是一個(gè)正規(guī)語(yǔ)言. DFA 的語(yǔ)言的語(yǔ)言正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述

14、編譯原理Startpr0, 10q1(1)Startp0, 11qr0, 1(2) 非確定有限自動(dòng)機(jī)舉例非確定有限自動(dòng)機(jī)舉例正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 有限狀態(tài)集有限狀態(tài)集 - 有限輸入符號(hào)有限輸入符號(hào)集集 - 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù) - 一個(gè)開始狀態(tài)一個(gè)開始狀態(tài) - 一個(gè)終態(tài)集合一個(gè)終態(tài)集合 一個(gè)非確定有限狀態(tài)自動(dòng)機(jī)一個(gè)非確定有限狀態(tài)自動(dòng)機(jī) NFA nondeterministicfinite automata) 是一個(gè)五元組是一個(gè)五元組 A = (Q, , , q0 , F ).q0 Q F Q- 與與 DFA 唯一不同之處唯一不同之處 : Q 2Q 非確定有限自動(dòng)機(jī)的形式定義非

15、確定有限自動(dòng)機(jī)的形式定義正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理Startpr0, 10q1(1)Startp0, 11qr0, 1(2)pq r0 q q q, r 1pq r0 p r r 1 p, q 轉(zhuǎn)移圖和轉(zhuǎn)移表表示的轉(zhuǎn)移圖和轉(zhuǎn)移表表示的NFA正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理Startp0, 11qr0, 1010100100111010 NFA 如何接受輸入符號(hào)串如何接受輸入符號(hào)串 正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 設(shè)一個(gè)設(shè)一個(gè) NFA A = (Q, , , q0 , F ) - : Q 2Q - 擴(kuò)充定義擴(kuò)充定義 : Q * 2Q - 對(duì)任何對(duì)任何q Q，定義

16、定義： 1 (q , ) = q 2 若若w = xa, 其中其中 x * , a , 并且假設(shè)并且假設(shè) ( q , x) = p1 , p2 , , pk , 則則 ( q , w) = ( pi , a ) i = 1k 擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串?dāng)U展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 舉例舉例 ( p , ) = p ( p , 0 ) = q ( p , 01 ) = q , r ( p , 010 ) = q ( p , 0100 ) = q ( p , 01001 ) = q , r pq r0 q q q, r 1Startpr0, 10q1 擴(kuò)

17、展轉(zhuǎn)移函數(shù)適合于輸入字符串?dāng)U展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 設(shè)一個(gè)設(shè)一個(gè) NFA A = (Q, , , q0 , F ) - 定義定義 A 的語(yǔ)言的語(yǔ)言： L(A) = w ( q0 , w) F - 設(shè)設(shè) L 是是 上的語(yǔ)言，上的語(yǔ)言，如果存在如果存在一個(gè)一個(gè) NFA A = (Q, , , q0 , F )，滿足滿足L = L(A) ，則則 可以證明可以證明 L 也也是一個(gè)正規(guī)語(yǔ)言是一個(gè)正規(guī)語(yǔ)言. NFA 的語(yǔ)言的語(yǔ)言正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 定理定理: L 是某個(gè)是某個(gè) DFA 的語(yǔ)言的語(yǔ)言, 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) L 也是某個(gè)也是某

18、個(gè) NFA 的語(yǔ)言的語(yǔ)言. - 證明思路證明思路: 分兩步證明分兩步證明. (1) 設(shè)設(shè) L 是某個(gè)是某個(gè) DFA D 的語(yǔ)言的語(yǔ)言, 則存在一個(gè)則存在一個(gè) NFA N , 滿足滿足 L(N) = L(D) = L; (2) 設(shè)設(shè) L 是某個(gè)是某個(gè) NFA N 的語(yǔ)言的語(yǔ)言, 則存在一個(gè)則存在一個(gè) DFA D , 滿足滿足 L(D) = L(N) = L; DFA 和和 NFA 的等價(jià)性的等價(jià)性正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 設(shè)設(shè) L 是某個(gè)是某個(gè) DFA D = (Q, , D , q0 , F ) 的語(yǔ)的語(yǔ) 言言, 則存在一個(gè)則存在一個(gè) NFA N = (Q, , N ,q0,

19、F ) , 其中其中 N定義為定義為 對(duì)對(duì)q Q 和和a , 若若 D (q,a) = p, 則則 N (q,a) = p. 可以證明可以證明: L(N) = L(D) = L. 從從 DFA 構(gòu)造等價(jià)的構(gòu)造等價(jià)的 NFA正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 設(shè)設(shè) L 是某個(gè)是某個(gè) NFA N = (QN, , N , q0 , FN) 的語(yǔ)言的語(yǔ)言, 則存在一個(gè)則存在一個(gè) DFA D = (QD, , D , q0 , FD ) , 其中其中 QD = S S QN 對(duì)對(duì) S QD 和和 a , D ( S , a ) = N (q,a) . FD = S S QN S FN 可以證明

20、可以證明: L(D) = L(N) = L.q S 從從 NFA 構(gòu)造等價(jià)的構(gòu)造等價(jià)的 DFA（子集構(gòu)造法）（子集構(gòu)造法）正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理pq r0 q q q, r 10 q 1 p q r p, q p, r q, r p, q, r q q, r q q, r q q q, r q q, r Startp0, 10q1q,r1010 子集構(gòu)造法舉例子集構(gòu)造法舉例正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理01 p p, q, r p p, q pq r0 p r r 1 p, q p p, q p, q p, r p, q, r p, r p, r p, q, r S

21、tartp1p,q10100p,q,rp,r01 子集構(gòu)造法舉例子集構(gòu)造法舉例正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4比較：比較：NFA without Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.0,1, . ,90,1, . ,9.q0q1q2q3q4q 5+, 帶帶 -轉(zhuǎn)移的非確定有限自動(dòng)機(jī)轉(zhuǎn)移的非確定有限自動(dòng)機(jī)( - NFA )舉例舉例正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 一個(gè)一個(gè) - NFA 是一個(gè)五元組是一個(gè)五元組 A

22、= (Q, , , q0 , F ). 有限狀態(tài)集有限狀態(tài)集 有限輸入符號(hào)集有限輸入符號(hào)集 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù) 一個(gè)開始狀態(tài)一個(gè)開始狀態(tài) 一個(gè)終態(tài)集合一個(gè)終態(tài)集合q0 Q F Q 與與 NFA 的不同之處的不同之處 : Q 2Q 帶帶 - 轉(zhuǎn)移的非確定有限自動(dòng)機(jī)（轉(zhuǎn)移的非確定有限自動(dòng)機(jī)（ - NFA） 的的形式定義形式定義正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4 q1 +,.0,1, ,9q0q1q2q3q4q5 q1 q2 q3 q3 q5 q3 q1,q4 轉(zhuǎn)移圖和轉(zhuǎn)移表表示

23、的轉(zhuǎn)移圖和轉(zhuǎn)移表表示的 - NFA正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理q1q0q2q3q5 ,+,q4- 該該 - NFA 可以接受的字符串如：可以接受的字符串如： 3.14 +.314 314. - NFA 如何接受輸入符號(hào)串如何接受輸入符號(hào)串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4- 狀態(tài)狀態(tài) q 的的 - 閉包，記為閉包，記為ECLOSE(q)，定義為從，定義為從 q 經(jīng)經(jīng) 所有的所有的 路徑可以到達(dá)的狀態(tài)（包括路徑可以到達(dá)的狀態(tài)（包括q自身），如：自身），如： EC

24、LOSE(q0) = q0,q1 ECLOSE(q2) = q2 ECLOSE(q3) = q3,q5 - 閉包（閉包（closure）正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 設(shè)設(shè) - NFA A = (Q, , , q0 , F )，q Q，ECLOSE(q) 為滿足如下條件的最小集：為滿足如下條件的最小集： （1）q ECLOSE(q)（2）if p ECLOSE(q) and r (p, ) , then r ECLOSE(q)- 對(duì)于右圖，有：對(duì)于右圖，有： ECLOSE(1) = 1,2,4,5,6,7 ECLOSE(2) = 2,4,5,6,7 ECLOSE(7) = 5,7

25、1235647abcStart - 閉包閉包正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 設(shè)一個(gè)設(shè)一個(gè) - NFA E = (Q, , , q0 , F ) - : Q 2Q - 擴(kuò)充定義擴(kuò)充定義 : Q * 2Q - 對(duì)任何對(duì)任何q Q，定義：定義： 1 (q , ) = ECLOSE(q ) 2 若若w = xa, 其中其中 x * , a , 假設(shè)假設(shè) ( q , x) = p1 , p2 , , pk , 并且并且 令令 ( pi , a ) = r1 , r2 , , rm ， 則則 ( q , w) = ECLOSE( rj ) i = 1kj = 1m 擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串

26、擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4- 舉例舉例 計(jì)算計(jì)算 (q0, 5.6) (q0, ) = ECLOSE( (q0) ) = q0,q1 (q0, 5) (q1, 5) = q1,q4 (q0, 5) = ECLOSE( (q1) ) ECLOSE( (q4) ) = q1,q4 (q1, .) (q4, .) = q2,q3 (q0, 5.) = ECLOSE( (q2) ) ECLOSE( (q3) ) = q2,q3 ,q5 (q2,

27、 6) (q3, 6) (q5, 6) = q3 (q0, 5.6) = ECLOSE( (q3) ) = q3 ,q5 擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串?dāng)U展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 設(shè)一個(gè)設(shè)一個(gè) - NFA E = (Q, , , q0 , F ) - 定義定義 E 的語(yǔ)言：的語(yǔ)言： L(E) = w ( q0 , w) F - 設(shè)設(shè) L 是是 上的語(yǔ)言，上的語(yǔ)言，如果存在如果存在一個(gè)一個(gè) -NFA E = (Q, , , q0 , F )，滿足，滿足L = L(E) ，則則 可以證明可以證明 L 也也是一個(gè)正規(guī)語(yǔ)言是一個(gè)正規(guī)語(yǔ)言. - NFA 的的 語(yǔ)

28、語(yǔ) 言言正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 定理定理: L 是某個(gè)是某個(gè) - NFA 的語(yǔ)言的語(yǔ)言, 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) L 也是某個(gè)也是某個(gè) DFA 的語(yǔ)言的語(yǔ)言. - 證明思路證明思路: 分兩步證明分兩步證明. (1) 設(shè)設(shè) L 是某個(gè)是某個(gè) DFA D 的語(yǔ)言的語(yǔ)言, 則存在一個(gè)則存在一個(gè) - NFA E , 滿足滿足 L(E) = L(D) = L; (2) 設(shè)設(shè) L 是某個(gè)是某個(gè) - NFA E 的語(yǔ)言的語(yǔ)言, 則存在則存在 一個(gè)一個(gè) DFA D , 滿足滿足 L(D) = L(E) = L. - NFA 與與 DFA 的等價(jià)性的等價(jià)性正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理-

29、 設(shè)設(shè) L 是某個(gè)是某個(gè) DFA D = (Q, , D , q0 , F ) 的語(yǔ)言的語(yǔ)言, 則存在一個(gè)則存在一個(gè) - NFA E = (Q, , E , q0 , FE ) , 其中其中 E 定義為定義為 對(duì)任何對(duì)任何q Q, E (q, ) = 對(duì)任何對(duì)任何q Q 和和a , 若若 D (q,a) = p, 則則 N (q,a) = p. 可以證明可以證明L(E) = L(D) = L 從從 DFA 構(gòu)造等價(jià)的構(gòu)造等價(jià)的 - NFA正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 設(shè)設(shè) L 是某個(gè)是某個(gè) - NFA E = (QE, , E , q0 , FE) 的語(yǔ)言的語(yǔ)言, 則則存存 在一

30、個(gè)在一個(gè) DFA D = (QD, , D , qD , FD ) , 其中其中 QD = S S QE S = ECLOSE(S) qD = ECLOSE(q0) FD = S S QD S FE 對(duì)對(duì) S QD 和和 a , 令令 S = p1 , p2 , , pk ， 并設(shè)并設(shè) E ( pi , a ) = r1 , r2 , , rm ， 則則 D ( S , a ) = ECLOSE( rj ) . 可以證明可以證明: L(D) = L(E) = L.i = 1kj = 1m 從從 - NFA 構(gòu)造等價(jià)的構(gòu)造等價(jià)的 DFA（修改的子集構(gòu)造法）（修改的子集構(gòu)造法）正規(guī)語(yǔ)言及其描述正規(guī)

31、語(yǔ)言及其描述編譯原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4Startq0 q1+,-q10,1, . , 9q1 q4.q20,1, . ,9.0,1, . ,9.q2 q3 q50,1, . ,9q3 q50,1, . ,90,1, . ,9 修改的子集構(gòu)造法舉例修改的子集構(gòu)造法舉例正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 用代數(shù)的方法用代數(shù)的方法表示正規(guī)語(yǔ)言表示正規(guī)語(yǔ)言 - 語(yǔ)義語(yǔ)義 作用于語(yǔ)言上的三種代數(shù)運(yùn)算作用于語(yǔ)言上的三種代數(shù)運(yùn)算 聯(lián)合聯(lián)合（union） 連接連接（concatenation） （星）（

32、星）閉包閉包（closure） - 語(yǔ)法語(yǔ)法 不同應(yīng)用有所不同，但都含有上述不同應(yīng)用有所不同，但都含有上述 三種代數(shù)運(yùn)算的表示形式；為方便起見(jiàn)，三種代數(shù)運(yùn)算的表示形式；為方便起見(jiàn)， 通常還需要引入一些助記符通常還需要引入一些助記符 正規(guī)表達(dá)式正規(guī)表達(dá)式正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理- 定義定義及及解釋解釋 設(shè)正規(guī)表達(dá)式設(shè)正規(guī)表達(dá)式E代表的語(yǔ)言為代表的語(yǔ)言為L(zhǎng)(E),歸納定義歸納定義正規(guī)表達(dá)式正規(guī)表達(dá)式如下：如下：歸納歸納1 和和 為正規(guī)表達(dá)式，且為正規(guī)表達(dá)式，且L( ) = 、 L( ) = 2 若若a 為任一字符，則為任一字符，則 a 為正規(guī)表達(dá)式，且為正規(guī)表達(dá)式，且L(a) =

33、a3 任一變量（通常大寫）任一變量（通常大寫）L 為正規(guī)表達(dá)式，代表任意語(yǔ)言為正規(guī)表達(dá)式，代表任意語(yǔ)言 1 若若 E 和和 F 為正規(guī)表達(dá)式，則為正規(guī)表達(dá)式，則E | F也為正規(guī)表達(dá)式，且也為正規(guī)表達(dá)式，且 滿足滿足 L( E | F ) = L( E ) L( F ) 2 若若 E 和和 F 為正規(guī)表達(dá)式，則為正規(guī)表達(dá)式，則 EF 也為正規(guī)表達(dá)式，且也為正規(guī)表達(dá)式，且 滿滿足足 L( EF ) = L( E ) L( F ) 基礎(chǔ)基礎(chǔ) 3 若若 E 為正規(guī)表達(dá)式，則為正規(guī)表達(dá)式，則 E* 也為正規(guī)表達(dá)式，且也為正規(guī)表達(dá)式，且 滿足滿足 L( E* ) = ( L( E ) ) * 4 若若

34、E 為正規(guī)表達(dá)式，則為正規(guī)表達(dá)式，則 ( E ) 也為正規(guī)表達(dá)也為正規(guī)表達(dá)式，且式，且 滿足滿足 L( ( E ) ) = L( E ) 正規(guī)表達(dá)式正規(guī)表達(dá)式（regular expression）正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理算符優(yōu)先級(jí)（算符優(yōu)先級(jí)（precedence）依次為）依次為- （ closure ）- 連接連接（concatenation）- |（ union ） 正規(guī)表達(dá)式算符優(yōu)先級(jí)正規(guī)表達(dá)式算符優(yōu)先級(jí)正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 設(shè)計(jì)表示如下語(yǔ)言的正規(guī)表達(dá)式：設(shè)計(jì)表示如下語(yǔ)言的正規(guī)表達(dá)式： 該語(yǔ)言中的每個(gè)字符串由該語(yǔ)言中的每個(gè)字符串由交替的交替的 0 和

35、和 1 構(gòu)成構(gòu)成- (01)* | (10)* | 0(10)* | 1(01)*- ( | 1) (01)* ( | 0) - ( | 0) (10)* ( | 1) 正規(guī)表達(dá)式舉例正規(guī)表達(dá)式舉例正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 有限自動(dòng)機(jī)與正規(guī)表達(dá)式的關(guān)系有限自動(dòng)機(jī)與正規(guī)表達(dá)式的關(guān)系結(jié)論結(jié)論: 正規(guī)表達(dá)式所表示的語(yǔ)言是正規(guī)語(yǔ)言正規(guī)表達(dá)式所表示的語(yǔ)言是正規(guī)語(yǔ)言.證明策略證明策略 -NFANFADFARE正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 從從有限自動(dòng)機(jī)有限自動(dòng)機(jī)構(gòu)造等價(jià)的正規(guī)表達(dá)式構(gòu)造等價(jià)的正規(guī)表達(dá)式思路（狀態(tài)消去法）思路（狀態(tài)消去法） : - 擴(kuò)展自動(dòng)機(jī)的概念，允許正規(guī)表達(dá)式

36、作為轉(zhuǎn)移擴(kuò)展自動(dòng)機(jī)的概念，允許正規(guī)表達(dá)式作為轉(zhuǎn)移弧弧 的標(biāo)記的標(biāo)記. 這樣，就有可能在消去某一中間狀態(tài)這樣，就有可能在消去某一中間狀態(tài) 時(shí)，保證自動(dòng)機(jī)能夠接受的字符串集合保持不變時(shí)，保證自動(dòng)機(jī)能夠接受的字符串集合保持不變. - 在消去某一中間狀態(tài)時(shí)，與其相關(guān)的轉(zhuǎn)移弧也在消去某一中間狀態(tài)時(shí)，與其相關(guān)的轉(zhuǎn)移弧也將將 同時(shí)消去，所造成的影響將通過(guò)修改從每一個(gè)前同時(shí)消去，所造成的影響將通過(guò)修改從每一個(gè)前 趨狀態(tài)到每一個(gè)后繼狀態(tài)的轉(zhuǎn)移弧標(biāo)記來(lái)彌補(bǔ)趨狀態(tài)到每一個(gè)后繼狀態(tài)的轉(zhuǎn)移弧標(biāo)記來(lái)彌補(bǔ). 正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 從從有限自動(dòng)機(jī)有限自動(dòng)機(jī)構(gòu)造等價(jià)的正規(guī)表達(dá)式構(gòu)造等價(jià)的正規(guī)表達(dá)式 （中間狀

37、態(tài)的消去）（中間狀態(tài)的消去）sSq1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+ Q1S* P1R1m+ Q1S* PmRkm+ QkS* PmRk1 + QkS* P1q1p1qkpm消去消去 s正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 從從有限自動(dòng)機(jī)有限自動(dòng)機(jī)構(gòu)造等價(jià)的正規(guī)表達(dá)式構(gòu)造等價(jià)的正規(guī)表達(dá)式步驟（狀態(tài)消去法）步驟（狀態(tài)消去法） : (1) 對(duì)每一終態(tài)對(duì)每一終態(tài)q，依次消去除，依次消去除 q 和初態(tài)和初態(tài) q0 之外的其它狀態(tài)之外的其它狀態(tài);StartRStartSTUR(2) 若若q q0，最終可得到一般形式如下左圖兩狀態(tài)自動(dòng)機(jī)，最終可得到一般形式如下左圖兩狀態(tài)自動(dòng)

38、機(jī)， 該自動(dòng)機(jī)對(duì)應(yīng)的正規(guī)表達(dá)式可表示為該自動(dòng)機(jī)對(duì)應(yīng)的正規(guī)表達(dá)式可表示為 ( R | SU*T )*SU*.(3) 若若q= q0，最終可得到如下右圖的自動(dòng)機(jī)，它對(duì)應(yīng)的正規(guī)，最終可得到如下右圖的自動(dòng)機(jī)，它對(duì)應(yīng)的正規(guī) 表達(dá)式可以表示為表達(dá)式可以表示為 R*.(4) 最終的正規(guī)表達(dá)式為每一終態(tài)對(duì)應(yīng)的最終的正規(guī)表達(dá)式為每一終態(tài)對(duì)應(yīng)的 正規(guī)表達(dá)式之和（并）正規(guī)表達(dá)式之和（并）.正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 從從有限自動(dòng)機(jī)有限自動(dòng)機(jī)構(gòu)造等價(jià)的正規(guī)表達(dá)式構(gòu)造等價(jià)的正規(guī)表達(dá)式- 狀態(tài)消去法舉例狀態(tài)消去法舉例A0,1StartBCD0,10,11正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 從從有限自動(dòng)

39、機(jī)有限自動(dòng)機(jī)構(gòu)造等價(jià)的正規(guī)表達(dá)式構(gòu)造等價(jià)的正規(guī)表達(dá)式- 狀態(tài)消去法舉例狀態(tài)消去法舉例對(duì)于終態(tài)對(duì)于終態(tài)D正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 從從有限自動(dòng)機(jī)有限自動(dòng)機(jī)構(gòu)造等價(jià)的正規(guī)表達(dá)式構(gòu)造等價(jià)的正規(guī)表達(dá)式- 狀態(tài)消去法舉例狀態(tài)消去法舉例對(duì)于終態(tài)對(duì)于終態(tài)C正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理對(duì)于終態(tài)對(duì)于終態(tài)C對(duì)于終態(tài)對(duì)于終態(tài)D D等價(jià)的正規(guī)表達(dá)式等價(jià)的正規(guī)表達(dá)式(0|1)*1(0|1) | (0|1)*1(0|1)(0|1) 從從有限自動(dòng)機(jī)有限自動(dòng)機(jī)構(gòu)造等價(jià)的正規(guī)表達(dá)式構(gòu)造等價(jià)的正規(guī)表達(dá)式- 狀態(tài)消去法舉例狀態(tài)消去法舉例正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 從正規(guī)表達(dá)式構(gòu)造等價(jià)的從正

40、規(guī)表達(dá)式構(gòu)造等價(jià)的 - NFA （歸納構(gòu)造過(guò)程（歸納構(gòu)造過(guò)程: : Thompson 構(gòu)造法構(gòu)造法）基礎(chǔ)基礎(chǔ):1 對(duì)于對(duì)于 ，構(gòu)造為構(gòu)造為 3 對(duì)于對(duì)于 a ，構(gòu)造為構(gòu)造為a2 對(duì)于對(duì)于 ，構(gòu)造構(gòu)造為為正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理歸納歸納:1 對(duì)于對(duì)于 R | S ，構(gòu)造為構(gòu)造為SR 正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述 從正規(guī)表達(dá)式構(gòu)造等價(jià)的從正規(guī)表達(dá)式構(gòu)造等價(jià)的 - NFA （歸納構(gòu)造過(guò)程（歸納構(gòu)造過(guò)程: : Thompson 構(gòu)造法構(gòu)造法）編譯原理歸納歸納:2 對(duì)于對(duì)于 RS ，構(gòu)造為構(gòu)造為RS R3 對(duì)于對(duì)于 R* ，構(gòu)造為構(gòu)造為 正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述 從正規(guī)表達(dá)式

41、構(gòu)造等價(jià)的從正規(guī)表達(dá)式構(gòu)造等價(jià)的 - NFA （歸納構(gòu)造過(guò)程（歸納構(gòu)造過(guò)程: : Thompson 構(gòu)造法構(gòu)造法）編譯原理 從正規(guī)表達(dá)式構(gòu)造等價(jià)的從正規(guī)表達(dá)式構(gòu)造等價(jià)的 - NFA 從正規(guī)表達(dá)式構(gòu)造等價(jià)的從正規(guī)表達(dá)式構(gòu)造等價(jià)的 - NFA舉例舉例:設(shè)正規(guī)表達(dá)式設(shè)正規(guī)表達(dá)式 1*0(0|1)*, 構(gòu)造等價(jià)構(gòu)造等價(jià)的的 -NFA.100|1 11* 正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 從正規(guī)表達(dá)式構(gòu)造等價(jià)的從正規(guī)表達(dá)式構(gòu)造等價(jià)的 - NFA舉例舉例:設(shè)正規(guī)表達(dá)式設(shè)正規(guī)表達(dá)式 1*0(0|1)*, 構(gòu)造等價(jià)構(gòu)造等價(jià)的的 -NFA.(0|1)*10 11001*0(0|1)* 正規(guī)語(yǔ)言及其描述正

42、規(guī)語(yǔ)言及其描述編譯原理 DFA 的化簡(jiǎn)的化簡(jiǎn)- 知識(shí)回顧：知識(shí)回顧：集合上的等價(jià)關(guān)系與劃集合上的等價(jià)關(guān)系與劃分分等價(jià)關(guān)系等價(jià)關(guān)系 設(shè)設(shè) Q 為一個(gè)集合，二元關(guān)系為一個(gè)集合，二元關(guān)系 R 是是 Q 上的一個(gè)上的一個(gè) 等價(jià)關(guān)系等價(jià)關(guān)系, 當(dāng)且僅當(dāng)滿足以下條件：當(dāng)且僅當(dāng)滿足以下條件： 1. 自反性自反性 對(duì)任何對(duì)任何a Q , aRa 成立；成立； 2. 對(duì)稱性對(duì)稱性 對(duì)任何對(duì)任何a,b Q , 如果如果 aRb 成立成立, 則有則有 bRa 成立；成立； 3. 傳遞性傳遞性 對(duì)任何對(duì)任何a,b,c Q , 如果如果 aRb 和和 bRc 成立成立, 則有則有 aRc 成立成立.正規(guī)語(yǔ)言及其描述正規(guī)

43、語(yǔ)言及其描述編譯原理 DFA 的化簡(jiǎn)的化簡(jiǎn)設(shè)設(shè) Q 為一個(gè)集合，為一個(gè)集合，R 是是 Q 上的一個(gè)上的一個(gè)等價(jià)關(guān)系等價(jià)關(guān)系, 由由 R 產(chǎn)產(chǎn)生的所有等價(jià)類（或塊）的集合構(gòu)成生的所有等價(jià)類（或塊）的集合構(gòu)成 Q 的一個(gè)的一個(gè)劃分劃分.- 注釋注釋 1. 等價(jià)類等價(jià)類 對(duì)任何對(duì)任何a Q , a 所在的塊用所在的塊用a表示表示, 定義為定義為 a = x | xRa ； 2. 每一元素都屬于唯一的塊每一元素都屬于唯一的塊 即滿足即滿足 （1） a Q a = Q ; 和和 （2）對(duì)任何）對(duì)任何a,b Q , 或者或者 a=b , 或者或者 a b= - 知識(shí)回顧：知識(shí)回顧：集合上的等價(jià)關(guān)系與劃集合

44、上的等價(jià)關(guān)系與劃分分正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 DFA 的化簡(jiǎn)的化簡(jiǎn)- DFA 狀態(tài)集合上的一個(gè)等價(jià)關(guān)狀態(tài)集合上的一個(gè)等價(jià)關(guān)系系設(shè)一個(gè)設(shè)一個(gè) DFA D = (Q, , , q0 , F ), 定義定義Q上的一個(gè)二上的一個(gè)二元關(guān)系元關(guān)系 R 為：為： 對(duì)任何對(duì)任何 p,q Q, pRq iff w *. ( (p,w) F (q,w) F )證明：證明：1. 自反性自反性 對(duì)任何對(duì)任何q Q , qRq 成立；成立； 2. 對(duì)稱性對(duì)稱性 對(duì)任何對(duì)任何p,q Q , pRq qRp 成立；成立；3. 傳遞性傳遞性 對(duì)任何對(duì)任何p,q,r Q , 設(shè)設(shè)pRq 和和 qRr 成立成立,

45、 即對(duì)任何即對(duì)任何w *, (p,w) F (q,w) F 和和 (q,w) F (r,w) F 成立；由此，也有成立；由此，也有 (p,w) F (r,w) F 成立成立. 所以所以，qRr 成立成立正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 DFA 的化簡(jiǎn)的化簡(jiǎn)- DFA 狀態(tài)集合上的一個(gè)等價(jià)關(guān)狀態(tài)集合上的一個(gè)等價(jià)關(guān)系系若若pRq, 稱稱 p 和和 q 等價(jià)等價(jià)（equivalent）. 若若p 和和q 不等不等價(jià)，則稱價(jià)，則稱 p 和和q 是是可區(qū)別的可區(qū)別的（distinguashable）.關(guān)系關(guān)系 R 對(duì)應(yīng)有限狀態(tài)集對(duì)應(yīng)有限狀態(tài)集 Q 的一個(gè)劃分；的一個(gè)劃分； 該劃分的每個(gè)塊是該劃分

46、的每個(gè)塊是 Q 的一個(gè)子集；的一個(gè)子集；同一劃分塊同一劃分塊中的所有狀態(tài)之間都是中的所有狀態(tài)之間都是相互等價(jià)相互等價(jià)的；的；分屬分屬不同劃分塊不同劃分塊的任何兩個(gè)狀態(tài)之間都是的任何兩個(gè)狀態(tài)之間都是可區(qū)別的可區(qū)別的.- DFA 的優(yōu)化的優(yōu)化 通過(guò)合并等價(jià)的（或不可區(qū)別的）狀通過(guò)合并等價(jià)的（或不可區(qū)別的）狀態(tài)態(tài). 關(guān)鍵：如何計(jì)算上述劃分？關(guān)鍵：如何計(jì)算上述劃分？正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 DFA 的化簡(jiǎn)的化簡(jiǎn)- 計(jì)算狀態(tài)集劃分的算計(jì)算狀態(tài)集劃分的算法法填表算法（填表算法（table-filling algorithm）基于如下遞歸基于如下遞歸地標(biāo)記可區(qū)別的狀態(tài)偶對(duì)的過(guò)程地標(biāo)記可區(qū)別的

47、狀態(tài)偶對(duì)的過(guò)程:（ (r,aw) = (p,w) , (s,aw) = (q,w) ）基礎(chǔ)基礎(chǔ) 如果如果 p 為終態(tài)，而為終態(tài)，而 q 為非終態(tài)，則為非終態(tài)，則 p 和和 q 標(biāo)標(biāo)記為可區(qū)別的；記為可區(qū)別的；歸納歸納 設(shè)設(shè) p 和和 q 已標(biāo)記為可區(qū)別的已標(biāo)記為可區(qū)別的, 如果狀態(tài)如果狀態(tài) r 和和 s 通過(guò)某個(gè)通過(guò)某個(gè) 輸入符號(hào)輸入符號(hào) a 可分別轉(zhuǎn)移到可分別轉(zhuǎn)移到 p 和和 q ，即，即 (r,a)=p , (s,a)=q , 則則 r 和和 s 也標(biāo)記為可區(qū)別的；也標(biāo)記為可區(qū)別的；這是因?yàn)椋哼@是因?yàn)椋喝羧?p 和和 q 可為字符串可為字符串 w 區(qū)別區(qū)別, 則則 r 和和 s可為字符串可

48、為字符串 aw 區(qū)別區(qū)別. 正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 DFA 的化簡(jiǎn)的化簡(jiǎn)- 填表算法舉例填表算法舉例212334455667xxxxxxxxxxxxx651Start3724aaaaaaabbbbbbb(1) 區(qū)別所有終態(tài)和非終態(tài)區(qū)別所有終態(tài)和非終態(tài)(2) 區(qū)別區(qū)別(1,3), (1,4), (2,3), (2,4), (5,6), (5,7)xxxxx(3) 區(qū)別區(qū)別 (3,4)x(4) 結(jié)束結(jié)束. 劃分結(jié)果：劃分結(jié)果：1,2, 3, 4, 5, 6,7正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 DFA 的最小化的最小化- 可以證明：可以證明： 通過(guò)以下通過(guò)以下步驟步驟 ，可

49、以得到狀態(tài)數(shù)最少的等價(jià)，可以得到狀態(tài)數(shù)最少的等價(jià)DFA 1. 刪除所有從開始狀態(tài)不可到達(dá)的狀態(tài)及與其相關(guān)的邊刪除所有從開始狀態(tài)不可到達(dá)的狀態(tài)及與其相關(guān)的邊, 設(shè)所得到的設(shè)所得到的 DFA 為為 A = (Q, , , q0 , F ) ； 2. 使用填表算法找出所有等價(jià)的狀態(tài)偶對(duì)；使用填表算法找出所有等價(jià)的狀態(tài)偶對(duì)； 3. 根據(jù)根據(jù) 2 的結(jié)果計(jì)算當(dāng)前狀態(tài)集合的劃分塊，每一劃分的結(jié)果計(jì)算當(dāng)前狀態(tài)集合的劃分塊，每一劃分 塊中的狀態(tài)相互之間等價(jià)，而不同劃分塊中的狀態(tài)之塊中的狀態(tài)相互之間等價(jià)，而不同劃分塊中的狀態(tài)之 間都是可區(qū)別的間都是可區(qū)別的. 包含狀態(tài)包含狀態(tài) q 的劃分塊用的劃分塊用 q 表示

50、表示. 4. 構(gòu)造與構(gòu)造與 A 等價(jià)的等價(jià)的 DFA B = (QB, , B, q0, FB ) , 其中其中 QB= q | q Q, FB = q | q F, B(q ,a)= (q,a)正規(guī)語(yǔ)言及其描述正規(guī)語(yǔ)言及其描述編譯原理 DFA 的最小化的最小化- 舉例舉例 651Start3724aaaaaaabbbbbbb 劃分結(jié)果：劃分結(jié)果： 1, 2 , 3, 4, 5, 6, 7 651Start34aaaabbbbba- 最小化結(jié)最小化結(jié)果果 等價(jià)的狀態(tài)偶對(duì)為：等價(jià)的狀態(tài)偶對(duì)為： （1, 2）,（6, 7） 新的狀態(tài)集合：新的狀態(tài)集合： 1, 3, 4, 5, 6正規(guī)語(yǔ)言及其描述正

51、規(guī)語(yǔ)言及其描述編譯原理上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法(context-free grammars)- 例子例子 E EOE E (E) E v E d O O 編譯原理 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法的的四個(gè)基本要素四個(gè)基本要素 1. 終結(jié)符終結(jié)符(terminals)的集合的集合 有限符號(hào)集，相當(dāng)于字母表有限符號(hào)集，相當(dāng)于字母表E EOEE (E)E vE dO O 終結(jié)符終結(jié)符 2. 非終結(jié)符非終結(jié)符(nonterminals)的集合的集合 有限變量符號(hào)的集合有限變量符號(hào)的集合非終結(jié)符非終結(jié)符 3. 開始符號(hào)開始符號(hào)(start symbol) 一

52、個(gè)特殊的非終結(jié)符一個(gè)特殊的非終結(jié)符開始符號(hào)開始符號(hào) 4. 產(chǎn)生式產(chǎn)生式(productions)的集合的集合 形如：形如： 產(chǎn)生式集合產(chǎn)生式集合上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理 上下文無(wú)關(guān)文法的形式定義上下文無(wú)關(guān)文法的形式定義終結(jié)符的集合終結(jié)符的集合 一個(gè)上下文無(wú)關(guān)文法一個(gè)上下文無(wú)關(guān)文法 CFG (context-free grammars) 是一個(gè)四元組是一個(gè)四元組 G = (VN, VT, P , S ).非終結(jié)符的集合非終結(jié)符的集合產(chǎn)生式的集合產(chǎn)生式的集合開始符號(hào)開始符號(hào)滿足滿足 VN VT = S VN產(chǎn)生式形如產(chǎn)生式形如 A , 其中其中 A VN, (VN VT

53、)*上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法舉例舉例CFG Gexp = (E,O, (, ), , v, d , P , E ). 其中產(chǎn)式集合其中產(chǎn)式集合 P 為為 E EOE E (E) E v E d O O 上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理 產(chǎn)生式集合的縮寫記法產(chǎn)生式集合的縮寫記法形如形如 A 1, A 2, , A n 的產(chǎn)生式的產(chǎn)生式集合可簡(jiǎn)縮記為集合可簡(jiǎn)縮記為 A 1 2 n ，如，如 E EOEE (E)E vE dO O E EOE (E) v dO 上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理 歸約與推

54、導(dǎo)歸約與推導(dǎo)- 用于推理字符串是否屬于文法所定義的語(yǔ)用于推理字符串是否屬于文法所定義的語(yǔ)言言 一種是自下而上的方法，稱為一種是自下而上的方法，稱為遞歸推理遞歸推理 （recursive inference），遞歸推理的過(guò)程），遞歸推理的過(guò)程 習(xí)稱為習(xí)稱為歸約歸約；另一種是自上而下的方法，稱；另一種是自上而下的方法，稱 為為推導(dǎo)推導(dǎo)（derivation）.- 歸約過(guò)程歸約過(guò)程 將產(chǎn)生式的右部（將產(chǎn)生式的右部（body）替換）替換為為 產(chǎn)生式的左部（產(chǎn)生式的左部（ head ）.- 推導(dǎo)過(guò)程推導(dǎo)過(guò)程 將產(chǎn)生式的左部（將產(chǎn)生式的左部（ head ）替換）替換 為產(chǎn)生式的右部（為產(chǎn)生式的右部（ bo

55、dy ）.上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理 歸約過(guò)程舉例歸約過(guò)程舉例對(duì)于對(duì)于CFG Gexp = (E,O, (, ), , v, d , P , E ) ，P 為為 （1）E EOE （2） E (E) （3） E v （4） E d （5） O （6） O 遞歸推理出字符串遞歸推理出字符串 v (vd) 的一個(gè)歸約過(guò)程為的一個(gè)歸約過(guò)程為v (vd)（4）v (vE)（6）vO(vE)（3）vO(EE)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）E上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理 推導(dǎo)過(guò)程舉例推導(dǎo)過(guò)程舉例對(duì)于對(duì)于CFG Gexp

56、= (E,O, (, ), , v, d , P , E ) ，P 為為 （1）E EOE （2） E (E) （3） E v （4） E d （5） O （6） O 遞歸推理出字符串遞歸推理出字符串 v (vd) 的一個(gè)推導(dǎo)過(guò)程為的一個(gè)推導(dǎo)過(guò)程為v (vd)（4）v (vE)（6）E (E)（3）（1）v (EOE)（5）（3）EOE（1）EE E（2）v (E)v (EE)上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理G 推導(dǎo)關(guān)系推導(dǎo)關(guān)系 對(duì)于對(duì)于 CFG G = (VN, VT, P , S )，上述推導(dǎo)過(guò)程可用關(guān)系，上述推導(dǎo)過(guò)程可用關(guān)系 描述描述. 設(shè)設(shè) , (VN VT)*，A

57、 是一個(gè)產(chǎn)生式，則定義是一個(gè)產(chǎn)生式，則定義 A . 若若 G 在上下文中是明確的，則簡(jiǎn)記為在上下文中是明確的，則簡(jiǎn)記為 A .G 擴(kuò)展推導(dǎo)關(guān)系到自反傳遞閉包擴(kuò)展推導(dǎo)關(guān)系到自反傳遞閉包 定義上述關(guān)系的自反傳遞閉包，記為定義上述關(guān)系的自反傳遞閉包，記為 ，可歸納定義如下：，可歸納定義如下： 基礎(chǔ)基礎(chǔ) 對(duì)任何對(duì)任何 (VN VT)*，滿足滿足 . 歸納歸納 設(shè)設(shè) , , (VN VT)*，若，若 ， 成立，則成立，則 . GGGGG 上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理 最左推導(dǎo)最左推導(dǎo) (leftmost derivations) 若推導(dǎo)過(guò)程的每一步總是替換出現(xiàn)在最左邊的非終結(jié)符，

58、若推導(dǎo)過(guò)程的每一步總是替換出現(xiàn)在最左邊的非終結(jié)符， 則這樣的推導(dǎo)稱為則這樣的推導(dǎo)稱為最左推導(dǎo)最左推導(dǎo). 為方便，最左推導(dǎo)關(guān)系用為方便，最左推導(dǎo)關(guān)系用 表示，其自反傳遞閉包用表示，其自反傳遞閉包用表示表示. 如對(duì)于文法如對(duì)于文法Gexp ，下面是關(guān)于，下面是關(guān)于 v (vd) 的一個(gè)最左推導(dǎo)的一個(gè)最左推導(dǎo)： lmlmE EOEE (E)E vE dO O v (vd)v (vE)v (EOE)EOEEv (E)vOEv Ev (vOE) lm lm lm lm lm lm lm lm上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理 最右推導(dǎo)最右推導(dǎo) (rightmost derivation

59、s) 若推導(dǎo)過(guò)程的每一步總是替換出現(xiàn)在最右邊的非終結(jié)符，若推導(dǎo)過(guò)程的每一步總是替換出現(xiàn)在最右邊的非終結(jié)符， 則這樣的推導(dǎo)稱為則這樣的推導(dǎo)稱為最右推導(dǎo)最右推導(dǎo). 為方便，最右推導(dǎo)關(guān)系用為方便，最右推導(dǎo)關(guān)系用 表示，其自反傳遞閉包用表示，其自反傳遞閉包用表示表示. 如對(duì)于文法如對(duì)于文法Gexp ，下面是關(guān)于，下面是關(guān)于 v (vd) 的一個(gè)最右推導(dǎo)的一個(gè)最右推導(dǎo)： rmrmE EOEE (E)E vE dO O v (vd)E (vd)EO(Ed)EOEEEO(EOd)EO(E)EO(EOE)EO(vd) rm rm rm rm rm rm rm rm上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編

60、譯原理 句型句型 (sentential forms) 設(shè)設(shè) CFG G = (VN, VT, P , S )，稱，稱 (VN VT)* 為為 G 的一個(gè)的一個(gè)句型句型，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng) S . 若若 S ，則，則 是一個(gè)是一個(gè)左句型左句型; 若若 S ，則，則 是一個(gè)是一個(gè)右句型右句型. 若句型若句型 VT* ，則稱，則稱 為一個(gè)為一個(gè)句子句子（sentence）. lmrm 上下文無(wú)關(guān)語(yǔ)言及其描述上下文無(wú)關(guān)語(yǔ)言及其描述編譯原理 上下文無(wú)關(guān)文法的語(yǔ)言上下文無(wú)關(guān)文法的語(yǔ)言 設(shè)設(shè) CFG G = (VN, VT , P , S )，定義，定義 G 的語(yǔ)言為的語(yǔ)言為 L(G) = w w VT*