第03章、文法和語言

1、1第三章第三章 文法和語言文法和語言本章目的本章目的 為語言的語法描述尋求工具為語言的語法描述尋求工具工具要對程序設(shè)計語言給出精確無二義的語法描述。工具要對程序設(shè)計語言給出精確無二義的語法描述。（嚴謹、簡潔、易讀）（嚴謹、簡潔、易讀）形式形式工具工具形式語言形式語言，抽象地定義為一個數(shù)學(xué)，抽象地定義為一個數(shù)學(xué)系統(tǒng)。系統(tǒng)。 “形式形式”是指這樣的事實：語言的所有規(guī)則只以是指這樣的事實：語言的所有規(guī)則只以什么符號串能出現(xiàn)的方式來陳述。什么符號串能出現(xiàn)的方式來陳述。 2本章知識點本章知識點( (內(nèi)容內(nèi)容) )引言和預(yù)備知識引言和預(yù)備知識文法和語言的形式定義文法和語言的形式定義文法的類型文法的類型上下

2、文無關(guān)文法及其語法樹上下文無關(guān)文法及其語法樹上下文無關(guān)文法的句型分析上下文無關(guān)文法的句型分析有關(guān)文法實用中的一些說明有關(guān)文法實用中的一些說明33.1 文法的直觀概念和文法的直觀概念和語言概述語言概述當(dāng)我們表述一種語言時，無非是說明這種語言的當(dāng)我們表述一種語言時，無非是說明這種語言的句子，如果語言只含有有窮多個句子，則只需列句子，如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。語言來講，存在著如何給出它的有窮表示的問題。以自然語言為例，人們無法列出全部句子，但是以自然語言為例，人們

3、無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明人們可以給出一些規(guī)則，用這些規(guī)則來說明(或者或者定義定義)句子的組成結(jié)構(gòu)。句子的組成結(jié)構(gòu)。4“我是大學(xué)生我是大學(xué)生”。是漢語的一個句子是漢語的一個句子句子句子 =主語主語謂語謂語主語主語 =代詞代詞名詞名詞代詞代詞 =我我你你他他名詞名詞 =王明王明大學(xué)生大學(xué)生工人工人英語英語謂語謂語 =動詞動詞直接賓語直接賓語動詞動詞 =是是學(xué)習(xí)學(xué)習(xí)直接賓語直接賓語 =代詞代詞名詞名詞 有了一組規(guī)則以后，有了一組規(guī)則以后， 不斷地用不斷地用 =的的右邊代替右邊代替左邊左邊，就可以導(dǎo)出句子。，就可以導(dǎo)出句子。5“我是大學(xué)生我是大學(xué)生”的構(gòu)成符合上述規(guī)

4、則，而的構(gòu)成符合上述規(guī)則，而“我我大學(xué)生是大學(xué)生是”不符合上述規(guī)則，我們說它不是不符合上述規(guī)則，我們說它不是句子。句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。元語言，用它描述漢語。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中一種描述元語言稱為文法。一種描述元語言稱為文法。6語語 言言 概概 述述語言是由句子組成的集合，是由一組符號所構(gòu)成的語言是由句子組成的集合，是由一組符號所構(gòu)成的集合。集合。漢語漢語-所有符合漢語語法的句子的全體所有符合漢

5、語語法的句子的全體英語英語-所有符合英語語法的句子的全體所有符合英語語法的句子的全體程序設(shè)計語言程序設(shè)計語言-所有該語言的程序的全體所有該語言的程序的全體 語法語法 Syntax語言研究的三個方面語言研究的三個方面 語義語義 Semantics 語用語用 Pragmatics7如果不考慮語義和語用，即只從語法這一側(cè)面來看如果不考慮語義和語用，即只從語法這一側(cè)面來看語言，這種意義下的語言稱作形式語言。語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個數(shù)學(xué)系統(tǒng)。形式語言抽象地定義為一個數(shù)學(xué)系統(tǒng)?！靶问叫问健笔侵高@樣的事實：語言的所有規(guī)則只以什是指這樣的事實：語言的所有規(guī)則只以什么符號串能

6、出現(xiàn)的方式來陳述。么符號串能出現(xiàn)的方式來陳述。形式語言理論是對符號串集合的表示法、結(jié)構(gòu)及其形式語言理論是對符號串集合的表示法、結(jié)構(gòu)及其特性的研究。特性的研究。是程序設(shè)計語言語法分析研究的基礎(chǔ)。是程序設(shè)計語言語法分析研究的基礎(chǔ)。83.2 3.2 有關(guān)定義和記號的回顧有關(guān)定義和記號的回顧符號和符號串符號和符號串符號：符號：可以相互區(qū)別的記號（元素）?？梢韵嗷^(qū)別的記號（元素）。字母表字母表 ：符號（元素）的非空有窮集合（符號集）。符號（元素）的非空有窮集合（符號集）。符號串：符號串：由字母表由字母表 中的符號組成的任何有窮序列稱為該字母中的符號組成的任何有窮序列稱為該字母表上的符號串。表上的符號串

