《文法和語(yǔ)言》ppt課件

1、第三章第三章 文法和言語(yǔ)文法和言語(yǔ)本章目的為言語(yǔ)的語(yǔ)法描畫(huà)尋求工具本章目的為言語(yǔ)的語(yǔ)法描畫(huà)尋求工具,以便：以便：對(duì)源程序給出準(zhǔn)確無(wú)二義的語(yǔ)法描畫(huà)。嚴(yán)對(duì)源程序給出準(zhǔn)確無(wú)二義的語(yǔ)法描畫(huà)。嚴(yán)謹(jǐn)、簡(jiǎn)約、易讀謹(jǐn)、簡(jiǎn)約、易讀根據(jù)言語(yǔ)文法的特點(diǎn)來(lái)指點(diǎn)語(yǔ)法分析的過(guò)程根據(jù)言語(yǔ)文法的特點(diǎn)來(lái)指點(diǎn)語(yǔ)法分析的過(guò)程從描畫(huà)言語(yǔ)的文法可以自動(dòng)構(gòu)造出可用的分從描畫(huà)言語(yǔ)的文法可以自動(dòng)構(gòu)造出可用的分析程序析程序制導(dǎo)語(yǔ)義翻譯制導(dǎo)語(yǔ)義翻譯文法和言語(yǔ)文法和言語(yǔ)z預(yù)備知識(shí)預(yù)備知識(shí)z文法和言語(yǔ)的方式定義文法和言語(yǔ)的方式定義z文法的類(lèi)型文法的類(lèi)型z上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)z上下文無(wú)關(guān)文法的句型分析上下文無(wú)關(guān)文法的句型分

2、析z有關(guān)文法適用中的一些闡明有關(guān)文法適用中的一些闡明z有關(guān)文法的一些關(guān)系有關(guān)文法的一些關(guān)系預(yù)備知識(shí)預(yù)備知識(shí) -言語(yǔ)概述言語(yǔ)概述z言語(yǔ)是由句子組成的集合，是由一組記號(hào)言語(yǔ)是由句子組成的集合，是由一組記號(hào)所構(gòu)成的集合。所構(gòu)成的集合。z漢語(yǔ)漢語(yǔ)-一切符合漢語(yǔ)語(yǔ)法的句子的全體一切符合漢語(yǔ)語(yǔ)法的句子的全體z英語(yǔ)英語(yǔ)-一切符合英語(yǔ)語(yǔ)法的句子的全體一切符合英語(yǔ)語(yǔ)法的句子的全體z程序設(shè)計(jì)言語(yǔ)程序設(shè)計(jì)言語(yǔ)-一切該言語(yǔ)的程序的全體一切該言語(yǔ)的程序的全體z 每個(gè)句子構(gòu)成的規(guī)律每個(gè)句子構(gòu)成的規(guī)律z研討言語(yǔ)研討言語(yǔ) 每個(gè)句子的含義每個(gè)句子的含義z 每個(gè)句子和運(yùn)用者的關(guān)系每個(gè)句子和運(yùn)用者的關(guān)系預(yù)備知識(shí)預(yù)備知識(shí) -言語(yǔ)概述

3、言語(yǔ)概述研討程序設(shè)計(jì)言語(yǔ)研討程序設(shè)計(jì)言語(yǔ) 每個(gè)程序構(gòu)成的規(guī)律每個(gè)程序構(gòu)成的規(guī)律 每個(gè)程序的含義每個(gè)程序的含義 每個(gè)程序和運(yùn)用者的關(guān)系每個(gè)程序和運(yùn)用者的關(guān)系言語(yǔ)研討的三個(gè)方面言語(yǔ)研討的三個(gè)方面 語(yǔ)法語(yǔ)法 Syntax 語(yǔ)義語(yǔ)義 Semantics 語(yǔ)用語(yǔ)用 Pragmatics預(yù)備知識(shí)預(yù)備知識(shí) -言語(yǔ)概述言語(yǔ)概述語(yǔ)法語(yǔ)法 - 表示構(gòu)成言語(yǔ)句子的各個(gè)記號(hào)之間的表示構(gòu)成言語(yǔ)句子的各個(gè)記號(hào)之間的組合規(guī)律組合規(guī)律語(yǔ)義語(yǔ)義 - 表示按照各種表示方法所表示的各個(gè)表示按照各種表示方法所表示的各個(gè)記號(hào)的特定含義。各個(gè)記號(hào)和記號(hào)所表記號(hào)的特定含義。各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系示的對(duì)象之間的關(guān)系語(yǔ)用語(yǔ)用 -

4、表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來(lái)源、運(yùn)用和影響。們的來(lái)源、運(yùn)用和影響。預(yù)備知識(shí)預(yù)備知識(shí) -言語(yǔ)概述言語(yǔ)概述z每種言語(yǔ)具有兩個(gè)可識(shí)別的特性，即言語(yǔ)每種言語(yǔ)具有兩個(gè)可識(shí)別的特性，即言語(yǔ)的方式和該方式相關(guān)聯(lián)的意義。的方式和該方式相關(guān)聯(lián)的意義。z言語(yǔ)的實(shí)例假設(shè)在語(yǔ)法上是正確的，其相言語(yǔ)的實(shí)例假設(shè)在語(yǔ)法上是正確的，其相關(guān)聯(lián)的意義可以從兩個(gè)觀念來(lái)看，其一是關(guān)聯(lián)的意義可以從兩個(gè)觀念來(lái)看，其一是該句子的創(chuàng)建者所想要表示的意義，另一該句子的創(chuàng)建者所想要表示的意義，另一是接納者所檢驗(yàn)到的意義。這兩個(gè)意義并是接納者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的，前者稱(chēng)為言語(yǔ)的語(yǔ)義，后

