《形式語(yǔ)言基礎(chǔ)》PPT課件.ppt

《《形式語(yǔ)言基礎(chǔ)》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《形式語(yǔ)言基礎(chǔ)》PPT課件.ppt（19頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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