7、。1.空符號串空符號串(沒有沒有符號的符號串符號的符號串)是是 上的符號串上的符號串 2.若若x是是 上的符號串，上的符號串，a是是 的元素，則的元素，則xa是是 上的符號串上的符號串 3. y是是 上的符號串，當(dāng)且僅當(dāng)它可以由上的符號串，當(dāng)且僅當(dāng)它可以由1和和2導(dǎo)出。導(dǎo)出。 例如：例如： =a,b =a,b ,a,b,aa,ab,aabba ,a,b,aa,ab,aabba都都是是 上的符號串上的符號串9 符號串符號串s的頭（前綴）：的頭（前綴）：移走符號串移走符號串s尾部的零個或多于零尾部的零個或多于零個符號得到的符號串。個符號得到的符號串。 如：如： b是符號串是符號串banana的一個

8、前綴。的一個前綴。 符號串符號串s的尾（后綴）：的尾（后綴）：刪去符號串刪去符號串s頭部的零個或多于零頭部的零個或多于零個符號得到的符號串。個符號得到的符號串。 如如:nana是符號串是符號串banana的一個后綴。的一個后綴。 符號串符號串s的子串：的子串：從從s中刪去一個前綴和一個后綴得到的符中刪去一個前綴和一個后綴得到的符號串。號串。 如如:ana是符號串是符號串banana的一個子串。的一個子串。10 對于每個符號串對于每個符號串s， s和和兩者兩者都都是符號串是符號串s的前綴，后綴的前綴，后綴和子串。和子串。 符號串符號串s的真前綴，真后綴，真子串：的真前綴，真后綴，真子串：任何非空

9、符號串任何非空符號串 x,相應(yīng)地，是相應(yīng)地，是s的前綴，后綴或子串，并且的前綴，后綴或子串，并且 s x 符號串的運算符號串的運算 符號串的長度：符號串的長度：符號串中符號的個數(shù)符號串中符號的個數(shù).符號串符號串s的長度記的長度記為為|s|。 的長度為的長度為0 連接：連接：符號串符號串x x、y y的連接的連接, ,是把是把y y的符號寫在的符號寫在x x的符號之的符號之后得到的符號串后得到的符號串xy xy 如如 x=ab,y=cd x=ab,y=cd 則則 xy=abcd xy=abcd 有有a = a a = a 方冪：方冪：符號串自身連接符號串自身連接n n次得到的符號串次得到的符號串

10、 a an n 定義為定義為 aaaaaa naa n個個a a的連接的連接 a a1 1=a, a=a, a2 2=aa=aa則則a a0 0=11 符號串集合符號串集合：若集合若集合A中所有元素都是某字母表中所有元素都是某字母表 上的符號上的符號串，則稱串，則稱A為字母表為字母表 上的符號串集合。上的符號串集合。 兩個符號串集合兩個符號串集合A和和B的乘積的乘積 定義為定義為 AB = xy|xxy|x A A且且y y B B 若若 集合集合A= ab,cdeab,cde ，B = 0,10,1 則則 AB = ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 使用使

11、用 * 表示表示 上的一切符號串（包括上的一切符號串（包括）組成的集合。）組成的集合。* *稱為稱為的閉包的閉包。 上的上的除除外外的所有符號串組成的集合記為的所有符號串組成的集合記為 + 。 + +稱為稱為的正閉包的正閉包。12例：例：=a,b=a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab, .2*.32*13有關(guān)定義和記號有關(guān)定義和記號 語言語言是由句子組成的集合，是由一組符號所構(gòu)成的集合。是由句子組成的集合，是

12、由一組符號所構(gòu)成的集合。換言之，字母表換言之，字母表 上上的一個語言是的一個語言是 上的一些符號串的集合上的一些符號串的集合 (字母表字母表 上上的每個語言是的每個語言是 *的一個子集的一個子集)。 例如：例如：字母表字母表=a,b ,=a,b ,* *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, 集合集合ab,aabb,aaabbb,ab,aabb,aaabbb,a,an nb bn n, , 或表示為或表示為w|ww|w* *且且w=aw=an nb bn n,n1,n1為為字母表字母表 上上的一個語言。的一個語言。 集合集合a,

13、aa,aaa,a,aa,aaa, 或或表示為表示為w|ww|w* *且且w=aw=an n,n1 ,n1 為為字字母表母表 上上的一個語言。的一個語言。 是一個語言。是一個語言。 即即 是一個語言。是一個語言。14語言語言上上的有關(guān)運算的有關(guān)運算 設(shè)設(shè)L是（是（ 上的）一個語言，上的）一個語言，M是（是（ 上的）一個語言，上的）一個語言， 語語言言L和和M的并，交，差，補的并，交，差，補是一個語言。是一個語言。 語言語言L和和M的并為的并為 L M，是一個語言是一個語言: w|w is in L or w|w is in L or is in M is in M 如：如： L1 =a,b, =

