




已閱讀5頁(yè),還剩13頁(yè)未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
語(yǔ)言與計(jì)算理論導(dǎo)引 上下文無(wú)關(guān)文法第三部分 上下文無(wú)關(guān)語(yǔ)言和下推自動(dòng)機(jī)前面介紹的有限自動(dòng)機(jī)是計(jì)算的初級(jí)模型,它所接受的正規(guī)語(yǔ)言不太關(guān)心字符串自身的結(jié)構(gòu)。上下文無(wú)關(guān)文法(CFL)是一種簡(jiǎn)單的描述語(yǔ)法規(guī)則的遞歸方法,語(yǔ)言中的字符串由這些規(guī)則產(chǎn)生。所有的正規(guī)語(yǔ)言都能用上下文無(wú)關(guān)文法描述,它也可以描述非正規(guī)語(yǔ)言。上下文無(wú)關(guān)文法描述的語(yǔ)法規(guī)則更復(fù)雜多變,可以在相當(dāng)大的程度上,描述高級(jí)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法和其他一些形式語(yǔ)言。類(lèi)似正則語(yǔ)言對(duì)應(yīng)的抽象機(jī)模型是有限自動(dòng)機(jī),CFL也有對(duì)應(yīng)的抽象機(jī)模型。CFL對(duì)應(yīng)的計(jì)算模型是在有限自動(dòng)機(jī)的基礎(chǔ)上增加存儲(chǔ)空間得到,并被設(shè)想成無(wú)限空間(對(duì)應(yīng)有限自動(dòng)機(jī)的有限空間),采用了一種簡(jiǎn)單的管理模式,棧(stack),這種新的計(jì)算模型(或抽象機(jī))稱(chēng)為下推自動(dòng)機(jī)(pushdown automata),下推是棧最典型的操作。有必要在下推自動(dòng)機(jī)中保留非確定性,確定型下推自動(dòng)機(jī)不能接受所有的CFL,但給定一個(gè)CFG,容易構(gòu)造一個(gè)相應(yīng)的非確定型下推自動(dòng)機(jī),它在識(shí)別字符串過(guò)程中的移動(dòng)模擬了文法的推導(dǎo)過(guò)程,這個(gè)過(guò)程稱(chēng)為分析(parse)。分析不是一定需要下推自動(dòng)機(jī)來(lái)完成。CFL仍然不夠通用,不能包括所有有意義的、或有用的形式語(yǔ)言。采用類(lèi)似第五章的技術(shù),我們將給出一些不是CFL的簡(jiǎn)單例子,這些技術(shù)也用于解決與CFL相關(guān)的判定問(wèn)題。1陶曉鵬 Copyright 2003語(yǔ)言與計(jì)算理論導(dǎo)引 上下文無(wú)關(guān)文法6 上下文無(wú)關(guān)文法6.1 上下文無(wú)關(guān)文法的定義為了描述我們?cè)诘诙糠挚疾斓母鞣N語(yǔ)言,包括一些非正則語(yǔ)言,我們引入一種語(yǔ)言的遞歸定義方法,稱(chēng)為文法。文法與我們熟悉的語(yǔ)言的語(yǔ)法描述相近,是描述語(yǔ)言和分析語(yǔ)言的有力工具。問(wèn)題:文法的形式化定義似乎可以模仿有限自動(dòng)機(jī),比如5元組或6元組之類(lèi)。例子6.1 正如我們?cè)诶?.16中所見(jiàn),字母表a, b上的回文語(yǔ)言pal可以用下面的遞歸方法描述:1. L, a, bpal2. 對(duì)每個(gè)Spal,aSa和bSb也屬于pal3. pal中不包含其他字符串如果將上面的符號(hào)S看成一個(gè)變量,代表了所有我們希望計(jì)算(比如某種遞歸算法)的pal的元素,那么上面的規(guī)則1和規(guī)則2可以非正式地重新表述如下:1. S的值可以是L, a, b2. 每個(gè)S可以寫(xiě)成aSa或bSb的形式如果我們用表示“可以取值為”,則可以寫(xiě)出下面的式子:SaSaabSbaabLba=abba上面的產(chǎn)生過(guò)程可以總結(jié)成下面的兩組產(chǎn)生式(或稱(chēng)規(guī)則):Sa | b | LSaSa | bSb符號(hào)“|”表示“或”的含義。上式的含義是aSa或bSb,而不是a或b,即連接運(yùn)算的優(yōu)先級(jí)高于“|”。我們使用的這套術(shù)語(yǔ)中,小寫(xiě)字母a和b表示終結(jié)符,大寫(xiě)字母S表示非終結(jié)符,或稱(chēng)變量??偣灿?條規(guī)則,或產(chǎn)生式(production)。符號(hào)S是非終結(jié)符,也是起始終結(jié)符,即我們生成字符串的起始符號(hào)是S,然后不斷利用規(guī)則替換符號(hào)串中的非終結(jié)符,直到最終得到一個(gè)不含非終結(jié)符的符號(hào)串,就生成了規(guī)則所定義的語(yǔ)言的一個(gè)字符串。例子2中的產(chǎn)生式具有除起始符S外的多個(gè)非終結(jié)符,我們?cè)O(shè)想S表示了語(yǔ)言中任意的字符串,其他非終結(jié)符表示了其他輔助性的字符串類(lèi)型,他們可用來(lái)方便地生成S表示的字符串。例子6.2 我們要構(gòu)造一個(gè)生成所有在字母表a, b上的非回文字符串的文法,那樣的字符串可以描述如下:從字符串的兩端開(kāi)始比較,也許能夠發(fā)現(xiàn)一些相同的字符對(duì),但最終能夠發(fā)現(xiàn)一對(duì)不同的字符。對(duì)于前一種情況,我們可以借用回文語(yǔ)言的產(chǎn)生式:SaSa | bSb如果加入產(chǎn)生式Sa | b | L則這種左右匹配的形式將體現(xiàn)在整個(gè)字符串上,為了中斷這種左右匹配的情況,即體現(xiàn)上面提到的第二種情況,我們引入新的非終結(jié)符,比如D,表示那些左右兩個(gè)端點(diǎn)上的字符不同的字符串。且所有符合D的字符串也符合S,因此有SD。非終結(jié)符的定義比較簡(jiǎn)單,它唯一的條件是左右兩個(gè)端點(diǎn)的字符不相同,中間的字符串可以是任意的,我們用非終結(jié)符A表示任意的字符串,則有DaAb | bAa。A表示任意的字符串,因此A的產(chǎn)生式更簡(jiǎn)單了,不用添加新的非終結(jié)符來(lái)簡(jiǎn)化問(wèn)題,它的產(chǎn)生式是,AL | aA | bA。我們把上面三個(gè)非終結(jié)符的產(chǎn)生式寫(xiě)在一起,就得到了描述所規(guī)定語(yǔ)言的產(chǎn)生式集:SaSa | bSb | DDaAb | bAaAL | aA | bA因此一個(gè)完整的非回文字符串“abbaaba”的產(chǎn)生過(guò)程是,SaSaabSbaabDbaabbAabaabbaAabaabbaLabaabbaaba定義6.1 上下文無(wú)關(guān)文法(context-free grammar, CFG)是一個(gè)4元組G=(V, , S, P),其中,V和是不相交的有限集,SV,P是一組有限的產(chǎn)生式規(guī)則,形如Aa,其中AV,且a(V)*。V的元素稱(chēng)為非終結(jié)符(或變量),的元素稱(chēng)為終結(jié)符,S是一個(gè)特殊的非終結(jié)符,稱(chēng)為起始符,P的元素稱(chēng)為語(yǔ)法規(guī)則,或產(chǎn)生式。設(shè)G=(V, , S, P)是一個(gè)CFG,我們將符號(hào)保留給P的產(chǎn)生式專(zhuān)用,符號(hào)G用于表示字符串的產(chǎn)生過(guò)程的每一步,如aGb表示字符串b能夠通過(guò)替換a中的某些變量(根據(jù)P定義的產(chǎn)生式來(lái)替換)得到,即如果有a=a1Aa2且AgP,則b=a1ga2。這里能夠看到,我們命名為上下文無(wú)關(guān)(context-free)的含義,即我們?cè)诶卯a(chǎn)生式規(guī)則,用一組符號(hào)替換某個(gè)非終結(jié)符時(shí),與非終結(jié)符的上下文無(wú)關(guān)(此處,A的替換與a1和a2無(wú)關(guān)),替換是無(wú)限制的。在沒(méi)有多個(gè)文法出現(xiàn),很清楚用到文法G是什么的情況下,推導(dǎo)符號(hào)G可以簡(jiǎn)寫(xiě)成。多步的推導(dǎo)可以寫(xiě)成*G,即如果存在一組符號(hào)串,a=a0、a1、ak=b,每個(gè)后者都是前者的直接推導(dǎo),則稱(chēng)為a可以多步推導(dǎo)出b,記為a*Gb,簡(jiǎn)寫(xiě)成a*b。定義6.2 G=(V, , S, P)是一個(gè)CFG,則G產(chǎn)生的語(yǔ)言是所有可由G產(chǎn)生的字符串組成的集合,即L(G)=x* | S*Gx。一個(gè)語(yǔ)言L(fǎng)是上下文無(wú)關(guān)語(yǔ)言(context-free language, CFL),當(dāng)且僅當(dāng)存在一個(gè)CFG G,使得L=L(G)。此處可以把文法設(shè)想成類(lèi)似自動(dòng)機(jī)的抽象模型,則一個(gè)語(yǔ)言L(fǎng)是CFL當(dāng)且僅當(dāng)存在一個(gè)CFG G接受它(或識(shí)別它),類(lèi)似前面正則語(yǔ)言與有限自動(dòng)機(jī)的關(guān)系,接受(或識(shí)別)的含義是兩方面的,一方面凡是L中的字符串都能由G產(chǎn)生,另一方面,凡是不屬于L的字符串都不能由G產(chǎn)生。前面的例子,能夠比較容易地說(shuō)明這兩方面的限制,下面的例子則不是很明顯。例子6.3 考慮語(yǔ)言L(fǎng)=x0, 1* | n0(x)=n1(x),其中ni(x)表示數(shù)字i在x中的出現(xiàn)次數(shù)(即含有相同數(shù)目0和1的語(yǔ)言)。寫(xiě)出生成L的CFG。分析:既然CFG的本質(zhì)是一個(gè)遞歸定義,那么類(lèi)似例子6.1,我們可以先發(fā)現(xiàn)歸納基礎(chǔ),然后找到歸納推理。顯然LL,另外如果存在一個(gè)字符串xL,那么得到更長(zhǎng)的屬于L的字符串的兩個(gè)方法是,0x1和1x0,即分別在兩端添加相同數(shù)量的0和1。(當(dāng)然,還有很多生成方法,比如x01,x10,或在x中插入相同數(shù)量的0和1),這樣得到三個(gè)產(chǎn)生式:SL | 0S1 | 1S0顯然,還遺漏了一些字符串,如0110。我們注意到L中任意兩個(gè)元素的連接仍然屬于L,因此可以增加一個(gè)產(chǎn)生式,SSS。與前面的三個(gè)產(chǎn)生式合并,我們得到一個(gè)CFG G如下,SL | 0S1 | 1S0 | SS顯然G產(chǎn)生的字符串都滿(mǎn)足0和1數(shù)目相等這個(gè)條件,即L(G)L,現(xiàn)在只要證明LL(G)。令d(x)=n0(x)-n1(x)。則字符串xL,當(dāng)且僅當(dāng)d(x)=0。因此只需證明每個(gè)滿(mǎn)足d(x)=0的x,都有xL(G)。我們用數(shù)學(xué)歸納法來(lái)證明LL(G)。歸納對(duì)象是字符串的長(zhǎng)度|x|。1. 歸納基礎(chǔ),|x|=0且d(x)=0,則xL(G),這是顯然的,因?yàn)榇藭r(shí)x=L,而L可以由產(chǎn)生式SL得到。2. 歸納推理,設(shè)k=0,每個(gè)滿(mǎn)足|y|=k,d(y)=0的字符串y都屬于L(G)。要證明每個(gè)長(zhǎng)度等于k+1且d(x)=0的字符串x也屬于L(G)。分情況討論如下:a) 如果x以0開(kāi)始,以1結(jié)尾,則可以寫(xiě)成x=0y1,且d(y)=0,根據(jù)歸納假設(shè)yL(G),即存在一組推導(dǎo),S*Gy。因此對(duì)于x,存在推導(dǎo),S0S1*0y1x。b) 如果x以1開(kāi)始,以0結(jié)尾,類(lèi)似a)的處理,能夠得到從S到x的推導(dǎo)。c) 如果x以0開(kāi)始,且以0結(jié)尾。則x的長(zhǎng)度至少為2,設(shè)x=0y0?,F(xiàn)在考察x的所有前綴z的d(z),其中d(0)=1,d(0y)=d(0y0)-d(0)=-1,而d(z)隨著z的長(zhǎng)度增1,至多增加1或減少1,而當(dāng)前綴從0變化到0y時(shí),d(z)從1變化到-1,因此存在某個(gè)長(zhǎng)于0短于0y的前綴z,使得d(z)=0,則x=zw,顯然d(w)=0,由于z、w的長(zhǎng)度都0的x都能由G0產(chǎn)生,對(duì)x的長(zhǎng)度應(yīng)用數(shù)學(xué)歸納法。1. 歸納基礎(chǔ),顯然|x|=1且d(x)0時(shí),即x=0,x可由S0推導(dǎo),屬于L(G0)。2. 歸納推理,設(shè)k=0,對(duì)每個(gè)|x|0的x都屬于L(G0),要證明每個(gè)|x|0的x也屬于L(G0)。分情況討論,此處僅討論x=0y0的情況(即以0開(kāi)始和結(jié)尾的情況),a) x僅由0組成,易證。b) x至少含有一個(gè)1。則x=w1z,現(xiàn)在證明d(w)0且d(z)0。設(shè)x含有n個(gè)1,n=1,對(duì)每個(gè)1=i=n,令wi是x的前綴,緊接wi的下一個(gè)字符就是第i個(gè)1,則x=wi1zi。分兩種情況1)不存在wi,使得d(wi)0,則d(wn)0,令w=wn,z=zn,顯然d(z)0,得證;2)存在一個(gè)wi,使得d(wi)=0,設(shè)i=m是第一個(gè)d(wi)0,且d(wm-1)=10,令w=wm-1,z=zm-1,易證d(zm-1)0,因此得證。其他兩種情況,x以1開(kāi)始,以1結(jié)尾證明略。類(lèi)似方法能夠得到生成L1的產(chǎn)生式,我們用A表示生成L0的產(chǎn)生式,B表示生成L1的產(chǎn)生式,那么生成語(yǔ)言L(fǎng)的全部文法是:SA | BA0 | 0A | 1AA | AA1 | A1AB1 | 1B | 0BB | BB0 | B0B注意其中的第一個(gè)規(guī)則,它恰如其分地表示了合集的含義。6.2 更多地例子,包括一些熟悉的語(yǔ)言例子6.5 我們前面已經(jīng)提到了在計(jì)算機(jī)科學(xué)和其他領(lǐng)域應(yīng)用很廣泛的書(shū)寫(xiě)代數(shù)表達(dá)式的語(yǔ)言。一般地,我們?cè)试S任意的標(biāo)識(shí)符和數(shù)字常數(shù)出現(xiàn)在表達(dá)式中,為了簡(jiǎn)化問(wèn)題,我們規(guī)定只有一個(gè)標(biāo)識(shí)符(字母a)、4種兩項(xiàng)運(yùn)算符(+、-、*、/)和左括號(hào)、右括號(hào)。我們用變量A表示這個(gè)簡(jiǎn)單的表達(dá)式語(yǔ)言。它可以嵌入到復(fù)雜的表達(dá)式語(yǔ)言中。一個(gè)容易發(fā)現(xiàn)的遞歸現(xiàn)象是,如果存在兩個(gè)表達(dá)式,那么可以利用運(yùn)算符和括號(hào),連接它們構(gòu)成新的表達(dá)式。顯然,除了單個(gè)標(biāo)識(shí)符a,其他表達(dá)式都是通過(guò)這個(gè)遞歸過(guò)程構(gòu)造的,因此我們得到下面的文法:SS+S | S-S | S*S | S/S | (S) | a表達(dá)式a+(a*a)/a-a的推導(dǎo)過(guò)程如下,SS-SS+S-Sa+S-Sa+S/S-Sa+(S)/S-Sa+(S*S)/S-Sa+(a*S)/S-S.a+(a*a)/a-a還存在其他一些推導(dǎo)過(guò)程,如SS/SS+S/Sa+S/Sa+(S)/Sa+(S*S)/Sa+(a*S)/Sa+(a*a)/Sa+(a*a)/S-Sa+(a*a)/a-Sa+(a*a)/a-a顯然,第一種推導(dǎo)比第二種更自然,它符合了通常的運(yùn)算符的優(yōu)先級(jí)和計(jì)算次序。比如,上述表達(dá)式通常的計(jì)算次序如下:1. 計(jì)算a*a,記為A2. 計(jì)算A/a,記為B3. 計(jì)算a+B,記為C4. 計(jì)算C-a盡管第二種推導(dǎo)不符合通常的表達(dá)式結(jié)構(gòu),或表達(dá)式語(yǔ)義,但整個(gè)推導(dǎo)是符合文法規(guī)定的,是一個(gè)合法的推導(dǎo)。一個(gè)可能的結(jié)論是本例給出的CFG不是最合理的,它沒(méi)有體現(xiàn)出運(yùn)算符和括號(hào)的優(yōu)先級(jí),另外好的CFG對(duì)每個(gè)字符串僅僅提供一種推導(dǎo)過(guò)程(如果忽略次序不同的一些簡(jiǎn)單替換),在6.4節(jié)我們將回到這個(gè)問(wèn)題,它稱(chēng)為CFG的歧義。例子6.6 上面的例子類(lèi)似例子3.5和3.6,僅僅描述了程序設(shè)計(jì)語(yǔ)言(比如C和Pascal)的某個(gè)部分,本例將顯示,CFG可用來(lái)描述程序設(shè)計(jì)語(yǔ)言的整個(gè)語(yǔ)法結(jié)構(gòu)。C語(yǔ)言有兩大類(lèi)語(yǔ)法結(jié)構(gòu),和。包括條件聲明()和循環(huán)聲明()等等,因此有,. | | | .if () for (; ; ) .可以類(lèi)似構(gòu)造多個(gè)聲明連接而成的復(fù)合聲明,以及等等。例子6.7 高級(jí)程序設(shè)計(jì)語(yǔ)言的一個(gè)大的優(yōu)點(diǎn)是寫(xiě)出的程序與英文陳述很接近,既然我們可以用CFG去描述高級(jí)程序設(shè)計(jì)語(yǔ)言,那么可不可以用來(lái)描述英語(yǔ)呢?對(duì)于一些簡(jiǎn)單的英語(yǔ)語(yǔ)法,容易找到它的CFG,比如最基本、最典型的英語(yǔ)陳述句的結(jié)構(gòu)是, ,因此可以構(gòu)造出如下的產(chǎn)生式, 可以進(jìn)一步構(gòu)造生成右部三個(gè)非終結(jié)符的產(chǎn)生式。寫(xiě)出一套合理的、具有廣泛性、符合常用語(yǔ)法習(xí)慣的英語(yǔ)規(guī)則并不困難,且規(guī)則的數(shù)目也可以不是很多。困難的地方是防止產(chǎn)生不合語(yǔ)法,或合乎語(yǔ)法,然而不合語(yǔ)義,沒(méi)有人會(huì)使用的英語(yǔ)句子。下面的產(chǎn)生式就是一個(gè)例子, John | Janereminded | himself | herself上面文法能夠產(chǎn)生很多不“正確”的英語(yǔ)句子,如“John reminded herself”,“Jane reminded himself”??梢酝ㄟ^(guò)增加文法的復(fù)雜性(更多的非終結(jié)符和更多的產(chǎn)生式)來(lái)消除這種不正確的推導(dǎo),比如修改產(chǎn)生式為, 而對(duì)于例如“Jane reminded Jane”還需要其他消除方法,因?yàn)榫渥印癑ane reminded John”是一個(gè)好的英語(yǔ)句子。要想?yún)^(qū)別這兩個(gè)句子,需要上下文信息,因此本章討論的CFG無(wú)法很深入、精細(xì)地刻畫(huà)自然語(yǔ)言的一些細(xì)微特征。6.3 CFL的合并、連接和Kleene*運(yùn)算例子6.4我們構(gòu)造了一個(gè)CFG,它生成的語(yǔ)言是另外兩種語(yǔ)言的合集,而且找到了另外兩種語(yǔ)言對(duì)應(yīng)的CFG。例子6.4揭示的方法和處理連接和Kleene*運(yùn)算的相應(yīng)方法構(gòu)成了下面定理的基礎(chǔ)。定理6.1 L1和L2是兩個(gè)CFL,則語(yǔ)言L(fǎng)1L2、L1L2和L1*也是CFL。證明:我們用構(gòu)造法證明。假設(shè)生成L1和L2的文法分別是G1=(V1, , S1, P1)和G2=(V2, , S2, P2),以此為基礎(chǔ),分別構(gòu)造生成上面三種新語(yǔ)言的CFG。首先假設(shè)V1V2=f(否則可以通過(guò)改名來(lái)到達(dá)目的),設(shè)生成L1L2的文法Gu=(Vu, , Su, Pu),其中,Su是不屬于V1和V2的新增非終結(jié)符,Vu=V1V2Su,Pu=P1P2SuS1 | S2。現(xiàn)在證明L(Gu)=L1L2。一方面,任取xL1=L(G1),則S1*x,又由于存在產(chǎn)生式SuS1,因此Su*x。類(lèi)似地,任取xL1,也有S*x。因此L1L2L(Gu)。另一方面,任取xL(Gu),則存在S*x,則存在S1*x或S2*x,因此L(Gu)L1L2。得證。類(lèi)似處理連接運(yùn)算,文法Gc=(Vc, , Sc, Pc),其中Sc是不屬于V1和V2的新增非終結(jié)符。定義Vc=V1V2Sc,Pc=P1P2ScS1S2。任給xL1L2,則x=x1x2,x1L1,x2L2。因此有SS1S2*x1S2*x1x2=x,即L1L2L(Gc)。任給xL(Gc),即S*x,則有S1S2*x,由于V1和V2不相交,則存在x1x2=x,滿(mǎn)足S1*x1,S2*x2,因此L(Gc)L1L2。文法G*=(V, , S, P)生成語(yǔ)言L(fǎng)1*,其中,S是不屬于V的新增非終結(jié)符。語(yǔ)言L(fǎng)1*所含字符串x的形式是x=x1x2.xk,其中每個(gè)xiL1,如果能夠S連續(xù)地產(chǎn)生k個(gè)S1,則S能夠推導(dǎo)出x,因此得到下面的產(chǎn)生式,SS1S | L,而P=P1SS1S | L。顯然,L1*L(G1*)。任給xL(G1*),則存在S*x,而S推導(dǎo)的第一步一定是SS1k,因此xL(G1)kL(G1)*。得證。下面的例子說(shuō)明了證明的第一步消除V1和V2中的同名是很重要的。比如有兩個(gè)CFG如下:S1XA, Xc, AaS2XB, Xd, Bb此處非終結(jié)符X出現(xiàn)在兩個(gè)文法中,如果不改名將帶來(lái)混亂。如SS1XAdAda,而事實(shí)上S1無(wú)法推導(dǎo)出da。推論6.1 每個(gè)正則語(yǔ)言都是CFL。證明:根據(jù)正則語(yǔ)言的遞歸定義(定義3.1),每個(gè)正則語(yǔ)言是以三種簡(jiǎn)單的字符(f、L、a)為基礎(chǔ),多次施加三種運(yùn)算(合并、連接、Kleeen*)得到。顯然三種簡(jiǎn)單的字符組成的語(yǔ)言是CFL,又根據(jù)定理6.1,三種運(yùn)算保持了CFL的性質(zhì),因此根據(jù)結(jié)構(gòu)歸納法,命題得證。例子6.8 語(yǔ)言L(fǎng)是正則表達(dá)式,(011+1)*(01)*,表示的正則語(yǔ)言,寫(xiě)出它對(duì)應(yīng)的CFG。分析:定理6.1的證明過(guò)程給出了發(fā)現(xiàn)一個(gè)CFL的CFG的方法。分別考慮(011+1)*和(01)*。而(011+1)*可進(jìn)一步轉(zhuǎn)化成考慮(011+1),得到A011 | 1,然后加上Kleene*運(yùn)算,得到,BAB | L類(lèi)似地,對(duì)應(yīng)正則表達(dá)式(01)*的產(chǎn)生式是,CDC | L, D01最后應(yīng)用連接運(yùn)算,得到語(yǔ)言L(fǎng)對(duì)應(yīng)的CFG是SBCBAB | LA011 | 1CDC | LD01最后引入的符號(hào)S是非終結(jié)符,構(gòu)造過(guò)程中引入的符號(hào)是輔助非終結(jié)符。例子6.9 語(yǔ)言L(fǎng)=0i1j0k | ji+k的CFG。分析:一個(gè)直觀的觀察是L的每個(gè)字符串都是三部分連接而成的:0i、1j、0k。因此似乎可以分別構(gòu)造三部分語(yǔ)言的CFG,然后通過(guò)連接運(yùn)算構(gòu)造整個(gè)語(yǔ)言的CFG。這種方法是錯(cuò)誤的,因?yàn)楸纠Z(yǔ)言的三部分是相互關(guān)聯(lián)的,而不是相互獨(dú)立的,定理6.1揭示的方法僅僅用在相互獨(dú)立的兩個(gè)CFG之間的運(yùn)算??尚械姆椒ㄊ牵瑢⒈纠芯哂嘘P(guān)系的參數(shù)i、j、k轉(zhuǎn)換成相互無(wú)關(guān)的參數(shù)。由于ji+k,不妨令j=i+k+m,m0。則0i1j0k=0i1i1m1k0k。此處的三個(gè)參數(shù)i、m、k相互獨(dú)立,因此語(yǔ)言L(fǎng)=L1L2L3,其中,L1=0i1i | i=0L2=1m | m0L3=1k0k | k=0先分別構(gòu)造語(yǔ)言L(fǎng)1、L2、L3的CFG,然后利用連接運(yùn)算構(gòu)造L的CFG。L1和L3類(lèi)似,L2易于構(gòu)造。發(fā)現(xiàn)L1的遞歸性質(zhì),LL1,對(duì)每個(gè)xL1,都有0x1L1。因此得到L1的CFG,A0A1 | L。類(lèi)似地,L3的CFG是C1C0 | L。L2的CFG是B1B | 1(注意,不是BL,因?yàn)長(zhǎng)2的字符串長(zhǎng)度至少為1)。因此連接三部分,得到最終的CFG G=(V, , S, P),其中,V=S, A, B, C,=0, 1,P=SABC, A0A1 | L, B1B | 1, C1C0 | L。字符串01402=(01)(1)(1202)的推導(dǎo)過(guò)程如下,SABC0A1BC0L1BC011C0111C001111C0001111L0001111006.4 推導(dǎo)樹(shù)和歧義對(duì)于一個(gè)自然語(yǔ)言,比如英語(yǔ),理解它的句子從理解它的語(yǔ)法結(jié)構(gòu)開(kāi)始,即了解句子是怎樣根據(jù)語(yǔ)言的句法規(guī)則產(chǎn)生的。給定一個(gè)CFG和一個(gè)它所生成的字符串x,知道了x的推導(dǎo)過(guò)程有助于正確理解x的含義。一個(gè)展示推導(dǎo)過(guò)程(或推導(dǎo)結(jié)構(gòu))的自然的方法是畫(huà)出推導(dǎo)樹(shù)或分析樹(shù)。樹(shù)的根部是文法的起始非終結(jié)符,它是推導(dǎo)的起點(diǎn)。樹(shù)的內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)文法的一個(gè)非終結(jié)符,比如A,A的子節(jié)點(diǎn)對(duì)應(yīng)形如Aa的產(chǎn)生式的右部a的每個(gè)符號(hào)。對(duì)于形如AL的產(chǎn)生式,標(biāo)記為A的內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)只有一個(gè),即L。以例子6.5文法為例,SS+S | S-S | S*S | S/S | (S) | a,存在一個(gè)字符串的推導(dǎo),SS-SS*S-Sa*S-Sa*a-Sa*a-a,它對(duì)應(yīng)的推導(dǎo)樹(shù)如圖6-1a所示。另一個(gè)字符串的推導(dǎo),SS-SS-S/S.a-a/a的推導(dǎo)樹(shù)如圖6-1b。這兩個(gè)代數(shù)表達(dá)式常常用表達(dá)式樹(shù)(expression trees)表示,表達(dá)式樹(shù)是一個(gè)二叉樹(shù),它的葉節(jié)點(diǎn)是標(biāo)識(shí)符或常量,內(nèi)部節(jié)點(diǎn)是運(yùn)算符(參見(jiàn)圖6-2)。表達(dá)式樹(shù)顯示了表達(dá)式的結(jié)構(gòu)和推導(dǎo)過(guò)程,本節(jié)提出的推導(dǎo)樹(shù)類(lèi)似于這種表達(dá)式樹(shù)。在一個(gè)CFL的字符串的完整推導(dǎo)樹(shù)上,根節(jié)點(diǎn)對(duì)應(yīng)文法的起始非終結(jié)符,葉節(jié)點(diǎn)(或稱(chēng)終端節(jié)點(diǎn))對(duì)應(yīng)終結(jié)符或L。有時(shí)我們也用推導(dǎo)樹(shù)表示起于某個(gè)普通非終結(jié)符的推導(dǎo)結(jié)構(gòu),或部分推導(dǎo)過(guò)程,這種推導(dǎo)樹(shù)的根節(jié)點(diǎn)不一定是起始非終結(jié)符,葉節(jié)點(diǎn)也不一定是終結(jié)符。推導(dǎo)的每一步都是用某個(gè)產(chǎn)生式的右部代替左部的非終結(jié)符,每個(gè)推導(dǎo)都由一組這樣的替換按照一定順序組成。替換的順序很重要,因此推導(dǎo)SS+Sa+Sa+a和SS+SS+aa+a是不同的推導(dǎo)。這種差異是在細(xì)節(jié)上,當(dāng)?shù)玫絊+S時(shí),前者選取了最左非終結(jié)符,后者選取了最右非終結(jié)符。兩種推導(dǎo)對(duì)應(yīng)的推導(dǎo)樹(shù)是完全一樣的,因此可以認(rèn)為推導(dǎo)過(guò)程中的細(xì)微的次序差異是不重要的。推導(dǎo)樹(shù)完全反映了推導(dǎo)中用到的產(chǎn)生式,但不關(guān)心推導(dǎo)中用到的臨時(shí)節(jié)點(diǎn),或某些產(chǎn)生式的應(yīng)用次序,這些次序也與字符串的語(yǔ)法結(jié)構(gòu)無(wú)關(guān),因此對(duì)應(yīng)相同推導(dǎo)樹(shù)的推導(dǎo)都認(rèn)為是相同的推導(dǎo)。另一個(gè)比較兩個(gè)推導(dǎo)的方法是將推導(dǎo)的過(guò)程標(biāo)準(zhǔn)化,比如采用最左原則,即每次替換最左(或第一個(gè))非終結(jié)符。如果兩個(gè)遵循最左原則的推導(dǎo)是不同的,那么認(rèn)為是“本質(zhì)”不同的推導(dǎo)。實(shí)際上,最左原則和推導(dǎo)樹(shù)原則是兩個(gè)相當(dāng)?shù)呐卸?biāo)準(zhǔn)。一方面,對(duì)應(yīng)不同推導(dǎo)樹(shù)的最左推導(dǎo)過(guò)程是顯然不同的。另一方面,對(duì)應(yīng)不同最左推導(dǎo)過(guò)程的推導(dǎo)樹(shù)也是不同的。比如設(shè)下面的推導(dǎo)是第一次出現(xiàn)差異的情況,xAbxa1bxAbxa2b其中,x是終結(jié)符組成的字符串,A是非終結(jié)符,且a1a2,因此體現(xiàn)在推導(dǎo)樹(shù)則一定不同?,F(xiàn)在定義,一個(gè)字符串具有多個(gè)(超過(guò)1個(gè))推導(dǎo)樹(shù)當(dāng)且僅當(dāng)具有多個(gè)最左推導(dǎo)。注意我們也可以采用最右原則,關(guān)鍵是消除一些細(xì)節(jié)上的差異。我們發(fā)現(xiàn)許多CFG生成的字符串具有多個(gè)“本質(zhì)”不同的生成辦法。定義6.3 CFG G是歧義的(ambiguous)當(dāng)且僅當(dāng)存在一個(gè)xL(G)具有多個(gè)推導(dǎo)樹(shù)(或最左推導(dǎo)過(guò)程)。顯然,上面定義的歧義很接近我們?nèi)粘?yīng)用的自然語(yǔ)言句子的歧義。比如一個(gè)記者用到的標(biāo)題“Disabled Fly to See Carter”,如果它出現(xiàn)在美國(guó)第39任總統(tǒng)當(dāng)政時(shí)期,對(duì)應(yīng)的推導(dǎo)是:S .。但通常更多的解釋是:S .。此處,正確理解一個(gè)新聞標(biāo)題的關(guān)鍵是選擇相應(yīng)的語(yǔ)法推導(dǎo)。例子6.10 回到例子6.5給出的代數(shù)表達(dá)式的CFG,我們考察了字符串a(chǎn)+(a*a)/a-a具有的本質(zhì)不同的推導(dǎo)過(guò)程。分析:本例的CFG形如,SS+S | S-S | S*S | S/S | (s) | a,看一個(gè)簡(jiǎn)單的例子“a+a+a”,存在兩個(gè)不同的最左推導(dǎo):SS+Sa+Sa+S+Sa+a+Sa+a+aSS+SS+S+Sa+S+Sa+a+Sa+a+a它們對(duì)應(yīng)的推導(dǎo)樹(shù)分別見(jiàn)圖6-3a和圖6-3b。如果結(jié)合具體的代數(shù)運(yùn)算符含義,兩者最終含義是相同的,前者等同于a+(a+a),后者等同于(a+a)+a??梢?jiàn)括號(hào)具有消除歧義的作用。從例子6.10容易看到,凡是具有形如AAaA的產(chǎn)生式的CFG都是有歧義的。然而有很多種引入歧義的方式,有時(shí)很難發(fā)現(xiàn)并排除它們。例子6.11 程序設(shè)計(jì)語(yǔ)言歧義的一個(gè)標(biāo)準(zhǔn)的例子是“dangling else”,考慮下面的產(chǎn)生式:if () | if () else |現(xiàn)在考慮聲明:if (expr1) if (expr2) f(); else g();根據(jù)上面的產(chǎn)生式,可以有兩個(gè)推導(dǎo)樹(shù),一種將else看成與第一個(gè)if相關(guān),另一種將else看成與第二個(gè)if相關(guān)。參見(jiàn)圖6-4a和圖6-4b。在C語(yǔ)言中,為了消除歧義,常常引入括號(hào),如,if (expr1) if (expr2) f(); else g();if (expr1) if (expr2) f(); else g();或者修改文法,如 | if () else | if () | if () else 目前我們無(wú)法證明為什么新文法消除了歧義,但可以直觀地解釋。生成的都是if-else匹配的情況,生成的是if-else不匹配的情況。而且出現(xiàn)在else之前的都是,因此不匹配的情況出現(xiàn)在else之后,即else總是與最接近的if匹配。程序設(shè)計(jì)語(yǔ)言Modula-2使用了類(lèi)似括號(hào)的方法消除歧義,IF THEN END |IF THEN ELSE END |在上面文法下,圖6-4a和圖6-4b對(duì)應(yīng)的字符串分別是IF A1 THEN IF A2 THEN S1 END ELSE S2 ENDIF A1 THEN IF A2 THEN S1 ELSE S2 END END6.5 一個(gè)無(wú)歧義的代數(shù)表達(dá)式盡管有些CFL是“內(nèi)在”歧義的,即只能由有歧義的CFG生成,但通常意義的歧義是針對(duì)文法而言,而不是語(yǔ)言。如果一個(gè)CFG是歧義的,常??赡艽嬖冢ㄒ彩俏覀兿Ml(fā)現(xiàn)的)一個(gè)與其相當(dāng)?shù)姆瞧缌x的CFG,本節(jié)我們消除例子6.5給出的代數(shù)表達(dá)式的文法的歧義。為了簡(jiǎn)化問(wèn)題,我們僅僅使用兩個(gè)運(yùn)算符“+”和“*”,得到產(chǎn)生式如下,SS+S | S*S | (S) | a如果消除了這兩個(gè)運(yùn)算符的歧義,能夠類(lèi)似地消除“-”和“/”的歧義。正如前面講到,產(chǎn)生式SS+S能夠帶來(lái)歧義,我們需要消除這種類(lèi)型的產(chǎn)生式,同時(shí)保持各種運(yùn)算符的優(yōu)先級(jí),比如*的優(yōu)先級(jí)高于+,且位于前面的+優(yōu)先級(jí)高于后面的+。新文法G1的產(chǎn)生式如下,SS+T | TTT*F | FF(S) | a需要證明兩個(gè)方面:1)G1與G相當(dāng);2)G1沒(méi)有歧義。為了證明方便,G1中的起始符號(hào)改寫(xiě)成S1。定理6.2 文法G的產(chǎn)生式是SS+S | S*S | (S) | a,文法G1的產(chǎn)生式是S1S1+T | TTT*F | FF(S1) | a則L(G)=L(G1)。證明:首先證明L(G1)L(G)。對(duì)屬于L(G1)的字符串x的長(zhǎng)度使用數(shù)學(xué)歸納法。1. 歸納基礎(chǔ),x=a時(shí),顯然xL(G)2. 歸納推理,設(shè)k=1,每個(gè)屬于L(G1)、長(zhǎng)度=k的字符串y也屬于L(G),要證明如果xL(G1)且|x|=k+1,則xL(G)。顯然G1推導(dǎo)x的第一步是下面三種情況之一,S1S1+TS1TT*FS1T(S1)如果是情況一,則x=y+z,S1*y,T*z,由于S1*T,因此也有S1*z,由于y和z的長(zhǎng)度都=1,對(duì)每個(gè)yL(G)且|y|=k,yL(G1)也成立,要證明如果xL(G)且|x|=k+1,則xL(G1)。設(shè)x在G上的第一步推導(dǎo)是S(S),對(duì)應(yīng)x=(y),則|y|=1,任何一個(gè)從S1、T、F推導(dǎo)出來(lái)的長(zhǎng)度=1,如果AGnx,則AG1*x。對(duì)n使用數(shù)學(xué)歸納法。1. 歸納基礎(chǔ),n=1,即AG1x,則P中存在Ax,x是非空的,因此P1中也有Ax,則AG11x,AG1*x。2. 歸納推理,n=k時(shí)所有|x|=k的x滿(mǎn)足上式。要證明對(duì)|x|=k+1的x也滿(mǎn)足上式。設(shè)AG*x的第一步是AX1X2.Xn,對(duì)應(yīng)x=x1x2.xn。其中Xi=xi或XiG=1,如果AG1nx,則AG*x。類(lèi)似可證。顯然,消除文法的空產(chǎn)生式,需要添加大量新的產(chǎn)生式(很類(lèi)似,消除FA的空轉(zhuǎn)移需要添加大量新的轉(zhuǎn)移)。于是存在一個(gè)問(wèn)題,添加的新產(chǎn)生式是否帶來(lái)了新的不好的性質(zhì)。部分的回答是算法6.1不會(huì)帶來(lái)歧義,即如果原來(lái)文法G是非歧義的,則處理后的文法G1也是非歧義的。證明并不困難,參見(jiàn)練習(xí)6.38。單一產(chǎn)生式的消除類(lèi)似空產(chǎn)生式的消除。比如要?jiǎng)h除AB(更普遍地,A*B),就要對(duì)所有Ba,添加Aa。為了簡(jiǎn)化討論,我們消除單一產(chǎn)生式的工作基礎(chǔ)是無(wú)空產(chǎn)生式的文法。下面先定義A可推導(dǎo)集(A-derivable)。1. 如果存在產(chǎn)生式AB,則B是A可推導(dǎo)的;2. 如果存在產(chǎn)生式CB,且C是A可推導(dǎo)的,BA,則B是A可推導(dǎo)的;3. 僅包含1和2產(chǎn)生的非終結(jié)符。算法6.2 給定一個(gè)沒(méi)有空產(chǎn)生式的CFG G=(V, , S, P),構(gòu)造一個(gè)沒(méi)有單一產(chǎn)生式的文法G1=(V, , S, P1)。1. 初始化P1=P2. 對(duì)每個(gè)AV,發(fā)現(xiàn)A的可推導(dǎo)集3. 對(duì)A的可推導(dǎo)集的每個(gè)元素B,如果存在Ba,則添加產(chǎn)生式Aa到P14. 刪除P1中的所有單一產(chǎn)生式定理6.5 設(shè)G是沒(méi)有空產(chǎn)生式CFG,G1是算法6.2得到的文法,則G1沒(méi)有單一產(chǎn)生式,且L(G1)=L(G)。證明:略,參見(jiàn)練習(xí)6.37。值得指出的是,如果文法G是無(wú)歧義的,則文法G1也是無(wú)歧義的。例子6.13 G是生成代數(shù)表達(dá)式的文法,它的產(chǎn)生式如下:SS+T | TTT*F | FF(S) | a則S的可推導(dǎo)集是T, F,T的可推導(dǎo)集是F。根據(jù)算法6.2的第3步,加入產(chǎn)生式ST*F | (S) | a和T(S) | a,然后刪除單一產(chǎn)生式,最后的產(chǎn)生式集合如下,SS+T | T*F | (S) | aTT*F | (S) | aF(S) | a除了刪除一些“不好”的產(chǎn)生式,如空產(chǎn)生式和單一產(chǎn)生式,對(duì)產(chǎn)生式的格式添加更多的限制也是有用的。已經(jīng)提出了多種產(chǎn)生式的“規(guī)范形式”,本節(jié)介紹其中的一種,Chomsky范式。定義6.6 一個(gè)CFG的每個(gè)產(chǎn)生式符合下面兩個(gè)形式中的一種,則稱(chēng)為Chomsky范式(Chomsky normal form, CNF):ABC和Aa。其中,A、B、C是非終結(jié)符,a是終結(jié)符。將一個(gè)文法G轉(zhuǎn)換成CNF需要三個(gè)步驟。第一步應(yīng)用算法6.1和算法6.2得到?jīng)]有空產(chǎn)生式和單一產(chǎn)生式的文法G1,L(G1)=L(G)-L;第二步構(gòu)造新的文法G2,它的產(chǎn)生式只有下面兩種形式:AB1B2.Bk和Aa,其中,A、Bi是非終結(jié)符,a是終結(jié)符,L(G2)=L(G1)。從G1構(gòu)造G2很簡(jiǎn)單,給每個(gè)終結(jié)符a引入一個(gè)相應(yīng)的非終結(jié)符Xa,添加產(chǎn)生式Xaa,原產(chǎn)生式中的a都替換成Xa(除了Aa這類(lèi)產(chǎn)生式)。文法G2已經(jīng)很接近Chomsky范式了,產(chǎn)生式的右部要么全是非終結(jié)符,要么是單個(gè)終結(jié)符。第三步,將G2中右部長(zhǎng)度超過(guò)2的產(chǎn)生式用多個(gè)產(chǎn)生式替換。定理6.6 對(duì)于每個(gè)CFG G都存在一個(gè)符合Chomsky范式的CFG G,使得L(G)=L(G)-L。證明:略。例子6.14 CFG G的產(chǎn)生式如下:SAACDAaAb | LCaC | aDaDa | bDb | L構(gòu)造G對(duì)應(yīng)的符合Chomsky范式的文法G。分析:1. 刪除空產(chǎn)生式,得到SAACD | ACD | AAC | CD | AC | CAaAb | abCaC | aDaDa | bDb | aa | bb2. 刪除單一產(chǎn)生式,增加SaC | a,刪除SC。3. 增加產(chǎn)生式的限制,不允許非終結(jié)符和終結(jié)符在產(chǎn)生式右部混雜出現(xiàn),得到SAACD | ACD | AAC | CD | AC | XaC | aAXaAXb | XbXbCXaC | aDXaDXa | XbDXb | XaXb | XbXbXaaXbb4. 轉(zhuǎn)換成CNF,得到SAT1T1A
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 零售業(yè)店鋪顧客流量分析與營(yíng)銷(xiāo)策略考核試卷
- 針織品銷(xiāo)售區(qū)域布局優(yōu)化考核試卷
- 重疾險(xiǎn)產(chǎn)品設(shè)計(jì)
- 胸痛常見(jiàn)疾病及診斷
- 班主任六一匯報(bào)工作總結(jié)
- 沖管操作與感染防控要點(diǎn)
- 妊高征的急救處理
- 中醫(yī)外科疾病診療概要
- 事故隱患內(nèi)部報(bào)告獎(jiǎng)勵(lì)制度模板三
- 港股6月IPO火熱給港股投資帶來(lái)更多選擇
- 2025年度飛機(jī)買(mǎi)賣(mài)及航空法律咨詢(xún)服務(wù)合同4篇
- 工程測(cè)量學(xué)知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋山東科技大學(xué)
- 2025年云南省社會(huì)科學(xué)院中國(guó)(昆明)南亞?wèn)|南亞研究院招聘高層次人才7人歷年高頻重點(diǎn)提升(共500題)附帶答案詳解
- DB33-T 1401-2024 公共機(jī)構(gòu)合同能源管理實(shí)施規(guī)范
- 產(chǎn)褥期膿毒血癥護(hù)理查房
- 英語(yǔ)名詞所有格課件
- 公共倫理復(fù)習(xí)要點(diǎn)
- 管道打壓、吹掃方案
- 石頭雕刻合同范例
- 《個(gè)人所得稅法解讀》課件
- 《產(chǎn)品檢驗(yàn)方法培訓(xùn)》課件
評(píng)論
0/150
提交評(píng)論