《形式語言基礎》PPT課件.ppt

《《形式語言基礎》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《形式語言基礎》PPT課件.ppt（19頁珍藏版）》請在裝配圖網(wǎng)上搜索。

編譯程序的設計原理與實現(xiàn),如何讓計算機 認識、理解 和 執(zhí)行 高級程序設計語言 ？,,,第 2 章 形式語言基礎,計算機處理語言，首先應考慮語言的形式化、規(guī) 范化，使其具有可計算性和可操作性；這就是形式語 言理論研究的問題。 形式語言誕生于1956年，由chomsky創(chuàng)立。通常， 語言研究至少涉及三個方面：語法、語義和語用； 這里僅側(cè)重于語法的研究。,※ 形式語言的基本觀點是 ： 語言是符號串之集合！,,※ 形式語言理論研究的基本問題是：,研究符號串集合的表示方法、結(jié)構特性,以及運算規(guī)律。,【前 言】,,,【內(nèi)容提要】,,第 2 章 形式語言基礎,2.1 形式語言是符號串集合 2.2 形式語言是由文法定義的 2.3 主要語法成分的定義 2.4 兩類特性文法 2.5 文法變換方法 2.6 關于形式語言的分類問題,,,字母表 -- 元素(符號)的非空有限集合； 符號串 -- 符號的有限序列； 符號串集合 -- 有限個或者無限個符號串組成的集合； 規(guī) 則 -- 以某種形式表達的在一定范圍內(nèi)共同遵守的章程和制度；這里，指符號串的組成規(guī)則。,2.1 形式語言是符號串集合,【形式語言】是字母表上的符號，按一定的 規(guī)則組成的所有符號串集合；其中的每個符號串 稱為句子。,【名詞解釋】：,三要素！,,,,【例2.1】 L1={ 00,01,10,11 }; 字母表∑1= {0,1}, 句子有：00,01,10,11,【注】 ⑴ b0=?（epsilon空符號串）,b1=b,b2=bb,b3=bbb,… ⑵ L1 為有限語言; L2 為無限語言。,形式語言概念示例：,【例2.2】 L2={ abmc,bn | m0,n≥0 } 字母表∑2= {a,b,c}, 句型1: abmc , 有句子： abc, abbc, abbbc,… 句型2: bn ; 有句子： ?, b, bb, bbb,…,兩個語言！,,,,,1. 連接：?.? = ?? 如 a.b=ab,2.1.1 符號串(集合)的運算,3. 方冪： ?n = ?? … ? = ??n-1 = ?n-1?,,4. 閉包：,n個,Ⅰ. 符號串的運算,設 ? , ? 為兩個符號串，則：,? 的正閉包： ?+ = ?1|?2|…|?n|…,? 的星閉包： ?* = ?0|?1|?2|…|?n|…,※ ?0 =? (空符號串) 什麼符號也沒有的符號串 ！,,?1= ? ； ?2 = ?? ；…,2. 或： ?|?= ? (或者 ?）,,這是一種 泛指！,2.1.1 符號串(集合)的運算(續(xù)1),,【例】：,⑵ ab|cd = ab（或者 cd ）,⑴ abc.de= abcde,⑶ (a|b)1 =(a|b)= a|b,(a|b)* =(a|b)0 |(a|b)1 |(a|b)2 |…,(a|b)2 =(a|b)(a|b)=aa|ab|ba|bb,…,即：(a|b)* = (a|b)n ，n≥0,同理： (a|b)+ = (a|b)n ，n＞0,※ 符號串運算示例,,泛指： 由a，b組成的 任意符號串！ （包括空串）,,,1.乘積： AB={xy |x?A 且 y?B},2.1.1 符號串(集合)的運算(續(xù)2),4.閉包： A 的正閉包： A+ = A1∪A2∪…∪An∪… A 的星閉包： A* = A0∪A1∪A2∪…∪An∪…,設 A 和 B 為兩個符號串集合，則：,,3.方冪： An = AA…A = AAn-1 = An-1A,,n個,※ A0 ={?};,A1 =A ; A2 =AA ; A3 =AAA ; …,Ⅱ. 符號串集合的運算,,,符號串集合運算示例：,【例2.3】 設 A={a,b},B={c,d} 則 A+B={a,b,c,d} 則 AB={xy|x?A,y?B}={ac,ad,bc,bd},【例2.4】 設 A={a} 則 A* = A0∪A1∪A2∪…∪An∪… ={?}+{a}+{aa}+{aaa}+… ={?,a,aa,aaa,…} ={an|n≥0},,【例2.5】 設 A={a，b}， A* = ? ∵ A* = A0∪A1∪A2∪…∪An∪… A0 ={?}; A1 = A ={a，b}; A2 = A.A={a，b}.{a，b}={aa,ab,ba,bb}; A3 = A.A2={a，b}.{aa,ab,ba,bb} ={aaa,aab,aba,abb,baa,bab,bba,bbb}; … ∴ A* = { x | x=(a|b)n ，n≥0 },符號串集合運算示例(續(xù))：,推論：若 A為任一字母表,則 A* 就是該字母 表上的所有符號串(包括空串)的集合。,,,,⑴ S,A — 定義的對象(S 句子,最大的定義對象，又 稱為開始符號; A為句型aAc的短語）， ⑵ a,b,c -- 為字母表∑中的符號;ε- 空符號串。 ⑶ - ,| -- 為描述符號( - 定義為; | 或者是）,2.1.2 符號串集合的文法描述,【例2.5】 L ={ abnc | n≥0 }， 字母表：∑= {a,b,c}； 展開：L ={ac,abc,abbc,abbbc,… },右圖給出的表示,,S - aAc,A - bA | ?,長久以來，探討符號串集合(即形式語言)的各種描述方法，一直是語言計算機處理的重要任務之一。,方法 --文法規(guī)則 ；,,其中：,,,從開始符號出發(fā)，對符號串中的定義對象，采用推導的方法（用其規(guī)則右部替換左部）產(chǎn)生新的符號串，如此進行，直到新符號串中不再出現(xiàn)定義的對象為止，則最終的符號串就是一個句子。,S - aAc A - bA | ?,規(guī)則應用說明示例：,【句子產(chǎn)生過程】(= 推導算符):,怎樣利用上述文法規(guī)則表示語言L?,① S,= aAc,= aεc,= ac,② S,= aAc,= abAc,= abεc,= abc,③ S,= aAc,= abAc,= abbAc,= abbc,…,,一個句子!,,又一個句子!,,∴ S abnc , n≥0,再一個句子!,,,,,,【定義】 文法(grammar)是規(guī)則的有限集, 其中的上下文無關文法可定義為四元組： G(Z)=(VN, VT, Z, P),VN : 非終結(jié)符集（定義的對象集，如：語法成分等)； VT : 終結(jié)符集（字母表）； Z : 開始符號（研究范疇中，最大的定義對象）； P : 規(guī)則集（又稱產(chǎn)生式集）；,A - ? 或者 A - ? | ? 其中, 描述符號 ： -(定義為)，|(或者是) 文法符號 ： Z,A∈VN，?,?∈(VN+VT)*,2.2 形式語言是由文法定義的,每個元素,每個規(guī)則,2.2.1 什麼是文法 ？,,,2.2 形式語言是由文法定義的（續(xù)3）,【注意】 提供了規(guī)則集，就相當給出了一個文法：,G(S):,2.2.2 文法是怎樣定義語言的？,則 L(G)={ x | Z x,x∈VT* },,即：一個文法所定義的語言，就是由該文法開始,設 有文法 G(Z), L(G)為G所定義的語言；,VT={ a,b,c };,Z = S ;,P :,VN={ S,A }；,G(Z)=(VN, VT, Z, P),,利用 = 進行連續(xù)推導之意！,符號推導出的所有僅含終結(jié)符的符號串之集合。,其中的每個符號串皆稱為句子。,,〖2.1〗,,,,【例2.6】標識符的文法,【標識符】 指字母開頭的字母、數(shù)字序列。,令 G(Z)= (VN, VT, Z, P),同理，【無符號整數(shù)】文法 可寫成：,G(N):,,N - d N | d,※其四元組也可寫成：G(N)=( {N}, p9jjjr9, N, P ),,,,,得： I = ? (?|d)n , n≥0,,令： I = ? A | ? A = ? A | d A | ?,,※標識符文法所定義的語言求解：,上面構造的 標識符文法屬于 正規(guī)文法(定義在后)類， 正確性檢驗較容易；下面給出一個算法：,※ 求解 I 值步驟：,先求解 A: A=(?|d) A , A=(?|d)2 A , … , A=(?|d)n A,代入 A= ? 得： A= (?|d)n , n≥0,② ∵ I=? A | ? 代入 A= (?|d)n , n≥0,正規(guī)方程式,,《標識符》：字母開頭的字母、數(shù)字序列；,,,,則 VN ={ E(算術表達式),T(項)，F(xiàn)(因式)}； VT ={ i(變量或常數(shù)),+,-,*,/,(,）}； Z = E ; P :,【例2.7】簡單算術表達式文法,【注】此文法定義了算術表達式的層次嵌套結(jié) 構:,,,,,,,,E - T | E + T | E - T,T - F | T * F | T / F,F - i | ( E ),令 G(Z)= (VN, VT, Z, P),( 表達式 ),,表達式,項,因式,,,※ 算術表達式文法應用示例：,根據(jù) 語言定義式〖2.1〗，,證明 i*(i+i-i),是文法G(E)的一個句子,(即 合法的算術表達式):,∵ E,∴,=T,=T*F,=T*(E),=T*(E-T),=T*(E+T-T),=F*(E+T-T),=i*(E+T-T),=…,觀察推導過程，可以看到：一旦產(chǎn)生式選擇錯了，會導致失?。?=i*(i+i-i),,,合法的算術表達式是指：,,練習題,【習題2.1】解釋下列詞語： ⑴形式語言； ⑵文法； ⑶文法所定義的語言。 【習題2.2】試構造下述語言L的文法： L={ ambn |m≥0,n≥1}; 【習題2.3】試求下述文法G(Z)所定義的語言： G(Z): Z-b|bB , B-bZ,