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

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

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

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

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

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

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

7、101100正規(guī)語言及其描述正規(guī)語言及其描述編譯原理- 有限狀態(tài)集有限狀態(tài)集 - 有限輸入符號有限輸入符號集集 - 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù) - 一個開始狀態(tài)一個開始狀態(tài) - 一個終態(tài)集合一個終態(tài)集合 一個確定有限狀態(tài)自動機一個確定有限狀態(tài)自動機 DFA (deterministic finite automata) 是一個五元組是一個五元組 A = (Q, , , q0 , F ). : Q Q q0 Q F Q 確定有限自動機的形式定義確定有限自動機的形式定義正規(guī)語言及其描述正規(guī)語言及其描述編譯原理- 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ī)語言及其描述正規(guī)語言及其描述編譯原理 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ī)語言及其描述正規(guī)語言及其描述編譯原理q1q2q3q0 DFA如何接受輸入符號串如何接受輸入符號串正規(guī)語言及其描述正規(guī)語言及其描述編譯原理q2q3q0q1 DFA如何接受輸入符號串如何接受輸入符號串正規(guī)語言及其描述正規(guī)語言及其描述編譯原理q2q0q1q3 DFA如何接受輸入符號串如何接受輸入符號串正規(guī)語言及其描述正規(guī)語言及其描述編譯原理q2q3q0q1 DFA如何接受輸入符號串如何接受輸入符號串正規(guī)語言及其描述正規(guī)語言及其

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

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

12、描述編譯原理- 設一個設一個 DFA A = (Q, , , q0 , F ) : Q Q - 擴充定義擴充定義 : Q * Q 對任何對任何q Q，定義：定義： 1 (q , ) = q 2 若若w = xa, 其中其中 x *, a , 則則 ( q , w) = ( ( q , x) , a) 擴展轉(zhuǎn)移函數(shù)適合于輸入字符串擴展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語言及其描述正規(guī)語言及其描述編譯原理 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 擴展轉(zhuǎn)移函數(shù)適合于輸入字符串擴展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語言及其描述正規(guī)語言及其描述編譯原理- 設一個設一個 DFA A = (Q, , , q0 , F ) - 定義定義 A 的語言：的語言： L(A) = w ( q0 , w) F - 可以證明，可以證明，如果存在如果存在一個一個 DFA A = (Q, , , q0 , F )，滿足，滿足L = L(A) ， 則則 L 是一個正規(guī)語言是一個正規(guī)語言. DFA 的語言的語言正規(guī)語言及其描述正規(guī)語言及其描述

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

15、確定有限自動機的形式定義正規(guī)語言及其描述正規(guī)語言及其描述編譯原理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ī)語言及其描述正規(guī)語言及其描述編譯原理Startp0, 11qr0, 1010100100111010 NFA 如何接受輸入符號串如何接受輸入符號串 正規(guī)語言及其描述正規(guī)語言及其描述編譯原理- 設一個設一個 NFA A = (Q, , , q0 , F ) - : Q 2Q - 擴充定義擴充定義 : Q * 2Q - 對任何對任何q Q，定義

16、定義： 1 (q , ) = q 2 若若w = xa, 其中其中 x * , a , 并且假設并且假設 ( q , x) = p1 , p2 , , pk , 則則 ( q , w) = ( pi , a ) i = 1k 擴展轉(zhuǎn)移函數(shù)適合于輸入字符串擴展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語言及其描述正規(guī)語言及其描述編譯原理- 舉例舉例 ( 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 擴

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

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

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

20、可以證明: L(D) = L(N) = L.q S 從從 NFA 構造等價的構造等價的 DFA（子集構造法）（子集構造法）正規(guī)語言及其描述正規(guī)語言及其描述編譯原理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 子集構造法舉例子集構造法舉例正規(guī)語言及其描述正規(guī)語言及其描述編譯原理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 子集構造法舉例子集構造法舉例正規(guī)語言及其描述正規(guī)語言及其描述編譯原理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)移的非確定有限自動機轉(zhuǎn)移的非確定有限自動機( - NFA )舉例舉例正規(guī)語言及其描述正規(guī)語言及其描述編譯原理 一個一個 - NFA 是一個五元組是一個五元組 A

22、= (Q, , , q0 , F ). 有限狀態(tài)集有限狀態(tài)集 有限輸入符號集有限輸入符號集 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù) 一個開始狀態(tài)一個開始狀態(tài) 一個終態(tài)集合一個終態(tài)集合q0 Q F Q 與與 NFA 的不同之處的不同之處 : Q 2Q 帶帶 - 轉(zhuǎn)移的非確定有限自動機（轉(zhuǎn)移的非確定有限自動機（ - NFA） 的的形式定義形式定義正規(guī)語言及其描述正規(guī)語言及其描述編譯原理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ī)語言及其描述正規(guī)語言及其描述編譯原理q1q0q2q3q5 ,+,q4- 該該 - NFA 可以接受的字符串如：可以接受的字符串如： 3.14 +.314 314. - NFA 如何接受輸入符號串如何接受輸入符號串正規(guī)語言及其描述正規(guī)語言及其描述編譯原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4- 狀態(tài)狀態(tài) q 的的 - 閉包，記為閉包，記為ECLOSE(q)，定義為從，定義為從 q 經(jīng)經(jīng) 所有的所有的 路徑可以到達的狀態(tài)（包括路徑可以到達的狀態(tài)（包括q自身），如：自身），如： EC

