Chapt文法和語(yǔ)言實(shí)用PPT課件

1、學(xué)習(xí)重點(diǎn)學(xué)習(xí)重點(diǎn)n1 文法的定義、分類(lèi)和二義性n2 最左推導(dǎo)、規(guī)范推導(dǎo)(或最右推導(dǎo))n3 語(yǔ)言、句型和句子n4 短語(yǔ)、簡(jiǎn)單短語(yǔ)(或直接短語(yǔ))和句柄n5 語(yǔ)法樹(shù)第1頁(yè)/共81頁(yè)形式形式語(yǔ)言語(yǔ)言(P12)n如果不考慮語(yǔ)義和語(yǔ)用，只從語(yǔ)法這一側(cè)面來(lái)看語(yǔ)言，它是由符合某種語(yǔ)法（用規(guī)則定義）的句子構(gòu)成的集合，這種意義下的語(yǔ)言稱(chēng)作形式語(yǔ)言。 例 漢語(yǔ)：所有符合漢語(yǔ)語(yǔ)法的句子的全體 英語(yǔ)：所有符合英語(yǔ)語(yǔ)法的句子的全體 程序設(shè)計(jì)語(yǔ)言：所有符合該語(yǔ)言語(yǔ)法的程序的 全體第2頁(yè)/共81頁(yè)形式形式語(yǔ)言語(yǔ)言n形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)，即能用數(shù)學(xué)符號(hào)和規(guī)則描述的語(yǔ)言。形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特

2、性的研究。這種理論對(duì)程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)和編譯程序的構(gòu)造有著重大的作用。第3頁(yè)/共81頁(yè)2.1 2.1 字母表和符號(hào)串字母表和符號(hào)串(P12) 字母表 (或符號(hào)集) ：元素的非空有窮集合。例 二進(jìn)制數(shù)語(yǔ)言的字母表=0,1 漢語(yǔ)的字母表中包括漢字、數(shù)字及標(biāo)點(diǎn)符號(hào)等 PASCAL語(yǔ)言的字母表是由字母、數(shù)字、若干專(zhuān)用符號(hào)及BEGIN、IF之類(lèi)的保留字組成 C語(yǔ)言的字母表由字母、數(shù)字、若干專(zhuān)用符號(hào)以及if、else、while等關(guān)鍵字組成第4頁(yè)/共81頁(yè)2.1 2.1 字母表和符號(hào)串字母表和符號(hào)串 符號(hào)：字母表中的元素。 例 =a,b,for,1，則a,b,for,1都是的符號(hào)。 不要把符號(hào)理解成字符。

3、 典型的符號(hào)有字母、數(shù)字、各種標(biāo)點(diǎn)符號(hào)和各種運(yùn)算符。 第5頁(yè)/共81頁(yè)2.1 2.1 字母表和符號(hào)串字母表和符號(hào)串 符號(hào)串：由字母表上0個(gè)或多個(gè)符號(hào)所組成的任何有窮序列?？辗?hào)串 也是字母表上的符號(hào)串，它由0個(gè)符號(hào)組成。例 =0,1，則， 0，1，01，10，00，11，100，0110，111110000等二進(jìn)制數(shù)都是上的符號(hào)串 =a,b,c,+,*，則， a ， b ， c ， + ， *，aa，ab，ac，a+，a*，ba，bb，bc，b+，b*，aaa，bbb等都是上的符號(hào)串一個(gè)字母表上的全部符號(hào)串所組成的集合是無(wú)窮的。 第6頁(yè)/共81頁(yè)2.1 2.1 字母表和符號(hào)串字母表和符號(hào)串 符

4、號(hào)串的長(zhǎng)度：指符號(hào)串x中所含符號(hào)的個(gè)數(shù)，記為|x|。特別地， |=0。例 =a,b,c,+,*， |abc|=3，|abc+*abc|=8符號(hào)串相等：若x、y是字母表上的兩個(gè)符號(hào)串，那么當(dāng)且僅當(dāng)組成x的各符號(hào)與組成y的各符號(hào)依次相等時(shí)，則符號(hào)串x與符號(hào)串y相等，記作x=y。例 當(dāng)x=abbc，y=abbc 時(shí)，則x=y 當(dāng)x=ab，y=ba 時(shí)，則xy 第7頁(yè)/共81頁(yè)2.1 2.1 字母表和符號(hào)串字母表和符號(hào)串 符號(hào)串的前綴：指從符號(hào)串x的末尾刪除0或多個(gè)符號(hào)后得到的符號(hào)串。例 u、uni、university都是university的前綴符號(hào)串的后綴：指從符號(hào)串x的開(kāi)頭刪除0或多個(gè)符號(hào)后得

5、到的符號(hào)串。例 ty、sity、university都是university的后綴 符號(hào)串的子串：指從符號(hào)串x的開(kāi)頭和末尾刪除0或多個(gè)符號(hào)后得到的符號(hào)串，例 ver是university的子串, 符號(hào)串的前綴、后綴都是它的子串。第8頁(yè)/共81頁(yè)2.1 2.1 字母表和符號(hào)串字母表和符號(hào)串 符號(hào)串的連接：若x、y是兩個(gè)符號(hào)串，則xy是將符號(hào)串y連接在符號(hào)串x的后面。例 x=ab，y=ba，則 xy=abba若x、y是字母表上的兩個(gè)符號(hào)串，則xy也是字母表上的符號(hào)串。 除x=x=x外，連接沒(méi)有交換率， 即 xy yx 。 第9頁(yè)/共81頁(yè)2.1 2.1 字母表和符號(hào)串字母表和符號(hào)串 集合的乘積運(yùn)算

