《編譯原理第二章形式語言基礎(1)》由會員分享，可在線閱讀，更多相關《編譯原理第二章形式語言基礎(1)（20頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,編譯程序的設計原理與實現(xiàn),如何讓計算機,認識、理解 和 執(zhí)行,高級程序設計語言？,第 2 章 形式語言基礎,計算機處理語言，首先應考慮語言的形式化、規(guī),范化，使其具有可計算性和可操作性；這就是形式語,言理論研究的問題。,形式語言誕生于1956年，由chomsky創(chuàng)立。通常，,語言研究至少涉及三個方面：,語法,、,語義,和,語用,；,這里僅側重于,語法的研究,。,形式語言的,基本觀點,是：,語言是符號串之集合！,形式語言理論研究的,基本問題,是：,研究符號串集合的表示方法、結構特性,以及運算規(guī)律。,【前 言

2、】,【內(nèi)容提要】,第 2 章 形式語言基礎,2.1,形式語言是,符號串集合,2.2,形式語言是由,文法定義,的,2.3,主要,語法成分,的定義,2.4,兩類,特性文法,2.5,文法變換,方法,2.6 關于,形式語言的分類,問題,字母表,-,元素,(,符號,),的非空有限集合；,符,號串,-,符號的有限序列；,符號串集合,-,有限個或者無限個符號串組成的集合；,規(guī) 則,-,以,某種形式表達的在一定范圍內(nèi)共同遵守的章程和制度；這里，指符號串的組成規(guī)則。,2.1 形式語言是符號串集合,【形式語言】,是,字母表,上的符號，按一定的,規(guī)則,組成的所有,符號串集合,；其中的每個符號串,稱為,句子,。,【名

3、詞解釋】：,三要素！,【例2.1】L,1,=00,01,10,11;,字母表,1,=0,1,句子有：00,01,10,11,【注】b,0,=,（空符號串）,b,1,=b,b,2,=bb,b,3,=bbb,L,1,為有限語言;L,2,為無限語言。,形式語言概念示例：,【例2.2】L,2,=ab,m,c,b,n,|m0,n0,字母表,2,=a,b,c,句型,1:,ab,m,c,有句子：,abc,abbc,abbbc,句型,2:,b,n,;,有句子：,b,bb,bbb,兩個語言！,1.,連接,：,.,=,如,a.b=ab,2.1.1 符號串(集合)的運算,3.,方冪,：,n,=,=,n-1,=,n-

4、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),*,=

5、(a|b),n,，,n0,同理：,(a|b),+,=(a|b),n,，,n0,符號串運算示例,泛指：,由a，b組成的,任意符號串！,（包括空串）,1.,乘積：,AB=xy|x,A,且,yB,2.1.1 符號串(集合)的運算(續(xù)2),4.,閉包：,A,的正閉包,：A,+,=A,1,A,2,A,n,A,的星閉包,：A,*,=A,0,A,1,A,2,A,n,設,A,和,B,為兩個符號串集合，則：,2.,和：,AB=A+B=x|x,A 或 xB,3.,方冪：,A,n,=AAA=AA,n-1,=A,n-1,A,n,個,A,0,=,;,A,1,=A,;,A,2,=AA;A,3,=AAA;,.符號串集合的運

6、算,符號串集合運算示例：,【例2.3】設 A=a,b,B=c,d,則 A+B=a,b,c,d,則 AB=xy|x,A,yB=,ac,ad,bc,bd,【例2.4】設 A=a,則 A,*,=A,0,A,1,A,2,A,n,=,+a+aa+aaa+,=,a,aa,aaa,=a,n,|n0,【例2.5】設 A=a，b，A,*,=?,A,*,=A,0,A,1,A,2,A,n,A,0,=,;,A,1,=A=a，b;,A,2,=A.A=a，b.a，b=aa,ab,ba,bb;,A,3,=A.A,2,=a，b.aa,ab,ba,bb,=aaa,aab,aba,abb,baa,bab,bba,bbb;,A,*