14、a,b,y,z My,z M1 1 =0,1,2 =0,1,28,9 8,9 L1 M1 1=a,b,=a,b, y,z y,z， 0,1,20,1,28,9 8,9 語言語言L和和M的連接的連接是一個語言，記是一個語言，記為為 LM LM=st |sst |sL且且 t tM 如：如： L1M1 =a1,b1, =a1,b1,y1,z0,z1,a2,b2y1,z0,z1,a2,b2a9a9z9 z9 有有L = = L=L。 L的的n次連接次連接Ln= LL.L 15 語言語言L的的 閉包閉包記記為為 L*， L*= L0 L1 L2 L0= Ln= L Ln-1= Ln-1 L，n 1 語

15、言語言L的正的正 閉包閉包記記為為 L+ L+= L1 L2 L3 . L*= L+ 如：如： L1 =a,b,=a,b,y,zy,z， M M1 1 =0,1,2=0,1,28,9 8,9 （L1 M1 1）=a,b,=a,b, y,z y,z，0,1,20,1,28,98,9 （L1 M1 1）* *=a,b,=a,b, y,z,0,1,2 y,z,0,1,28,9,8,9,aa,0a,xyz,6789st. L1（L1 M1 1）* *=所有字母打頭的字母和數(shù)字符號串所有字母打頭的字母和數(shù)字符號串 163.3 3.3 文法和語言的形式定義文法和語言的形式定義如果語言是如果語言是有窮有窮的

16、（只含有有窮多個句子），可以將句子的（只含有有窮多個句子），可以將句子逐一列出來表示逐一列出來表示如果語言是如果語言是無窮無窮的，找出語言的有窮表示。語言的有窮表的，找出語言的有窮表示。語言的有窮表示有兩個途經(jīng)：示有兩個途經(jīng)： 1. 1. 生成方式生成方式 （文法）（文法）：語言中的每個句子可以用嚴格語言中的每個句子可以用嚴格定義的規(guī)則來構(gòu)造。定義的規(guī)則來構(gòu)造。 2. 2. 識別方式識別方式（自動機）（自動機）：用一個過程，當(dāng)輸入的一任意用一個過程，當(dāng)輸入的一任意串屬于語言時，該過程經(jīng)有限次計算后就會停止并回答串屬于語言時，該過程經(jīng)有限次計算后就會停止并回答“是是”，若不屬于，要么能停止并回答

17、，若不屬于，要么能停止并回答“不是不是”，（要，（要么永遠繼續(xù)下去。）么永遠繼續(xù)下去。） 17文法即是用生成方式描述語言的：文法即是用生成方式描述語言的：語言中的每個句子可以用嚴格定義的規(guī)則來構(gòu)造語言中的每個句子可以用嚴格定義的規(guī)則來構(gòu)造.下面給出文法的定義，進而在下面給出文法的定義，進而在文法的定義的基礎(chǔ)上，文法的定義的基礎(chǔ)上，給出給出推導(dǎo)的概念，句型、句子和語言的定義。推導(dǎo)的概念，句型、句子和語言的定義。18文法文法G定義為四元組定義為四元組(VN，VT，P，S )其中：其中：VN為非終結(jié)符號為非終結(jié)符號(或語法實體，或變量或語法實體，或變量)集；集；VT為終結(jié)符號集；為終結(jié)符號集；P為產(chǎn)

18、生式為產(chǎn)生式(也稱規(guī)則也稱規(guī)則)的集合；的集合； VN，VT和和P是是 非空有窮集。非空有窮集。 S稱作識別符號或開始符號，它是一個非終結(jié)符，至少要在稱作識別符號或開始符號，它是一個非終結(jié)符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。一條產(chǎn)生式中作為左部出現(xiàn)。 VN和和VT不含公共的元素，即不含公共的元素，即VN VT = 用用V表示表示VN VT ，稱為文法，稱為文法G的字母表或字匯表。的字母表或字匯表。規(guī)則規(guī)則，也稱重寫規(guī)則、產(chǎn)生式或生成式，是形如，也稱重寫規(guī)則、產(chǎn)生式或生成式，是形如或或 =的的(，)有序?qū)?，其中有序?qū)Γ渲惺亲帜副硎亲帜副鞻的正閉包的正閉包V+中的中的一個符號，且一個符號，且至

19、少包含一個非終結(jié)符至少包含一個非終結(jié)符;是是V*中的一個符號。中的一個符號。稱為規(guī)則的左部，稱為規(guī)則的左部，稱作規(guī)則的右部。稱作規(guī)則的右部。19例：例： 文法文法G=（VN，VT，P，S）VN = S VT = 0, 1 P= S0S1， S01 S為開始符號為開始符號20例：例： 文法文法G=（VN，VT，P，S）VN =標(biāo)識符，字母，數(shù)字標(biāo)識符，字母，數(shù)字VT =a,b,c,x,y,z,0,1,9P= a, zz 0,0, , 99 S=21 1. G1. G：SaASaAb Aab Aab AaA AaAb A A 2. GS 2. GS： SaASaAb Aab AaA Aab AaA