24、LOSE(q0) = q0,q1 ECLOSE(q2) = q2 ECLOSE(q3) = q3,q5 - 閉包（閉包（closure）正規(guī)語言及其描述正規(guī)語言及其描述編譯原理- 設設 - 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)- 對于右圖，有：對于右圖，有： ECLOSE(1) = 1,2,4,5,6,7 ECLOSE(2) = 2,4,5,6,7 ECLOSE(7) = 5,7

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

26、擴展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語言及其描述正規(guī)語言及其描述編譯原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4- 舉例舉例 計算計算 (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 擴展轉(zhuǎn)移函數(shù)適合于輸入字符串擴展轉(zhuǎn)移函數(shù)適合于輸入字符串正規(guī)語言及其描述正規(guī)語言及其描述編譯原理- 設一個設一個 - NFA E = (Q, , , q0 , F ) - 定義定義 E 的語言：的語言： L(E) = w ( q0 , w) F - 設設 L 是是 上的語言，上的語言，如果存在如果存在一個一個 -NFA E = (Q, , , q0 , F )，滿足，滿足L = L(E) ，則則 可以證明可以證明 L 也也是一個正規(guī)語言是一個正規(guī)語言. - NFA 的的 語

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

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

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

31、語言及其描述編譯原理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 修改的子集構造法舉例修改的子集構造法舉例正規(guī)語言及其描述正規(guī)語言及其描述編譯原理- 用代數(shù)的方法用代數(shù)的方法表示正規(guī)語言表示正規(guī)語言 - 語義語義 作用于語言上的三種代數(shù)運算作用于語言上的三種代數(shù)運算 聯(lián)合聯(lián)合（union） 連接連接（concatenation） （星）（

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47、狀態(tài)偶對的過程:（ (r,aw) = (p,w) , (s,aw) = (q,w) ）基礎基礎 如果如果 p 為終態(tài)，而為終態(tài)，而 q 為非終態(tài)，則為非終態(tài)，則 p 和和 q 標標記為可區(qū)別的；記為可區(qū)別的；歸納歸納 設設 p 和和 q 已標記為可區(qū)別的已標記為可區(qū)別的, 如果狀態(tài)如果狀態(tài) r 和和 s 通過某個通過某個 輸入符號輸入符號 a 可分別轉(zhuǎn)移到可分別轉(zhuǎn)移到 p 和和 q ，即，即 (r,a)=p , (s,a)=q , 則則 r 和和 s 也標記為可區(qū)別的；也標記為可區(qū)別的；這是因為：這是因為：若若 p 和和 q 可為字符串可為字符串 w 區(qū)別區(qū)別, 則則 r 和和 s可為字符串可

48、為字符串 aw 區(qū)別區(qū)別. 正規(guī)語言及其描述正規(guī)語言及其描述編譯原理 DFA 的化簡的化簡- 填表算法舉例填表算法舉例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) 結束結束. 劃分結果：劃分結果：1,2, 3, 4, 5, 6,7正規(guī)語言及其描述正規(guī)語言及其描述編譯原理 DFA 的最小化的最小化- 可以證明：可以證明： 通過以下通過以下步驟步驟 ，可

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

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

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

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

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

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

55、dy ）.上下文無關語言及其描述上下文無關語言及其描述編譯原理 歸約過程舉例歸約過程舉例對于對于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) 的一個歸約過程為的一個歸約過程為v (vd)（4）v (vE)（6）vO(vE)（3）vO(EE)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）E上下文無關語言及其描述上下文無關語言及其描述編譯原理 推導過程舉例推導過程舉例對于對于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) 的一個推導過程為的一個推導過程為v (vd)（4）v (vE)（6）E (E)（3）（1）v (EOE)（5）（3）EOE（1）EE E（2）v (E)v (EE)上下文無關語言及其描述上下文無關語言及其描述編譯原理G 推導關系推導關系 對于對于 CFG G = (VN, VT, P , S )，上述推導過程可用關系，上述推導過程可用關系 描述描述. 設設 , (VN VT)*，A

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

58、若推導過程的每一步總是替換出現(xiàn)在最左邊的非終結符， 則這樣的推導稱為則這樣的推導稱為最左推導最左推導. 為方便，最左推導關系用為方便，最左推導關系用 表示，其自反傳遞閉包用表示，其自反傳遞閉包用表示表示. 如對于文法如對于文法Gexp ，下面是關于，下面是關于 v (vd) 的一個最左推導的一個最左推導： 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上下文無關語言及其描述上下文無關語言及其描述編譯原理 最右推導最右推導 (rightmost derivation

59、s) 若推導過程的每一步總是替換出現(xiàn)在最右邊的非終結符，若推導過程的每一步總是替換出現(xiàn)在最右邊的非終結符， 則這樣的推導稱為則這樣的推導稱為最右推導最右推導. 為方便，最右推導關系用為方便，最右推導關系用 表示，其自反傳遞閉包用表示，其自反傳遞閉包用表示表示. 如對于文法如對于文法Gexp ，下面是關于，下面是關于 v (vd) 的一個最右推導的一個最右推導： 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上下文無關語言及其描述上下文無關語言及其描述編

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