5、非總是一樣的，前者稱(chēng)為言語(yǔ)的語(yǔ)義，后者是其語(yǔ)意圖義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就者是其語(yǔ)意圖義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就是利用這兩方面意義間的差別。是利用這兩方面意義間的差別。預(yù)備知識(shí)預(yù)備知識(shí) -方式言語(yǔ)方式言語(yǔ)z假設(shè)不思索語(yǔ)義和語(yǔ)用，即只從語(yǔ)法這一側(cè)假設(shè)不思索語(yǔ)義和語(yǔ)用，即只從語(yǔ)法這一側(cè)面來(lái)看言語(yǔ)，這種意義下的言語(yǔ)稱(chēng)作方式言面來(lái)看言語(yǔ)，這種意義下的言語(yǔ)稱(chēng)作方式言語(yǔ)。方式言語(yǔ)籠統(tǒng)地定義為一個(gè)數(shù)學(xué)系統(tǒng)。語(yǔ)。方式言語(yǔ)籠統(tǒng)地定義為一個(gè)數(shù)學(xué)系統(tǒng)?！胺绞绞侵高@樣的現(xiàn)實(shí)：言語(yǔ)的一切規(guī)那方式是指這樣的現(xiàn)實(shí)：言語(yǔ)的一切規(guī)那么只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳說(shuō)。方么只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳說(shuō)。方式言語(yǔ)實(shí)踐是對(duì)符號(hào)串集合

6、的表示法、構(gòu)造式言語(yǔ)實(shí)踐是對(duì)符號(hào)串集合的表示法、構(gòu)造及其特性的研討。是程序設(shè)計(jì)言語(yǔ)語(yǔ)法分析及其特性的研討。是程序設(shè)計(jì)言語(yǔ)語(yǔ)法分析研討的根底。研討的根底。預(yù)備知識(shí)預(yù)備知識(shí) -有關(guān)定義和記號(hào)有關(guān)定義和記號(hào)z符號(hào)：可以相互區(qū)別的記號(hào)元素。符號(hào)：可以相互區(qū)別的記號(hào)元素。z字母表字母表 ：符號(hào)元素的非空有窮集合。：符號(hào)元素的非空有窮集合。z符號(hào)串：由字母表符號(hào)串：由字母表 中的符號(hào)組成的任何有窮中的符號(hào)組成的任何有窮序列稱(chēng)為該字母表上的符號(hào)串。序列稱(chēng)為該字母表上的符號(hào)串。1.空符號(hào)串空符號(hào)串(沒(méi)有符號(hào)的符號(hào)串沒(méi)有符號(hào)的符號(hào)串)是是 上的符號(hào)串上的符號(hào)串 2.假設(shè)假設(shè)x是是 上的符號(hào)串上的符號(hào)串,a是是

7、的元素的元素,那么那么xa是是 上的符上的符號(hào)串號(hào)串 3. y是是 上的符號(hào)串上的符號(hào)串,當(dāng)且僅當(dāng)它可以由當(dāng)且僅當(dāng)它可以由1和和2導(dǎo)出。導(dǎo)出。 例如：例如： =a,b ,a,b,aa,ab,aabba都是都是 上的符號(hào)串上的符號(hào)串預(yù)備知識(shí)預(yù)備知識(shí) -有關(guān)定義和記號(hào)有關(guān)定義和記號(hào)z符號(hào)串符號(hào)串s的前綴：移走符號(hào)串的前綴：移走符號(hào)串s尾部的零個(gè)或尾部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串多于零個(gè)符號(hào)得到的符號(hào)串. 如：如： b是符號(hào)串是符號(hào)串banana的一個(gè)前綴的一個(gè)前綴. z符號(hào)串符號(hào)串s的后綴：刪去符號(hào)串的后綴：刪去符號(hào)串s頭部的零個(gè)或頭部的零個(gè)或多于零個(gè)符號(hào)得到的符號(hào)串多于零個(gè)符號(hào)得到的符號(hào)串.

8、 如如:nana是符號(hào)串是符號(hào)串banana的一個(gè)后綴的一個(gè)后綴.z符號(hào)串符號(hào)串s的子串：從的子串：從s中刪去一個(gè)前綴和一個(gè)中刪去一個(gè)前綴和一個(gè)后綴得到的符號(hào)串后綴得到的符號(hào)串. 如如:ana是符號(hào)串是符號(hào)串banana的一個(gè)子串的一個(gè)子串.z對(duì)于每個(gè)符號(hào)串對(duì)于每個(gè)符號(hào)串s， s和和兩者都是符號(hào)串兩者都是符號(hào)串s的的前綴，后綴和子串。前綴，后綴和子串。 z符號(hào)串符號(hào)串s的真前綴，真后綴，真子串：任何非的真前綴，真后綴，真子串：任何非空符號(hào)串空符號(hào)串 x,相應(yīng)地，是相應(yīng)地，是s的前綴，后綴或子串，的前綴，后綴或子串，并且并且 s x z符號(hào)串的運(yùn)算符號(hào)串的運(yùn)算z符號(hào)串的長(zhǎng)度：符號(hào)串中符號(hào)的個(gè)數(shù)符

9、號(hào)串的長(zhǎng)度：符號(hào)串中符號(hào)的個(gè)數(shù).符號(hào)串符號(hào)串s的長(zhǎng)度記為的長(zhǎng)度記為|s|。 的長(zhǎng)度為的長(zhǎng)度為0z銜接：符號(hào)串銜接：符號(hào)串x、y的銜接的銜接,是把是把y的符號(hào)寫(xiě)在的符號(hào)寫(xiě)在x的符號(hào)之后得到的符號(hào)串的符號(hào)之后得到的符號(hào)串xy 如如 x=ab,y=cd 那么那么 xy=abcd 有有a = a z方冪：符號(hào)串本身銜接方冪：符號(hào)串本身銜接n次得到的符號(hào)串次得到的符號(hào)串 an 定義為定義為 aaaa n個(gè)個(gè)a a1=a, a2=aa那那么么a0=z符號(hào)串集合：假設(shè)集合符號(hào)串集合：假設(shè)集合A中一切元素都是某中一切元素都是某字母表字母表 上的符號(hào)串，那么稱(chēng)上的符號(hào)串，那么稱(chēng)A為字母表為字母表 上上的符號(hào)串集