20、b A A 3.3. GSGS：SaASaAb Aab |aA Aab |aAb | | 一般用寫法一般用寫法 3 322元符號元符號: = = | | 習(xí)慣表示習(xí)慣表示 大寫字母：大寫字母：非終結(jié)符非終結(jié)符 小寫字母：小寫字母：終結(jié)符終結(jié)符如：如： S AB A Ax | y B z231. 直接推導(dǎo)直接推導(dǎo) 是文法是文法G G的產(chǎn)生式，若有的產(chǎn)生式，若有v,wv,w滿足：滿足：v=,w=, v=,w=, 其中其中VV* *,V,V* * 則稱則稱v v直接推導(dǎo)直接推導(dǎo)到到w,w,也稱也稱w w是是v v的直接推導(dǎo)，的直接推導(dǎo)，記作記作 v v w w 也稱也稱w w直接歸約直接歸約到到v

21、v例：例：GSGS： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S124 + *2. 推導(dǎo)推導(dǎo): 若存在若存在v w0 w1 . wn=w,(n0) 則記為則記為v = w，稱，稱v推導(dǎo)出推導(dǎo)出w，或，或w歸約到歸約到v 若有若有v = w，或，或v=w， 則記為則記為v = w+*25例：例：GSGS： S0S1， S01 S 0S1 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S = 00001111 S = S 00S11 =

22、00S11+*261. 句型句型 有文法有文法G，若，若S = x，則稱，則稱x是文法是文法G的句型。的句型。 即：即：從開始符號推導(dǎo)出的任意符號串。從開始符號推導(dǎo)出的任意符號串。2. 句子句子 有文法有文法G，若，若S = x，且，且xVVT T* *，則稱，則稱x是文法是文法G的的句子。句子。即：即：從開始符號推導(dǎo)出的終結(jié)符號串。從開始符號推導(dǎo)出的終結(jié)符號串。例：例：G G： S0S1， S01 S 0S1 00S11 000S111 00001111 S 01 G的的句型句型有：有：S，0S1，00S11，000S111，00001111，01 G的的句子句子有：有：00001111,

23、01*27例：例：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句子：用符號句子：用符號a，+，*，(和和)構(gòu)成的算術(shù)表達式構(gòu)成的算術(shù)表達式28由文法由文法G生成的生成的語言語言記為記為L(G)，它是文法，它是文法G的一切句子的集合的一切句子的集合: L(G)=x|S = x，其中，其中S為文法的開始符為文法的開始符號，且號，且x VVT T* * 例：例：GS： S0S1， S01 L(G)=0n1n|n1*29文法的等價文法的等價若若L（G1）=L（G2），則

