1、1第四章第四章 文法和語言文法和語言u本章內容：本章內容：文法和語言的形式定義文法和語言的形式定義 文法的類型文法的類型上下文無關文法及其語法樹上下文無關文法及其語法樹上下文無關文法的句型分析上下文無關文法的句型分析語法-一組規則-文法 語言語義靜態：類型匹配、作用域、動態：功能對程序設計語言給出精確無二義的對程序設計語言給出精確無二義的語法描述（嚴謹、簡潔、易讀）語法描述（嚴謹、簡潔、易讀）2預備知識預備知識 -語言概述語言概述z 任何一種語言都是由該語言的基本符號（字母表）組成的符號串（句子）的集合。z 漢語-所有符合漢語語法的句子的全體z 英語-所有符合英語語法的句子的全體z 程序設計語

2、言-所有該語言的程序的全體z 句子是無限的，但句子都是有結構的，其構成是有規律的（句型），可用規則嚴格定義-可用有限規則（文法），刻畫無限句子。例如： 我是學生、你學習英語、他喜歡運動、3z 語言具有兩個可識別的特性，即語言的形式和該形式相關聯的意義。z 如果不考慮語義，即只從語法這一側面來看語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個數學系統。“形式”是指這樣的事實：語言的所有規則只以什么符號串能出現的方式來陳述。形式語言理論是對符號串集合的表示法、結構及其特性的研究。是程序設計語言語法分析研究的基礎。4預備知識 -有關定義和記號z符號：可以相互區別的記號（元素）。z字母表：

3、符號（元素）的非空有窮集合。z符號串：由字母表中的符號組成的任何有窮序列稱為該字母表上的符號串。特別空符號串。z符號串s的前綴、符號串s的后綴、符號串s的子串 對于每個符號串s，s和兩者都是符號串s的前綴，后綴和子串。 z符號串s的真前綴、真后綴、真子串x是s的前綴，后綴或子串，并且 s x5z 符號串的運算y符號串s的長度|s|，的長度為0y連接：符號串x、y的連接,是把y的符號寫在x的符號之后得到的符號串xy，如x=ab,y=cd，則xy=abcd，特別a = a y方冪：符號串自身連接n次得到的符號串an ：a1=a,a2=aa，a0=z 符號串集合：字母表上的z 兩個符號串集合A和B的

4、乘積定義為AB =xy|xA且yB 若集合A=ab,cde，B = 0,1，則 AB=ab1,ab0,cde0,cde1z *稱為的閉包，表示上的一切符號串(包括)組成的集合z 上的除外的所有符號串組成的集合+ ，稱為的正閉包。.2*.32*6z語言：字母表上的一個語言是上的一些符號串的集合 (上的每個語言是*的一個子集)。 例如：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,anbn,或w|w*且w=anbn,n1為字母表上的一個語言。 特別、 即 都是語言。 7語言語言上上的運算的運算若設L 和M是上的語言： z 語言L和M的并LM ，交，差，補是一

5、個語言z 語言L和M的連接是一個語言，記為 LM=st |sL且 tM有L = L=L。 L的n次連接Ln= LL.L z 語言L的 閉包記為 L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1= Ln-1 L,n1z 語言L的正 閉包記為 L+， L+= L1 L2 L3 . L+= LL*= L*L，L*= L+ 若L1=a,b, y,z， M1=1,28,9 ， 則L1(L1M1)*=所有字母打頭的字母和數字符號串81 1 文法和語言的形式定義文法和語言的形式定義如何來描述一種語言？如何來描述一種語言？有窮語言（只含有窮個句子），可以逐一列舉有窮語言（只含有窮個句子）

