1、1第3章文法和語言語言文法概述文法和語言的形式定義文法的類型上下文無關(guān)文法及其語法樹句型的分析有關(guān)文法實(shí)用中的一些說明2語言文法概述本章目的語言概述語言的一般描述文法的直觀概念3本章目的本章目的為語言的語法描述尋求工具 通過該工具，可以：對源語言給出精確無二義的語法描述。（嚴(yán)謹(jǐn)、簡潔、易讀）根據(jù)語言文法的特點(diǎn)來指導(dǎo)語法分析的過程從描述語言的文法可以自動構(gòu)造出可用的分析程序(如：第13章介紹的基于LALR(1)文法的yacc和基于LL(2)文法的SD&EBNF_LL(2) )制導(dǎo)語義翻譯4語言概述語言是由句子組成的集合，是由一組記號所構(gòu)成的集合。漢語-所有符合漢語語法的句子的全體英語-所有符合英

2、語語法的句子的全體程序設(shè)計(jì)語言-所有該語言的程序的全體 每個句子構(gòu)成的規(guī)律研究語言 每個句子的含義 每個句子和使用者的關(guān)系5語言概述語言研究的三個方面:語法（ Syntax ） - 表示構(gòu)成語言句子的各個記號之間的組合規(guī)律語義 （Semantics） - 表示按照各種表示方法所表示的各個記號的特定含義。（各個記號和記號所表示的對象之間的關(guān)系）語用（Pragmatics） -表示在各個記號所出現(xiàn)的行為中，它們的來源、使用和影響。（本章不做進(jìn)一步的介紹）6語言概述形式語言理論（formal language theory）： 是一種從語法上研究語言的理論。它是抽象的數(shù)學(xué)系統(tǒng)，著重研究符號串集合的表

3、示法、結(jié)構(gòu)及其特性。是程序設(shè)計(jì)語言語法分析研究的基礎(chǔ)。（本章僅使用其與編譯程序構(gòu)造有關(guān)的結(jié)論，而不做證明）形式語義（formal semantics）：（本課程不介紹）。7語言的一般描述語言可以看成在一個基本符號集上定義的，按一定規(guī)則構(gòu)成的基本符號串組成的所有集合。一些基本概念8一些基本概念符號：可以相互區(qū)別的記號（元素）字母表：符號（元素）的非空有窮集合符號串：由字母表中的符號組成的任何有窮序列稱為該字母表上的符號串。例： (1)符號“a”組成的字母表記作a； a,aa,aa;都是字母表a上的符號串。 (2) 符號“a”和“b”組成的字母表記作 a,b；a,b,aa ,bb,ab,abb,b

4、aa,.都是字母表a,b上的符號串。9一些基本概念符號串的長度：符號串中符號的個數(shù)?？沾洪L度為0的符號串，它不同于符號串的運(yùn)算連接：連接符號串x、y,是把y的符號寫在x的符號之后得到的符號串； 即x、y的連接為xy 。方冪：符號串自身連接n次得到的符號串； 如： x的n次連接為x x. x (n個x)也可記作x n10一些基本概念頭、尾、固有頭、固有尾； 例：符號串 x=abc的 頭：,a,ab,abc； 尾: ,c,bc,abc； 固有頭: ,a,ab； 固有尾:,c,bc； 符號串集合：若集合中所有元素都是某字母表上的符號串，則稱之為該字母表上的符號串集合。符號串集合的乘積：例：符號串集

5、合A =ab,aa; B =ba,bb; 乘積A B =abba,abbb,aaba,aabbA B =x y | x A ,yB11一些基本概念閉包：*稱為的閉包，若*表示上的所有有窮長的串的集合。正閉包： +稱為的正閉包，表示為（其中用代表邏輯或運(yùn)算）例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,* = 2 .+ =* -= * = 2 3 .12一些基本概念語言 （language）某個字母表上的串的集合，是*的一個子集例如： =a,ba,aa,aaa,或記作：w|w*且w=an,n1 ab,aabb,aaabb

6、b,anbn,或記作：w|w*且w=anbn,n1 都可稱為一種語言13語言的一般描述如何來描述一種語言？如果語言是有窮的（只含有窮多個句子），可以將句子逐一列出來表示。如果語言是無窮的，找出語言的有窮表示。14文法的直觀概念句子的產(chǎn)生 （用 “ ”表示推導(dǎo)）:=:=|:=我|你|他:=王明|大學(xué)生|工人|英語:=:=是|學(xué)習(xí):= | 15文法的直觀概念 我 我 我是 我是 我是大學(xué)生16文法的直觀概念可以用EBNF來表示句子的構(gòu)成規(guī)則，這些規(guī)則看成是一種元語言（meta-language），這樣的語言描述稱為文法?？梢愿鶕?jù)規(guī)則推導(dǎo)，產(chǎn)生句子例：pl/0語言（用 “ ”表示推導(dǎo)）. . VAR