24、稱文法），則稱文法G1和和G2是等價的。是等價的。如文法如文法G G1AA：A0R A0R 與與 G G2SS：S0S1 S0S1 等價等價 A01 S01A01 S01 RA1 RA1303.4 3.4 文法的類型文法的類型 通過對產(chǎn)生式施加不同的限制，通過對產(chǎn)生式施加不同的限制，Chomsky(喬姆斯基）將文法分為四種類型：喬姆斯基）將文法分為四種類型：0型文法（短語文法）型文法（短語文法）：對任一產(chǎn)生式：對任一產(chǎn)生式，都，都有有(V(VN NVVT T) )+ +，且至少含有一個非終結(jié)符，且至少含有一個非終結(jié)符， (V(VN NVVT T) )* *1 1型文法（上下文有關(guān)文法）型文法（

25、上下文有關(guān)文法）：對任一產(chǎn)生式對任一產(chǎn)生式，都有，都有|， 僅僅僅僅 SS除外除外 31文法的類型文法的類型( (續(xù)續(xù)) )2 2型文法（上下文無關(guān)文法）型文法（上下文無關(guān)文法）：對任一對任一產(chǎn)生式產(chǎn)生式，都有，都有VVN N ， (V(VN NVVT T) )* *3 3型文法（正規(guī)文法）型文法（正規(guī)文法）：任一產(chǎn)生式任一產(chǎn)生式的形式都為的形式都為AaBAaB或或AaAa，其，其中中AVAVN N ，BVBVN N ，aVaVT T32文法的類型舉例文法的類型舉例例：例：1 1型（上下文有關(guān)）文法型（上下文有關(guān)）文法 文法文法GSGS： SCDSCDAbAaAbAa CaCA CaCABaB

26、ABaBA CbCB CbCBBbAbBbAbADaDADaD Ca CaBDbDBDbD Da DaAaDaAaDa33文法的類型舉例文法的類型舉例例：例：2 2型（上下文無關(guān)）文法型（上下文無關(guān)）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|134文法的類型舉例文法的類型舉例GS： S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d例：例：3 3型文法（正規(guī)文法）型文法（正規(guī)文法）35四種四種文法文法之間之間的的逐級逐級“包含包含”關(guān)系關(guān)系2型文法型文法1

27、型文法型文法0型文法型文法3型文法型文法36文法和語言文法和語言0型文法產(chǎn)生的語言稱為型文法產(chǎn)生的語言稱為0型語言型語言1 1型文法或上下文有關(guān)文法（型文法或上下文有關(guān)文法（ CSG ）產(chǎn)生的語言產(chǎn)生的語言稱為稱為1 1型語言型語言或上下文有關(guān)或上下文有關(guān)語言（語言（CSL）2 2型文法或上下文無關(guān)文法型文法或上下文無關(guān)文法（ CFG ）產(chǎn)生的語言產(chǎn)生的語言稱為稱為2型語言型語言或上下文無關(guān)或上下文無關(guān)語言（語言（ CF L ） 3 3型文法或正則（正規(guī)）文法型文法或正則（正規(guī)）文法（ RG ）產(chǎn)生的語言產(chǎn)生的語言稱為稱為3型語言型語言正則（正規(guī)）正則（正規(guī)）語言（語言（ RL ）四種文法之間

28、的關(guān)系四種文法之間的關(guān)系 是將產(chǎn)生式做進一步限制而是將產(chǎn)生式做進一步限制而定義的。定義的。 37根據(jù)形式語言理論根據(jù)形式語言理論, ,文法和自動機（識文法和自動機（識別系統(tǒng)）間有這樣的關(guān)系別系統(tǒng)）間有這樣的關(guān)系 0型文法型文法（短語結(jié)構(gòu)文法）的能力相當(dāng)于（短語結(jié)構(gòu)文法）的能力相當(dāng)于圖靈機圖靈機，可以表征任何遞歸可枚舉集，而且任何可以表征任何遞歸可枚舉集，而且任何0型語言都型語言都是遞歸可枚舉的是遞歸可枚舉的 1型文法型文法（上下文有關(guān)文法）：產(chǎn)生式的形式為（上下文有關(guān)文法）：產(chǎn)生式的形式為1 1AA2 21 12 2，即只有，即只有A A出現(xiàn)在出現(xiàn)在1 1和和2 2的上的上下文中時，才允許下文

29、中時，才允許取代取代A A。其識別系統(tǒng)是。其識別系統(tǒng)是線性界線性界限自動機限自動機。38 帶帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁頭磁頭 任何能用任何能用圖靈機圖靈機描述的計算都能機械實現(xiàn)，描述的計算都能機械實現(xiàn)，任何能在現(xiàn)代計算機上實現(xiàn)的計算都能用圖靈任何能在現(xiàn)代計算機上實現(xiàn)的計算都能用圖靈機描述機描述39 2型文法型文法（上下文無關(guān)文法（上下文無關(guān)文法CFG）：產(chǎn)生式的形式）：產(chǎn)生式的形式為為AA，取代取代A A時與時與A A的上下文無關(guān)。其識別的上下文無關(guān)。其識別系統(tǒng)是不確定的系統(tǒng)是不確定的下推自動機下推自動機。 3型文法型文法（

30、正規(guī)文法（正規(guī)文法RG）：產(chǎn)生的語言是有）：產(chǎn)生的語言是有窮自窮自動機動機（FA）所接受的集合）所接受的集合403.5 3.5 上下文無關(guān)文法及其語法樹上下文無關(guān)文法及其語法樹上下文無關(guān)文法有足夠的能力描述程序設(shè)計語言的上下文無關(guān)文法有足夠的能力描述程序設(shè)計語言的語法結(jié)構(gòu)語法結(jié)構(gòu)語法樹語法樹-句型推導(dǎo)句型推導(dǎo)的的直觀表示直觀表示41GE： EE+T|T TT*F|F F(E)|iEE+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*i EE+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*iEE+T T+T T+T*F F+T*F F

31、+F*F i+F*F i+F*i i+i*i42規(guī)范推導(dǎo)規(guī)范推導(dǎo) 規(guī)范句型規(guī)范句型最左（最右）推導(dǎo)：最左（最右）推導(dǎo)：在推導(dǎo)的任何一步在推導(dǎo)的任何一步，其，其中中、是句型，都是對是句型，都是對中的最左（右）非終中的最左（右）非終結(jié)符進行替換結(jié)符進行替換最右推導(dǎo)被稱為最右推導(dǎo)被稱為規(guī)范推導(dǎo)規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型規(guī)范句型43 設(shè)設(shè)G=( VN,VT,P,S)為一為一CFG，若一棵樹滿足下列，若一棵樹滿足下列4個條件，個條件，則此樹稱作則此樹稱作G的語法樹的語法樹(推導(dǎo)樹推導(dǎo)樹)(派生樹）：派生樹）：1. 每個結(jié)點都有一個標(biāo)記，此標(biāo)記是每個結(jié)點都有一個標(biāo)記

32、，此標(biāo)記是V的一個符號的一個符號2. 根的標(biāo)記是根的標(biāo)記是S3. 若一結(jié)點若一結(jié)點n至少有一個它自己除外的子孫，并且有標(biāo)記至少有一個它自己除外的子孫，并且有標(biāo)記A，則肯定則肯定AVVN N4. 如果結(jié)點如果結(jié)點n有標(biāo)記有標(biāo)記A,其直接子孫結(jié)點從左到右的次序是其直接子孫結(jié)點從左到右的次序是n1，n2，nk，其標(biāo)記分別為，其標(biāo)記分別為A1，A2，Ak，那么，那么AA1A2，Ak一定是一定是P中的一個產(chǎn)生式中的一個產(chǎn)生式語法樹的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之語法樹的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之 44語法樹語法樹-句型推導(dǎo)句型推導(dǎo)的的直觀表示直觀表示給定文法給定文法G=(VN

33、,VT,P,S)，對于，對于G的任何句型都能構(gòu)的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹造與之關(guān)聯(lián)的語法樹(推導(dǎo)樹推導(dǎo)樹)定理：定理：G為上下文無關(guān)文法，為上下文無關(guān)文法，對于對于，有，有S = ，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)文法文法G有以有以為結(jié)果的一棵語法樹為結(jié)果的一棵語法樹(推導(dǎo)樹推導(dǎo)樹)*45構(gòu)造語法樹構(gòu)造語法樹GE： EE+T|T TT*F|F F(E)|iEE+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*i E EE + T E + T T E E + T T F46E EE+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*i (最左推導(dǎo)最左推導(dǎo))

34、E EE+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i (最右推導(dǎo)最右推導(dǎo))E EE+T T+T T+T*F F+T*F F+F*F i+F*F i+F*i i+i*i E E E + T E + T T T T T * * F F F F i F F i i i i i 看不出句型中的符號被替代看不出句型中的符號被替代的順序的順序47上下文無關(guān)文法的語法樹的用處上下文無關(guān)文法的語法樹的用處用于描述上下文無關(guān)文法用于描述上下文無關(guān)文法句型推導(dǎo)句型推導(dǎo)的的直觀方法直觀方法 例例: GS:SaASASbAASSSaAba S a A S S b A a a

35、 b a句型句型aabbaa的的語法樹語法樹（推導(dǎo)樹）（推導(dǎo)樹）葉子結(jié)點葉子結(jié)點：樹中：樹中沒有子孫的結(jié)點沒有子孫的結(jié)點。從左到右從左到右讀出推導(dǎo)樹的讀出推導(dǎo)樹的葉子標(biāo)記葉子標(biāo)記連接成的連接成的文文法符號法符號串串，為，為GS的的句型句型。也把該推導(dǎo)樹稱。也把該推導(dǎo)樹稱為該為該句型句型的的語法樹語法樹。48上下文無關(guān)文法的語法樹上下文無關(guān)文法的語法樹z推導(dǎo)過程中推導(dǎo)過程中施用施用產(chǎn)生式產(chǎn)生式的的順序順序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaS

36、aASaSbASaSbAaaabAaaabbaa49一棵語法樹表示了一個句型的種種可能的一棵語法樹表示了一個句型的種種可能的( (但但未必是所有的未必是所有的) )不同推導(dǎo)過程，包括最左不同推導(dǎo)過程，包括最左( (最右最右) )推導(dǎo)。推導(dǎo)。但是，一個句型是否只對應(yīng)唯一的一棵語法但是，一個句型是否只對應(yīng)唯一的一棵語法樹呢樹呢? ?一個句型是否只有唯一的一個最左一個句型是否只有唯一的一個最左( (最右最右) )推推導(dǎo)呢導(dǎo)呢? ?50例：例：GE:GE: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

37、 i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的兩個不同的最左推導(dǎo)：的兩個不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)推導(dǎo)2：E E*E i*E i*E+E i*i+E i*i+i51 若一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這若一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個個文法是二義文法是二義的的或者，若一個文法存在某個句子有兩個不同的最左（右）或者，若一個文法存在某個句子有兩個不同的最左（右）推導(dǎo)，則稱這個推導(dǎo)，則稱這個文法是二義文法是二義的的 判定任給的一個上下文無