10、合。的符號(hào)串集合。z兩個(gè)符號(hào)串集合兩個(gè)符號(hào)串集合A和和B的乘積定義為的乘積定義為 AB =xy|xA且且yB 假設(shè)假設(shè) 集合集合A=ab,cde B = 0,1 那么那么 AB =ab1,ab0,cde0,cde1 z運(yùn)用運(yùn)用 * 表示表示 上的一切符號(hào)串包括上的一切符號(hào)串包括組成的集合。組成的集合。*稱(chēng)為稱(chēng)為的閉包。的閉包。z 上的除上的除外的一切符號(hào)串組成的集合記為外的一切符號(hào)串組成的集合記為 + 。 +稱(chēng)為稱(chēng)為的正閉包。的正閉包。z例：例：=a,b=a,bz * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,z +=a,b,aa

11、,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,z.2*.32*z言語(yǔ)：字母表言語(yǔ)：字母表 上的一個(gè)言語(yǔ)是上的一個(gè)言語(yǔ)是 上的一些符號(hào)上的一些符號(hào)串的集合串的集合 ( 上的每個(gè)言語(yǔ)是上的每個(gè)言語(yǔ)是 *的一個(gè)子集的一個(gè)子集)。z例如：例如： =a,b *=,a,b,aa,ab,ba,bb,aaa,aab,z集合集合ab,aabb,aaabbb,anbn,z或或w|w*且且w=anbn,n1為字為字母表母表 上的一個(gè)言語(yǔ)。上的一個(gè)言語(yǔ)。z集合集合a,aa,aaa,z或或w|w*且且w=an,n1 為字母為字母表表 上的一個(gè)言語(yǔ)。上的一個(gè)言語(yǔ)。 是一個(gè)言語(yǔ)。

12、是一個(gè)言語(yǔ)。 即即 是一個(gè)言語(yǔ)。是一個(gè)言語(yǔ)。言語(yǔ)上的運(yùn)算言語(yǔ)上的運(yùn)算z設(shè)設(shè)L是是 上的一個(gè)言語(yǔ)上的一個(gè)言語(yǔ),M是是 上的一個(gè)上的一個(gè)言語(yǔ)言語(yǔ), z言語(yǔ)言語(yǔ)L和和M的并，交，差，補(bǔ)是一個(gè)言語(yǔ)。的并，交，差，補(bǔ)是一個(gè)言語(yǔ)。 如言語(yǔ)如言語(yǔ)L和和M的并為的并為 LM，是一個(gè)言語(yǔ)，是一個(gè)言語(yǔ): 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 z言語(yǔ)言語(yǔ)L和和M的銜接是一個(gè)言語(yǔ)，記為的銜接是一個(gè)言語(yǔ)，記為 LM LM=st |sL且且 tM 如：如： L1M1 =a1,b1,y1,z1,a2,b2a9z9 z有

13、有L = L=L。 L的的n次銜接次銜接Ln= LL.L 言語(yǔ)上的運(yùn)算言語(yǔ)上的運(yùn)算z言語(yǔ)言語(yǔ)L的的 閉包記為閉包記為 L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1= Ln-1 L,n1z言語(yǔ)言語(yǔ)L的正的正 閉包記為閉包記為 L+， L+= L1 L2 L3 . L+= LL*= L*L L*= L+ z如：如： L1 =a,b,y,z M1 =1,28,9 L1M1=a,b, y,z，1,28,9 zL1M1*=a,b, y,z，1,28,9 ，aa,1a,xyz,6789st.z L1L1M1*=一切字母打頭的字母和數(shù)一切字母打頭的字母和數(shù)字符號(hào)串字符號(hào)串言語(yǔ)的描畫(huà)

14、言語(yǔ)的描畫(huà)z如何來(lái)描畫(huà)一種言語(yǔ)？如何來(lái)描畫(huà)一種言語(yǔ)？z假設(shè)言語(yǔ)是有窮的只含有有窮多個(gè)句子，假設(shè)言語(yǔ)是有窮的只含有有窮多個(gè)句子，可以將句子逐一列出來(lái)表示可以將句子逐一列出來(lái)表示z假設(shè)言語(yǔ)是無(wú)窮的，找出言語(yǔ)的有窮表示。兩假設(shè)言語(yǔ)是無(wú)窮的，找出言語(yǔ)的有窮表示。兩個(gè)途經(jīng)：個(gè)途經(jīng)： 生成方式生成方式 文法：言語(yǔ)中的每個(gè)句子可以用文法：言語(yǔ)中的每個(gè)句子可以用嚴(yán)峻定義的規(guī)那么來(lái)構(gòu)造。嚴(yán)峻定義的規(guī)那么來(lái)構(gòu)造。 識(shí)別方式自動(dòng)機(jī)：用一個(gè)過(guò)程，當(dāng)輸入的識(shí)別方式自動(dòng)機(jī)：用一個(gè)過(guò)程，當(dāng)輸入的一恣意串屬于言語(yǔ)時(shí)，該過(guò)程經(jīng)有限次計(jì)算后一恣意串屬于言語(yǔ)時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停頓并回答就會(huì)停頓并回答“是，假設(shè)不屬于，要麼

15、能是，假設(shè)不屬于，要麼能停頓并回答停頓并回答“不是，要麼永遠(yuǎn)繼續(xù)下去。不是，要麼永遠(yuǎn)繼續(xù)下去。 文法文法 數(shù)學(xué)系統(tǒng)數(shù)學(xué)系統(tǒng)z一個(gè)方式數(shù)學(xué)系統(tǒng)可由以下根本成分來(lái)描一個(gè)方式數(shù)學(xué)系統(tǒng)可由以下根本成分來(lái)描寫(xiě)：一組根本符號(hào)，一組構(gòu)成規(guī)那么，一寫(xiě)：一組根本符號(hào)，一組構(gòu)成規(guī)那么，一組公理，一組推理規(guī)那么。組公理，一組推理規(guī)那么。文法和言語(yǔ)的方式定義文法和言語(yǔ)的方式定義z文法的定義文法的定義z推導(dǎo)的定義推導(dǎo)的定義z句型、句子、言語(yǔ)的定義句型、句子、言語(yǔ)的定義文法的定義文法的定義z文法文法G定義為四元組定義為四元組VN，VT，P，SzVN ：非終結(jié)符集：非終結(jié)符集zVT ：終結(jié)符集：終結(jié)符集zP：產(chǎn)生式規(guī)那么集

