《文法和語言》PPT課件.ppt

1,第三章 文法和語言,本章目的為語言的語法描述尋求工具,以便： 對源程序給出精確無二義的語法描述。（嚴謹、簡潔、易讀） 根據語言文法的特點來指導語法分析的過程 從描述語言的文法可以自動構造出可用的分析程序 制導語義翻譯,2,文法和語言,預備知識 文法和語言的形式定義 文法的類型 上下文無關文法及其語法樹 上下文無關文法的句型分析 有關文法實用中的一些說明 有關文法的一些關系,3,預備知識 -語言概述,語言是由句子組成的集合，是由一組記號所構成的集合。 漢語-所有符合漢語語法的句子的全體 英語-所有符合英語語法的句子的全體 程序設計語言-所有該語言的程序的全體 每個句子構成的規(guī)律 研究語言 每個句子的含義 每個句子和使用者的關系,4,預備知識 -語言概述,研究程序設計語言 每個程序構成的規(guī)律 每個程序的含義 每個程序和使用者的關系 語言研究的三個方面 語法 Syntax 語義 Semantics 語用 Pragmatics,5,預備知識 -語言概述,語法 - 表示構成語言句子的各個記號之間的組合規(guī)律 語義 - 表示按照各種表示方法所表示的各個記號的特定含義。（各個記號和記號所表示的對象之間的關系） 語用 -表示在各個記號所出現的行為中，它們的來源、使用和影響。,6,預備知識 -語言概述,每種語言具有兩個可識別的特性，即語言的形式和該形式相關聯的意義。 語言的實例若在語法上是正確的，其相關聯的意義可以從兩個觀點來看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗到的意義。這兩個意義并非總是一樣的，前者稱為語言的語義，后者是其語用意義。幽默、雙關語和謎語就是利用這兩方面意義間的差異。,7,預備知識 -形式語言,如果不考慮語義和語用，即只從語法這一側面來看語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個數學系統(tǒng)?！靶问健笔侵高@樣的事實：語言的所有規(guī)則只以什麼符號串能出現的方式來陳述。形式語言理論是對符號串集合的表示法、結構及其特性的研究。是程序設計語言語法分析研究的基礎。,8,預備知識 -有關定義和記號,符號：可以相互區(qū)別的記號（元素）。 字母表：符號（元素）的非空有窮集合。 符號串：由字母表中的符號組成的任何有窮序列稱為該字母表上的符號串。1.空符號串(沒有符號的符號串)是上的符號串 2.若x是上的符號串,a是的元素,則xa是上的符號串 3. y是上的符號串,當且僅當它可以由1和2導出。 例如： =a,b ,a,b,aa,ab,aabba都是上的符號串,9,預備知識 -有關定義和記號,符號串s的前綴：移走符號串s尾部的零個或多于零個符號得到的符號串. 如： b是符號串banana的一個前綴. 符號串s的后綴：刪去符號串s頭部的零個或多于零個符號得到的符號串. 如:nana是符號串banana的一個后綴. 符號串s的子串：從s中刪去一個前綴和一個后綴得到的符號串. 如:ana是符號串banana的一個子串.,10,對于每個符號串s， s和兩者都是符號串s的前綴，后綴和子串。 符號串s的真前綴，真后綴，真子串：任何非空符號串 x,相應地，是s的前綴，后綴或子串，并且 s x 符號串的運算 符號串的長度：符號串中符號的個數.符號串s的長度記為|s|。 的長度為0 連接：符號串x、y的連接,是把y的符號寫在x的符號之后得到的符號串xy 如 x=ab,y=cd 則 xy=abcd 有a = a 方冪：符號串自身連接n次得到的符號串 an 定義為 aaaa n個a a1=a, a2=aa則a0=,11,符號串集合：若集合A中所有元素都是某字母表上的符號串，則稱A為字母表上的符號串集合。 兩個符號串集合A和B的乘積定義為 AB =xy|xA且yB 若 集合A=ab,cde B = 0,1 則 AB =ab1,ab0,cde0,cde1 使用 * 表示上的一切符號串（包括）組成的集合。*稱為的閉包。 上的除外的所有符號串組成的集合記為+ 。 +稱為的正閉包。,12,例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,13,語言：字母表上的一個語言是上的一些符號串的集合 (上的每個語言是*的一個子集)。 例如： =a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,aaabbb,anbn, 或w|w*且w=anbn,n1為字母表上的一個語言。 集合a,aa,aaa, 或w|w*且w=an,n1 為字母表上的一個語言。 是一個語言。 即 是一個語言。,14,語言上的運算,設L是（上的）一個語言,M是（上的）一個語言, 語言L和M的并，交，差，補是一個語言。 如語言L和M的并為 LM，是一個語言: w|w is in L or is in M 如： L1 =a,b,y,z M1 =1,28,9 L1M1=a,b, y,z，1,28,9 語言L和M的連接是一個語言，記為 LM LM=st |sL且 tM 如： L1M1 =a1,b1,y1,z1,a2,b2a9z9 有L = L=L。 L的n次連接Ln= LL.L,15,語言上的運算,語言L的 閉包記為 L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1= Ln-1 L,n1 語言L的正 閉包記為 L+， L+= L1 L2 L3 . L+= LL*= L*L L*= L+ 如： L1 =a,b,y,z M1 =1,28,9 （L1M1）=a,b, y,z，1,28,9 （L1M1）*=a,b, y,z，1,28,9 ，aa,1a,xyz,6789st L1（L1M1）*=所有字母打頭的字母和數字符號串,16,語言的描述,如何來描述一種語言？ 如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示 如果語言是無窮的，找出語言的有窮表示。兩個途經： 生成方式 （文法）：語言中的每個句子可以用嚴格定義的規(guī)則來構造。 識別方式（自動機）：用一個過程，當輸入的一任意串屬于語言時，該過程經有限次計算后就會停止并回答“是”，若不屬于，要麼能停止并回答“不是”，（要麼永遠繼續(xù)下去。）,17,文法 數學系統(tǒng),一個形式數學系統(tǒng)可由下列基本成分來刻畫：一組基本符號，一組形成規(guī)則，一組公理，一組推理規(guī)則。,18,文法和語言的形式定義,文法的定義 推導的定義 句型、句子、語言的定義,19,文法的定義,文法G定義為四元組（VN，VT，P，S） VN ：非終結符集 VT ：終結符集 P：產生式（規(guī)則）集合 S：開始符號 VNVT= ， SVN V=VNVT，稱為文法G的文法符號集合,20,規(guī)則的定義,規(guī)則（重寫規(guī)則、產生式或生成式），是形如或=的（，）有序對，且V+，V*。 稱為規(guī)則的左部(或生成式的左部)。 稱為規(guī)則的右部(或生成式的右部)。,21,文法的定義,例3.1 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S為開始符號,22,文法的定義,習慣上只將產生式寫出。并有如下約定： 第一條產生式的左部是開始符號 用尖括號括起的是非終結符，否則為終結符。或者大寫字母表示非終結符，小寫字母表示終結符 G可寫成GS，S是開始符號 G：SaAb Aab AaAb A GS： Aab AaAb A SaSb 縮寫形式 GS： Aab |aAb | SaSb 注意：元符號和源符號,例3.2 文法G=（VN，VT，P，S） VN =標識符，字母，數字 VT =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S=,24,推導的定義,直接推導“” 是文法G的產生式，若有v,w滿足： v=,w= , 其中V*,V* 則稱v直接推導到w,記作 v w 或w直接歸約到v 例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 . . . VAR;BEGIN READ()END. VAR A;BEGIN READ(A) END.,25,推導的定義,若存在v w0 w1 . wn=w,(n0) 則稱v w，v推導出w，或w歸約到v 若有v w，或v=w， 則記為v w,26,文法的句型、句子的定義,句型 有文法G，若S x，則稱x是文法G的句型。 句子 有文法G，若S x，且xVT*，則稱x是文法G的句子。 例：G： S0S1， S01 S 0S1 00S11 000S111 00001111,27,例：GE：EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 表示一切能用符號a，+，*，(和)構成的算術表達式,28,文法，語言的定義,由文法G生成的語言記為L(G),它是文法G的一切句子的集合: L(G)=x|S x，其中S為文法的開始符號，且x VT* 例：G： S0S1， S01 L(G)=0n1n|n1,例3.3 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee L（G）= anbnen | n1 ,30,S a S BE (SaSBE) a aBEBE (SaBE) aabEBE ( aBab ) aabBEE ( EBBE ) aabbEE （bBbb) aabbeE （bEbe) aabbee （eEee) G生成的每個串都在L(G)中 L(G)中的每個串確實能被G生成,已知語言描述，寫出文法 例：若語言由0、1符號串組成，串中0和1的個數相同，構造其文法。 A 0B|1C B 1|1A|0BB C 0|0A|1CC 已知文法，寫出語言描述 例：GE：EE+T|T TT*F|F F(E)|a,32,語法 Syntax 語義 Semantics,偶正整數的集合0,2,4,2n , dd.0(2，4，6，8),33,文法的等價,若L（G1）=L（G2），則稱文法G1和G2是等價的。 如文法G1A：A0R 與G2S：S0S1 等價 A01 S01 RA1,34,文法的類型,通過對產生式施加不同的限制，Chomsky將文法分為四種類型： 0型文法：對任一產生式，都有(VNVT)+， (VNVT)* 1型文法：對任一產生式，都有|， 僅僅 S除外 2型文法：對任一產生式，都有VN ， (VNVT)* 3型文法：任一產生式的形式都為AaB或Aa，其中AVN ，BVN ，aVT,35,文法的類型,例：1型（上下文有關）文法 文法GS： SaSBE SaBE EBBE aBab bBbb bEbe eEee,36,文法的類型,例：1型（上下文有關）文法 文法GS： SCD AbbA CaCA BaaB CbCB BbbB ADaD C BDbD D AabD L(G)=ww|wa,b*,37,文法的類型,例：2型（上下文無關）文法 文法GS： SaB|bA Aa|aS|bAA Bb|bS|aBB 文法GS： S0A|1B|0 A0A|1B|0S B1B|1|0,38,文法的類型,例：定義標識符的3型（正規(guī)）文法 文法GI： I lT I l T lT T dT T l T d,39,文法和語言,0型文法產生的語言稱為0型語言 1型文法或上下文有關文法（ CSG ）產生的語言稱為1型語言或上下文有關語言（CSL） 2型文法或上下文無關文法（ CFL ）產生的語言稱為2型語言或上下文無關語言（ CF L ） 3型文法或正則（正規(guī)）文法（ RG ）產生的語言稱為3型語言正則（正規(guī)）語言（ RL ）,40,文法和語言,四種文法之間的關系 是將產生式做進一步限制而定義的。 語言之間的關系依次：有不是上下文有關語言的0型語言，有不是上下文無關語言的1型語言，有不是正則語言的上下文無關語言。,41,文法和識別系統(tǒng),0型文法（短語文法）的能力相當于圖靈機，可以表征任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的 1型文法（上下文有關文法）：產生式的形式為1A212，即只有A出現在1和2的上下文中時，才允許取代A。其識別系統(tǒng)是線性界限自動機。,42,帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁頭,圖靈機,43,文法的類型,2型文法（上下文無關文法、CFG）：產生式的形式為A，取代A時與A的上下文無關。其識別系統(tǒng)是不確定的下推自動機。 3型文法（正規(guī)文法、右線性文法）：產生的語言是有窮自動機（FA）所接受的集合,44,上下文無關文法及其語法樹,上下文無關文法有足夠的能力描述現今程序設計語言的語法結構 算術表達式 語句 賦值語句 條件語句 讀語句 ,45,算術表達式上下文無關文法表示,文法G=(E, +,*,I,(,), P, E P: E i E E+E E E*E E (E),46,條件語句上下文無關文法表示,ifthen | ifthenelse ,47,上下文無關文法的語法樹,用于描述上下文無關文法的句型推導的直觀方法,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,句型aabbaa的語法樹（推導樹）,葉子結點：樹中沒有子孫的結點。 從左到右讀出推導樹的葉子標記，所得的句型為推導樹的結果。也把該推導樹稱為該句型的語法樹。,48,上下文無關文法的語法樹,給定文法G，對于G的任何句型都能構造與之關聯的語法樹（推導樹）。這棵樹滿足下列4個條件： 1、每個結點都有一個V中的符號作標記 2、根的標記是開始符號S 3、若一結點n至少有一個它自己除外的子孫，并且n有標記A，則AVN 4、如果結點n的直接子孫，從左到右的次序是結點n1,n2,nk，其標記分別為A1,A2,Ak，那么AA1A2,Ak一定是P中的一個產生式,49,上下文無關文法的語法樹,定理：G為上下文無關文法， 對于，有S ，當且僅當 文法G有以為結果的一棵推導樹。,50,上下文無關文法的語法樹,推導過程中施用產生式的順序,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,51,最左（最右）推導：在推導的任何一步，其中、是句型，都是對中的最左（右）非終結符進行替換 最右推導被稱為規(guī)范推導。 由規(guī)范推導所得的句型稱為規(guī)范句型,52,問題：一個句型是否對應唯一的一棵語法樹？,53,例：GE: E i E E+E E E*E E (E),E E + E E * E i i i,E E * E i E + E 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 i*i+E i*i+i,54,二義文法,若一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。 或者，若一個文法存在某個句子有兩個不同的最左（右）推導，則稱這個文法是二義的。 產生某上下文無關語言的每一個文法都是二義的，則稱此語言是先天二義的。,55,二義文法,判定任給的一個上下文無關文法是否二義，或它是否產生一個先天二義的上下文無關語言，這兩個問題是遞歸不可解的。但可以為無二義性尋找一組充分條件。 二義文法改造為無二義文法 GE: E i GE：E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 規(guī)定優(yōu)先順序和結合律,56,句型的分析,句型分析就是識別一個符號串是否為某文法的句型，是某個推導的構造過程。 在語言的編譯實現中，把完成句型分析的程序稱為分析程序或識別程序。分析算法又稱識別算法。 從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號。,57,句型的分析,分析算法可分為： 自上而下分析法： 從文法的開始符號出發(fā)，反復使用各種產生式，尋找與輸入符號匹配的推導。 自下而上分析法： 從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。 兩種方法反映了兩種不同的語法樹的構造過程,58,自上而下的語法分析,例：文法G：S cAd A ab A a 識別輸入串w=cabd是否該文法的句子,S S S c A d c A d a b 推導過程：S cAd cabd,59,自下而上的語法分析,例：文法G：S cAd A ab A a 識別輸入串w=cabd是否該文法的句子,S A A c a b d c a b d c a b d 規(guī)約過程：S cAd cabd,60,句型分析的有關問題,1）如何選擇使用哪個產生式進行推導？ 假定要被代換的最左非終結符號是V，且有n條規(guī)則：VA1|A2|An，那么如何確定用哪個右部去替代V？ 2）如何識別可歸約的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是從當前串中選擇一個子串，將它歸約到某個非終結符號，該子串稱為“可歸約串”,61,句型分析,短語、直接短語、句柄的定義：文法GS， S A且A b則稱b是句型b相對于非終結符A的短語。若有A b則稱b是句型b相對于該規(guī)則A b的直接短語。一個句型的最左直接短語稱為該句型的句柄。,62,句型分析,E F T T F F i1 * i2 + i3 短語： 直接短語： 句柄：,GE：EE+T|T TT*F|F F(E)|i 句型：i*i+i,63,有關文法實用中的一些說明,有關文法的實用限制 上下文無關文法中的規(guī)則,64,有關文法的實用限制,文法中不得含有有害規(guī)則和多余規(guī)則 有害規(guī)則：形如UU的產生式。會引起文法的二義性 多余規(guī)則：指文法中任何句子的推導都不會用到的規(guī)則 1）文法中某些非終結符不在任何規(guī)則的右部出現，該非終結符稱為不可到達 2）文法中某些非終結符，由它不能推出終結符號串來，稱為不可終止的,65,有關文法的實用限制,對于文法GS，為了保證任一非終結符A在句子推導中出現，必須滿足如下兩個條件： 1）A必須在某句型中出現。 2）必須能從A推出終結符號串t來。 即1）文法GS，對 某兩個符號串和： S A 2）A t ,tVT,66,化簡文法,例：GS 1) SBe SBe 2) BCe BAf 3) BAf AAe 4) AAe Ae 5) Ae 6) CCf 7) Df,67,上下文無關文法中的規(guī)則,具有形式A的規(guī)則稱為規(guī)則，其中AVN 某些著作和講義中限制這種規(guī)則的出現。因為規(guī)則會使有關文法的一些討論和證明變得復雜 兩種定義的唯一差別是句子在不在語言中。,68,上下文無關文法中的規(guī)則,如果語言L有一個有窮的描述，則L也同樣有一個有窮描述。并且可以證明，若L是上下文有關語言、上下文無關語言或正規(guī)語言，則L和L-分別是上下文有關語言、上下文無關語言和正規(guī)語言,69,上下文無關文法中的規(guī)則,定理3.1 文法G，任一P中的產生式A，都有AVN，(VN VT)*,(即可能為)，則L(G)也能這樣一種文法產生，任一產生式A，只有如下兩種形式： AVN， (VN VT)+,(即) 或者 S且 S不出現在任何產生式右邊,70,上下文無關文法中的規(guī)則,定理3.2 G是上下文有關文法，則存在另一個上下文有關文法G1，L(G)=L(G1)，且G1的開始符號不出現在G1的任何產生式的右邊。 若G為上下文無關文法或正規(guī)文法，類似結論成立。,71,有關文法的一些關系,一般