38、關(guān)文法是否二義，或它是否產(chǎn)生判定任給的一個上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個先天二義的上下文無關(guān)語言，這兩個問題是遞歸不可一個先天二義的上下文無關(guān)語言，這兩個問題是遞歸不可解的，但可以為無二義性尋找一組充分條件，如：規(guī)定運解的，但可以為無二義性尋找一組充分條件，如：規(guī)定運算符的優(yōu)先順序和結(jié)合規(guī)則。算符的優(yōu)先順序和結(jié)合規(guī)則。 52文法的二義性和語言的二義性是兩個不同的概念。因為可能文法的二義性和語言的二義性是兩個不同的概念。因為可能有兩個不同的文法有兩個不同的文法G G和和GG，其中，其中G G是二義的，但是卻有是二義的，但是卻有L(G)=L(G)L(G)=L(G)，也就是說，這兩個文法所

39、產(chǎn)生的語言是相，也就是說，這兩個文法所產(chǎn)生的語言是相同的。同的。二義文法改造為無二義文法二義文法改造為無二義文法GE: E i GEGE: E i GE：E T|E+TE T|E+T E E+E T F|T E E+E T F|T* *F F E E E E* *E F E F （E E）|i|i E (E) E (E) 規(guī)定優(yōu)先順序和結(jié)合律規(guī)定優(yōu)先順序和結(jié)合律z 如果產(chǎn)生上下文無關(guān)語言的每一個文法都是二義的，則說如果產(chǎn)生上下文無關(guān)語言的每一個文法都是二義的，則說此語言是先天二義的。對于一個程序設(shè)計語言來說，常常此語言是先天二義的。對于一個程序設(shè)計語言來說，常常希望它的文法是無二義的，因為希望