6、：令A(yù)、B為兩個(gè)符號(hào)串集合，AB=xy|xA ,yB 。對(duì)于空集合有，有 A=A =A 。例 A=a,b， B=c,d，則AB=ac,ad,bc,bd 符號(hào)串的冪運(yùn)算：若x是符號(hào)串，則： x0=, x1=x ， x2=xx，xn=xxx=xxn-1=xn-1 x，其中 n0 。 例 x=abc, x0=， x1=abc， x2=abcabc，第10頁(yè)/共81頁(yè)2.1 2.1 字母表和符號(hào)串字母表和符號(hào)串 集合的冪運(yùn)算：設(shè)A為符號(hào)串集合，則： A0= A1=A A2=AA An=AAA=AAn-1=An-1 A，其中 n0 例 A =a，b，則 A0= A1=a,b A2=aa,ab,ba,bb

7、 第11頁(yè)/共81頁(yè)2.1 2.1 字母表和符號(hào)串字母表和符號(hào)串 集合的正閉包：設(shè)A為一個(gè)集合，則： A+ =A1A2.An例 A =a,b，則A+ =a,b,aa,ab,ba,bb,aaa,aab,集合的閉包：設(shè)A為一個(gè)集合，則： A* =A0 A+ 例 A =a,b，則A* =,a,b,aa,ab,ba,bb,aaa,aab,一個(gè)集合的閉包比正閉包多個(gè)。 第12頁(yè)/共81頁(yè)例：2.2 文法(P14) 文法實(shí)際上就是描述語(yǔ)言語(yǔ)法結(jié)構(gòu)的形式規(guī)則。 第13頁(yè)/共81頁(yè)第14頁(yè)/共81頁(yè)例終結(jié)符號(hào)集Vt=the, gray, wolf, will, eat, goat非終結(jié)符號(hào)集Vn=, , ,

8、, , , , , , 產(chǎn)生式集P= , 開(kāi)始符號(hào)Z= 又稱(chēng)為語(yǔ)法規(guī)則集，即符號(hào)的組成規(guī)則組成語(yǔ)言的基本符號(hào)語(yǔ)言的語(yǔ)法成分第15頁(yè)/共81頁(yè)文法G的形式定義：G=(Vn，Vt，P，Z)Vn(非終結(jié)符號(hào)集)是一個(gè)由非終結(jié)符號(hào)（一般是大寫(xiě)字母或用）構(gòu)成的非空有窮集合。Vt (終結(jié)符號(hào)集)是一個(gè)由終結(jié)符號(hào)（如小寫(xiě)字母、數(shù)字、標(biāo)點(diǎn)符號(hào)等）構(gòu)成的非空有窮集合。 VtVn=，VtVn，V是該文法的字母表或詞匯表。P(產(chǎn)生式集)是一個(gè)由產(chǎn)生式或規(guī)則構(gòu)成的非空有窮集合。 產(chǎn)生式的形式為： 或:= 產(chǎn)生式的左部V+，即不能為空，產(chǎn)生式的右部V*，“”或”“:=”含義相同，表示“定義為”或“由組成”。Z是文法的識(shí)

9、別符號(hào)或開(kāi)始符號(hào)， Z Vn，要求Z至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。第16頁(yè)/共81頁(yè)2.2 2.2 文法文法例2-1(P15)文法 G1=(Vn，Vt，P，Z)，其中：Vn=， ， ， ， ， Vt= the，ate，banana，monkey P由下面8條規(guī)則組成:識(shí)別符號(hào)： the ate banana monkey 第17頁(yè)/共81頁(yè)2.2 2.2 文法文法例2-1(P15)文法 G1可以簡(jiǎn)化寫(xiě)成： G1 : the ate banana monkey the ate banana monkey 或第18頁(yè)/共81頁(yè)2.2 2.2 文法文法 例2-2(P15) 有如下簡(jiǎn)化表示文法，

10、只給出規(guī)則集，寫(xiě)出該文法的終結(jié)符號(hào)集合、非終結(jié)符號(hào)集合和識(shí)別符號(hào)。0123456789解：根據(jù)簡(jiǎn)化約定，可確定：Vn=, Vt=0,1,2,3,4,5,6,7,8,9識(shí)別符號(hào)：第19頁(yè)/共81頁(yè)2.2 2.2 文法文法文法的EBNF表示（P16）：用一些特殊的元符號(hào)“|”、“”和“”、“”、“（” 和“）”、“” 和“”來(lái)表示文法。例2-3 對(duì)例2.2文法的13條規(guī)則可縮寫(xiě)成： := :=| :=0|1|2|3|4|5|6|7|8|9“|”：表示“或” 。 對(duì)于具有相同左部的那些規(guī)則， 如 1， 2 ， n 縮寫(xiě)為: 1 |2 |n第20頁(yè)/共81頁(yè)2.2 2.2 文法文法“”：用于括起由中文

