上下文無(wú)關(guān)文法.doc

語(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是歧義的，常?？赡艽嬖冢ㄒ彩俏覀兿Ｍl(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