40、對它的每個語句的分希望它的文法是無二義的，因為希望對它的每個語句的分析是唯一的。析是唯一的。533.6 3.6 句型的分析句型的分析一、有關(guān)概念一、有關(guān)概念1.句型分析句型分析 句型分析就是識別一個符號串是否為某文法的句型分析就是識別一個符號串是否為某文法的句型，是某個推導(dǎo)的構(gòu)造過程。句型，是某個推導(dǎo)的構(gòu)造過程。2.分析程序分析程序 在語言的編譯實現(xiàn)中，把完成句型分析的程序在語言的編譯實現(xiàn)中，把完成句型分析的程序稱為稱為分析程序分析程序或或識別程序識別程序。分析算法又稱。分析算法又稱識別算法識別算法。3.從左到右的分析算法從左到右的分析算法 從左到右的分析算法從左到右的分析算法，即總是從左，即

41、總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號，直到分析結(jié)束。而依次識別右邊的一個符號，直到分析結(jié)束。54二、句型的分析算法分類二、句型的分析算法分類 分析算法可分為分析算法可分為2類：類：1.自頂向下自頂向下(自上而下自上而下)分析法：分析法： 從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號串匹配的生式，尋找與輸入符號串匹配的推導(dǎo)推導(dǎo)。2.自底向上自底向上(自下而上自下而上)分析法：分析法： 從輸入符號串開始，逐步進行從輸入符號串開始，逐步進行歸約歸約，

42、直至歸約，直至歸約到文法的開始符號。到文法的開始符號。55兩種方法反映了兩種語法樹的構(gòu)造過程兩種方法反映了兩種語法樹的構(gòu)造過程自頂向下方法自頂向下方法 是從文法符號開始，將它做為語是從文法符號開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的法樹的根，向下逐步建立語法樹，使語法樹的結(jié)果正好是輸入符號串；結(jié)果正好是輸入符號串；自底向上方法自底向上方法 則是從輸入符號串開始，以它做則是從輸入符號串開始，以它做為語法樹的結(jié)果，自底向上地構(gòu)造語法樹。為語法樹的結(jié)果，自底向上地構(gòu)造語法樹。56自頂向下的語法分析自頂向下的語法分析- -例例例：文法例：文法G：S cAd A ab A a識別輸入串識

43、別輸入串w=cabd是否為該文法的是否為該文法的句子句子SSScAdcAd a b推導(dǎo)過程：推導(dǎo)過程：S cAd cAd cabd57自底向上的語法分析自底向上的語法分析- -例例例：文法例：文法G： S cAd A ab A a識別輸入串識別輸入串w=cabd是否該文法的是否該文法的句子句子SAA c a b d c a b d c a b d 規(guī)約規(guī)約過程構(gòu)造的推導(dǎo)：過程構(gòu)造的推導(dǎo)： cAd cabd S cAd58(1)S cAd (2) A ab (3)A a 識別輸入串識別輸入串w=cabd是否為該文法的是否為該文法的句子句子1. 1. 自頂向下的語法分析自頂向下的語法分析若若S c

44、Ad 后選擇后選擇(3)擴展擴展A， S cAd cad ， 那將會？那將會？ w的第二個符號可以與葉子結(jié)點的第二個符號可以與葉子結(jié)點a得以匹配，但第得以匹配，但第三個符號卻不能與下一葉子結(jié)點三個符號卻不能與下一葉子結(jié)點d匹配匹配？宣告分析失?。ㄆ湟馕吨?，識別程序不能為串？宣告分析失?。ㄆ湟馕吨?，識別程序不能為串cad構(gòu)造語法樹，即構(gòu)造語法樹，即cad不是句子）不是句子）-顯然是錯誤的結(jié)論。顯然是錯誤的結(jié)論。導(dǎo)致失敗的原因是在分析中對導(dǎo)致失敗的原因是在分析中對A的選擇不是正確的。的選擇不是正確的。 S c A d a59對串對串cabd的分析中，如果不是的分析中，如果不是選擇選擇ab用產(chǎn)生式用

45、產(chǎn)生式(2),而是選而是選擇擇a用產(chǎn)生式用產(chǎn)生式(3)將將a歸約到了歸約到了A，那么最終就達不到歸約，那么最終就達不到歸約到到S的結(jié)果，因而也無從知的結(jié)果，因而也無從知道道cabd是一個句子。是一個句子。c a b d c A b d a(1)S cAd (2) A ab (3)A a 識別輸入串識別輸入串w=cabd是否為該文法的是否為該文法的句子句子2. 2. 自底向上的語法分析自底向上的語法分析60三、句型分析的有關(guān)問題三、句型分析的有關(guān)問題1. 在自頂向下的分析方法中在自頂向下的分析方法中如何如何選擇選擇使用使用哪個哪個產(chǎn)生產(chǎn)生式進行推導(dǎo)式進行推導(dǎo)？假定要被代換的最左非終結(jié)符號是假定要