11、字組成的非終結(jié)符號(hào)或由多個(gè)字母組成的符號(hào)。例（一般寫(xiě)成monkey ）第21頁(yè)/共81頁(yè)2.2 2.2 文法文法“”和“”：表示可重復(fù)連接，tkm表示符號(hào)串t可重復(fù)連接k到m次，而t表示符號(hào)串t可重復(fù)連接0到無(wú)窮次。例13 等價(jià)于： | EE+T|T 與 ET+T 相同字母打頭、后面可跟字母或數(shù)字的不超過(guò)8個(gè)字符的標(biāo)識(shí)符文法則為： |07第22頁(yè)/共81頁(yè)2.2 2.2 文法文法“”和“ ”：表示括起來(lái)的內(nèi)容可有可無(wú)。如t表示符號(hào)串t可有可無(wú)。例 IF THEN IF THEN ELSE 可寫(xiě)成： IF THEN ELSE 第23頁(yè)/共81頁(yè)2.2 2.2 文法文法“（”和“）”：表示括號(hào)內(nèi)的

12、成分優(yōu)先。常用于在規(guī)則中提取公因子。例 Uxy|xw|xz 可寫(xiě)成： Ux（y|w|z）第24頁(yè)/共81頁(yè)2.2 2.2 文法文法 課堂練習(xí)（1）已知字母表=begin, end, if, then, else，則它的符號(hào)有_。（2）某程序設(shè)計(jì)語(yǔ)言的一個(gè)源程序，就是該語(yǔ)言字母表上的滿(mǎn)足相應(yīng)語(yǔ)法規(guī)則的一個(gè)_。 A. 終結(jié)符號(hào) B. 非終結(jié)符號(hào) C. 字符串 D. 文法（3）已知文法 SaBc | bAB AaAb| b Bb | 寫(xiě)出該文法的開(kāi)始符號(hào)、 Vn和Vt。第25頁(yè)/共81頁(yè)2.132.13文法和語(yǔ)言分類(lèi)文法和語(yǔ)言分類(lèi)（P26P26） 0型文法(或短語(yǔ)結(jié)構(gòu)文法) 若文法中有如下形式的規(guī)則

13、： 其中， V+ (即可以是V上的符號(hào)序列，但不能為空)，V* (即是V上的符號(hào)序列，可以是) 。如果文法中有產(chǎn)生式的右部為，并且該產(chǎn)生式的左部不是一個(gè)非終結(jié)符，則該文法一定是0型文法。0型文法描述的語(yǔ)言為0型語(yǔ)言。例 文法G1=(Vn,Vt,P,S)，其中：Vn=S,A,B,C,D,E ，Vt=a ，P=S:=ACaB,Ca:=aaC,CB:=DB,CB:=E,aD:=Da,AD:=AC,aE:= ，該文法是一個(gè)0型文法。 第26頁(yè)/共81頁(yè)2.132.13文法和語(yǔ)言分類(lèi)文法和語(yǔ)言分類(lèi)（P26P26） 1型文法(或上下文有關(guān)文法) 若文法中有如下形式的規(guī)則： Uu 其中， UVn，、V*，u

14、 V* ，即規(guī)則左部可為符號(hào)序列，其中U為非終結(jié)符號(hào)且只有在左右為和的環(huán)境下U可變?yōu)閡。1型文法的產(chǎn)生式左部的長(zhǎng)度小于等于其右部的長(zhǎng)度，但S除外。1型文法描述的語(yǔ)言為1型語(yǔ)言。例 文法G2=(Vn,Vt,P,S) ，其中, Vn=S,A,B,C ，Vt=a,b,c ，P=S:=aSBC,S:=aBC,aB:=ab,bB:=bb,bC:=bc,CB:=BC,cC:=cc ，該文法是一個(gè)1型文法。第27頁(yè)/共81頁(yè)2.132.13文法和語(yǔ)言分類(lèi)文法和語(yǔ)言分類(lèi)（P26P26） 2型文法(或上下文無(wú)關(guān)文法) 若文法中的規(guī)則都具有如下形式： Uu 其中， U Vn ， u V*，即2型文法中的規(guī)則左部必

15、須是一個(gè)非終結(jié)符號(hào)，規(guī)則右部u是V上的符號(hào)序列。該文法相當(dāng)于對(duì)1型文法中的規(guī)則形式加以限制，即要求和必須為空。2型文法也稱(chēng)作上下文無(wú)關(guān)文法，描述的語(yǔ)言為2型語(yǔ)言。一般用2型文法來(lái)描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則。例 文法G3=(Vn,Vt,P,N) ，其中, Vn=N,D ，Vt=0,1,2,3,4,5,6,7,8,9 ，P=N:=ND|D,D:=0|1|2|3|4|5|6|7|8|9 ，該文法是一個(gè)2型文法。第28頁(yè)/共81頁(yè)2.132.13文法和語(yǔ)言分類(lèi)文法和語(yǔ)言分類(lèi)（P27P27） 3型文法(或正規(guī)文法) 若文法中的規(guī)則都具有如下形式： Ua |Wa（左線性）或 Ua|aW（右線性） 其中，

