編譯原理：文法和語言.ppt

1,第二章 文法和語言,2.1 文法的直觀表示 2.2 符號和符號串 2.3 文法和語言的形式定義 2.4文法的類型 2.5 上下文無關(guān)文法及語法樹 2.6 句型分析 2.7 文法的實用限制,2,第2章 文法和語言,【學(xué)習(xí)目標(biāo)】 本章是為語言的語法描述尋求工具 掌握對程序設(shè)計語言給出精確、無二義（嚴(yán)謹、易讀）的語法描述的手段之一文法。 對形式語言的理論有一個初步基礎(chǔ) 根據(jù)文法的特點指導(dǎo)語法分析過程,3,2.1 文法的直觀表示,文法：闡明語法的一個工具，也可以說是以有窮的集合刻畫無窮的集合的一個工具。 語言：程序設(shè)計語言。 一、語言概述 語言是由符合語法的句子組成的集合。 漢語-所有符合漢語語法的句子的全體 英語-所有符合英語語法的句子的全體 程序設(shè)計語言-所有該語言的程序的全體 每個句子構(gòu)成的規(guī)律語法 研究語言 每個句子的含義 語義 每個句子和使用者的關(guān)系語用,4,形式語言：只考慮語法而不考慮語義的符號語言。 每種語言具有兩個可識別的特性 語言的形式 與該形式相關(guān)聯(lián)的意義 “形式”指語言的所有規(guī)則，描述出現(xiàn)什么符號串 語言可以看成在一個基本符號集上定義的，按一定規(guī)則構(gòu)成的基本符號串組成的所有集合。 形式語言理論是對符號串集合的表示法、結(jié)構(gòu)及其特性的研究，是程序設(shè)計語言語法分析研究的基礎(chǔ)。,5,表達語言時，一般無法窮盡語言的所有句子，常用規(guī)則加以描述 例：漢語句子的構(gòu)成規(guī)則： 句子=主語謂語 主語=代詞|名詞 代詞= 我 | 你 | 他 名詞= 王明 | 大學(xué)生 | 工人 | 英語 謂語=動詞直接賓語 動詞= 是 | 學(xué)習(xí) 直接賓語=代詞|名詞,二、文法的直觀概念,6,推導(dǎo)：“我是大學(xué)生” 是漢語的一個句子 句子 主語 謂語 代詞謂語 我謂語 我動詞直接賓語 我是直接賓語 我是名詞 我是大學(xué)生,7,2.2 符號與符號串,一、相關(guān)概念 程序設(shè)計語言是由程序構(gòu)成的集合，程序是由基本符號按照一定的規(guī)則構(gòu)成的集合。 1. 符號、字母表和符號串 基本符號：可以相互區(qū)別的基本元素，如字母，數(shù)字，標(biāo)點符號。 字母表：基本符號的非空有窮集合，常用表示。例： =0,1， =a, b, c, , x,y, z,8,符號串：由字母表中的符號構(gòu)成的任何有窮序列稱為符號串。符號串中的符號是有順序的。,例如 =0,1上的符號串0, 1, 00, 01, 11, 10 注意：表示空符號串,它表示不包含任何符號串，不是空格符。,符號串集合：字母表上若干個符號串組成的集合. 例：字母表=0,1 的符號串集合A=1, 00, 01; 約定：小寫字母 a,b,r表示符號. 小寫字母 s,t,z表示符號串;,9,符號串s的頭（前綴）和尾（后綴） ： 如果s=xy是一符號串，那么x是s的頭，y是s的尾。若x是非空，則y是固有尾；若y非空，則x是固有頭。 前綴：移走符號串s尾部的零個或多個符號得到的串。 如：設(shè)s=abc,那么s的前綴是，a，ab，abc 后綴：移走符號串s頭部的零個或多個符號得到的串。 如：s =abc的后綴是，c，bc，abc，s的固有尾是，c，bc。,10,符號串s的子串： 從s中刪去任何前綴或后綴得到的串. 如:bc是符號串a(chǎn)bc的一個子串. 對符號串s， s和兩者都是符號串s的前綴、后綴和子串。 符號串s的真前綴，真后綴，真子串： 任何非空符號串 x，是s的前綴，后綴或子串，并且 s x,11,2.符號串的運算 (1)符號串相等： 符號串x，y，如果兩者諸符號依次相等，則兩符號串相等。 (2)符號串的長度：符號串中包含符號的個數(shù)。 |abc|=3；| |=0； (3)符號串的連結(jié)： x=abc，y=def 則xy=abcdef；yx=defabc； xy yx x=x =x；,12,(4)符號串集合的乘積： 設(shè)A、B為兩個符號串集合，其乘積為AB=xy|x A，yB； 例：A=aa，bb，B=cc，dd，則 AB=aacc，aadd，bbcc，bbdd A=A =A； (5)空集： 不含任何元素的集合稱為空集。記為； 對任何集合A：A = A= ; 注意： ,13,(6)符號串的方冪： x是字母表上的符號串，則x的冪運算為： x0= ; x1= x; x2= xx; xn= xn-1x=x xn-1 (n0) xn表示n個x相連結(jié)。 eg：x=ok；則 x0= ; x1= ok; x2= okok; (7)符號串集合的方冪： A為符號串集合，則A的冪運算為： A0=; A1=A; A2=AA;. An= An-1A=AAn-1;(n0) A=aa，bb，則A0=； A1=aa，bb； A2=AA=aaaa，aabb，bbaa，bbbb;.,14,(8)符號串集合的閉包和正閉包 集合A的閉包表示為A*（亦稱為自反閉包或星閉包）定義為： A*=A0 A1 A2 A3 =Ak， k0 正閉包表示為A+具體定義為 A+=A1 A2 A3 =Ak， k1 由定義可以看到A*= A0 A+,例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,15,3、語言 (1)由一組符號所構(gòu)成的集合。即： 字母表上的每個語言是*的一個子集。 例如：字母表=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 為字母表上的一個語言。 (2) 是一個語言。 (3) 即 是一個語言。,16,2.3 文法和語言的形式定義,如何來描述一種語言？ 如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示 如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個途徑：,生成方式 （文法）：語言中的每個句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。 識別方式（自動機）：用一個過程，當(dāng)輸入的一個任意串屬于語言時，該過程經(jīng)有限次計算后就會停止并回答“是”，若不屬于，要么能停止并回答“不是”，（要么永遠繼續(xù)下去。）,17,一、規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式）,規(guī)則是形如或=的(，)有序?qū)Γ?其中 V+， V*中的一個符號 稱為規(guī)則的左部 稱作規(guī)則的右部。 例： 文法可利用規(guī)則來描述。,18,二、文法的定義,1、文法G定義為四元組(VN，VT，P，S )其中VN ：非終結(jié)符號；VT：終結(jié)符號集；P：規(guī)則集合；VN，VT和P是非空有窮集。 S：開始符或識別符，是一個非終結(jié)符，至少要在一條規(guī)則的左部出現(xiàn)。 VN VT = ，V=VN VT ，V稱為文法G的字母表,例1：文法G = (VN，VT，P，S)， 其中 VN=S， VT=0，1， P=S0S1，S01。,19,文法G習(xí)慣上只將規(guī)則寫出。 如例1還可以寫成： G：S0S1 S01 或GS：S0S1 S01 或GS：S0S1 | S01,20,總結(jié)一個文法的幾種寫法 G=(S,A，a,b，P，S) 其中P：SaAb Aab AaAb A G：SaAb Aab AaAb A GS： S aAb Aab AaAb A GS： SaAb Aab |aAb |,21,三、推導(dǎo)的定義,用文法定義語言的中心思想是：從文法的開始符號出發(fā)，反復(fù)使用合適規(guī)則，對非終結(jié)符施行替換和展開。 1、直接推導(dǎo)： 是文法G的產(chǎn)生式，若有v，w滿足：v =，w = , 其中V*,V*。則稱v直接推導(dǎo)到w,或w直接歸約到v記作 vw， 2、推導(dǎo)：如果存在直接推導(dǎo)的序列：v=W0 W1 W2 Wn=w,(n0)；稱v推導(dǎo)出w(推導(dǎo)長度為n)，或稱w歸約到v。 記作v w。 若有v w，或v=w，則記作v w ，(n=0),*,22,例3：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111 S S 00S11 00S11,+,*,*,23,3、規(guī)范推導(dǎo) 最左(最右)推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對中的最左（右）非終結(jié)符進行替換 最右推導(dǎo)被稱為規(guī)范推導(dǎo)。 例4：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（最左推導(dǎo)） EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a （最右推導(dǎo)）,24,四、句型、句子和語言的定義,1.句型:文法GS，若S x，則稱x是G的句型。 2.句子:文法GS，若S x，且xVT*，則稱x是G的句子。句子是句型的特殊，只包含終結(jié)符。 例5：G：S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型S, 0S1 ,00S11 ,000S111,00001111 G的句子00001111 3.語言:文法G的一切句子的集合, 記為L(G)，,*,*,25,例 6 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee SanBnEn anbnen 則 L（G）= anbnen | n1 因為San-1S（BE）n-1 an（BE）n ，繼續(xù)推導(dǎo)時，將用規(guī)則(3)(7)替換,*,*,26,S a S BE (SaSBE) a aBEBE (SaBE) aabEBE ( aBab ) aabBEE ( EBBE ) aabbEE （bBbb) aabbeE （bEbe) aabbee （eEee) G生成的每個串都在L(G)中 L(G)中的每個串確實能被G生成,27,五、語言和文法,給定一個文法，能從結(jié)構(gòu)上唯一確定其語言 給定一個語言，不能唯一確定其文法，即一個語言可有多個文法與之對應(yīng) 已知語言描述，寫出文法，應(yīng)滿足： 所描述的語言的任何句子都能由該文法產(chǎn)生 該文法推導(dǎo)不出不是已知語言的任何句子 已知文法，寫出語言描述，應(yīng)滿足： 該文法能推導(dǎo)出的任何句子都包含在所描述的語言中 描述的語言中不包含該文法推導(dǎo)不出的句子,28,六、文法的等價,若L（G1）=L（G2），稱文法G1和G2是等價的 如文法G1A：A0R 與G2S：S0S1 等價 A01 S01 RA1 作業(yè)：P47:1，4，5,29,2.4 文 法 的 類 型,一、文法分類 通過對產(chǎn)生式施加不同的限制，將文法分為四類 設(shè)有文法G=(VN，VT，P，S); 0型文法：（短語結(jié)構(gòu)文法）圖靈機 對任一產(chǎn)生式，都有(VNVT)+，且至少包含一個非終結(jié)符，(VNVT)* 1型文法：（上下文有關(guān)文法） 對任一產(chǎn)生式，都有|， 僅僅 S除外。,30,文法GS是1型文法 SaSBC| aBC CB DB DB DC DCBC aBab bBbb bCbc cCcc SaSBC aaBCBC aabCBC aabbcc,*,31,2型文法：（上下文無關(guān)文法） 對任一產(chǎn)生式，都有VN ，(VNVT)* 設(shè)文法G(VN,VT,P,S)是一個2型文法， VN S,A,B, VT a,b 其中P為: (0) S aB (1) S bA (2) A a (3) A aS | bAA (4) B b (5) B bS | aBB,32,3型文法：（正規(guī)文法） 右線性文法 任一產(chǎn)生式的形式都為AaB或Aa，其中AVN ，BVN ，aVT(a可為) 左線性文法 任一產(chǎn)生式的形式都為ABa或Aa，其中AVN ，BVN ，aVT(a可為),33,例：GE： EE+T|T TT*F|F F(E)|a G是上下文無關(guān)文法。 例文法G=(S,A,B,0,1,P,S)，其中P由下列產(chǎn)生式組成： S0A A1B S1B B1B S0 B1 A0A B0 A0S G是正規(guī)文法。,34,二、四類文法之間的關(guān)系,四種文法之間的逐級“包含”關(guān)系,35,2.5 上下文無關(guān)文法及其語法樹,上下文無關(guān)文法有足夠的能力描述程序設(shè)計語言的語法結(jié)構(gòu) 例:文法GE：Ea|E+E|E*E|(E) E表示算術(shù)表達式, a表示程序的“變量”， 該文法定義了由變量，+，*,(和)組成的算術(shù)表達式的語法結(jié)構(gòu),句型推導(dǎo)的直觀表示-語法樹,36,設(shè)G為一上下文無關(guān)文法，若一棵樹滿足下列4個條件，則稱作G的語法樹(推導(dǎo)樹，派生樹） 1. 每個結(jié)點都有一個標(biāo)記，此標(biāo)記是V的一個符號 2. 根的標(biāo)記是 文法開始符號S 3. 如果結(jié)點n至少有一個除自己外的子孫并有標(biāo)記A，則肯定AVN 4. 如果結(jié)點n有標(biāo)記A,其直接子孫結(jié)點從左到右的次序是n1，n2，nk，其標(biāo)記分別為A1，A2，Ak，那么AA1A2，Ak一定是P中的一個產(chǎn)生式 語法樹的結(jié)果： 從左到右讀出葉子的標(biāo)記而構(gòu)成的行,一、語法樹,37,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,E,E,+,T,E,E,+,T,T,E,E,+,T,T,F,E,E,+,T,T,F,a,T,*,F,F,a,a,給定文法G=(VN, VT, P, S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導(dǎo)樹),38,用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法,葉子結(jié)點：樹中沒有子孫的結(jié)點。 從左到右讀出推導(dǎo)樹的葉子標(biāo)記連接成的文法符號串，為GS的句型。該推導(dǎo)樹稱為該句型的語法樹。,用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法,用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法,例: GS: SaAS ASbA ASS Sa Aba,用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法,句型aabbaa的語法樹（推導(dǎo)樹）,39,推導(dǎo)過程中施用產(chǎn)生式的順序,例: GS: SaAS ASbA ASS Sa Aba,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,40,例：GE： EE+T|T TT*F|F F(E)|a 試給出表達式a+a*a的推導(dǎo)，并畫出語法樹。 左: EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 右: EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a 混合: EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,41,例如，有一個2型文法 G= (S,A,B,a,b,P,S), 其中P: (0) S aB|bA (1)A a|aS|bAA (2)B b|bS|aBB 采用最左推導(dǎo)產(chǎn)生句子aabbab: S aB aaBB aabSB aabbAB aabbaB aabbab,一棵語法樹表示了一個句型的種種可能的不同推導(dǎo)過程，一個句型是否只對應(yīng)唯一的一棵語法樹呢? 是否只有唯一的一個最左(最右)推導(dǎo)呢?,42,語法樹 其中P: (0) S aB|bA (1)A a|aS|bAA (2)B b|bS|aBB 分析句子aabbab,43,例：GE: E a E E+E E E*E E (E),句型 a*a+a 的兩個不同的最左推導(dǎo)： (1)EE+EE*E+E a*E+E a*a+E a*a+a (2)E E*E a*E a*E+E a*a+E a*a+a,44,若一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。 或者，若一個文法存在某個句子有兩個不同的最左（右）推導(dǎo)，則稱這個文法是二義的 文法的二義性和語言的二義性是兩個不同的概念。因為可能有兩個不同的文法G和G，其中G是二義的，但是卻有L(G)=L(G)，也就是說，這兩個文法所產(chǎn)生的語言是相同的。,45,如果產(chǎn)生上下文無關(guān)語言的每一個文法都是二義的，則說此語言是先天二義的。對于一個程序設(shè)計語言來說，常常希望它的文法是無二義的，因為希望對它的每個語句的分析是唯一的。 二義文法改造為無二義文法 GE: E a GE：E T|E+T E E+E T F|T*F E E*E F （E）|a E (E) 規(guī)定優(yōu)先順序和結(jié)合律,46,2.6 句型的分析,句型分析就是識別一個符號串是否為某文法的句型，是某個推導(dǎo)的構(gòu)造過程。 在語言的編譯實現(xiàn)中，完成句型分析的程序稱為分析程序或識別程序。分析算法稱識別算法。 從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號，直到分析結(jié)束。,47,一、句型的分析算法分類,分析算法可分為： 自上而下分析法： 從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號串匹配的推導(dǎo)。 自下而上分析法： 從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。 兩種方法反映了兩種不同的語法樹的構(gòu)造過程。,48,1、自上而下的語法分析,例：文法G：S cAd A ab A a 識別輸入串w=cabd是否為該文法的句子,49,2、自下而上的語法分析,例：文法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ī)約過程構(gòu)造的推導(dǎo)： cAd cabd S cAd,50,3、句型分析的有關(guān)問題,1）在自上而下的分析方法中如何選擇使用哪個產(chǎn)生式進行推導(dǎo)？ 假定要被代換的最左非終結(jié)符是B，且有n條規(guī)則：BA1|A2|An，如何確定用哪個右部去替代B？ 2）自下而上分析法中，分析程序工作的每一步，都是從當(dāng)前串中選擇一個子串，將它歸約到某個非終結(jié)符，該子串稱為“可歸約串”,如何識別可歸約串？ 3）存在確定和不確定分析，本課只討論確定分析,51,4、短語、直接短語、句柄的定義,對于文法GS （1）句型的短語: S = A且 A =，則稱是句型相對于非終結(jié)符A的短語。 （2）句型的直接短語：若有A ，則稱是句型相對于非終結(jié)符A 的直接短語。 （3）句型的句柄：一個句型的最左直接短語稱為該句型的句柄。,*,+,52,語法樹子樹分析法： 短語：任意一顆子樹的葉子結(jié)點從左至右順序排列的字符串（按給定句型排除）。 直接短語：只有父子兩層的子樹的葉子結(jié)點從左至右順序排列的字符串。 句柄：最左最下的只有父子兩層的子