7、; . VAR A; . VAR A; BEGIN END . VAR A; BEGIN READ()END. VAR A;BEGIN READ(A) END.17文法和語言的形式定義規(guī)則的定義文法的定義推導(dǎo)的定義句型、句子、語言的定義18規(guī)則的定義規(guī)則（重寫規(guī)則、產(chǎn)生式（production）/生成式） 是形如或=，是（，）的有序?qū)?，且V+ （不能為空）， V*。 稱為規(guī)則的左部(或產(chǎn)生式的左部)。 稱為規(guī)則的右部(或產(chǎn)生式的右部)。19文法的定義文法G定義為四元組（VN，VT，P，S）VN ：非終結(jié)符集VT ：終結(jié)符集P：產(chǎn)生式（規(guī)則）集合S：開始符號VNVT= ， S VNV=VNVT，

8、 V稱為文法G的文法符號集合20文法的定義例3.1 文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S為開始符號 描述的語言為： L=0n1n|n1（ S 0S1 00S11 . 0n-1S1n-1 0n1n）例3.2 文法G=（VN，VT，P，S）VN =，VT =a,b,c,x,y,z,0,1,9P= | | a|b|z 0|1|9 S=22文法的定義文法習(xí)慣上只將產(chǎn)生式寫出。并可有如下約定：第一條產(chǎn)生式的左部是開始符號用尖括號括起的是非終結(jié)符，否則為終結(jié)符， 或者大寫字母表示非終結(jié)符，小寫字母或其它字符表示終結(jié)符。G可寫成GS，S是開始符號