16、U，WVn，aVt ( a可為)。 3型文法中的產(chǎn)生式全部是左線性產(chǎn)生式或全部是右線性產(chǎn)生式。 3型文法描述的語(yǔ)言為3型語(yǔ)言。用3型文法描述程序設(shè)計(jì)語(yǔ)言的單詞的構(gòu)詞規(guī)則，如標(biāo)識(shí)符、無(wú)符號(hào)整數(shù)等。例 左線性3型文法： NN0|N1|N2|N3|N4|N5|N6|N7|N8|N9 N0|1|2|3|4|5|6|7|8|9 這個(gè)文法定義的語(yǔ)言就是無(wú)符號(hào)整數(shù)。 第29頁(yè)/共81頁(yè)2.132.13文法和語(yǔ)言分類(lèi)文法和語(yǔ)言分類(lèi) 練習(xí) 判斷以下文法的類(lèi)型 S:=ABCC:=BCC:=ABA:=GEBG:=GBFAG:=ADDB:=BDDE:=AEFB:=BFFE:=EaAA:=文法GZ:Z:=0B|1CB:

17、=1Z|1C:=0Z|00型文法3型文法第30頁(yè)/共81頁(yè)2.132.13文法和語(yǔ)言分類(lèi)文法和語(yǔ)言分類(lèi) 練習(xí) 判斷以下文法的類(lèi)型 文法GS:S:=AA:=aABD|abBBD:=CBCB:=CDCD:=BDbB:=bbD:=c文法GZ:Z:=B0C|C1B:=Z1|1C:=Z0|01型文法2型文法第31頁(yè)/共81頁(yè)文法的四種分類(lèi)第32頁(yè)/共81頁(yè)2.132.13文法和語(yǔ)言分類(lèi)文法和語(yǔ)言分類(lèi)四種文法的關(guān)系：通過(guò)對(duì)文法的產(chǎn)生式逐漸增加限制來(lái)定義四種文法，因此 0型語(yǔ)言包含1型語(yǔ)言，1型語(yǔ)言包含2型語(yǔ)言，2型語(yǔ)言包含3型語(yǔ)言。或者說(shuō)，3型文法是2型文法的特例，2型文法是1型文法的特例，1型文法又是0

18、型文法的特例 。第33頁(yè)/共81頁(yè)n直接推導(dǎo)（）：是文法G的一個(gè)產(chǎn)生式， x,yV*，符號(hào)串xy中的非終結(jié)符號(hào)用替換，從而得到符號(hào)串xy，則表示為： xy xy 其中“”讀為“直接推導(dǎo)出”或“直接產(chǎn)生” 。即稱(chēng)xy直接推導(dǎo)出xy,或xy直接產(chǎn)生xy。若從反方向看，則稱(chēng)xy直接歸約到xy。顯然，文法的產(chǎn)生式右部是其左部的直接推導(dǎo)。 例 已知文法GS： S0S1， S010S10011 (使用規(guī)則S01,x=0,y=1)S 0S1 (使用規(guī)則S0S1,x=,y=)0S100S11 (使用規(guī)則S0S1,x=0,y=1)2.3 2.3 推導(dǎo)推導(dǎo)(P17) 第34頁(yè)/共81頁(yè)2.3 2.3 推導(dǎo)推導(dǎo) 練

19、習(xí) 已知文法G:| a|b|z 0|1|9 指出下面直接推導(dǎo)所使用的規(guī)則： abc abc5第35頁(yè)/共81頁(yè)n推導(dǎo)（ ）：如果存在一直接推導(dǎo)序列0 1 n， 則表示為： 0 n 其中， “ ”讀為“推導(dǎo)出”或“產(chǎn)生”，即 0推導(dǎo)出或產(chǎn)生n。若從反方向看，則稱(chēng)n歸約到0。 n 是推導(dǎo)長(zhǎng)度，要求n0 。2.3 2.3 推導(dǎo)推導(dǎo) +第36頁(yè)/共81頁(yè)2.3 2.3 推導(dǎo)推導(dǎo)例 已知文法： := :=| :=0|1|2|3|4|5|6|7|8|9有： 2 將上述三個(gè)直接推導(dǎo)連接起來(lái)，可得如下推導(dǎo)過(guò)程： 2則記： 2，顯然，n=3。+第37頁(yè)/共81頁(yè)n廣義推導(dǎo)（ ）：如果有0 n 或0 =n, 即n

20、 0，則表示為： 0 n 其中， “ ”讀為“廣義推導(dǎo)出”或“廣義產(chǎn)生”。若從反方向看，則稱(chēng)n廣義歸約到0。2.3 2.3 推導(dǎo)推導(dǎo) +*第38頁(yè)/共81頁(yè)2.3 2.3 推導(dǎo)推導(dǎo)例 已知文法： := :=| :=0|1|2|3|4|5|6|7|8|9 2，也可記為： 2， 從到的推導(dǎo)，無(wú)須使用任何規(guī)則，其推導(dǎo)長(zhǎng)度n=0，則記作： +*第39頁(yè)/共81頁(yè)2.3 2.3 推導(dǎo)推導(dǎo) 例 GS:SaASASbAASSSaAba證明S aabbaa。證明：第1種 SaASaAaaSbAaaSbbaaaabbaa 第2種 SaASaSbASaabASaabbaSaabbaa第3種 SaASaSbASaS

