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

語言與計算理論導(dǎo)引 上下文無關(guān)文法第三部分 上下文無關(guān)語言和下推自動機前面介紹的有限自動機是計算的初級模型，它所接受的正規(guī)語言不太關(guān)心字符串自身的結(jié)構(gòu)。上下文無關(guān)文法（CFL）是一種簡單的描述語法規(guī)則的遞歸方法，語言中的字符串由這些規(guī)則產(chǎn)生。所有的正規(guī)語言都能用上下文無關(guān)文法描述，它也可以描述非正規(guī)語言。上下文無關(guān)文法描述的語法規(guī)則更復(fù)雜多變，可以在相當大的程度上，描述高級程序設(shè)計語言的語法和其他一些形式語言。類似正則語言對應(yīng)的抽象機模型是有限自動機，CFL也有對應(yīng)的抽象機模型。CFL對應(yīng)的計算模型是在有限自動機的基礎(chǔ)上增加存儲空間得到，并被設(shè)想成無限空間（對應(yīng)有限自動機的有限空間），采用了一種簡單的管理模式，棧（stack），這種新的計算模型（或抽象機）稱為下推自動機（pushdown automata），下推是棧最典型的操作。有必要在下推自動機中保留非確定性，確定型下推自動機不能接受所有的CFL，但給定一個CFG，容易構(gòu)造一個相應(yīng)的非確定型下推自動機，它在識別字符串過程中的移動模擬了文法的推導(dǎo)過程，這個過程稱為分析（parse）。分析不是一定需要下推自動機來完成。CFL仍然不夠通用，不能包括所有有意義的、或有用的形式語言。采用類似第五章的技術(shù)，我們將給出一些不是CFL的簡單例子，這些技術(shù)也用于解決與CFL相關(guān)的判定問題。1陶曉鵬 Copyright 2003語言與計算理論導(dǎo)引 上下文無關(guān)文法6 上下文無關(guān)文法6.1 上下文無關(guān)文法的定義為了描述我們在第二部分考察的各種語言，包括一些非正則語言，我們引入一種語言的遞歸定義方法，稱為文法。文法與我們熟悉的語言的語法描述相近，是描述語言和分析語言的有力工具。問題：文法的形式化定義似乎可以模仿有限自動機，比如5元組或6元組之類。例子6.1 正如我們在例子2.16中所見，字母表a, b上的回文語言pal可以用下面的遞歸方法描述：1. L, a, bpal2. 對每個Spal，aSa和bSb也屬于pal3. pal中不包含其他字符串如果將上面的符號S看成一個變量，代表了所有我們希望計算（比如某種遞歸算法）的pal的元素，那么上面的規(guī)則1和規(guī)則2可以非正式地重新表述如下：1. S的值可以是L, a, b2. 每個S可以寫成aSa或bSb的形式如果我們用表示“可以取值為”，則可以寫出下面的式子：SaSaabSbaabLba=abba上面的產(chǎn)生過程可以總結(jié)成下面的兩組產(chǎn)生式（或稱規(guī)則）：Sa | b | LSaSa | bSb符號“|”表示“或”的含義。上式的含義是aSa或bSb，而不是a或b，即連接運算的優(yōu)先級高于“|”。我們使用的這套術(shù)語中，小寫字母a和b表示終結(jié)符，大寫字母S表示非終結(jié)符，或稱變量?？偣灿?條規(guī)則，或產(chǎn)生式（production）。符號S是非終結(jié)符，也是起始終結(jié)符，即我們生成字符串的起始符號是S，然后不斷利用規(guī)則替換符號串中的非終結(jié)符，直到最終得到一個不含非終結(jié)符的符號串，就生成了規(guī)則所定義的語言的一個字符串。例子2中的產(chǎn)生式具有除起始符S外的多個非終結(jié)符，我們設(shè)想S表示了語言中任意的字符串，其他非終結(jié)符表示了其他輔助性的字符串類型，他們可用來方便地生成S表示的字符串。例子6.2 我們要構(gòu)造一個生成所有在字母表a, b上的非回文字符串的文法，那樣的字符串可以描述如下：從字符串的兩端開始比較，也許能夠發(fā)現(xiàn)一些相同的字符對，但最終能夠發(fā)現(xiàn)一對不同的字符。對于前一種情況，我們可以借用回文語言的產(chǎn)生式：SaSa | bSb如果加入產(chǎn)生式Sa | b | L則這種左右匹配的形式將體現(xiàn)在整個字符串上，為了中斷這種左右匹配的情況，即體現(xiàn)上面提到的第二種情況，我們引入新的非終結(jié)符，比如D，表示那些左右兩個端點上的字符不同的字符串。且所有符合D的字符串也符合S，因此有SD。非終結(jié)符的定義比較簡單，它唯一的條件是左右兩個端點的字符不相同，中間的字符串可以是任意的，我們用非終結(jié)符A表示任意的字符串，則有DaAb | bAa。A表示任意的字符串，因此A的產(chǎn)生式更簡單了，不用添加新的非終結(jié)符來簡化問題，它的產(chǎn)生式是，AL | aA | bA。我們把上面三個非終結(jié)符的產(chǎn)生式寫在一起，就得到了描述所規(guī)定語言的產(chǎn)生式集：SaSa | bSb | DDaAb | bAaAL | aA | bA因此一個完整的非回文字符串“abbaaba”的產(chǎn)生過程是，SaSaabSbaabDbaabbAabaabbaAabaabbaLabaabbaaba定義6.1 上下文無關(guān)文法（context-free grammar, CFG）是一個4元組G=(V, , S, P)，其中，V和是不相交的有限集，SV，P是一組有限的產(chǎn)生式規(guī)則，形如Aa，其中AV，且a(V)*。V的元素稱為非終結(jié)符（或變量），的元素稱為終結(jié)符，S是一個特殊的非終結(jié)符，稱為起始符，P的元素稱為語法規(guī)則，或產(chǎn)生式。設(shè)G=(V, , S, P)是一個CFG，我們將符號保留給P的產(chǎn)生式專用，符號G用于表示字符串的產(chǎn)生過程的每一步，如aGb表示字符串b能夠通過替換a中的某些變量（根據(jù)P定義的產(chǎn)生式來替換）得到，即如果有a=a1Aa2且AgP，則b=a1ga2。這里能夠看到，我們命名為上下文無關(guān)（context-free）的含義，即我們在利用產(chǎn)生式規(guī)則，用一組符號替換某個非終結(jié)符時，與非終結(jié)符的上下文無關(guān)（此處，A的替換與a1和a2無關(guān)），替換是無限制的。在沒有多個文法出現(xiàn)，很清楚用到文法G是什么的情況下，推導(dǎo)符號G可以簡寫成。多步的推導(dǎo)可以寫成*G，即如果存在一組符號串，a=a0、a1、ak=b，每個后者都是前者的直接推導(dǎo)，則稱為a可以多步推導(dǎo)出b，記為a*Gb，簡寫成a*b。定義6.2 G=(V, , S, P)是一個CFG，則G產(chǎn)生的語言是所有可由G產(chǎn)生的字符串組成的集合，即L(G)=x* | S*Gx。一個語言L是上下文無關(guān)語言（context-free language, CFL），當且僅當存在一個CFG G，使得L=L(G)。此處可以把文法設(shè)想成類似自動機的抽象模型，則一個語言L是CFL當且僅當存在一個CFG G接受它（或識別它），類似前面正則語言與有限自動機的關(guān)系，接受（或識別）的含義是兩方面的，一方面凡是L中的字符串都能由G產(chǎn)生，另一方面，凡是不屬于L的字符串都不能由G產(chǎn)生。前面的例子，能夠比較容易地說明這兩方面的限制，下面的例子則不是很明顯。例子6.3 考慮語言L=x0, 1* | n0(x)=n1(x)，其中ni(x)表示數(shù)字i在x中的出現(xiàn)次數(shù)（即含有相同數(shù)目0和1的語言）。寫出生成L的CFG。分析：既然CFG的本質(zhì)是一個遞歸定義，那么類似例子6.1，我們可以先發(fā)現(xiàn)歸納基礎(chǔ)，然后找到歸納推理。顯然LL，另外如果存在一個字符串xL，那么得到更長的屬于L的字符串的兩個方法是，0x1和1x0，即分別在兩端添加相同數(shù)量的0和1。（當然，還有很多生成方法，比如x01，x10，或在x中插入相同數(shù)量的0和1），這樣得到三個產(chǎn)生式：SL | 0S1 | 1S0顯然，還遺漏了一些字符串，如0110。我們注意到L中任意兩個元素的連接仍然屬于L，因此可以增加一個產(chǎn)生式，SSS。與前面的三個產(chǎn)生式合并，我們得到一個CFG G如下，SL | 0S1 | 1S0 | SS顯然G產(chǎn)生的字符串都滿足0和1數(shù)目相等這個條件，即L(G)L，現(xiàn)在只要證明LL(G)。令d(x)=n0(x)-n1(x)。則字符串xL，當且僅當d(x)=0。因此只需證明每個滿足d(x)=0的x，都有xL(G)。我們用數(shù)學(xué)歸納法來證明LL(G)。歸納對象是字符串的長度|x|。1. 歸納基礎(chǔ)，|x|=0且d(x)=0，則xL(G)，這是顯然的，因為此時x=L，而L可以由產(chǎn)生式SL得到。2. 歸納推理，設(shè)k=0，每個滿足|y|=k，d(y)=0的字符串y都屬于L(G)。要證明每個長度等于k+1且d(x)=0的字符串x也屬于L(G)。分情況討論如下：a) 如果x以0開始，以1結(jié)尾，則可以寫成x=0y1，且d(y)=0，根據(jù)歸納假設(shè)yL(G)，即存在一組推導(dǎo)，S*Gy。因此對于x，存在推導(dǎo)，S0S1*0y1x。b) 如果x以1開始，以0結(jié)尾，類似a)的處理，能夠得到從S到x的推導(dǎo)。c) 如果x以0開始，且以0結(jié)尾。則x的長度至少為2，設(shè)x=0y0?，F(xiàn)在考察x的所有前綴z的d(z)，其中d(0)=1，d(0y)=d(0y0)-d(0)=-1，而d(z)隨著z的長度增1，至多增加1或減少1，而當前綴從0變化到0y時，d(z)從1變化到-1，因此存在某個長于0短于0y的前綴z，使得d(z)=0，則x=zw，顯然d(w)=0，由于z、w的長度都0的x都能由G0產(chǎn)生，對x的長度應(yīng)用數(shù)學(xué)歸納法。1. 歸納基礎(chǔ)，顯然|x|=1且d(x)0時，即x=0，x可由S0推導(dǎo)，屬于L(G0)。2. 歸納推理，設(shè)k=0，對每個|x|0的x都屬于L(G0)，要證明每個|x|0的x也屬于L(G0)。分情況討論，此處僅討論x=0y0的情況（即以0開始和結(jié)尾的情況），a) x僅由0組成，易證。b) x至少含有一個1。則x=w1z，現(xiàn)在證明d(w)0且d(z)0。設(shè)x含有n個1，n=1，對每個1=i=n，令wi是x的前綴，緊接wi的下一個字符就是第i個1，則x=wi1zi。分兩種情況1）不存在wi，使得d(wi)0，則d(wn)0，令w=wn，z=zn，顯然d(z)0，得證；2）存在一個wi，使得d(wi)=0，設(shè)i=m是第一個d(wi)0，且d(wm-1)=10，令w=wm-1，z=zm-1，易證d(zm-1)0，因此得證。其他兩種情況，x以1開始，以1結(jié)尾證明略。類似方法能夠得到生成L1的產(chǎn)生式，我們用A表示生成L0的產(chǎn)生式，B表示生成L1的產(chǎn)生式，那么生成語言L的全部文法是：SA | BA0 | 0A | 1AA | AA1 | A1AB1 | 1B | 0BB | BB0 | B0B注意其中的第一個規(guī)則，它恰如其分地表示了合集的含義。6.2 更多地例子，包括一些熟悉的語言例子6.5 我們前面已經(jīng)提到了在計算機科學(xué)和其他領(lǐng)域應(yīng)用很廣泛的書寫代數(shù)表達式的語言。一般地，我們允許任意的標識符和數(shù)字常數(shù)出現(xiàn)在表達式中，為了簡化問題，我們規(guī)定只有一個標識符（字母a）、4種兩項運算符（+、-、*、/）和左括號、右括號。我們用變量A表示這個簡單的表達式語言。它可以嵌入到復(fù)雜的表達式語言中。一個容易發(fā)現(xiàn)的遞歸現(xiàn)象是，如果存在兩個表達式，那么可以利用運算符和括號，連接它們構(gòu)成新的表達式。顯然，除了單個標識符a，其他表達式都是通過這個遞歸過程構(gòu)造的，因此我們得到下面的文法：SS+S | S-S | S*S | S/S | (S) | a表達式a+(a*a)/a-a的推導(dǎo)過程如下，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)過程，如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ōu)先級和計算次序。比如，上述表達式通常的計算次序如下：1. 計算a*a，記為A2. 計算A/a，記為B3. 計算a+B，記為C4. 計算C-a盡管第二種推導(dǎo)不符合通常的表達式結(jié)構(gòu)，或表達式語義，但整個推導(dǎo)是符合文法規(guī)定的，是一個合法的推導(dǎo)。一個可能的結(jié)論是本例給出的CFG不是最合理的，它沒有體現(xiàn)出運算符和括號的優(yōu)先級，另外好的CFG對每個字符串僅僅提供一種推導(dǎo)過程（如果忽略次序不同的一些簡單替換），在6.4節(jié)我們將回到這個問題，它稱為CFG的歧義。例子6.6 上面的例子類似例子3.5和3.6，僅僅描述了程序設(shè)計語言（比如C和Pascal）的某個部分，本例將顯示，CFG可用來描述程序設(shè)計語言的整個語法結(jié)構(gòu)。C語言有兩大類語法結(jié)構(gòu)，和。包括條件聲明（）和循環(huán)聲明（）等等，因此有，. | | | .if () for (; ; ) .可以類似構(gòu)造多個聲明連接而成的復(fù)合聲明，以及等等。例子6.7 高級程序設(shè)計語言的一個大的優(yōu)點是寫出的程序與英文陳述很接近，既然我們可以用CFG去描述高級程序設(shè)計語言，那么可不可以用來描述英語呢？對于一些簡單的英語語法，容易找到它的CFG，比如最基本、最典型的英語陳述句的結(jié)構(gòu)是， ，因此可以構(gòu)造出如下的產(chǎn)生式， 可以進一步構(gòu)造生成右部三個非終結(jié)符的產(chǎn)生式。寫出一套合理的、具有廣泛性、符合常用語法習(xí)慣的英語規(guī)則并不困難，且規(guī)則的數(shù)目也可以不是很多。困難的地方是防止產(chǎn)生不合語法，或合乎語法，然而不合語義，沒有人會使用的英語句子。下面的產(chǎn)生式就是一個例子， John | Janereminded | himself | herself上面文法能夠產(chǎn)生很多不“正確”的英語句子，如“John reminded herself”，“Jane reminded himself”?？梢酝ㄟ^增加文法的復(fù)雜性（更多的非終結(jié)符和更多的產(chǎn)生式）來消除這種不正確的推導(dǎo)，比如修改產(chǎn)生式為， 而對于例如“Jane reminded Jane”還需要其他消除方法，因為句子“Jane reminded John”是一個好的英語句子。要想?yún)^(qū)別這兩個句子，需要上下文信息，因此本章討論的CFG無法很深入、精細地刻畫自然語言的一些細微特征。6.3 CFL的合并、連接和Kleene*運算例子6.4我們構(gòu)造了一個CFG，它生成的語言是另外兩種語言的合集，而且找到了另外兩種語言對應(yīng)的CFG。例子6.4揭示的方法和處理連接和Kleene*運算的相應(yīng)方法構(gòu)成了下面定理的基礎(chǔ)。定理6.1 L1和L2是兩個CFL，則語言L1L2、L1L2和L1*也是CFL。證明：我們用構(gòu)造法證明。假設(shè)生成L1和L2的文法分別是G1=(V1, , S1, P1)和G2=(V2, , S2, P2)，以此為基礎(chǔ)，分別構(gòu)造生成上面三種新語言的CFG。首先假設(shè)V1V2=f（否則可以通過改名來到達目的），設(shè)生成L1L2的文法Gu=(Vu, , Su, Pu)，其中，Su是不屬于V1和V2的新增非終結(jié)符，Vu=V1V2Su，Pu=P1P2SuS1 | S2?，F(xiàn)在證明L(Gu)=L1L2。一方面，任取xL1=L(G1)，則S1*x，又由于存在產(chǎn)生式SuS1，因此Su*x。類似地，任取xL1，也有S*x。因此L1L2L(Gu)。另一方面，任取xL(Gu)，則存在S*x，則存在S1*x或S2*x，因此L(Gu)L1L2。得證。類似處理連接運算，文法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，滿足S1*x1，S2*x2，因此L(Gc)L1L2。文法G*=(V, , S, P)生成語言L1*，其中，S是不屬于V的新增非終結(jié)符。語言L1*所含字符串x的形式是x=x1x2.xk，其中每個xiL1，如果能夠S連續(xù)地產(chǎn)生k個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)*。得證。下面的例子說明了證明的第一步消除V1和V2中的同名是很重要的。比如有兩個CFG如下：S1XA, Xc, AaS2XB, Xd, Bb此處非終結(jié)符X出現(xiàn)在兩個文法中，如果不改名將帶來混亂。如SS1XAdAda，而事實上S1無法推導(dǎo)出da。推論6.1 每個正則語言都是CFL。證明：根據(jù)正則語言的遞歸定義（定義3.1），每個正則語言是以三種簡單的字符（f、L、a）為基礎(chǔ)，多次施加三種運算（合并、連接、Kleeen*）得到。顯然三種簡單的字符組成的語言是CFL，又根據(jù)定理6.1，三種運算保持了CFL的性質(zhì)，因此根據(jù)結(jié)構(gòu)歸納法，命題得證。例子6.8 語言L是正則表達式，(011+1)*(01)*，表示的正則語言，寫出它對應(yīng)的CFG。分析：定理6.1的證明過程給出了發(fā)現(xiàn)一個CFL的CFG的方法。分別考慮(011+1)*和(01)*。而(011+1)*可進一步轉(zhuǎn)化成考慮(011+1)，得到A011 | 1，然后加上Kleene*運算，得到，BAB | L類似地，對應(yīng)正則表達式(01)*的產(chǎn)生式是，CDC | L, D01最后應(yīng)用連接運算，得到語言L對應(yīng)的CFG是SBCBAB | LA011 | 1CDC | LD01最后引入的符號S是非終結(jié)符，構(gòu)造過程中引入的符號是輔助非終結(jié)符。例子6.9 語言L=0i1j0k | ji+k的CFG。分析：一個直觀的觀察是L的每個字符串都是三部分連接而成的：0i、1j、0k。因此似乎可以分別構(gòu)造三部分語言的CFG，然后通過連接運算構(gòu)造整個語言的CFG。這種方法是錯誤的，因為本例語言的三部分是相互關(guān)聯(lián)的，而不是相互獨立的，定理6.1揭示的方法僅僅用在相互獨立的兩個CFG之間的運算?？尚械姆椒ㄊ牵瑢⒈纠芯哂嘘P(guān)系的參數(shù)i、j、k轉(zhuǎn)換成相互無關(guān)的參數(shù)。由于ji+k，不妨令j=i+k+m，m0。則0i1j0k=0i1i1m1k0k。此處的三個參數(shù)i、m、k相互獨立，因此語言L=L1L2L3，其中，L1=0i1i | i=0L2=1m | m0L3=1k0k | k=0先分別構(gòu)造語言L1、L2、L3的CFG，然后利用連接運算構(gòu)造L的CFG。L1和L3類似，L2易于構(gòu)造。發(fā)現(xiàn)L1的遞歸性質(zhì)，LL1，對每個xL1，都有0x1L1。因此得到L1的CFG，A0A1 | L。類似地，L3的CFG是C1C0 | L。L2的CFG是B1B | 1（注意，不是BL，因為L2的字符串長度至少為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)過程如下，SABC0A1BC0L1BC011C0111C001111C0001111L0001111006.4 推導(dǎo)樹和歧義對于一個自然語言，比如英語，理解它的句子從理解它的語法結(jié)構(gòu)開始，即了解句子是怎樣根據(jù)語言的句法規(guī)則產(chǎn)生的。給定一個CFG和一個它所生成的字符串x，知道了x的推導(dǎo)過程有助于正確理解x的含義。一個展示推導(dǎo)過程（或推導(dǎo)結(jié)構(gòu)）的自然的方法是畫出推導(dǎo)樹或分析樹。樹的根部是文法的起始非終結(jié)符，它是推導(dǎo)的起點。樹的內(nèi)部節(jié)點對應(yīng)文法的一個非終結(jié)符，比如A，A的子節(jié)點對應(yīng)形如Aa的產(chǎn)生式的右部a的每個符號。對于形如AL的產(chǎn)生式，標記為A的內(nèi)部節(jié)點的子節(jié)點只有一個，即L。以例子6.5文法為例，SS+S | S-S | S*S | S/S | (S) | a，存在一個字符串的推導(dǎo)，SS-SS*S-Sa*S-Sa*a-Sa*a-a，它對應(yīng)的推導(dǎo)樹如圖6-1a所示。另一個字符串的推導(dǎo)，SS-SS-S/S.a-a/a的推導(dǎo)樹如圖6-1b。這兩個代數(shù)表達式常常用表達式樹（expression trees）表示，表達式樹是一個二叉樹，它的葉節(jié)點是標識符或常量，內(nèi)部節(jié)點是運算符（參見圖6-2）。表達式樹顯示了表達式的結(jié)構(gòu)和推導(dǎo)過程，本節(jié)提出的推導(dǎo)樹類似于這種表達式樹。在一個CFL的字符串的完整推導(dǎo)樹上，根節(jié)點對應(yīng)文法的起始非終結(jié)符，葉節(jié)點（或稱終端節(jié)點）對應(yīng)終結(jié)符或L。有時我們也用推導(dǎo)樹表示起于某個普通非終結(jié)符的推導(dǎo)結(jié)構(gòu)，或部分推導(dǎo)過程，這種推導(dǎo)樹的根節(jié)點不一定是起始非終結(jié)符，葉節(jié)點也不一定是終結(jié)符。推導(dǎo)的每一步都是用某個產(chǎn)生式的右部代替左部的非終結(jié)符，每個推導(dǎo)都由一組這樣的替換按照一定順序組成。替換的順序很重要，因此推導(dǎo)SS+Sa+Sa+a和SS+SS+aa+a是不同的推導(dǎo)。這種差異是在細節(jié)上，當?shù)玫絊+S時，前者選取了最左非終結(jié)符，后者選取了最右非終結(jié)符。兩種推導(dǎo)對應(yīng)的推導(dǎo)樹是完全一樣的，因此可以認為推導(dǎo)過程中的細微的次序差異是不重要的。推導(dǎo)樹完全反映了推導(dǎo)中用到的產(chǎn)生式，但不關(guān)心推導(dǎo)中用到的臨時節(jié)點，或某些產(chǎn)生式的應(yīng)用次序，這些次序也與字符串的語法結(jié)構(gòu)無關(guān)，因此對應(yīng)相同推導(dǎo)樹的推導(dǎo)都認為是相同的推導(dǎo)。另一個比較兩個推導(dǎo)的方法是將推導(dǎo)的過程標準化，比如采用最左原則，即每次替換最左（或第一個）非終結(jié)符。如果兩個遵循最左原則的推導(dǎo)是不同的，那么認為是“本質(zhì)”不同的推導(dǎo)。實際上，最左原則和推導(dǎo)樹原則是兩個相當?shù)呐卸藴省Ｒ环矫?，對?yīng)不同推導(dǎo)樹的最左推導(dǎo)過程是顯然不同的。另一方面，對應(yīng)不同最左推導(dǎo)過程的推導(dǎo)樹也是不同的。比如設(shè)下面的推導(dǎo)是第一次出現(xiàn)差異的情況，xAbxa1bxAbxa2b其中，x是終結(jié)符組成的字符串，A是非終結(jié)符，且a1a2，因此體現(xiàn)在推導(dǎo)樹則一定不同?，F(xiàn)在定義，一個字符串具有多個（超過1個）推導(dǎo)樹當且僅當具有多個最左推導(dǎo)。注意我們也可以采用最右原則，關(guān)鍵是消除一些細節(jié)上的差異。我們發(fā)現(xiàn)許多CFG生成的字符串具有多個“本質(zhì)”不同的生成辦法。定義6.3 CFG G是歧義的（ambiguous）當且僅當存在一個xL(G)具有多個推導(dǎo)樹（或最左推導(dǎo)過程）。顯然，上面定義的歧義很接近我們?nèi)粘?yīng)用的自然語言句子的歧義。比如一個記者用到的標題“Disabled Fly to See Carter”，如果它出現(xiàn)在美國第39任總統(tǒng)當政時期，對應(yīng)的推導(dǎo)是：S .。但通常更多的解釋是：S .。此處，正確理解一個新聞標題的關(guān)鍵是選擇相應(yīng)的語法推導(dǎo)。例子6.10 回到例子6.5給出的代數(shù)表達式的CFG，我們考察了字符串a(chǎn)+(a*a)/a-a具有的本質(zhì)不同的推導(dǎo)過程。分析：本例的CFG形如，SS+S | S-S | S*S | S/S | (s) | a，看一個簡單的例子“a+a+a”，存在兩個不同的最左推導(dǎo)：SS+Sa+Sa+S+Sa+a+Sa+a+aSS+SS+S+Sa+S+Sa+a+Sa+a+a它們對應(yīng)的推導(dǎo)樹分別見圖6-3a和圖6-3b。如果結(jié)合具體的代數(shù)運算符含義，兩者最終含義是相同的，前者等同于a+(a+a)，后者等同于(a+a)+a?？梢娎ㄌ柧哂邢缌x的作用。從例子6.10容易看到，凡是具有形如AAaA的產(chǎn)生式的CFG都是有歧義的。然而有很多種引入歧義的方式，有時很難發(fā)現(xiàn)并排除它們。例子6.11 程序設(shè)計語言歧義的一個標準的例子是“dangling else”，考慮下面的產(chǎn)生式：if () | if () else |現(xiàn)在考慮聲明：if (expr1) if (expr2) f(); else g();根據(jù)上面的產(chǎn)生式，可以有兩個推導(dǎo)樹，一種將else看成與第一個if相關(guān)，另一種將else看成與第二個if相關(guān)。參見圖6-4a和圖6-4b。在C語言中，為了消除歧義，常常引入括號，如，if (expr1) if (expr2) f(); else g();if (expr1) if (expr2) f(); else g();或者修改文法，如 | if () else | if () | if () else 目前我們無法證明為什么新文法消除了歧義，但可以直觀地解釋。生成的都是if-else匹配的情況，生成的是if-else不匹配的情況。而且出現(xiàn)在else之前的都是，因此不匹配的情況出現(xiàn)在else之后，即else總是與最接近的if匹配。程序設(shè)計語言Modula-2使用了類似括號的方法消除歧義，IF THEN END |IF THEN ELSE END |在上面文法下，圖6-4a和圖6-4b對應(yīng)的字符串分別是IF A1 THEN IF A2 THEN S1 END ELSE S2 ENDIF A1 THEN IF A2 THEN S1 ELSE S2 END END6.5 一個無歧義的代數(shù)表達式盡管有些CFL是“內(nèi)在”歧義的，即只能由有歧義的CFG生成，但通常意義的歧義是針對文法而言，而不是語言。如果一個CFG是歧義的，常常可能存在（也是我們希望發(fā)現(xiàn)的）一個與其相當?shù)姆瞧缌x的CFG，本節(jié)我們消除例子6.5給出的代數(shù)表達式的文法的歧義。為了簡化問題，我們僅僅使用兩個運算符“+”和“*”，得到產(chǎn)生式如下，SS+S | S*S | (S) | a如果消除了這兩個運算符的歧義，能夠類似地消除“-”和“/”的歧義。正如前面講到，產(chǎn)生式SS+S能夠帶來歧義，我們需要消除這種類型的產(chǎn)生式，同時保持各種運算符的優(yōu)先級，比如*的優(yōu)先級高于+，且位于前面的+優(yōu)先級高于后面的+。新文法G1的產(chǎn)生式如下，SS+T | TTT*F | FF(S) | a需要證明兩個方面：1）G1與G相當；2）G1沒有歧義。為了證明方便，G1中的起始符號改寫成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)。對屬于L(G1)的字符串x的長度使用數(shù)學(xué)歸納法。1. 歸納基礎(chǔ)，x=a時，顯然xL(G)2. 歸納推理，設(shè)k=1，每個屬于L(G1)、長度=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的長度都=1，對每個yL(G)且|y|=k，yL(G1)也成立，要證明如果xL(G)且|x|=k+1，則xL(G1)。設(shè)x在G上的第一步推導(dǎo)是S(S)，對應(yīng)x=(y)，則|y|=1，任何一個從S1、T、F推導(dǎo)出來的長度=1，如果AGnx，則AG1*x。對n使用數(shù)學(xué)歸納法。1. 歸納基礎(chǔ)，n=1，即AG1x，則P中存在Ax，x是非空的，因此P1中也有Ax，則AG11x，AG1*x。2. 歸納推理，n=k時所有|x|=k的x滿足上式。要證明對|x|=k+1的x也滿足上式。設(shè)AG*x的第一步是AX1X2.Xn，對應(yīng)x=x1x2.xn。其中Xi=xi或XiG=1，如果AG1nx，則AG*x。類似可證。顯然，消除文法的空產(chǎn)生式，需要添加大量新的產(chǎn)生式（很類似，消除FA的空轉(zhuǎn)移需要添加大量新的轉(zhuǎn)移）。于是存在一個問題，添加的新產(chǎn)生式是否帶來了新的不好的性質(zhì)。部分的回答是算法6.1不會帶來歧義，即如果原來文法G是非歧義的，則處理后的文法G1也是非歧義的。證明并不困難，參見練習(xí)6.38。單一產(chǎn)生式的消除類似空產(chǎn)生式的消除。比如要刪除AB（更普遍地，A*B），就要對所有Ba，添加Aa。為了簡化討論，我們消除單一產(chǎn)生式的工作基礎(chǔ)是無空產(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 給定一個沒有空產(chǎn)生式的CFG G=(V, , S, P)，構(gòu)造一個沒有單一產(chǎn)生式的文法G1=(V, , S, P1)。1. 初始化P1=P2. 對每個AV，發(fā)現(xiàn)A的可推導(dǎo)集3. 對A的可推導(dǎo)集的每個元素B，如果存在Ba，則添加產(chǎn)生式Aa到P14. 刪除P1中的所有單一產(chǎn)生式定理6.5 設(shè)G是沒有空產(chǎn)生式CFG，G1是算法6.2得到的文法，則G1沒有單一產(chǎn)生式，且L(G1)=L(G)。證明：略，參見練習(xí)6.37。值得指出的是，如果文法G是無歧義的，則文法G1也是無歧義的。例子6.13 G是生成代數(shù)表達式的文法，它的產(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)生式，對產(chǎn)生式的格式添加更多的限制也是有用的。已經(jīng)提出了多種產(chǎn)生式的“規(guī)范形式”，本節(jié)介紹其中的一種，Chomsky范式。定義6.6 一個CFG的每個產(chǎn)生式符合下面兩個形式中的一種，則稱為Chomsky范式（Chomsky normal form, CNF）：ABC和Aa。其中，A、B、C是非終結(jié)符，a是終結(jié)符。將一個文法G轉(zhuǎn)換成CNF需要三個步驟。第一步應(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é)符a引入一個相應(yīng)的非終結(jié)符Xa，添加產(chǎn)生式Xaa，原產(chǎn)生式中的a都替換成Xa（除了Aa這類產(chǎn)生式）。文法G2已經(jīng)很接近Chomsky范式了，產(chǎn)生式的右部要么全是非終結(jié)符，要么是單個終結(jié)符。第三步，將G2中右部長度超過2的產(chǎn)生式用多個產(chǎn)生式替換。定理6.6 對于每個CFG G都存在一個符合Chomsky范式的CFG G，使得L(G)=L(G)-L。證明：略。例子6.14 CFG G的產(chǎn)生式如下：SAACDAaAb | LCaC | aDaDa | bDb | L構(gòu)造G對應(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