46、被代換的最左非終結(jié)符號是B，且有，且有n條規(guī)則：條規(guī)則：BA1|A2|An，那么如何確定用哪個右，那么如何確定用哪個右部去替代部去替代B？2.在自底向上的分析方法中在自底向上的分析方法中如何如何識別可歸約的串識別可歸約的串？在分析程序工作的每一步，都是從當(dāng)前串中在分析程序工作的每一步，都是從當(dāng)前串中選選擇一個擇一個子串子串，將它，將它歸約歸約到到某個非終結(jié)符號某個非終結(jié)符號，該子串，該子串稱為稱為“可歸約串可歸約串”61四、四、刻畫刻畫“可歸約串可歸約串”文法文法GS1. 句型的短語句型的短語 S = A且且 A = ，則稱則稱是是句型句型相相對于非終結(jié)符對于非終結(jié)符A的的短語。短語。2. 句

47、型的直接短語句型的直接短語(或簡單短語或簡單短語) 若有若有A ，則稱則稱是句型是句型相對于非終相對于非終結(jié)符結(jié)符A 的的直接短語。直接短語。3. 句型的句柄句型的句柄 一個句型的一個句型的最左直接短語最左直接短語稱為稱為該句型該句型的的句柄。句柄。*+62例例i i* *i+ii+i例例 ：i i* *i+i i+i 的短語、直接短語和句柄的短語、直接短語和句柄 E E + T T FT * F i3 短語短語：i1* * i2+ + i3， i1* * i2 ，F(xiàn) i2 i1 ， i2 ， i3 。 i1 直接短語直接短語： i1 ， i2 ， i3 。句柄句柄： i1 GEGE：EE+T

48、|TEE+T|T TT TT* *F|FF|F F(E)|i F(E)|i句型：句型：i i* *i+ii+i633.7 3.7 文法實用中的一些說明文法實用中的一些說明- -化簡文法化簡文法一、文法中不含有害規(guī)則和多余規(guī)則一、文法中不含有害規(guī)則和多余規(guī)則1. 有害規(guī)則：有害規(guī)則：形如形如PP的產(chǎn)生式。會引起文法的二義性。的產(chǎn)生式。會引起文法的二義性。2. 多余規(guī)則：多余規(guī)則：指文法中任何句子的推導(dǎo)都不會用到的規(guī)則。指文法中任何句子的推導(dǎo)都不會用到的規(guī)則。文法中不含有文法中不含有不可到達不可到達和和不可終止不可終止的非終結(jié)符。的非終結(jié)符。 3. 不可到達：不可到達：文法中某些非終結(jié)符不在任何規(guī)

49、則的右部出文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，該非終結(jié)符稱為不可到達?，F(xiàn)，該非終結(jié)符稱為不可到達。4. 不可終止不可終止: 文法中某些非終結(jié)符，由它不能推出終結(jié)符文法中某些非終結(jié)符，由它不能推出終結(jié)符號串，該非終結(jié)符稱為不可終止。號串，該非終結(jié)符稱為不可終止。64二、不含多余非終結(jié)符的條件二、不含多余非終結(jié)符的條件 對于文法對于文法GS，為了保證任一非終結(jié)符，為了保證任一非終結(jié)符A在句在句子推導(dǎo)中出現(xiàn)，必須滿足如下兩個條件：子推導(dǎo)中出現(xiàn)，必須滿足如下兩個條件： 1. A必須在某句型中出現(xiàn)必須在某句型中出現(xiàn) 即有即有S = A，其中，其中，屬于屬于V V* * 2. 必須能夠從必須能夠從A

50、推出終結(jié)符號串推出終結(jié)符號串t來來 即即A = t，其中，其中tVT*65三、三、化簡文法化簡文法例例例：例：GS ： 1) SBe 2) BCe D為不可到達為不可到達 3) BAf C為不可終止為不可終止 4) AAe 5) Ae 6) CCf 7) Df 產(chǎn)生式產(chǎn)生式 2），），6），），7）為）為多余規(guī)則，多余規(guī)則，應(yīng)去應(yīng)去掉。掉。66四、四、上下文無關(guān)文法中的上下文無關(guān)文法中的規(guī)則規(guī)則z具有形式具有形式A的規(guī)則稱為的規(guī)則稱為規(guī)則規(guī)則，其中，其中AVNz某些著作和講義中限制這種規(guī)則的出現(xiàn)。因某些著作和講義中限制這種規(guī)則的出現(xiàn)。因為為規(guī)則會使有關(guān)文法的一些討論和證明變規(guī)則會使有關(guān)文法的一些討論和證明變得復(fù)雜得復(fù)雜z兩種定義的唯一差別是兩種定義的唯一差別是句子在不在語言中。句子在不在語言中。1. 什么是什