21、bAaaabAaaabbaa+第40頁(yè)/共81頁(yè)2.3 2.3 推導(dǎo)推導(dǎo)規(guī)范推導(dǎo)（或最右推導(dǎo)）：在推導(dǎo)的任何一步，都是對(duì)中的最右非終結(jié)符進(jìn)行替換。最左推導(dǎo)：在推導(dǎo)的任何一步，都是對(duì)中的最左非終結(jié)符進(jìn)行替換。例 上例中的S aabbaa SaASaAaaSbAaaSbbaaaabbaa(規(guī)范推導(dǎo)) SaASaSbASaabASaabbaSaabbaa(最左推導(dǎo)) SaASaSbASaSbAaaabAaaabbaa(非左非右推導(dǎo))+第41頁(yè)/共81頁(yè)2.4 2.4 句型和句子句型和句子（P18P18）句型：設(shè)Z是文法G的識(shí)別符號(hào)，如果Z x，xV* ，則稱(chēng)符號(hào)串x為文法G的一個(gè)句型。顯然，Z是文法

22、G的一個(gè)句型。*例 在S aabbaa中,有SaASaAaaSbAaaSbbaaaabbaa 則, aAS、aAa、aSbAa、aSbbaa和aabbaa是該文法的句型，也是該文法的規(guī)范句型。+規(guī)范句型：能用規(guī)范推導(dǎo)產(chǎn)生的句型。第42頁(yè)/共81頁(yè)2.4 2.4 句型和句子句型和句子句子:設(shè)Z是文法G的識(shí)別符號(hào)，如果Z x，xVt* ，則稱(chēng)符號(hào)串x為文法G的一個(gè)句子。顯然，句型包括句子或說(shuō)句子是特殊的句型，句子是完全由終結(jié)符號(hào)組成的句型。+例 在S aabbaa中,有SaASaAaaSbAaaSbbaaaabbaa則, aabbaa是該文法的句子。+第43頁(yè)/共81頁(yè)2.4 2.4 句型和句子句

23、型和句子每一個(gè)句子都有一個(gè)規(guī)范推導(dǎo)，但并非每一個(gè)句型都有規(guī)范推導(dǎo)。例 := :=| :=0|1|2|3|4|5|6|7|8|9 2句型“2 ”不是規(guī)范句型 3 3句型“3”是規(guī)范句型 第44頁(yè)/共81頁(yè)2.5 2.5 語(yǔ)言語(yǔ)言（P19P19）語(yǔ)言:一個(gè)文法GZ所產(chǎn)生的所有句子的集合L(GZ), 稱(chēng)為文法GZ所定義的語(yǔ)言, 即: L(GZ)=x|xVt* , 且Z x 例 已知文法GS：S:=0S1|01，求其所產(chǎn)生的語(yǔ)言。解： S 01 S 0S1 0011 S 0S1 00S11 000111 L(GS)=01，0011，000111，=0n1n|n0+第45頁(yè)/共81頁(yè)2.5 2.5 語(yǔ)言

24、語(yǔ)言例 the ate banana monkey 其語(yǔ)言只有下面4個(gè)句子： the monkey ate the banana the banana ate the monkey the monkey ate the monkey the banana ate the banana第46頁(yè)/共81頁(yè)2.5 2.5 語(yǔ)言語(yǔ)言練習(xí)句子:=主語(yǔ)謂語(yǔ) 主語(yǔ):=代詞|名詞 代詞:= 你 | 我 | 他 名詞:= 王明 | 大學(xué)生 | 工人 | 英語(yǔ) 謂語(yǔ):=動(dòng)詞直接賓語(yǔ) 動(dòng)詞:= 是 | 學(xué)習(xí) 直接賓語(yǔ):= 代詞|名詞下列是否是句子？我是大學(xué)生王明是大學(xué)生王明學(xué)習(xí)英語(yǔ)他學(xué)習(xí)英語(yǔ)你是工人下列是否是句子？

25、我大學(xué)生是大學(xué)生是王明英語(yǔ)學(xué)習(xí)王明大學(xué)生學(xué)習(xí)他工人是英語(yǔ)第47頁(yè)/共81頁(yè)2.5 2.5 語(yǔ)言語(yǔ)言 文法和語(yǔ)言的關(guān)系：給定一個(gè)文法，就能從結(jié)構(gòu)上唯一的確定其語(yǔ)言，即: GL(G)。給定一種語(yǔ)言，能確定其文法，但不唯一，即: LG1 或G2 或。等價(jià)文法：如果不同的文法可描述相同的語(yǔ)言，則稱(chēng)這些文法為等價(jià)文法。文法語(yǔ)言1:1n:1第48頁(yè)/共81頁(yè)2.5 2.5 語(yǔ)言語(yǔ)言例2-5(P19) 已知語(yǔ)言為 L(G)=abna|n 1，構(gòu)造產(chǎn)生該語(yǔ)言的文法。解：根據(jù)語(yǔ)言的形式，可構(gòu)造其文法G為: ZaBa BBb|b 還可以構(gòu)造文法G1為: ZaBa BbB|b 顯然，G和G1是兩個(gè)不同的文法，但它們

26、都可以描述語(yǔ)言abna|n1,因此它們是等價(jià)文法。 第49頁(yè)/共81頁(yè)2.62.6遞歸規(guī)則與遞歸文法遞歸規(guī)則與遞歸文法(P20)(P20)遞歸規(guī)則：是指那些在規(guī)則的右部含有與規(guī)則左部相同符號(hào)的規(guī)則。右遞歸規(guī)則： 形如U:=xU的規(guī)則。例 U:=xUy，因?yàn)橐?guī)則右部含有與規(guī)則左部相同符號(hào)U， 所以U:=xUy就是一條遞歸規(guī)則。左遞歸規(guī)則：形如U:=Uy的規(guī)則。第50頁(yè)/共81頁(yè)2.62.6遞歸規(guī)則與遞歸文法遞歸規(guī)則與遞歸文法直接遞歸文法：至少包含一條遞歸規(guī)則的文法。例 設(shè)文法GA: A:=B B:=X|BA X:=Xa|Xb|a|b該文法是一個(gè)具有直接左遞歸性的文法。 第51頁(yè)/共81頁(yè)2.62

