編譯原理第二章形式語言基礎(chǔ)(1)

1、編譯程序的設(shè)計原理與實現(xiàn)編譯程序的設(shè)計原理與實現(xiàn)如何讓計算機如何讓計算機認識、理解認識、理解 和和 執(zhí)行執(zhí)行 高級程序設(shè)計語言高級程序設(shè)計語言 ？ 第第 2 2 章章 形式語言基礎(chǔ)形式語言基礎(chǔ) 計算機處理語言，首先應(yīng)考慮語言的形式化、規(guī)計算機處理語言，首先應(yīng)考慮語言的形式化、規(guī)范化，使其具有可計算性和可操作性；這就是形式語范化，使其具有可計算性和可操作性；這就是形式語言理論研究的問題。言理論研究的問題。 形式語言誕生于形式語言誕生于19561956年，由年，由chomskychomsky創(chuàng)立。通常，創(chuàng)立。通常，語言研究至少涉及三個方面：語言研究至少涉及三個方面：語法語法、語義語義和和語用語用；

2、 這里僅側(cè)重于這里僅側(cè)重于語法的研究語法的研究。 形式語言的形式語言的基本觀點基本觀點是是 ： 語言是符號串之集合！語言是符號串之集合！ 形式語言理論研究的形式語言理論研究的基本問題基本問題是：是： 研究符號串集合的表示方法、結(jié)構(gòu)特性研究符號串集合的表示方法、結(jié)構(gòu)特性 以及運算規(guī)律。以及運算規(guī)律?！厩啊厩?言】言】【內(nèi)容提要】【內(nèi)容提要】第第 2 2 章章 形式語言基礎(chǔ)形式語言基礎(chǔ) 2.1 2.1 形式語言是形式語言是符號串集合符號串集合 2.22.2 形式語言是由形式語言是由文法定義文法定義的的 2.32.3 主要主要語法成分語法成分的定義的定義 2.42.4 兩類兩類特性文法特性文法 2.

3、5 2.5 文法變換文法變換方法方法 2.6 2.6 關(guān)于關(guān)于形式語言的分類形式語言的分類問題問題 字母表字母表 - - 元素元素( (符號符號) )的非空有限集合；的非空有限集合； 符符號串號串 - - 符號的有限序列；符號的有限序列； 符號串集合符號串集合 - - 有限個或者無限個符號串組成有限個或者無限個符號串組成的集合；的集合； 規(guī)規(guī) 則則 - - 以以某種形式表達的在一定范圍內(nèi)共某種形式表達的在一定范圍內(nèi)共同遵守的章程和制度；這里，指符號串的組成同遵守的章程和制度；這里，指符號串的組成規(guī)則。規(guī)則。2.1 2.1 形式語言是符號串集合形式語言是符號串集合 【形式語言】【形式語言】是是字

4、母表字母表上的符號，按一定的上的符號，按一定的規(guī)則規(guī)則組成的所有組成的所有符號串集合符號串集合；其中的每個符號串；其中的每個符號串稱為稱為句子句子?！久~解釋】：【名詞解釋】：三要素！三要素！【例【例2.12.1】 L L1 1= 00,01,10,11 ;= 00,01,10,11 ; 字母表字母表1 1= 0,1,= 0,1, 句子有：句子有：00,01,10,1100,01,10,11【注】【注】 b b0 0= = （空符號串）（空符號串）,b,b1 1=b,b=b,b2 2=bb,b=bb,b3 3=bbb,=bbb, L L1 1 為有限語言為有限語言; L; L2 2 為無限語言