9、例： G：S0S1 或 GS：S0S1 S01 S0123推導(dǎo)的定義直接推導(dǎo)： 用 “”表示在一個句型中用產(chǎn)生式的右部替換產(chǎn)生式的左部例：是文法G的產(chǎn)生式，若有U,W滿足： U =, W =,（用替換U中的） 其中、 、 V*, V+（ 不能為） 記作 U W 或 則稱U直接推導(dǎo)到W,或W直接歸約到U例：GS： S0S1， S01 S 0S1 00S11 000S111 00001111 可有U =00S11 ， W= 000S11124推導(dǎo)的定義 推導(dǎo) 若存在u=w0 w1 . wn=w,(n0) 則稱u w，u推導(dǎo)出w，或w歸約到u 推導(dǎo) 若有u w，或u=w (0步推導(dǎo)）， 則記為u w

10、 ,(n 0)25句型、句子、語言的定義 句型 ：有文法G，若S x ，且x V*則稱x是文法G的句型。 句子：有文法G，若S x，且 xVT*，則稱x是文法G的句子。（句子是句型的特殊）例：GS： S0S1， S01 S 0S1 00S11 000S111 00001111 S，0S1，00S11，000S111， 00001111都是句型 只有00001111是句子26句型、句子、語言的定義語言 L(G)=x|S x，其中S為文法的開始符號，且x VT* L(G)是文法GS描述的語言，也是該文法能推導(dǎo)出所有句子的集合。例：GS： S0S1， S01 L(G)=0n1n|n127例：算術(shù)表達(dá)

11、式例：GE：EE+T|T TT*F|F F(E)|a可推導(dǎo)出：EE+T T + T F + T a + T a + T*F a + F*F a + a*F a + a*a表示文法GE能推導(dǎo)出用符號a、 + 、*、 (和)構(gòu)成的所有算術(shù)表達(dá)式。例3.3 文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee S aSBE aaBEBE aabEBE aabBEE aabbEE aabbeE aabbee L（G）= anbnen | n1 29 有關(guān)語言、句子、文法和規(guī)則的 一些基本概念30 語言與文法已知語言描述，寫出文法 已知文法，寫出

12、語言描述都應(yīng)滿足：（1）所描述語言的任何句子都能由該文法產(chǎn)生；（2）該文法推導(dǎo)不出不是已知語言的任何句子。31語言與文法已知語言描述，寫出文法例：若語言由0、1符號串組成，串中0和1的個數(shù)相同，構(gòu)造其文法。若構(gòu)造GA: A 0B|1C B 1|1A|0BB C 0|0A|1CC 試推導(dǎo) ：符號串1001和011100A 1C 10A 100B 1001A 0B 01A 011C 0111CC 01110C 01110032語言與文法已知文法，寫出語言描述例：GE：EE+T|T TT*F|F F(E)|a表示文法GE能推導(dǎo)出用符號a、 + 、*、 (和)構(gòu)成的所有算術(shù)表達(dá)式。33文法的等價(jià)若L（

13、G1）=L（G2），則稱文法G1和G2是等 價(jià)的（它們產(chǎn)生的句子集合相同）。例如：文法G1A： 與G2S： A0R S0S1 A01 S01 RA1 即G1A與G2S等價(jià)34文法的類型通過對產(chǎn)生式施加不同的限制，Chomsky將文法分為四種類型：0型文法：（短語結(jié)構(gòu)文法）對任一產(chǎn)生式，都有(VNVT)+且至少包含一個非終結(jié)符， (VNVT)*1型文法：（上下文有關(guān)文法）對任一產(chǎn)生式，都有|， 僅僅 S除外 并且S不出現(xiàn)在其他產(chǎn)生式的右部。35文法的類型2型文法：（上下文無關(guān)文法）對任一產(chǎn)生式，都有VN ， (VNVT)* 3型文法：（正規(guī)文法）（1）右線性文法： 對任一產(chǎn)生式的形式都為Aa B

14、 或 Aa ，其中A 、B VN ，a VT* （a可為） （2）左線性文法： 對任一產(chǎn)生式的形式都為AB a 或 Aa ，其中A 、BVN ，a VT* （a可為） 36 文法的類型例：1型（上下文有關(guān)）文法 文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee L（G）= anbnen | n1 37文法的類型例：2型（上下文無關(guān)）文法 文法GS：SaB|bAAa|aS|bAABb|bS|aBB 文法GS：S0A|1B|0A0A|1B|0SB1B|1|038文法的類型例：寫出標(biāo)識符的3型（正規(guī)）文法 文法GI：I lTI lT lTT dTT lT d為右線性文法。 (其中

15、l代表字母 d代表數(shù)字)39文法的類型例：寫出標(biāo)識符的3型（正規(guī)）文法 文法GI： I Il I Id I l 為左線性文法。若 AB 或 A，其中A 、B VN ，VT*如當(dāng) =ab 時則：AB 即 AabB 可寫為：AaD DbB A 即 Aab 可寫為：AaD Db （D為新增加的非終結(jié)符）40文法的類型0型文法（短語結(jié)構(gòu)文法）的能力相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的；1型文法（上下文有關(guān)文法）：產(chǎn)生式的形式為1A212，即只有A出現(xiàn)在1和2的上下文中時，才允許替換A。其識別系統(tǒng)是線性界限自動機(jī)。41文法的類型2型文法（上下文無關(guān)文法 CFG （co

16、ntext free grammar）：產(chǎn)生式的形式為A，取代A時與A的上下文無關(guān)。其識別系統(tǒng)是不確定的下推自動機(jī)。3型文法（正規(guī)文法 RG （regular grammar ）右/左線性文法）：識別系統(tǒng)是有窮自動機(jī)，即正規(guī)文法產(chǎn)生的語言是有窮自動機(jī)（FA finite automata）所接受的集合。本課將著重介紹2型文法、 3型文法和有窮自動機(jī)。42文法的類型四種文法之間的關(guān)系 由于四種文法是按照將產(chǎn)生式做進(jìn)一步限制而定義的，所以它們之間是逐級“包含”的關(guān)系， 由四種文法產(chǎn)生的語言也是逐級“包含”的關(guān)系。43文法的類型2型文法1型文法0型文法四種文法之間的逐級“包含”關(guān)系3型文法44上下文

17、無關(guān)文法及其語法樹上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語言的語法結(jié)構(gòu)，如：算術(shù)表達(dá)式語句賦值語句條件語句讀語句45算術(shù)表達(dá)式的上下文無關(guān)文法表示文法G=(E, +,*, i,(,), P, E P:E E+EE E*EE (E) E i 46條件語句的上下文無關(guān)文法表示ifthen | ifthenelse 47上下文無關(guān)文法的語法樹用于描述上下文無關(guān)文法句型推導(dǎo)的直觀方法 例: GS:SaASASbAASS SaAba S a A S S b A a a b a句型aabbaa的語法樹（推導(dǎo)樹）葉子結(jié)點(diǎn)：樹中沒有子孫的結(jié)點(diǎn)。從左到右讀出推導(dǎo)樹的葉子標(biāo)記連接成的文法符號串，為GS的句型。

18、也把該推導(dǎo)樹稱為該句型的語法樹。48上下文無關(guān)文法的語法樹給定文法G，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹滿足下列4個條件：1.每個結(jié)點(diǎn)都有一個V中的符號作標(biāo)記2.根的標(biāo)記是開始符號S3.若一結(jié)點(diǎn)n至少有一個它自己除外的子孫，并且n有標(biāo)記A，則AVN4.如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,n2,nk，其標(biāo)記分別為A1,A2,Ak，那么AA1A2,Ak一定是P中的一個產(chǎn)生式。49上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S SaAS50上下文無關(guān)文法的語法樹

19、推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S a SaASaAa51上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S S b A a SaASaAaaSbAa52上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S S b A a b aSaASaAaaSbAaaSbbaa53上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)

20、生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaa每次替換句型中最右邊的非終結(jié)符54上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S SaAS55上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S S b ASaASaSbAS56上下文無關(guān)文法的語法樹推導(dǎo)過程

21、中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S S b A aSaASaSbASaabAS57上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S S b A a b aSaASaSbASaabASaabbaS58上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S S b A a a b aSaASaSbASaabASaabb

22、aSaabbaa每次替換句型中最左邊的非終結(jié)符59上下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例: GS:(1) SaAS(2) ASbA(3) ASS(4) Sa(5) Aba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa60上下文無關(guān)文法的語法樹最左（最右）推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對中的最左（右）非終結(jié)符由相應(yīng)產(chǎn)生式的右部進(jìn)行替換。最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。上例中第一個推導(dǎo)為最右推導(dǎo)，第二

23、個推導(dǎo)為最左推導(dǎo)，第三個推導(dǎo)既非最右推導(dǎo)也非最左推導(dǎo)。61 文法的二義性問題：一個句型是否對應(yīng)唯一的一棵語法樹？ 例：GE:E E+EE E*EE (E) E i E E + E E * E i i i E E * E i E + E i i句型 i*i+i 的兩個不同的最左推導(dǎo)：推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)2：E E*E i*E i*E+E i*i+E i*i+i62二義性文法若一個文法存在某個句型對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的?；蛘撸粢粋€文法存在某個句型有兩個不同的最左（右）推導(dǎo)，則稱這個文法是二義的。產(chǎn)生某上下文無關(guān)語言的每一個文法