27、.6遞歸規(guī)則與遞歸文法遞歸規(guī)則與遞歸文法間接遞歸文法：表面上看文法的每條規(guī)則都不是遞歸規(guī)則，但存在某個(gè)推導(dǎo)會(huì)導(dǎo)致遞歸出現(xiàn)。例 設(shè)有文法GS: S:=Qd Q:=Rb|Se R:=Sa|Qf|a S Qd Sed，即S Sed文法G是一個(gè)間接遞歸文法。+第52頁(yè)/共81頁(yè)2.62.6遞歸規(guī)則與遞歸文法遞歸規(guī)則與遞歸文法語(yǔ)言的句子的個(gè)數(shù)是有窮還是無(wú)窮取決于定義該語(yǔ)言的文法是否是遞歸的。例 例2-1（P15）的文法是無(wú)遞歸的，因此其所產(chǎn)生的句子是有窮的，只產(chǎn)生4個(gè)句子。例2-3（P16）的文法有遞歸規(guī)則，屬于遞歸文法，所以它所描述的語(yǔ)言為所有無(wú)符號(hào)整數(shù)，是無(wú)窮的。第53頁(yè)/共81頁(yè)2.62.6遞歸規(guī)

28、則與遞歸文法遞歸規(guī)則與遞歸文法遞歸文法包括直接遞歸文法和間接遞歸文法，運(yùn)用遞歸文法使我們能用有窮的文法刻畫(huà)無(wú)窮的語(yǔ)言。練習(xí) 判定如下文法所描述的語(yǔ)言是否是有窮的。 S:=(S) S:=解：因?yàn)槲姆ㄖ械牡谝粭l產(chǎn)生式S:=(S)是遞歸規(guī)則，所以該文法是遞歸文法，所描述的語(yǔ)言為L(zhǎng)(GS)=,(),(),(), =(n)n|n0，是無(wú)窮的。第54頁(yè)/共81頁(yè)2.8 2.8 語(yǔ)法樹(shù)語(yǔ)法樹(shù)(P21)(P21)語(yǔ)法樹(shù)（或推導(dǎo)樹(shù)）：用樹(shù)形結(jié)構(gòu)來(lái)直觀地表示句型的推導(dǎo)過(guò)程。設(shè)有文法G=(Vn,Vt,P,S)，對(duì)于文法G的任意一個(gè)句型都存在一棵相應(yīng)的語(yǔ)法樹(shù)，這棵樹(shù)滿(mǎn)足下列4個(gè)條件：如果樹(shù)中的一個(gè)結(jié)點(diǎn)A有若干個(gè)直接后

29、繼，從左到右分別是B1,B2,B3,Bn，則有A:=B1B2B3Bn P。如果樹(shù)中的一個(gè)結(jié)點(diǎn)至少有一個(gè)直接后繼，則說(shuō)明該結(jié)點(diǎn)一定是一個(gè)非終結(jié)符號(hào)。樹(shù)的根結(jié)點(diǎn)是文法的開(kāi)始符號(hào)S。樹(shù)中的每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V中的一個(gè)符號(hào)。第55頁(yè)/共81頁(yè)2.8 2.8 語(yǔ)法樹(shù)語(yǔ)法樹(shù)例: GS:SaASASbAASSSaAba例 上例中的S aabbaa SaASaAaaSbAaaSbbaaaabbaa(規(guī)范推導(dǎo)) SaASaSbASaabASaabbaSaabbaa(最左推導(dǎo)) SaASaSbASaSbAaaabAaaabbaa(非左非右推導(dǎo))+第56頁(yè)/共81頁(yè)2.8 2.8 語(yǔ)法樹(shù)語(yǔ)法樹(shù)文法的句型

30、都是按照文法的產(chǎn)生式來(lái)生成相應(yīng)的語(yǔ)法樹(shù)，其生成過(guò)程如下：推導(dǎo)過(guò)程不同，生成語(yǔ)法樹(shù)的過(guò)程也不同，但是，如果文法是無(wú)二義性的，則最終生成的語(yǔ)法樹(shù)是相同的。語(yǔ)法樹(shù)的末端節(jié)點(diǎn)（葉節(jié)點(diǎn)）從左向右排列起來(lái)，構(gòu)成句型。如果葉節(jié)點(diǎn)都是終結(jié)符號(hào)，則從左向右構(gòu)成句子。b.根據(jù)句型的結(jié)構(gòu)特點(diǎn)來(lái)選擇文法中產(chǎn)生式，最終生成該句型對(duì)應(yīng)的語(yǔ)法樹(shù)。a.以文法G的開(kāi)始符號(hào)作為語(yǔ)法樹(shù)的根結(jié)點(diǎn)第57頁(yè)/共81頁(yè)2.8 2.8 語(yǔ)法樹(shù)語(yǔ)法樹(shù)練習(xí)：已知文法 SaBc | bAB AaAb| b Bb | 寫(xiě)出符號(hào)串babbb的規(guī)范推導(dǎo)，并畫(huà)出語(yǔ)法樹(shù)。第58頁(yè)/共81頁(yè)2.10 2.10 由樹(shù)構(gòu)造推導(dǎo)過(guò)程由樹(shù)構(gòu)造推導(dǎo)過(guò)程（P23P23）