16、合：產(chǎn)生式規(guī)那么集合zS：開(kāi)場(chǎng)符號(hào)：開(kāi)場(chǎng)符號(hào)zVNVT= ， SVNzV=VNVT，稱(chēng)為文法，稱(chēng)為文法G的文法符號(hào)集合的文法符號(hào)集合規(guī)那么的定義規(guī)那么的定義z規(guī)那么重寫(xiě)規(guī)那么、產(chǎn)生式或生成式，規(guī)那么重寫(xiě)規(guī)那么、產(chǎn)生式或生成式，是形如是形如或或 =的的，有序?qū)Γ行驅(qū)?，且且V+，V*。z 稱(chēng)為規(guī)那么的左部稱(chēng)為規(guī)那么的左部(或生成式的左部或生成式的左部)。z 稱(chēng)為規(guī)那么的右部稱(chēng)為規(guī)那么的右部(或生成式的右部或生成式的右部)。文法的定義文法的定義z例例3.1 文法文法G=VN，VT，P，SzVN = S , VT = 0, 1 zP= S0S1, S01 zS為開(kāi)場(chǎng)符號(hào)為開(kāi)場(chǎng)符號(hào)文法的定義文法的定義

17、z習(xí)慣上只將產(chǎn)生式寫(xiě)出。并有如下商定：習(xí)慣上只將產(chǎn)生式寫(xiě)出。并有如下商定：z第一條產(chǎn)生式的左部是開(kāi)場(chǎng)符號(hào)第一條產(chǎn)生式的左部是開(kāi)場(chǎng)符號(hào)z用尖括號(hào)括起的是非終結(jié)符，否那么為終結(jié)用尖括號(hào)括起的是非終結(jié)符，否那么為終結(jié)符。或者大寫(xiě)字母表示非終結(jié)符，小寫(xiě)字母符?；蛘叽髮?xiě)字母表示非終結(jié)符，小寫(xiě)字母表示終結(jié)符表示終結(jié)符zG可寫(xiě)成可寫(xiě)成GS，S是開(kāi)場(chǎng)符號(hào)是開(kāi)場(chǎng)符號(hào)zG：SaAb Aab AaAb A GS： Aab AaAb A SaSb 縮寫(xiě)方式縮寫(xiě)方式 GS： Aab |aAb | SaSbz留意：元符號(hào)和源符號(hào)留意：元符號(hào)和源符號(hào)例例3.2 文法文法G=VN，VT，P，SVN =標(biāo)識(shí)符，字母，數(shù)字標(biāo)識(shí)符

18、，字母，數(shù)字VT =a,b,c,x,y,z,0,1,9P= a, z 0, 9 S=推導(dǎo)的定義推導(dǎo)的定義z直接推導(dǎo)直接推導(dǎo)“z是文法是文法G的產(chǎn)生式，假設(shè)有的產(chǎn)生式，假設(shè)有v,w滿(mǎn)足：滿(mǎn)足：zv=,w= , 其中其中V*,V*z那么稱(chēng)那么稱(chēng)v直接推導(dǎo)到直接推導(dǎo)到w,記作記作 v wz 或或w直接歸約到直接歸約到vz例：例：G： S0S1， S01z S 0S1 00S11 000S111 00001111 . . . VAR;BEGIN READ()END. VAR A;BEGIN READ(A) END.推導(dǎo)的定義推導(dǎo)的定義z假設(shè)存在假設(shè)存在v w0 w1 . wn=w,(n0)z那么稱(chēng)那么

19、稱(chēng)v w，v推導(dǎo)出推導(dǎo)出w，或，或w歸約到歸約到vz假設(shè)有假設(shè)有v w，或，或v=w，z那么記為那么記為v w*文法的句型、句子的定義文法的句型、句子的定義z句型句型z有文法有文法G，假設(shè)，假設(shè)S x，那么稱(chēng)，那么稱(chēng)x是文法是文法G的句型。的句型。z句子句子z有文法有文法G，假設(shè)，假設(shè)S x，且，且xVT*，那么，那么稱(chēng)稱(chēng)x是文法是文法G的句子。的句子。z例：例：G： S0S1， S01zS 0S1 00S11 000S111 00001111*y例：例：GE：EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a表示一切能用符

20、號(hào)表示一切能用符號(hào)a，+，*，(和和)構(gòu)成的算術(shù)構(gòu)成的算術(shù)表達(dá)式表達(dá)式文法，言語(yǔ)的定義文法，言語(yǔ)的定義z由文法由文法G生成的言語(yǔ)記為生成的言語(yǔ)記為L(zhǎng)(G),它是文法它是文法G的一切句子的集合的一切句子的集合: L(G)=x|S x，其中，其中S為文法的開(kāi)場(chǎng)符為文法的開(kāi)場(chǎng)符號(hào)，且號(hào)，且x VT*z z例：例：G： S0S1， S01zL(G)=0n1n|n1*z例例3.3 文法文法GS：z1SaSBEz2SaBEz3EBBEz4aBabz5bBbbz6bEbez7eEee LG= anbnen | n1 z S a S BE (SaSBE) a aBEBE (SaBE) aabEBE ( aBa

21、b ) aabBEE ( EBBE ) aabbEE bBbb) aabbeE bEbe) aabbee eEee)G生成的每個(gè)串都在生成的每個(gè)串都在L(G)中中L(G)中的每個(gè)串確實(shí)能被中的每個(gè)串確實(shí)能被G生成生成z知言語(yǔ)描畫(huà)，寫(xiě)出文法知言語(yǔ)描畫(huà)，寫(xiě)出文法z例：假設(shè)言語(yǔ)由例：假設(shè)言語(yǔ)由0、1符號(hào)串組成，串中符號(hào)串組成，串中0和和1的個(gè)數(shù)一樣，構(gòu)造其文法。的個(gè)數(shù)一樣，構(gòu)造其文法。A 0B|1CB 1|1A|0BBC 0|0A|1CCz知文法，寫(xiě)出言語(yǔ)描畫(huà)知文法，寫(xiě)出言語(yǔ)描畫(huà)z例：例：GE：EE+T|T TT*F|F F(E)|a語(yǔ)法語(yǔ)法 SyntaxSyntax 語(yǔ)義語(yǔ)義 Semantics