24、都是二義的，則稱此語言是先天二義的。63 二義性文法二義文法的判定問題任給的一個上下文無關(guān)文法是否為二義，或是否產(chǎn)生一個先天二義的上下文無關(guān)語言，這兩個問題是不可判定的。但可以為無二義性尋找一組充分條件。二義文法改造為無二義文法如下例：GE: E E+E GE：E E+T|T E E*E T T*F|F E (E)|i F （E)|i 二義文法 規(guī)定優(yōu)先順序和結(jié)合律 變?yōu)闊o二義文法64句型的分析句型分析就是識別一個符號串是否為某文法的句型，是某個推導(dǎo)的構(gòu)造過程。在語言的編譯程序?qū)崿F(xiàn)中，把完成句型分析的程序稱為分析程序或識別程序。分析算法又稱識別算法。從左到右的分析算法，即總是從左到右地識別輸入

25、符號串，首先識別符號串中的最左符號，進(jìn)而依次識別右邊的一個符號，直到分析結(jié)束。65句型的分析分析算法可分為：自上而下分析法：從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號串匹配的推導(dǎo)。自下而上分析法：從輸入符號串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號。 兩種方法反映了兩種不同的語法樹的構(gòu)造過程。66自上而下的語法分析例：文法G：S cAd A ab A a識別輸入串w=cabd是否為該文法的句子SSScAdcAd a b推導(dǎo)過程：S cAd cabd67自下而上的語法分析例：文法G：S cAd A ab A a識別輸入串w=cabd是否該文法的句子SAA c a b d c a b d c a b d 歸約過程：S cAd cabd68句型分析的有關(guān)問題1）如何選擇使用哪個產(chǎn)生式進(jìn)行推導(dǎo)？假定要被替換的最左非終結(jié)符號是B，且有n條規(guī)則：BA1|A2|An，那么如何確定用哪個右部去替代B？2）如何識別可歸約的串？在自下而上的分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中選擇一個子串，將它歸約到某個非終結(jié)符