31、根據(jù)已有的語(yǔ)法樹(shù)，可以從上而下或從下而上建立推導(dǎo)。從下而上的方法：逐層地修剪子樹(shù)末端節(jié)點(diǎn)來(lái)建立推導(dǎo)。當(dāng)有兩棵以上子樹(shù)時(shí)，原則上修剪那一棵都可以，如果每次總是修剪最左邊的子樹(shù)，即相當(dāng)于每步都對(duì)歸約句型的句柄歸約，則稱(chēng)為“最左歸約”或“規(guī)范歸約”。規(guī)范推導(dǎo)與規(guī)范歸約互為逆過(guò)程。 從上而下的方法：從樹(shù)根開(kāi)始由上而下逐層地用子節(jié)點(diǎn)代替父節(jié)點(diǎn)。當(dāng)一層中有兩棵以上子樹(shù)根時(shí)，原則上先選哪一棵樹(shù)根替換都可以。而每步都對(duì)最右邊的子樹(shù)樹(shù)根符號(hào)替換，則構(gòu)造出的推導(dǎo)是規(guī)范推導(dǎo)。第59頁(yè)/共81頁(yè)2.10 2.10 由樹(shù)構(gòu)造推導(dǎo)過(guò)程由樹(shù)構(gòu)造推導(dǎo)過(guò)程練習(xí) 已知文法： E:=E+T|T T:=T*F|F F:=(E)|i

32、句型E+(E+T)*i對(duì)應(yīng)的語(yǔ)法樹(shù)如圖所示,請(qǐng)根據(jù)該語(yǔ)法樹(shù)寫(xiě)它的規(guī)范推導(dǎo)。第60頁(yè)/共81頁(yè)2.10 2.10 由樹(shù)構(gòu)造推導(dǎo)過(guò)程由樹(shù)構(gòu)造推導(dǎo)過(guò)程句型E+(E+T)*i的規(guī)范推導(dǎo)：第61頁(yè)/共81頁(yè)2.10 2.10 由樹(shù)構(gòu)造推導(dǎo)過(guò)程由樹(shù)構(gòu)造推導(dǎo)過(guò)程語(yǔ)法樹(shù)和推導(dǎo)之間的對(duì)應(yīng)關(guān)系：每一棵語(yǔ)法樹(shù)至少存在一個(gè)推導(dǎo)與之相對(duì)應(yīng)每一個(gè)推導(dǎo)都存在一棵語(yǔ)法樹(shù)語(yǔ)法樹(shù)推導(dǎo)1:n1:1第62頁(yè)/共81頁(yè)2.7 2.7 短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄（P21P21）短語(yǔ)：設(shè)GZ是一文法, w=xuy是一句型,如果有 Z xUy 且U u ,其中UVn , uV+,則稱(chēng)u為句型w(相對(duì)于非終結(jié)符號(hào)U)的短語(yǔ)。顯然

33、,w是相對(duì)Z的句型w的短語(yǔ)。句柄：任一句型的最左簡(jiǎn)單短語(yǔ)稱(chēng)為該句型的句柄。一個(gè)句型的句柄一定是該句型的簡(jiǎn)單短語(yǔ)。 簡(jiǎn)單短語(yǔ)(或直接短語(yǔ))：若有 Z xUy 且U u，則稱(chēng)u是句型w相對(duì)于非終結(jié)符號(hào)U的簡(jiǎn)單短語(yǔ)。一個(gè)句型的直接短語(yǔ)一定是該句型的短語(yǔ)。 *+*第63頁(yè)/共81頁(yè)2.7 2.7 短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄求一個(gè)句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄的方法: 語(yǔ)法樹(shù)（建議用該方法）：由文法的開(kāi)始符號(hào)開(kāi)始，通過(guò)產(chǎn)生式來(lái)構(gòu)造與該句型相對(duì)應(yīng)的語(yǔ)法樹(shù)。推導(dǎo)法：由文法的開(kāi)始符號(hào)開(kāi)始，找出該句型的所有推導(dǎo)。第64頁(yè)/共81頁(yè)2.9 2.9 子樹(shù)和短語(yǔ)子樹(shù)和短語(yǔ)(P22)(P22)例 已知文法：