5、。為無限語言。 形式語言概念示例：形式語言概念示例：【例【例2.22.2】 L L2 2= ab= abm mc,bc,bn n | m0,n0 | m0,n0 字母表字母表2 2= a,b,c,= a,b,c,句型句型1: ab1: abm mc ,c ,有句子：有句子： abc, abbc, abbbc, abc, abbc, abbbc, 句型句型2: b2: bn n ; ;有句子：有句子： , b, bb, bbb, , b, bb, bbb, 兩個語言！兩個語言！1. 1. 連接連接： . . = = 如如 a.b=aba.b=ab 2.1.1 2.1.1 符號串符號串( (集合集

6、合) )的運算的運算3.3. 方冪方冪： n n = = = = n-1n-1 = = n-1n-1 4.4. 閉包：閉包：n n個個. . 符號串的運算符號串的運算 設(shè)設(shè) , , 為兩個符號串，則為兩個符號串，則： 的正閉包：的正閉包： + + = = 1 1| | 2 2| n n| 的星閉包：的星閉包： * * = = 0 0| | 1 1| | 2 2| n n| 0 0 = = ( (空符號串空符號串) ) 什麼符號也沒有的符號串什麼符號也沒有的符號串 ！ 1 1= = ； 2 2 = = ；2.2. 或或： | | = = ( (或者或者 ）這是一種這是一種泛指泛指！2.1.1 2

7、.1.1 符號串符號串( (集合集合) )的運算的運算( (續(xù)續(xù)1)1)【例】：【例】： ab|cd = ab ab|cd = ab（或者或者 cd cd ） abc.de= abcde abc.de= abcde (a|b) (a|b)1 1 =(a|b)= a|b =(a|b)= a|b (a|b) (a|b)* * =(a|b)=(a|b)0 0 |(a|b)|(a|b)1 1 |(a|b)|(a|b)2 2 |(a|b)(a|b)2 2 =(a|b)(a|b)=aa|ab|ba|bb=(a|b)(a|b)=aa|ab|ba|bb 即：即：(a|b)(a|b)* * = (a|b)= (

8、a|b)n n ，n0n0同理：同理： (a|b)(a|b)+ + = (a|b)= (a|b)n n ，n n0 0 符號串運算示例符號串運算示例泛指：泛指：由由a，b組成的組成的任意符號串！任意符號串！（包括空串）（包括空串）1.1.乘積：乘積： AB=xy |xAB=xy |x A A 且且 y y BB 2.1.1 2.1.1 符號串符號串( (集合集合) )的運算的運算( (續(xù)續(xù)2)2)4.4.閉包：閉包：A A 的正閉包的正閉包： A A+ + = A= A1 1AA2 2AAn nA A 的星閉包的星閉包： A A* * = A= A0 0AA1 1AA2 2AAn n設(shè)設(shè) A

9、A 和和 B B 為兩個符號串集合，則：為兩個符號串集合，則：2. 2. 和：和： AB=A+B=x| xAB=A+B=x| x A A 或或 x x BB 3.3.方冪：方冪： A An n = AAA = AA= AAA = AAn-1n-1 = A = An-1n-1A An n個個 A A0 0 = ; A A1 1 =A =A ; ; A A2 2 =AA ; A=AA ; A3 3 =AAA ; =AAA ; . . 符號串集合的運算符號串集合的運算 符號串集合運算示例：符號串集合運算示例：【例【例2.32.3】 設(shè)設(shè) A=a,b,B=c,dA=a,b,B=c,d 則則 A+B=a

10、,b,c,d A+B=a,b,c,d 則則 AB=xy|xAB=xy|x A,yA,y B=B=ac,ad,bc,bdac,ad,bc,bd【例【例2.42.4】 設(shè)設(shè) A=aA=a 則則 A A* * = A= A0 0AA1 1AA2 2AAn n = = +a+aa+aaa+a+aa+aaa+ = = ,a,aa,aaa,a,aa,aaa, =a =an n|n0 |n0 【例【例2.52.5】 設(shè)設(shè) A=aA=a，bb， A A* * = ? = ? A A* * = A = A0 0AA1 1AA2 2AAn n A A0 0 = = ; A A1 1 = A =a = A =a，b

11、;b; A A2 2 = A.A=a = A.A=a，b.ab.a，b=aa,ab,ba,bb;b=aa,ab,ba,bb; A A3 3 = A.A = A.A2 2=a=a，b.aa,ab,ba,bbb.aa,ab,ba,bb =aaa,aab,aba,abb,baa,bab,bba,bbb; =aaa,aab,aba,abb,baa,bab,bba,bbb; A A* * = x | x=(a|b) = x | x=(a|b)n n ，n0 n0 符號串集合運算示例符號串集合運算示例( (續(xù)續(xù)) )： 推論推論：若：若 A A為任一字母表為任一字母表, ,則則 A A* * 就是該字母就

12、是該字母表上表上的所有符號串的所有符號串( (包括空串包括空串) )的集合。的集合。 S,A S,A 定義的對象定義的對象(S (S 句子句子, ,最大的定義對象，又最大的定義對象，又 稱為開始符號稱為開始符號; A; A為句型為句型aAcaAc的的短語短語），）， a,b,c - a,b,c - 為為字母表字母表中的符號中的符號;- ;- 空符號串?？辗柎?- ,| - - ,| - 為為描述符號描述符號( - ( - 定義為定義為; | ; | 或者是）或者是） 2.1.2 2.1.2 符號串集合的文法描述符號串集合的文法描述【例【例2.52.5】 L = abL = abn nc |

13、 n0 c | n0 ， 字母表字母表：= a,b,c= a,b,c； 展開展開：L =ac,abc,abbc,abbbc, L =ac,abc,abbc,abbbc, 右圖給出的表示右圖給出的表示 S -S - aAcaAc A - bA | A - bA | 長久以來，探討符號串集合長久以來，探討符號串集合(即形式語言即形式語言)的各種的各種描述方法，一直是語言計算機處理的重要任務(wù)之一。描述方法，一直是語言計算機處理的重要任務(wù)之一。方法方法 -文法規(guī)則文法規(guī)則 ；其中：其中： 從開始符號開始符號出發(fā)，對符號串中的定義對象，采用推導(dǎo)推導(dǎo)的方法（用其規(guī)則右部替換左部）產(chǎn)生新的符號串，如此進行，

14、直到新符號串中不再出現(xiàn)定義的對象為止，則最終的符號串就是一個句子句子。 S - S - aAc aAc A - bA | A - bA | 規(guī)則應(yīng)用說明示例：規(guī)則應(yīng)用說明示例： 【句子產(chǎn)生過程句子產(chǎn)生過程】(= = 推導(dǎo)算符推導(dǎo)算符):): 怎樣利用上述怎樣利用上述文法規(guī)則文法規(guī)則表示語言表示語言L?L? S S= = aAcaAc = ac= ac = ac= ac S S= aAc= aAc = abAc= abAc = abc= abc = abc= abc S S = aAc= aAc = abAc= abAc= abbAc= abbAc = abbc= abbc 一個句子一個句子!

15、!又一個句子又一個句子! ! S abS abn nc , n0 c , n0 = + +再一個句子再一個句子! ! 【定義】【定義】 文法文法(grammar)(grammar)是規(guī)則的有限集是規(guī)則的有限集, ,其中的上下文無關(guān)文法可定義為四元組：其中的上下文無關(guān)文法可定義為四元組： G(Z)=(VG(Z)=(VN N, V, VT T, Z, P), Z, P) V VN N : : 非終結(jié)符集（定義的對象集，如：語法成分等非終結(jié)符集（定義的對象集，如：語法成分等) )； V VT T : : 終結(jié)符集（字母表）；終結(jié)符集（字母表）； Z : Z : 開始符號（研究范疇中，最大的定義對象）

16、；開始符號（研究范疇中，最大的定義對象）； P : P : 規(guī)則集（又稱產(chǎn)生式集）；規(guī)則集（又稱產(chǎn)生式集）； A - A - 或者或者 A - A - | | 其中其中, , 描述符號描述符號 ： -(-(定義為定義為) )，|(|(或者是或者是) ) 文法符號文法符號 ： Z,AVZ,AVN N， , , (V(VN N+V+VT T) )* * 2.2 2.2 形式語言是由文法定義的形式語言是由文法定義的每個元素每個元素每個規(guī)則每個規(guī)則2.2.1 2.2.1 什麼是文法什麼是文法 ？2.2 2.2 形式語言是由文法定義的（續(xù)形式語言是由文法定義的（續(xù)3 3）【注意】【注意】 提供了規(guī)則集，

17、就相當(dāng)給出了一個文法：提供了規(guī)則集，就相當(dāng)給出了一個文法： S - S - aAc aAc A - bA | A - bA | G(S):2.2.2 2.2.2 文法是怎樣定義語言的？文法是怎樣定義語言的？ 則則 L(G)= x | Z x,xVL(G)= x | Z x,xVT T* * 即：一個文法所定義的即：一個文法所定義的語言語言，就是由該文法，就是由該文法開始開始設(shè)設(shè) 有文法有文法 G(Z), L(G)G(Z), L(G)為為G G所定義的語言；所定義的語言；V VT T= a,b,c ; = a,b,c ; Z Z = S ; = S ; P P : :V VN N= S,A =

18、S,A ；G(Z)=(VG(Z)=(VN N, V, VT T, Z, P), Z, P)利用利用 = = 進行連續(xù)推導(dǎo)之意！進行連續(xù)推導(dǎo)之意！符號推導(dǎo)出符號推導(dǎo)出的所有的所有僅含終結(jié)符僅含終結(jié)符的的符號串符號串之集合之集合。其中的每個符號串皆稱為其中的每個符號串皆稱為句子句子。 = + +2.1【例【例2.62.6】標(biāo)識符標(biāo)識符的文法的文法 【標(biāo)識符標(biāo)識符】 指字母開頭的字母、數(shù)字序列。指字母開頭的字母、數(shù)字序列。令令 G(Z)= (VG(Z)= (VN N, V, VT T, Z, P), Z, P)則則 V VN N =I( =I(標(biāo)識符標(biāo)識符),A(),A(標(biāo)識符尾標(biāo)識符尾)； V V

19、T T = = ( (字母字母),d),d( (數(shù)字）數(shù)字） ； Z = I ; Z = I ; P : P : I - - A | A | A - A - A | d A | A | d A | 同理，同理，【無符號整數(shù)無符號整數(shù)】文法】文法 可寫成：可寫成：G(N):G(N):N - d N | dN - d N | d其其四元組四元組也可寫成：也可寫成：G(N)=( N, d, N, P ) 得：得： I = (|d|d)n , n0 令：令： I = = A | A | A = A = A | d A | A | d A | 標(biāo)識符文法標(biāo)識符文法所定義的語言求解：所定義的語言求解： 上

20、面構(gòu)造的上面構(gòu)造的標(biāo)識符文法標(biāo)識符文法屬于屬于正規(guī)文法正規(guī)文法( (定義在后定義在后) )類，類，正確性檢驗較容易；下面給出一個正確性檢驗較容易；下面給出一個算法算法：I - - A | A | A - A - A | d A | A | d A | 求解求解 I 值步驟：值步驟：先求解先求解 A: A=(|d|d) A , A=(|d|d)2 A , , A=(|d|d)n A 代入代入 A= A= 得：得： A= A= (|d|d)n , n0 I= A | A | 代入代入 A= A= (|d|d)n , n0正規(guī)方程式正規(guī)方程式標(biāo)識符標(biāo)識符：字母開頭的字母、數(shù)字序列；：字母開頭的字母、

21、數(shù)字序列；則則 V VN N = E( = E(算術(shù)表達式算術(shù)表達式),T(),T(項項) )，F(xiàn)(F(因式因式)； V VT T = i( = i(變量或常數(shù)變量或常數(shù)),),+,-,+,-,* *,/,(,/,(,） ； Z = E ; Z = E ; P : P : 【例【例2.72.7】簡單算術(shù)表達式文法】簡單算術(shù)表達式文法【注】此文法定義了算術(shù)表達式的層次嵌套結(jié)【注】此文法定義了算術(shù)表達式的層次嵌套結(jié)構(gòu)構(gòu): : E - T | E + E - T | E + T | E -T | E - T T T - F | T T - F | T * * F | T /F | T / F F F - i | ( E ) F - i | ( E )令令 G(Z)= (VG(Z)= (VN N, V, VT T, Z, P), Z