Chapt文法和語言實用PPT課件

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

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

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

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

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

6、：令A、B為兩個符號串集合，AB=xy|xA ,yB 。對于空集合有，有 A=A =A 。例 A=a,b， B=c,d，則AB=ac,ad,bc,bd 符號串的冪運算：若x是符號串，則： x0=, x1=x ， x2=xx，xn=xxx=xxn-1=xn-1 x，其中 n0 。 例 x=abc, x0=， x1=abc， x2=abcabc，第10頁/共81頁2.1 2.1 字母表和符號串字母表和符號串 集合的冪運算：設A為符號串集合，則： 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頁/共81頁2.1 2.1 字母表和符號串字母表和符號串 集合的正閉包：設A為一個集合，則： A+ =A1A2.An例 A =a,b，則A+ =a,b,aa,ab,ba,bb,aaa,aab,集合的閉包：設A為一個集合，則： A* =A0 A+ 例 A =a,b，則A* =,a,b,aa,ab,ba,bb,aaa,aab,一個集合的閉包比正閉包多個。 第12頁/共81頁例：2.2 文法(P14) 文法實際上就是描述語言語法結構的形式規(guī)則。 第13頁/共81頁第14頁/共81頁例終結符號集Vt=the, gray, wolf, will, eat, goat非終結符號集Vn=, , ,

8、, , , , , , 產生式集P= , 開始符號Z= 又稱為語法規(guī)則集，即符號的組成規(guī)則組成語言的基本符號語言的語法成分第15頁/共81頁文法G的形式定義：G=(Vn，Vt，P，Z)Vn(非終結符號集)是一個由非終結符號（一般是大寫字母或用）構成的非空有窮集合。Vt (終結符號集)是一個由終結符號（如小寫字母、數字、標點符號等）構成的非空有窮集合。 VtVn=，VtVn，V是該文法的字母表或詞匯表。P(產生式集)是一個由產生式或規(guī)則構成的非空有窮集合。 產生式的形式為： 或:= 產生式的左部V+，即不能為空，產生式的右部V*，“”或”“:=”含義相同，表示“定義為”或“由組成”。Z是文法的識

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

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

11、字組成的非終結符號或由多個字母組成的符號。例（一般寫成monkey ）第21頁/共81頁2.2 2.2 文法文法“”和“”：表示可重復連接，tkm表示符號串t可重復連接k到m次，而t表示符號串t可重復連接0到無窮次。例13 等價于： | EE+T|T 與 ET+T 相同字母打頭、后面可跟字母或數字的不超過8個字符的標識符文法則為： |07第22頁/共81頁2.2 2.2 文法文法“”和“ ”：表示括起來的內容可有可無。如t表示符號串t可有可無。例 IF THEN IF THEN ELSE 可寫成： IF THEN ELSE 第23頁/共81頁2.2 2.2 文法文法“（”和“）”：表示括號內的

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

13、： 其中， V+ (即可以是V上的符號序列，但不能為空)，V* (即是V上的符號序列，可以是) 。如果文法中有產生式的右部為，并且該產生式的左部不是一個非終結符，則該文法一定是0型文法。0型文法描述的語言為0型語言。例 文法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:= ，該文法是一個0型文法。 第26頁/共81頁2.132.13文法和語言分類文法和語言分類（P26P26） 1型文法(或上下文有關文法) 若文法中有如下形式的規(guī)則： Uu 其中， UVn，、V*，u

14、 V* ，即規(guī)則左部可為符號序列，其中U為非終結符號且只有在左右為和的環(huán)境下U可變?yōu)閡。1型文法的產生式左部的長度小于等于其右部的長度，但S除外。1型文法描述的語言為1型語言。例 文法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 ，該文法是一個1型文法。第27頁/共81頁2.132.13文法和語言分類文法和語言分類（P26P26） 2型文法(或上下文無關文法) 若文法中的規(guī)則都具有如下形式： Uu 其中， U Vn ， u V*，即2型文法中的規(guī)則左部必