6、，可以逐一列舉無窮語言，找出語言的有窮表示。有兩個途經：無窮語言，找出語言的有窮表示。有兩個途經： 生成方式生成方式 （文法）：每個句子可用嚴格定義的規則來構造（文法）：每個句子可用嚴格定義的規則來構造 識別方式識別方式（自動機）：用一個過程，當輸入的串屬于語言時，（自動機）：用一個過程，當輸入的串屬于語言時，該過程經有限次計算后就會停止并回答該過程經有限次計算后就會停止并回答“是是”，否則，要，否則，要么能停止并回答么能停止并回答“不是不是”，要么永遠繼續下去。，要么永遠繼續下去。9文法定義定義文法G定義為四元組(VN，VT，P，S )，其中 VN:非終結符號(語法實體)集；VT:終結符號集

7、；P: 規則的集合 S VN ，稱作識別符號或開始符號。 VN，VT和P是非空有窮集且VN VT = V=VN VT ，稱為文法G的字母表或字匯表 規則（產生式規則（產生式或生成式）生成式）形如，其中V+， V*。例：文法例：文法G=（VN，VT，P，S）VN = S , VT = 0, 1 , P= S0S1, S01 例例: 文法文法G=（VN，VT，P，S）VN =標識符，字母，數字標識符，字母，數字VT =a,b,c,x,y,z,0,1,9P= | a|z z 00|9 9 S=習慣上，只將產生式寫出，第一條產生式的左部是開始符號；習慣上，只將產生式寫出，第一條產生式的左部是開始符號；

8、大寫字母表示非終結符，小寫字母表示終結符大寫字母表示非終結符，小寫字母表示終結符 GS:GS: Aab |aA Aab |aAb | | SaS SaSb|A注意到遞歸11推導、歸約的定義推導、歸約的定義直接推導直接推導“” 是文法是文法G G的產生式，若有的產生式，若有v,wv,w滿足：滿足：v=,w=,v=,w=, 其中其中VV* *,V,V* * 則稱則稱v v直接直接推導推導到到w w（w w直接直接歸約歸約到到v v）, ,記作記作 v v w w若存在若存在v =w0 w1 . wn=w (n0)， 則記為則記為v w，稱作，稱作v推導出推導出w，或，或w歸約到歸約到v 若有若有

9、v w或或 v=w， 則記為則記為v w例例G G：S0S1， S01 S 0S1 00S11000S11100001111 簡寫為S 00001111*12句型、句子的定義句型、句子的定義z 有文法有文法GS，若，若S x，則稱，則稱x是文法是文法G的句型。的句型。z 有文法有文法GS，若，若S x，且，且xVVT T* *，則稱，則稱x是文法是文法G的句子。的句子。例：例：GE E：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a G的句型E E，E+T，T+T，F+T，a

10、+T，a+T*F，a+F*F，a+a*F， a+a*a G的句子a+a*a *程序就是句子13語言的定義語言的定義L(G)=x | S x，其中S為文法的開始符號，且x VT* 例G：S0S1 | 01 L(G)=0n1n|n1例GS：（1）SaSBE | aBE （2）EBBE （3）aBab （4）bBbb （5）bEbe （6）eEee L（G）= anbnen | n1 G生成的每個串都在L(G)中，L(G)中的每個串確實能被G生成*S an-1S(BE)n-1 = an(BE)n = anB(EB)n-1E = anB(BE)n-1E = anB2(EB)n-2E2 anBnEn a

11、nbnEn anbnen*14z 已知語言描述，寫出文法 例：若語言由0、1符號串組成，串中0和1的個數相同，構造其文法 A 0B | 1CB 1 | 1A | 0BBC 0 | 0A | 1CCz 已知文法，寫出語言描述例：GE：EE+T|T TT*F|F F(E)|az 若L(G1)=L(G2)，則稱文法G1和G2是等價的。 如G1A：A01|0E EA1與G2S：S0S1|01 等價152 2 文法及其語言的分類文法及其語言的分類通過對產生式通過對產生式施加不同的限制，施加不同的限制，Chomsky將文法分為四將文法分為四種類型，相應產生四類語言：種類型，相應產生四類語言：0型文法：對任