22、Semantics z偶正整數(shù)的集合0,2,4,2n , z dd.0(2，4，6，8)文法的等價(jià)文法的等價(jià)z假設(shè)假設(shè)LG1=LG2，那么稱(chēng)文法，那么稱(chēng)文法G1和和G2是等價(jià)的。是等價(jià)的。z如文法如文法G1A：A0R 與與G2S：S0S1 等價(jià)等價(jià)z A01 S01z RA1文法的類(lèi)型文法的類(lèi)型z經(jīng)過(guò)對(duì)產(chǎn)生式施加不同的限制，經(jīng)過(guò)對(duì)產(chǎn)生式施加不同的限制，Chomsky將文法分為四種類(lèi)型：將文法分為四種類(lèi)型：z0型文法：對(duì)任一產(chǎn)生式型文法：對(duì)任一產(chǎn)生式，都有，都有(VNVT)+， (VNVT)*z1型文法：對(duì)任一產(chǎn)生式型文法：對(duì)任一產(chǎn)生式，都有，都有|， 僅僅僅僅 S除外除外z2型文法：對(duì)任一產(chǎn)生

23、式型文法：對(duì)任一產(chǎn)生式，都有，都有VN ， (VNVT)*z3型文法：任一產(chǎn)生式型文法：任一產(chǎn)生式的方式都為的方式都為AaB或或Aa，其中，其中AVN ，BVN ，aVT文法的類(lèi)型文法的類(lèi)型z例：例：1 1型上下文有關(guān)文法型上下文有關(guān)文法z 文法文法GSGS：SaSBESaSBEzSaBESaBEzEBBEEBBEzaBabaBabzbBbbbBbbzbEbebEbezeEeeeEee文法的類(lèi)型文法的類(lèi)型z例：例：1 1型上下文有關(guān)文法型上下文有關(guān)文法z 文法文法GSGS： SCD SCDAbbAAbbAz CaCA CaCABaaBBaaBz CbCB CbCBBbbBBbbBzADaDAD

24、aD C CzBDbDBDbD D DzAabDAabDzL(G)=ww|wa,bL(G)=ww|wa,b* * 文法的類(lèi)型文法的類(lèi)型z例：例：2 2型上下文無(wú)關(guān)文法型上下文無(wú)關(guān)文法z 文法文法GSGS：SaB|bASaB|bAzAa|aS|bAAAa|aS|bAAzBb|bS|aBBBb|bS|aBBz 文法文法GSGS：S0A|1B|0S0A|1B|0zA0A|1B|0SA0A|1B|0SzB1B|1|0B1B|1|0z文法的類(lèi)型文法的類(lèi)型z例：定義標(biāo)識(shí)符的例：定義標(biāo)識(shí)符的3 3型正規(guī)文法型正規(guī)文法z 文法文法GIGI：I lTI lTzI lI lzT lTT lTzT dTT dTzT

25、 lT lzT dT dz文法和言語(yǔ)文法和言語(yǔ)z0型文法產(chǎn)生的言語(yǔ)稱(chēng)為型文法產(chǎn)生的言語(yǔ)稱(chēng)為0型言語(yǔ)型言語(yǔ)z1型文法或上下文有關(guān)文法型文法或上下文有關(guān)文法 CSG 產(chǎn)生的產(chǎn)生的言語(yǔ)稱(chēng)為言語(yǔ)稱(chēng)為1型言語(yǔ)或上下文有關(guān)言語(yǔ)型言語(yǔ)或上下文有關(guān)言語(yǔ)CSLz2型文法或上下文無(wú)關(guān)文法型文法或上下文無(wú)關(guān)文法 CFL 產(chǎn)生的產(chǎn)生的言語(yǔ)稱(chēng)為言語(yǔ)稱(chēng)為2型言語(yǔ)或上下文無(wú)關(guān)言語(yǔ)型言語(yǔ)或上下文無(wú)關(guān)言語(yǔ) CF L z3型文法或正那么正規(guī)文法型文法或正那么正規(guī)文法 RG 產(chǎn)產(chǎn)生的言語(yǔ)稱(chēng)為生的言語(yǔ)稱(chēng)為3型言語(yǔ)正那么正規(guī)言語(yǔ)型言語(yǔ)正那么正規(guī)言語(yǔ) RL 文法和言語(yǔ)文法和言語(yǔ)z四種文法之間的關(guān)系四種文法之間的關(guān)系 是將產(chǎn)生式做進(jìn)一步是

26、將產(chǎn)生式做進(jìn)一步限制而定義的。限制而定義的。z 言語(yǔ)之間的關(guān)系依次：有不是上下文有言語(yǔ)之間的關(guān)系依次：有不是上下文有關(guān)言語(yǔ)的關(guān)言語(yǔ)的0型言語(yǔ)，有不是上下文無(wú)關(guān)言語(yǔ)型言語(yǔ)，有不是上下文無(wú)關(guān)言語(yǔ)的的1型言語(yǔ)，有不是正那么言語(yǔ)的上下文無(wú)型言語(yǔ)，有不是正那么言語(yǔ)的上下文無(wú)關(guān)言語(yǔ)。關(guān)言語(yǔ)。文法和識(shí)別系統(tǒng)文法和識(shí)別系統(tǒng)z0型文法短語(yǔ)文法的才干相當(dāng)于圖靈機(jī)，型文法短語(yǔ)文法的才干相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集，而且任何可以表征任何遞歸可枚舉集，而且任何0型型言語(yǔ)都是遞歸可枚舉的言語(yǔ)都是遞歸可枚舉的z1型文法上下文有關(guān)文法：產(chǎn)生式的方型文法上下文有關(guān)文法：產(chǎn)生式的方式為式為1A212，即只需，即只需A出