34、E:=E+T|T T:=T*F|F F:=(E)|i 句型E+(E+T)*i對(duì)應(yīng)的語(yǔ)法樹(shù)如圖所示,請(qǐng)根據(jù)該語(yǔ)法樹(shù)寫(xiě)它的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。第65頁(yè)/共81頁(yè)2.9 2.9 子樹(shù)和短語(yǔ)子樹(shù)和短語(yǔ)句型E+(E+T)*i的短語(yǔ)為： E+(E+T)*i、 (E+T)*i 、 (E+T)、 E+T 、 i句型E+(E+T)*i的簡(jiǎn)單短語(yǔ)為： E+T 、 i句型E+(E+T)*i的句柄為： E+T第66頁(yè)/共81頁(yè)2.9 2.9 子樹(shù)和短語(yǔ)子樹(shù)和短語(yǔ)例 GS:SaASASbAASSSaAba 求句型aabbaa的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。句型aabbaa的短語(yǔ)為： aabbaa 、 abba、 a(左起第2

35、個(gè)) 、 ba 、 a(最后1個(gè)) 句型aabbaa的簡(jiǎn)單短語(yǔ)為： a(左起第2個(gè)) 、 ba 、 a(最后1個(gè)) 句型aabbaa的句柄為： a(左起第2個(gè)) 第67頁(yè)/共81頁(yè)2.9 2.9 子樹(shù)和短語(yǔ)子樹(shù)和短語(yǔ)課堂練習(xí)已知文法 GZ:ZAbB | bBAA Ba | cBAb | d求句型cbdab的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。第68頁(yè)/共81頁(yè)2.11 2.11 文法的二義性文法的二義性（P23P23）二義性文法：如果一個(gè)文法所定義的某個(gè)句子或句型，它存在兩棵（或兩棵以上）不同的語(yǔ)法樹(shù)，那么這個(gè)句子或句型是二義性的，該文法是二義性文法。 例2-11(P23) 有文法GE：E = E+E |

36、E*E |（E）| i，分析該文法是否為二義性文法。EE+EE*EiiiEE*EEEiii+解：句子i+i*i存在兩棵不同的語(yǔ)法樹(shù)，因此文法G 是二義性文法。 第69頁(yè)/共81頁(yè)2.11 2.11 文法的二義性文法的二義性EE+EE*EiiiEE*EEEiii+語(yǔ)法樹(shù)1 在語(yǔ)法樹(shù)1中， i+i*i的規(guī)范推導(dǎo)為：EE+EE+E*EE+E*iE+i*ii+i*i即，在語(yǔ)法樹(shù)1中的*先作為句柄歸約，表示*優(yōu)先于+進(jìn)行運(yùn)算。 語(yǔ)法樹(shù)2 二義性產(chǎn)生的后果會(huì)導(dǎo)致分析結(jié)果不同，導(dǎo)致對(duì)句子的理解不同。因此，在算術(shù)表達(dá)式中規(guī)定乘除高于加減，從而避免二義性。 在語(yǔ)法樹(shù)2中， i+i*i的規(guī)范推導(dǎo)為：EE*EE*i

37、E+E*iE+i*ii+i*i即，在語(yǔ)法樹(shù)2中的+先作為句柄歸約，表示+優(yōu)先于*進(jìn)行運(yùn)算。第70頁(yè)/共81頁(yè)2.11 2.11 文法的二義性文法的二義性例2-12(P24) if語(yǔ)句文法如下： = ifthen |ifthenelse |說(shuō)明該文法是二義性文法。解：假設(shè)有一個(gè)if語(yǔ)句嵌套的句型為：ifthen ifthenelse 該句型存在兩棵不同的語(yǔ)法樹(shù)，所以該文法是二義性文法。第71頁(yè)/共81頁(yè)2.11 2.11 文法的二義性文法的二義性語(yǔ)句 布爾表達(dá)式 if then語(yǔ)句 布爾表達(dá)式 ifthen語(yǔ)句 else 語(yǔ)句 語(yǔ)句 布爾表達(dá)式 if then語(yǔ)句 布爾表達(dá)式 if then 語(yǔ)

38、句 else語(yǔ)句 語(yǔ)法樹(shù)1 語(yǔ)法樹(shù)2 語(yǔ)法樹(shù)1意味著else和第2個(gè)if配對(duì)（就近配對(duì)），語(yǔ)法樹(shù)2表示else和第1個(gè)if配對(duì)。 因此，在if語(yǔ)句中規(guī)定else與最近的if配對(duì)(即就近配對(duì))。第72頁(yè)/共81頁(yè)2.11 2.11 文法的二義性文法的二義性文法的二義性是不可判定的，即不存在一種算法，它能夠在有限步內(nèi)確切地判定一個(gè)文法是否是二義性的。例2-13 改寫(xiě)文法GE： E = E+E | E*E |（E）| i，使其無(wú)二義性。解：新添非終結(jié)符號(hào)T和F，將文法改寫(xiě)成：E = T |E+T，T =F |T*F，F(xiàn) = (E) | i 這樣，就避免了二義性。用改寫(xiě)后的文法給出句i+i*i的語(yǔ)法樹(shù)如右圖所示。此時(shí)的語(yǔ)法樹(shù)是唯一的。 ET+EF*TTiFFii第73頁(yè)/共81頁(yè)2.12 2.12 有關(guān)文法的實(shí)用限制有關(guān)文法的實(shí)用限制（P25P25） 文法的實(shí)用限制：就是從實(shí)用的觀點(diǎn)出發(fā)，對(duì)文法做一些必要的限制。以下是對(duì)文法的實(shí)用限制：文法不能是二義性的。不能有U =U這樣的有害規(guī)則。不能有多余規(guī)則推導(dǎo)中始終用不到的規(guī)則。(不可達(dá)規(guī)則)一旦使用某規(guī)則后無(wú)法推出終結(jié)符號(hào)串的規(guī)則。(無(wú)用規(guī)則)第74頁(yè)/共81頁(yè)2.12 2.12 有關(guān)文法的實(shí)用限制有關(guān)文法的實(shí)用限制 檢查多余規(guī)則的方法：檢查文法中每一條規(guī)則