12、一產生式型文法：對任一產生式，都有，都有(V(VN NVVT T) )+ +且至少且至少含一個非終結符，含一個非終結符，(V(VN NVVT T) )* * -0型語言型語言1 1型文法：型文法：對任一產生式對任一產生式，都有，都有|， 僅僅僅僅 SS除外除外-上下文有關語言上下文有關語言2 2型文法：型文法：對任一產生式對任一產生式，都有，都有VVN N，(V(VN NVVT T) )* * 3 3型文法：型文法：任一產生式任一產生式的形式都為的形式都為AaBAaB或或AaAa， 其中其中AVAVN N ，BVBVN N ，aVaVT T * * -正則語言右線形應注意到，上下文無關文法的定

13、義等價于應注意到，上下文無關文法的定義等價于BNF表示法表示法16例：例：1 1型（上下文有關）文法型（上下文有關）文法 GSGS：SCDSCDAbbAAbbA CaCA|bCB CaCA|bCB BaaBBaaB ADaD ADaD BbbBBbbB BDbD BDbD CaCa AabD AabD DbDb例：例：2 2型（上下文無關）文法型（上下文無關）文法 GSGS：SABSAB ABS|0 ABS|0 BSA|1 BSA|1例：例：3 3型文法型文法 GS： S0A|1B|00A|1B|0 A0A|1B|0S0A|1B|0S B1B|1|01B|1|017文法的類型文法的類型2型文法

14、型文法1型文法型文法0型文法型文法四類四類文法文法之間之間的的逐級逐級“包含包含”關系關系3型文法型文法有不是上下文有關語言的0型語言，有不是上下文無關語言的1型語言，有不是正則語言的上下文無關語言。18文法和識別系統間的關系文法和識別系統間的關系0型文法（短語結構文法）的描述能力相當于圖靈機，可以表型文法（短語結構文法）的描述能力相當于圖靈機，可以表征任何遞歸可枚舉集，而且任何征任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的型語言都是遞歸可枚舉的任何能用圖靈機描述的計算都能機械實現，任何能在現代計任何能用圖靈機描述的計算都能機械實現，任何能在現代計算機上實現的計算都能用圖靈機描述算機上實

15、現的計算都能用圖靈機描述 帶帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁頭磁頭四類文法對應四種語言，每種語言被一種自動機所識別。四類文法對應四種語言，每種語言被一種自動機所識別。191型文法（上下文有關文法）：產生式的形式為1A212，即只有A出現在1和2的上下文中時，才允許取代A。其識別系統是線性界限自動機。 2型文法（上下文無關文法）：產生式的形式為A，取代A時與A的上下文無關。其識別系統是不確定的下推自動機。3型文法（正規文法RG）：產生的語言是有窮自動機（FA）所接受的集合定理定理 設設G=（VN，VT，P，S）是3 3型文法，則存在

16、一個有窮自型文法，則存在一個有窮自 動機動機 M=(K, , f, A, Z)M=(K, , f, A, Z)，使得，使得L(M)=L(G)L(M)=L(G)；反之，；反之，已知一有窮自動機M=(K, , f, A, Z),存在有一個3型文法G= （VN，VT，P，S）,使得L(G)=L(M)203 3型文法型文法和有窮自動機（有窮自動機（FAFA）G： SaA | bB AbB | aD | a BaA | bD | b DaD | bD | a | bBASaaabbba,bDZababDBASaaabba,bb先把D看成非終態21對上的正規式r ,存在一個RG=(VN,VT,P,S)：L

17、(G)=L(r)初始， VT= ，S VN ，生成正規產生式 Sr(R.1) 對形如 Ar1r2的正規產生式：Ar1B，Br2 (R.2)對形如Arr1的正規產生式：ArB | r1 ，BrB | r1 不斷應用(R.x)做變換，直到每個產生式右端至多有一個VN例 r=a(ad)(1) Sa(ad)(2) SaA，A(ad)A(ad)B | B(ad)B | Gs: SaA A | aB | dB BaB | dB | VT=a,d VN=S,A,B 22對RG=(VN,VT,P,S),存在一個 =VT上的正規式r：L(r)=L(G) AxB, By 形成正規式 A=xy AxAy 形成正規式