27、如今出如今1和和2的上下文中時(shí)，才允許的上下文中時(shí)，才允許取代取代A。其識(shí)。其識(shí)別系統(tǒng)是線(xiàn)性界限自動(dòng)機(jī)。別系統(tǒng)是線(xiàn)性界限自動(dòng)機(jī)。 帶帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁頭磁頭圖靈機(jī)圖靈機(jī)文法的類(lèi)型文法的類(lèi)型z2型文法上下文無(wú)關(guān)文法、型文法上下文無(wú)關(guān)文法、CFG：產(chǎn)生：產(chǎn)生式的方式為式的方式為A，取代取代A時(shí)與時(shí)與A的上下文的上下文無(wú)關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。無(wú)關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。z3型文法正規(guī)文法、右線(xiàn)性文法：產(chǎn)生型文法正規(guī)文法、右線(xiàn)性文法：產(chǎn)生的言語(yǔ)是有窮自動(dòng)機(jī)的言語(yǔ)是有窮自動(dòng)機(jī)FA所接受的集合所接受的集合

28、上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)z上下文無(wú)關(guān)文法有足夠的才干描畫(huà)現(xiàn)今程上下文無(wú)關(guān)文法有足夠的才干描畫(huà)現(xiàn)今程序設(shè)計(jì)言語(yǔ)的語(yǔ)法構(gòu)造序設(shè)計(jì)言語(yǔ)的語(yǔ)法構(gòu)造z算術(shù)表達(dá)式算術(shù)表達(dá)式z語(yǔ)句語(yǔ)句z賦值語(yǔ)句賦值語(yǔ)句z條件語(yǔ)句條件語(yǔ)句z讀語(yǔ)句讀語(yǔ)句z算術(shù)表達(dá)式上下文無(wú)關(guān)文法表示算術(shù)表達(dá)式上下文無(wú)關(guān)文法表示z文法文法G=(E, +,*,I,(,), P, Ez P: E izE E+EzE E*EzE (E)條件語(yǔ)句上下文無(wú)關(guān)文法表示條件語(yǔ)句上下文無(wú)關(guān)文法表示z ififthenthen | if | ifthenthenelse else 上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)z用于描畫(huà)上下

29、文無(wú)關(guān)文法的句型推導(dǎo)的直用于描畫(huà)上下文無(wú)關(guān)文法的句型推導(dǎo)的直觀方法觀方法 例例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的語(yǔ)法樹(shù)推導(dǎo)樹(shù)的語(yǔ)法樹(shù)推導(dǎo)樹(shù)葉子結(jié)點(diǎn)：樹(shù)中沒(méi)有子孫的結(jié)點(diǎn)。葉子結(jié)點(diǎn)：樹(shù)中沒(méi)有子孫的結(jié)點(diǎn)。從左到右讀出推導(dǎo)樹(shù)的葉子標(biāo)志，所得的句從左到右讀出推導(dǎo)樹(shù)的葉子標(biāo)志，所得的句型為推導(dǎo)樹(shù)的結(jié)果。也把該推導(dǎo)樹(shù)稱(chēng)為該句型為推導(dǎo)樹(shù)的結(jié)果。也把該推導(dǎo)樹(shù)稱(chēng)為該句型的語(yǔ)法樹(shù)。型的語(yǔ)法樹(shù)。上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)z給定文法給定文法G，對(duì)于，對(duì)于G的任何句型都能構(gòu)造與的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)推導(dǎo)樹(shù)。這棵樹(shù)滿(mǎn)足之

30、關(guān)聯(lián)的語(yǔ)法樹(shù)推導(dǎo)樹(shù)。這棵樹(shù)滿(mǎn)足以下以下4個(gè)條件：個(gè)條件：z1、每個(gè)結(jié)點(diǎn)都有一個(gè)、每個(gè)結(jié)點(diǎn)都有一個(gè)V中的符號(hào)作標(biāo)志中的符號(hào)作標(biāo)志z2、根的標(biāo)志是開(kāi)場(chǎng)符號(hào)、根的標(biāo)志是開(kāi)場(chǎng)符號(hào)Sz3、假設(shè)一結(jié)點(diǎn)、假設(shè)一結(jié)點(diǎn)n至少有一個(gè)它本人除外的至少有一個(gè)它本人除外的子孫，并且子孫，并且n有標(biāo)志有標(biāo)志A，那么，那么AVNz4、假設(shè)結(jié)點(diǎn)、假設(shè)結(jié)點(diǎn)n的直接子孫，從左到右的次的直接子孫，從左到右的次序是結(jié)點(diǎn)序是結(jié)點(diǎn)n1,n2,nk，其標(biāo)志分別為，其標(biāo)志分別為A1,A2,Ak，那么，那么AA1A2,Ak一定一定是是P中的一個(gè)產(chǎn)生式中的一個(gè)產(chǎn)生式上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)z定理：定理：G為上下文無(wú)關(guān)文法，為

31、上下文無(wú)關(guān)文法，z對(duì)于對(duì)于，有，有S ，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)z文法文法G有以有以為結(jié)果的一棵推導(dǎo)樹(shù)。為結(jié)果的一棵推導(dǎo)樹(shù)。*上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)z推導(dǎo)過(guò)程中施用產(chǎn)生式的順序推導(dǎo)過(guò)程中施用產(chǎn)生式的順序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaaz最左最右推導(dǎo)：在推導(dǎo)的任何一步最左最右推導(dǎo)：在推導(dǎo)的任何一步，其中，其中、是句型，都是對(duì)是句型，都是對(duì)中的最中的最左右非終結(jié)符進(jìn)展交換左右

32、非終結(jié)符進(jìn)展交換z最右推導(dǎo)被稱(chēng)為規(guī)范推導(dǎo)。最右推導(dǎo)被稱(chēng)為規(guī)范推導(dǎo)。z由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型z問(wèn)題：一個(gè)句型能否對(duì)應(yīng)獨(dú)一的一棵語(yǔ)法問(wèn)題：一個(gè)句型能否對(duì)應(yīng)獨(dú)一的一棵語(yǔ)法樹(shù)？樹(shù)？z例：例：GE:GE:E iE izE E E+EE+EzE E E E* *E EzE 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 的兩個(gè)不同的最左推導(dǎo)：的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E E*E+E i*E+E i*i