15、須是一個非終結符號，規(guī)則右部u是V上的符號序列。該文法相當于對1型文法中的規(guī)則形式加以限制，即要求和必須為空。2型文法也稱作上下文無關文法，描述的語言為2型語言。一般用2型文法來描述程序設計語言的語法規(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 ，該文法是一個2型文法。第28頁/共81頁2.132.13文法和語言分類文法和語言分類（P27P27） 3型文法(或正規(guī)文法) 若文法中的規(guī)則都具有如下形式： Ua |Wa（左線性）或 Ua|aW（右線性） 其中，

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

17、=1Z|1C:=0Z|00型文法3型文法第30頁/共81頁2.132.13文法和語言分類文法和語言分類 練習 判斷以下文法的類型 文法GS:S:=AA:=aABD|abBBD:=CBCB:=CDCD:=BDbB:=bbD:=c文法GZ:Z:=B0C|C1B:=Z1|1C:=Z0|01型文法2型文法第31頁/共81頁文法的四種分類第32頁/共81頁2.132.13文法和語言分類文法和語言分類四種文法的關系：通過對文法的產生式逐漸增加限制來定義四種文法，因此 0型語言包含1型語言，1型語言包含2型語言，2型語言包含3型語言?；蛘哒f，3型文法是2型文法的特例，2型文法是1型文法的特例，1型文法又是0

18、型文法的特例 。第33頁/共81頁n直接推導（）：是文法G的一個產生式， x,yV*，符號串xy中的非終結符號用替換，從而得到符號串xy，則表示為： xy xy 其中“”讀為“直接推導出”或“直接產生” 。即稱xy直接推導出xy,或xy直接產生xy。若從反方向看，則稱xy直接歸約到xy。顯然，文法的產生式右部是其左部的直接推導。 例 已知文法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 推導推導(P17) 第34頁/共81頁2.3 2.3 推導推導 練

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

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

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

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

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

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

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

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

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

28、則與遞歸文法遞歸規(guī)則與遞歸文法遞歸文法包括直接遞歸文法和間接遞歸文法，運用遞歸文法使我們能用有窮的文法刻畫無窮的語言。練習 判定如下文法所描述的語言是否是有窮的。 S:=(S) S:=解：因為文法中的第一條產生式S:=(S)是遞歸規(guī)則，所以該文法是遞歸文法，所描述的語言為L(GS)=,(),(),(), =(n)n|n0，是無窮的。第54頁/共81頁2.8 2.8 語法樹語法樹(P21)(P21)語法樹（或推導樹）：用樹形結構來直觀地表示句型的推導過程。設有文法G=(Vn,Vt,P,S)，對于文法G的任意一個句型都存在一棵相應的語法樹，這棵樹滿足下列4個條件：如果樹中的一個結點A有若干個直接后

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

30、都是按照文法的產生式來生成相應的語法樹，其生成過程如下：推導過程不同，生成語法樹的過程也不同，但是，如果文法是無二義性的，則最終生成的語法樹是相同的。語法樹的末端節(jié)點（葉節(jié)點）從左向右排列起來，構成句型。如果葉節(jié)點都是終結符號，則從左向右構成句子。b.根據句型的結構特點來選擇文法中產生式，最終生成該句型對應的語法樹。a.以文法G的開始符號作為語法樹的根結點第57頁/共81頁2.8 2.8 語法樹語法樹練習：已知文法 SaBc | bAB AaAb| b Bb | 寫出符號串babbb的規(guī)范推導，并畫出語法樹。第58頁/共81頁2.10 2.10 由樹構造推導過程由樹構造推導過程（P23P23）

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

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

33、,w是相對Z的句型w的短語。句柄：任一句型的最左簡單短語稱為該句型的句柄。一個句型的句柄一定是該句型的簡單短語。 簡單短語(或直接短語)：若有 Z xUy 且U u，則稱u是句型w相對于非終結符號U的簡單短語。一個句型的直接短語一定是該句型的短語。 *+*第63頁/共81頁2.7 2.7 短語、簡單短語和句柄短語、簡單短語和句柄求一個句型的短語、簡單短語和句柄的方法: 語法樹（建議用該方法）：由文法的開始符號開始，通過產生式來構造與該句型相對應的語法樹。推導法：由文法的開始符號開始，找出該句型的所有推導。第64頁/共81頁2.9 2.9 子樹和短語子樹和短語(P22)(P22)例 已知文法：

34、E:=E+T|T T:=T*F|F F:=(E)|i 句型E+(E+T)*i對應的語法樹如圖所示,請根據該語法樹寫它的短語、簡單短語和句柄。第65頁/共81頁2.9 2.9 子樹和短語子樹和短語句型E+(E+T)*i的短語為： E+(E+T)*i、 (E+T)*i 、 (E+T)、 E+T 、 i句型E+(E+T)*i的簡單短語為： E+T 、 i句型E+(E+T)*i的句柄為： E+T第66頁/共81頁2.9 2.9 子樹和短語子樹和短語例 GS:SaASASbAASSSaAba 求句型aabbaa的短語、簡單短語和句柄。句型aabbaa的短語為： aabbaa 、 abba、 a(左起第2

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

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

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

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