18、 A=xy Axy 形成正規式 A=xyGs: SaA | a AaAadAd A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a =a(ad)(ad)=a(ad) R=a(ad)233 3 上下文無關文法及其語法樹上下文無關文法及其語法樹上下文無關文法有足夠的能力描述程序設計語言的語法結構上下文無關文法有足夠的能力描述程序設計語言的語法結構GE： EE+T|T TT*F|F F(E)|a對a+a*a，觀察下列各種推導： EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aEE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*

19、a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a24規范推導、規范句型規范推導、規范句型最左（最右）推導：在推導的任何一步，其中、是句型，都是對中的最左（右）非終結符進行替換。最右推導被稱為規范推導。由規范推導所得的句型稱為規范句型語法樹語法樹-句型推導句型推導的的直觀表示直觀表示25語法樹語法樹-句型推導句型推導的的直觀表示直觀表示設G=( VN,VT,P,S)為一cfg，若一棵樹滿足下列4個條件，則此樹稱作G的語法樹(推導樹)(派生樹）：1. 每個結點都有一個標記，此標記是V的一個符號2. 根的標記是S3. 若一結點n至少有一個它自己除

20、外的子孫，并且有標記A，則肯定AVN4. 如果結點n有標記A,其直接子孫結點從左到右的次序是n1，n2，nk，其標記分別為A1，A2，Ak，那么AA1A2，Ak一定是P中的一個產生式26句型句型aabbaa的可能的可能推導推導序列和語法樹序列和語法樹 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa給定文法G=(VN,VT,P,S)，對于G的任何句型都能構造與之關聯的語法樹(推導樹)一棵語法樹表示了一個句

21、型的種種可能的(但未必是所有的)不同推導過程，包括最左(最右)推導。但是，一個句型是否只對應唯一的一棵語法樹呢?一個句型是否只有唯一的一個最左(最右)推導呢?27例：例：G GE:E:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的兩個不同的最左推導：的兩個不同的最左推導：推導推導1：E E+E E*E+E i*E+E i*i+E i*i+i推導推導2：E E*E i*E i*E+E

22、i*i+E i*i+I -導致語義上的二義性導致語義上的二義性 若一個文法存在某個句子對應兩棵不同的語法樹（或有兩若一個文法存在某個句子對應兩棵不同的語法樹（或有兩個不同的最左（右）推導），則稱這個文法是個不同的最左（右）推導），則稱這個文法是二義二義的的很顯然，計算機很顯然，計算機不喜歡二義性不喜歡二義性。28文法二義性的解決辦法文法二義性的解決辦法句子或句型含義的二義性是由文法的二義性引起的。句子或句型含義的二義性是由文法的二義性引起的。G GE: E iE: E i E E+E E E+E E E E E* *E E E (E) E (E)解決二義性的兩種途徑某些二義文法可變換為無二義的

23、根據提出的條件直接修改編譯算法GEGE：E T|E+T E T|E+T T F|T T F|T* *F F F F （E E）|i|i直接修改編譯算法：規定算符優先性和結合性規定算符優先性和結合性1229但也有一些上下文無關語言，它的每一個文法都是二義的，則但也有一些上下文無關語言，它的每一個文法都是二義的，則說此語言是先天二義的。說此語言是先天二義的。判定任給的一個上下文無關文法是否二義，或它是否產生一個判定任給的一個上下文無關文法是否二義，或它是否產生一個先天二義的上下文無關語言，這兩個問題是遞歸不可解的。先天二義的上下文無關語言，這兩個問題是遞歸不可解的。在編譯實踐中形成了一些比較實用的

24、技術，可以為無二義性尋在編譯實踐中形成了一些比較實用的技術，可以為無二義性尋找一組充分條件，用于將二義性文法變換為無二義性文法。找一組充分條件，用于將二義性文法變換為無二義性文法。比如利用優先級規則，左結合或右結合規則和最近嵌套規則比如利用優先級規則，左結合或右結合規則和最近嵌套規則等。等。GSGS：S-S-if B then S | if B then S else S | Aif B then S | if B then S else S | AG GSS：S-S-C | UC | U C- C-if B then C else S | A if B then C else S | A U

25、- U-if B then Sif B then S就近匹配就近匹配304 4 句型的分析句型的分析句型分析就是識別一個符號串是否為某文法句型的過程。編譯程序中，完成句型分析的模塊稱為分析程序或識別程序。兩類分析方式： 自上而下分析法：從文法的開始符號出發，反復使用文法的產生式，尋找與輸入符號串匹配的推導，或者說，為輸入串尋找一個最左推導。自下而上分析法：從輸入串開始，進行歸約，直至歸約到開始符號 不同分析方式反映了語法樹的的不同構造過程反映了語法樹的的不同構造過程31(1) S cAd (2) A ab (3) A a自上而下的語法分析自上而下的語法分析識別輸入串識別輸入串w=cad是否為該

26、文法的是否為該文法的句子句子若S cAd 后選擇(2)擴展A，S cAd cabd那將會？w的第二個符號可以匹配，但第三個符號卻不能匹配？宣告分析失敗，顯然結論錯誤結論錯誤。 -錯誤的選擇，導致分析的失敗！這時應該回朔回朔，把A為根的子樹剪掉，輸入a退還回去，再用產生式（3）試探自下而上的語法分析自下而上的語法分析識別輸入串識別輸入串w=cabd是否為該文法的是否為該文法的句子句子對串cabd的分析中，如果不選擇ab用產生式(2),而是選擇a用產生式(3)將a歸約到了A，那么在c A b d中無法找到一個可歸約串，最終就達不到歸約到S的結果32短語、直接短語、句柄短語、直接短語、句柄文法GS，

27、S A且A ，則稱是句型相對于非終結符A的短語。若有A 則稱是句型相對于規則A 的直接短語。一個句型的最左直接短語稱為該句型的句柄*GEGE：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|i F(E)|i句型：句型：i i* *i+ii+i 短語： 直接短語： 句柄： E E T T F T F F i1 * i2 + i3 33歸約T intT + int | 移進T + | int移進int | * int + int移進int * | int + int移進|int * int + intE |歸約E T + ET + E |歸約E TT + T |移進T | + i

28、nt歸約T int * Tint * T | + int歸約 T intint * int | + intETE+int*intTintT文法文法GE：E T + E | TT int * T | int | (E)34z 自下而上語法分析的策略：移進-歸約分析；z 移進就是將一個終結符推進棧z 歸約就是將0個或多個符號從棧中彈出，根據產生式將一個非終結符壓入棧z 移進-歸約過程是自頂向下最右推導的逆過程（規范歸約）z 我們如何決定什么時候移進，什么時候歸約？我們如何決定什么時候移進，什么時候歸約？y考慮考慮 int | * int + inty我們可以用我們可以用 T int進行歸約，而得到

29、進行歸約，而得到 T | * int + inty致命錯誤致命錯誤: 無法歸約到開始符號無法歸約到開始符號 Ey直覺: Want to reduce only if the result can still be reduced to the start symbolz 一般的移進一般的移進-歸約策略：歸約策略：y若若句柄句柄在棧頂出現，則歸約在棧頂出現，則歸約y否則移進否則移進35文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步驟步驟符號棧符號棧輸入符號串輸入符號串動作動作 1） # abbcde# 移進移進 2） #a bbcde# 移進移進A 3） #ab bcde# 歸約歸約(Ab) 4） #aA bcde# 移進移進A 5） #aAb cde# 歸約