33、+E i*i+i推導(dǎo)推導(dǎo)2：E E*E i*E i*E+E i*i+E i*i+i二義文法二義文法z假設(shè)一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同假設(shè)一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，那么稱(chēng)這個(gè)文法是二義的。的語(yǔ)法樹(shù)，那么稱(chēng)這個(gè)文法是二義的?；蛘?，假設(shè)一個(gè)文法存在某個(gè)句子有兩個(gè)或者，假設(shè)一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左右推導(dǎo)，那么稱(chēng)這個(gè)文法不同的最左右推導(dǎo)，那么稱(chēng)這個(gè)文法是二義的。是二義的。z產(chǎn)生某上下文無(wú)關(guān)言語(yǔ)的每一個(gè)文法都是產(chǎn)生某上下文無(wú)關(guān)言語(yǔ)的每一個(gè)文法都是二義的，那么稱(chēng)此言語(yǔ)是先天二義的。二義的，那么稱(chēng)此言語(yǔ)是先天二義的。二義文法二義文法z斷定任給的一個(gè)上下文無(wú)關(guān)文法能否二義，斷定任

34、給的一個(gè)上下文無(wú)關(guān)文法能否二義，或它能否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)或它能否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)言語(yǔ)，這兩個(gè)問(wèn)題是遞歸不可解的。但可言語(yǔ)，這兩個(gè)問(wèn)題是遞歸不可解的。但可以為無(wú)二義性尋覓一組充分條件。以為無(wú)二義性尋覓一組充分條件。z二義文法改造為無(wú)二義文法二義文法改造為無(wú)二義文法zGE: E i GE：E T|E+Tz E E+E T F|T*Fz E E*E F E|iz E (E) 規(guī)定優(yōu)先順序和結(jié)合律規(guī)定優(yōu)先順序和結(jié)合律句型的分析句型的分析z句型分析就是識(shí)別一個(gè)符號(hào)串能否為某文句型分析就是識(shí)別一個(gè)符號(hào)串能否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。z在言

35、語(yǔ)的編譯實(shí)現(xiàn)中，把完成句型分析的在言語(yǔ)的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱(chēng)為分析程序或識(shí)別程序。分析算法程序稱(chēng)為分析程序或識(shí)別程序。分析算法又稱(chēng)識(shí)別算法。又稱(chēng)識(shí)別算法。z從左到右的分析算法，即總是從左到右地從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)。左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)。句型的分析句型的分析z分析算法可分為：分析算法可分為：z自上而下分析法：自上而下分析法：從文法的開(kāi)場(chǎng)符號(hào)出發(fā)，反復(fù)運(yùn)用各種產(chǎn)從文法的開(kāi)場(chǎng)符號(hào)出發(fā)，反復(fù)運(yùn)用各種產(chǎn)生式，尋覓與輸入符號(hào)匹配的推導(dǎo)。生式，尋覓與輸入符號(hào)匹

36、配的推導(dǎo)。z自下而上分析法：自下而上分析法：從輸入符號(hào)串開(kāi)場(chǎng)，逐漸進(jìn)展歸約，直至從輸入符號(hào)串開(kāi)場(chǎng)，逐漸進(jìn)展歸約，直至歸約到文法的開(kāi)場(chǎng)符號(hào)。歸約到文法的開(kāi)場(chǎng)符號(hào)。z兩種方法反映了兩種不同的語(yǔ)法樹(shù)的構(gòu)造兩種方法反映了兩種不同的語(yǔ)法樹(shù)的構(gòu)造過(guò)程過(guò)程自上而下的語(yǔ)法分析自上而下的語(yǔ)法分析z例：文法例：文法G：S cAd A ab A a識(shí)別輸入串識(shí)別輸入串w=cabd能否該文法的句子能否該文法的句子SSScAdcAd a b推導(dǎo)過(guò)程：推導(dǎo)過(guò)程：S cAd cabd自下而上的語(yǔ)法分析自下而上的語(yǔ)法分析z例：文法例：文法G：S cAd A ab A a識(shí)別輸入串識(shí)別輸入串w=cabd能否該文法的句子能否該文

37、法的句子SAA c a b d c a b d c a b d 規(guī)約過(guò)程：規(guī)約過(guò)程：S cAd cabd句型分析的有關(guān)問(wèn)題句型分析的有關(guān)問(wèn)題1如何選擇運(yùn)用哪個(gè)產(chǎn)生式進(jìn)展推導(dǎo)？如何選擇運(yùn)用哪個(gè)產(chǎn)生式進(jìn)展推導(dǎo)？假定要被代換的最左非終結(jié)符號(hào)是假定要被代換的最左非終結(jié)符號(hào)是V，且有，且有n條規(guī)那么：條規(guī)那么：VA1|A2|An，那么如何確，那么如何確定用哪個(gè)右部去替代定用哪個(gè)右部去替代V？2如何識(shí)別可歸約的串？如何識(shí)別可歸約的串？在自下而上的分析方法中，在分析程序義在自下而上的分析方法中，在分析程序義務(wù)的每一步，都是從當(dāng)前串中選擇一個(gè)子務(wù)的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，

38、該子串串，將它歸約到某個(gè)非終結(jié)符號(hào)，該子串稱(chēng)為稱(chēng)為“可歸約串可歸約串句型分析句型分析z短語(yǔ)、直接短語(yǔ)、句柄的定義：文法短語(yǔ)、直接短語(yǔ)、句柄的定義：文法GS，zS A且且A b那么稱(chēng)那么稱(chēng)b是句型是句型b相對(duì)于相對(duì)于非終結(jié)符非終結(jié)符A的短語(yǔ)。假設(shè)有的短語(yǔ)。假設(shè)有A b那么稱(chēng)那么稱(chēng)b是句型是句型b相對(duì)于該規(guī)那么相對(duì)于該規(guī)那么A b的直接短的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的句柄。的句柄。*句型分析句型分析 E F T T F F i1 * i2 + i3短語(yǔ)：短語(yǔ)：直接短語(yǔ)：直接短語(yǔ)：句柄：句柄：GEGE：EE+T|TEE+T|T TT TT* *F|

