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

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

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

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

4、母表字母表上的符號(hào)，按一定的上的符號(hào)，按一定的規(guī)則規(guī)則組成的所有組成的所有符號(hào)串集合符號(hào)串集合；其中的每個(gè)符號(hào)串；其中的每個(gè)符號(hào)串稱為稱為句子句子?！久~解釋】：【名詞解釋】：三要素！三要素！【例【例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= = （空符號(hào)串）（空符號(hào)串）,b,b1 1=b,b=b,b2 2=bb,b=bb,b3 3=bbb,=bbb, L L1 1 為有限語(yǔ)言為有限語(yǔ)言; L; L2 2 為無(wú)限語(yǔ)言

5、。為無(wú)限語(yǔ)言。 形式語(yǔ)言概念示例：形式語(yǔ)言概念示例：【例【例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, 兩個(gè)語(yǔ)言！兩個(gè)語(yǔ)言！1. 1. 連接連接： . . = = 如如 a.b=aba.b=ab 2.1.1 2.1.1 符號(hào)串符號(hào)串( (集合集

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

7、.1.1 符號(hào)串符號(hào)串( (集合集合) )的運(yùn)算的運(yùn)算( (續(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 符號(hào)串運(yùn)算示例符號(hào)串運(yùn)算示例泛指：泛指：由由a，b組成的組成的任意符號(hào)串！任意符號(hào)串?。ò沾ò沾?.1.乘積：乘積： AB=xy |xAB=xy |x A A 且且 y y BB 2.1.1 2.1.1 符號(hào)串符號(hào)串( (集合集合) )的運(yùn)算的運(yùn)算( (續(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 為兩個(gè)符號(hào)串集合，則：為兩個(gè)符號(hào)串集合，則：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個(gè)個(gè) A A0 0 = ; A A1 1 =A =A ; ; A A2 2 =AA ; A=AA ; A3 3 =AAA ; =AAA ; . . 符號(hào)串集合的運(yùn)算符號(hào)串集合的運(yùn)算 符號(hào)串集合運(yùn)算示例：符號(hào)串集合運(yùn)算示例：【例【例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 符號(hào)串集合運(yùn)算示例符號(hào)串集合運(yùn)算示例( (續(xù)續(xù)) )： 推論推論：若：若 A A為任一字母表為任一字母表, ,則則 A A* * 就是該字母就

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

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

14、直到新符號(hào)串中不再出現(xiàn)定義的對(duì)象為止，則最終的符號(hào)串就是一個(gè)句子句子。 S - S - aAc aAc A - bA | A - bA | 規(guī)則應(yīng)用說(shuō)明示例：規(guī)則應(yīng)用說(shuō)明示例： 【句子產(chǎn)生過(guò)程句子產(chǎn)生過(guò)程】(= = 推導(dǎo)算符推導(dǎo)算符):): 怎樣利用上述怎樣利用上述文法規(guī)則文法規(guī)則表示語(yǔ)言表示語(yǔ)言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 一個(gè)句子一個(gè)句子!

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

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

17、就相當(dāng)給出了一個(gè)文法：提供了規(guī)則集，就相當(dāng)給出了一個(gè)文法： S - S - aAc aAc A - bA | A - bA | G(S):2.2.2 2.2.2 文法是怎樣定義語(yǔ)言的？文法是怎樣定義語(yǔ)言的？ 則則 L(G)= x | Z x,xVL(G)= x | Z x,xVT T* * 即：一個(gè)文法所定義的即：一個(gè)文法所定義的語(yǔ)言語(yǔ)言，就是由該文法，就是由該文法開(kāi)始開(kāi)始設(shè)設(shè) 有文法有文法 G(Z), L(G)G(Z), L(G)為為G G所定義的語(yǔ)言；所定義的語(yǔ)言；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)利用利用 = = 進(jìn)行連續(xù)推導(dǎo)之意！進(jìn)行連續(xù)推導(dǎo)之意！符號(hào)推導(dǎo)出符號(hào)推導(dǎo)出的所有的所有僅含終結(jié)符僅含終結(jié)符的的符號(hào)串符號(hào)串之集合之集合。其中的每個(gè)符號(hào)串皆稱為其中的每個(gè)符號(hào)串皆稱為句子句子。 = + +2.1【例【例2.62.6】標(biāo)識(shí)符標(biāo)識(shí)符的文法的文法 【標(biāo)識(shí)符標(biāo)識(shí)符】 指字母開(kāi)頭的字母、數(shù)字序列。指字母開(kāi)頭的字母、數(shù)字序列。令令 G(Z)= (VG(Z)= (VN N, V, VT T, Z, P), Z, P)則則 V VN N =I( =I(標(biāo)識(shí)符標(biāo)識(shí)符),A(),A(標(biāo)識(shí)符尾標(biāo)識(shí)符尾)； 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 | 同理，同理，【無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(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)識(shí)符文法標(biāo)識(shí)符文法所定義的語(yǔ)言求解：所定義的語(yǔ)言求解： 上

20、面構(gòu)造的上面構(gòu)造的標(biāo)識(shí)符文法標(biāo)識(shí)符文法屬于屬于正規(guī)文法正規(guī)文法( (定義在后定義在后) )類，類，正確性檢驗(yàn)較容易；下面給出一個(gè)正確性檢驗(yàn)較容易；下面給出一個(gè)算法算法：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)識(shí)符標(biāo)識(shí)符：字母開(kāi)頭的字母、數(shù)字序列；：字母開(kāi)頭的字母、

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