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

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