7、,=x|x=(a|b),n,，n0,符號串集合運算示例,(,續(xù),),：,推論,：若 A為任一字母表,則,A,*,就是該字母,表上,的所有符號串(包括空串)的集合。,S,A 定義的對象(S,句子,最大的定義對象，又,稱為開始符號;A為句型aAc的,短語,），,a,b,c-,為,字母表中的符號;-空符號串。,-,|-為,描述符號,(-定義為;|或者是）,2.1.2 符號串集合的文法描述,【例2.5】,L=ab,n,c|n0，,字母表,：=a,b,c；,展開,：L=ac,abc,abbc,abbbc,右圖給出的表示,S-,aAc,A-bA|,長久以來，探討符號串集合(即形式語言)的各種描述方法，一直

8、是語言計算機處理的重要任務之一。,方法-,文法規(guī)則,；,其中：,從,開始符號,出發(fā)，對符號串中的,定義對象,，采用,推導,的方法（,用其規(guī)則右部替換左部,）產(chǎn)生新的符號串，如此進行，直到新符號串中不再出現(xiàn)定義的對象為止，則最終的符號串就是一個,句子,。,S-,aAc,A-bA|,規(guī)則,應用,說明示例：,【,句子產(chǎn)生過程,】(,=,推導算符,):,怎樣利用上述,文法規(guī)則,表示語言L?,S,=,aAc,=ac,=ac,S,=aAc,=abAc,=abc,=abc,S,=aAc,=abAc,=abbAc,=abbc,一個句子!,又一個句子!,S ab,n,c,n0,=,+,再一個句子!,【定義】文法

9、(grammar)是規(guī)則的有限集,其中的上下文無關文法可定義為四元組：,G(Z)=(V,N,V,T,Z,P),V,N,:非終結符集（定義的對象集，如：語法成分等)；,V,T,:終結符集（字母表）；,Z:開始符號（研究范疇中，最大的定義對象）；,P:規(guī)則集（又稱產(chǎn)生式集）；,A-,或者 A-,|,其中,描述符號：-(定義為)，|(或者是),文法符號：Z,AV,N,，,(V,N,+V,T,),*,2.2 形式語言是由文法定義的,每個元素,每個規(guī)則,2.2.1 什麼是文法？,2.2 形式語言是由文法定義的（續(xù)3）,【注意】提供了規(guī)則集，就相當給出了一個文法：,S-,aAc,A-bA|,G(S):,2

10、.2.2 文法是怎樣定義語言的？,則 L(G)=x|Z x,xV,T,*,即：一個文法所定義的,語言,，就是由該文法,開始,設 有文法 G(Z),L(G)為G所定義的語言；,V,T,=a,b,c;,Z,=S;,P,:,V,N,=S,A；,G(Z)=(V,N,V,T,Z,P),利用=進行連續(xù)推導之意！,符號推導出,的所有,僅含終結符,的,符號串,之集合,。,其中的每個符號串皆稱為,句子,。,=,+,2.1,【例2.6】,標識符,的文法,【,標識符,】指字母開頭的字母、數(shù)字序列。,令 G(Z)=(V,N,V,T,Z,P),則 V,N,=I(標識符),A(標識符尾)；,V,T,=(字母),d,(數(shù)字

11、）,；,Z =I;,P:,I,-A|,A-A|d A|,同理，,【,無符號整數(shù),】文法 可寫成：,G(N):,N-d N|d,其,四元組,也可寫成：G(N)=(N,d,N,P ),得：,I,=,(,|d,),n,n0,令：,I,=A|,A=A|d A|,標識符文法,所定義的語言求解：,上面構造的,標識符文法,屬于,正規(guī)文法,(定義在后)類，,正確性檢驗較容易；下面給出一個,算法,：,I,-A|,A-A|d A|,求解 I 值步驟：,先求解,A:A=(,|d,)A,A=(,|d,),2,A,A=(,|d,),n,A,代入 A=,得：A=,(,|d,),n,n0,I=,A|,代入,A=,(,|d,

12、),n,n0,正規(guī)方程式,標識符：字母開頭的字母、數(shù)字序列；,則 V,N,=E(算術表達式),T(項)，F(xiàn)(因式)；,V,T,=i(變量或常數(shù)),+,-,*,/,(,）,；,Z =E;,P:,【例2.7】簡單算術表達式文法,【注】此文法定義了算術表達式的層次嵌套結,構:,E-T|E+,T|E-,T,T-F|T*,F|T/,F,F-i|(E ),令 G(Z)=(V,N,V,T,Z,P),(表達式),表達式,項,因式,算術表達式文法應用示例：,根據(jù),語言定義式,2.1，,G(E):E-T|E+T|E-T,T-F|T*,F|T/F,F-i|(E),證明,i*(i+i-i),是文法G(E)的一個,句子

13、,(即 合法的,算術表達式,):,=,+,E i*(i+i-i)成立嗎？,E,=,+,E i*(i+i-i),=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),L(G)=x|Z x,xV,T,*,=,+,合法的算術表達式是指：,練習題,【習題2.1】解釋下列詞語：,形式語言；,文法；,文法所定義的語言。,【習題2.2】試構造下述語言,L,的文法：,L,=a,m,b,n,|m0,n1;,【習題2.3】試求下述文法G(Z)所定義的語言：,G(Z):Z-b|bB,B-bZ,【習題2.4】P36_8,謝謝收看！,再見,