39、FF|F F(E)|i F(E)|i句型：句型：i i* *i+ii+i有關(guān)文法適用中的一些闡明有關(guān)文法適用中的一些闡明z有關(guān)文法的適用限制有關(guān)文法的適用限制z上下文無(wú)關(guān)文法中的上下文無(wú)關(guān)文法中的規(guī)那么規(guī)那么有關(guān)文法的適用限制有關(guān)文法的適用限制z文法中不得含有有害規(guī)那么和多余規(guī)那么文法中不得含有有害規(guī)那么和多余規(guī)那么z有害規(guī)那么：形如有害規(guī)那么：形如UU的產(chǎn)生式。會(huì)引起的產(chǎn)生式。會(huì)引起文法的二義性文法的二義性z多余規(guī)那么：指文法中任何句子的推導(dǎo)都多余規(guī)那么：指文法中任何句子的推導(dǎo)都不會(huì)用到的規(guī)那么不會(huì)用到的規(guī)那么z1文法中某些非終結(jié)符不在任何規(guī)那么的文法中某些非終結(jié)符不在任何規(guī)那么的右部出現(xiàn)，

40、該非終結(jié)符稱(chēng)為不可到達(dá)右部出現(xiàn)，該非終結(jié)符稱(chēng)為不可到達(dá)z2文法中某些非終結(jié)符，由它不能推出終文法中某些非終結(jié)符，由它不能推出終結(jié)符號(hào)串來(lái)，稱(chēng)為不可終止的結(jié)符號(hào)串來(lái)，稱(chēng)為不可終止的有關(guān)文法的適用限制有關(guān)文法的適用限制z對(duì)于文法對(duì)于文法GS，為了保證任一非終結(jié)符，為了保證任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn)，必需滿(mǎn)足如下兩個(gè)條在句子推導(dǎo)中出現(xiàn)，必需滿(mǎn)足如下兩個(gè)條件：件：1A必需在某句型中出現(xiàn)。必需在某句型中出現(xiàn)。2必需能從必需能從A推出終結(jié)符號(hào)串推出終結(jié)符號(hào)串t來(lái)。來(lái)。 即即1文法文法GS，對(duì)，對(duì) 某兩個(gè)符號(hào)串某兩個(gè)符號(hào)串和和： S A 2A t ,tVT*化簡(jiǎn)文法化簡(jiǎn)文法z例：例：GS z1) SBe

41、 SBez2) BCe BAfz3) BAf AAe 4) AAe Aez5) Ae 6) CCfz7) Df上下文無(wú)關(guān)文法中的上下文無(wú)關(guān)文法中的規(guī)那么規(guī)那么z具有方式具有方式A的規(guī)那么稱(chēng)為的規(guī)那么稱(chēng)為規(guī)那么，其中規(guī)那么，其中AVNz某些著作和講義中限制這種規(guī)那么的出現(xiàn)。某些著作和講義中限制這種規(guī)那么的出現(xiàn)。由于由于規(guī)那么會(huì)使有關(guān)文法的一些討論和證規(guī)那么會(huì)使有關(guān)文法的一些討論和證明變得復(fù)雜明變得復(fù)雜z兩種定義的獨(dú)一差別是兩種定義的獨(dú)一差別是句子在不在言語(yǔ)中。句子在不在言語(yǔ)中。上下文無(wú)關(guān)文法中的上下文無(wú)關(guān)文法中的規(guī)那么規(guī)那么z假設(shè)言語(yǔ)假設(shè)言語(yǔ)L有一個(gè)有窮的描畫(huà)，那么有一個(gè)有窮的描畫(huà)，那么L也同樣

42、有一個(gè)有窮描畫(huà)。并且可以證明，也同樣有一個(gè)有窮描畫(huà)。并且可以證明，假設(shè)假設(shè)L是上下文有關(guān)言語(yǔ)、上下文無(wú)關(guān)言語(yǔ)是上下文有關(guān)言語(yǔ)、上下文無(wú)關(guān)言語(yǔ)或正規(guī)言語(yǔ)，那么或正規(guī)言語(yǔ)，那么L和和L-分別是上分別是上下文有關(guān)言語(yǔ)、上下文無(wú)關(guān)言語(yǔ)和正規(guī)言下文有關(guān)言語(yǔ)、上下文無(wú)關(guān)言語(yǔ)和正規(guī)言語(yǔ)語(yǔ)上下文無(wú)關(guān)文法中的上下文無(wú)關(guān)文法中的規(guī)那么規(guī)那么z定理定理3.1 3.1 文法文法G G，任一，任一P P中的產(chǎn)生式中的產(chǎn)生式AA，都有都有AVNAVN，(VN VT)(VN VT)* *,(,(即即可以為可以為)，那么，那么L(G)L(G)也能這樣一種文法產(chǎn)生，任也能這樣一種文法產(chǎn)生，任一產(chǎn)生式一產(chǎn)生式AA，只需如下兩種方

43、式：，只需如下兩種方式： AVN AVN， (VN VT)+,( (VN VT)+,(即即)或者或者 S S且且 S S不出如今任何產(chǎn)生式右邊不出如今任何產(chǎn)生式右邊上下文無(wú)關(guān)文法中的上下文無(wú)關(guān)文法中的規(guī)那么規(guī)那么z定理定理3.23.2G G是上下文有關(guān)文法，那么存在另一個(gè)上下是上下文有關(guān)文法，那么存在另一個(gè)上下文有關(guān)文法文有關(guān)文法G1G1，L(G)=L(G1)L(G)=L(G1)，且，且G1G1的開(kāi)場(chǎng)的開(kāi)場(chǎng)符號(hào)不出如今符號(hào)不出如今G1G1的任何產(chǎn)生式的右邊。的任何產(chǎn)生式的右邊。假設(shè)假設(shè)G G為上下文無(wú)關(guān)文法或正規(guī)文法，類(lèi)似為上下文無(wú)關(guān)文法或正規(guī)文法，類(lèi)似結(jié)論成立。結(jié)論成立。 有關(guān)文法的一些關(guān)系z(mì)普通來(lái)說(shuō)，一個(gè)集合上的二目關(guān)系就是某一性質(zhì)，