第二章前后文無關(guān)文法和語言

1、第二章第二章 u 在在20世紀(jì)世紀(jì)50年代，年代，N.Chomsky首先對語言首先對語言的描述問題進(jìn)行了探討。他提出了一種用來描的描述問題進(jìn)行了探討。他提出了一種用來描述語言的數(shù)學(xué)系統(tǒng)，并以此定義了四類性質(zhì)不述語言的數(shù)學(xué)系統(tǒng)，并以此定義了四類性質(zhì)不同的語言，稱為同的語言，稱為語言（文法）的語言（文法）的ChomskyChomsky分類分類。u 人們把用一組數(shù)學(xué)符號和規(guī)則來描述語言的方人們把用一組數(shù)學(xué)符號和規(guī)則來描述語言的方式稱為形式描述，把所用的數(shù)學(xué)符號和規(guī)則稱式稱為形式描述，把所用的數(shù)學(xué)符號和規(guī)則稱為為形式語言形式語言。u 目前，目前，形式語言與自動機理論形式語言與自動機理論已成為計算機科已

2、成為計算機科學(xué)中的一個重要分支。學(xué)中的一個重要分支。u 本章將初步介紹形式語言中的某些基本概念和本章將初步介紹形式語言中的某些基本概念和知識，重點是與編譯技術(shù)密切相關(guān)的一些術(shù)語知識，重點是與編譯技術(shù)密切相關(guān)的一些術(shù)語和概念，諸如和概念，諸如文法文法、語言語言、句子句子、句型句型、短語短語、句柄句柄以及以及句型分析句型分析等。等。2.1 u 首先，我們確定一個概念：什么是語言？首先，我們確定一個概念：什么是語言？u 據(jù)統(tǒng)計，目前在世界各地，人們所使用的語言達(dá)據(jù)統(tǒng)計，目前在世界各地，人們所使用的語言達(dá)27002700多種。多種。u WebsterWebster的定義：的定義：“為相當(dāng)大地區(qū)的公眾所

3、懂得并使用的為相當(dāng)大地區(qū)的公眾所懂得并使用的話話，以及組成這些，以及組成這些話話的方法的統(tǒng)一體的方法的統(tǒng)一體”u 上述定義對于建立語言的數(shù)學(xué)理論的目的而言不夠精確。上述定義對于建立語言的數(shù)學(xué)理論的目的而言不夠精確。u 所以，有人又將語言定義為：所以，有人又將語言定義為：“某一字母表上符號串（句某一字母表上符號串（句子）的集合子）的集合”u 此定義仍需精確化。因為：此定義仍需精確化。因為：1 1）還應(yīng)為所定義的句子）還應(yīng)為所定義的句子提供一種結(jié)構(gòu)性的描述（提供一種結(jié)構(gòu)性的描述（語法規(guī)則語法規(guī)則）；2 2）最好能再提供一種手段，以便）最好能再提供一種手段，以便能準(zhǔn)確地判別什么是該語言能準(zhǔn)確地判別什

4、么是該語言中的正確句子（中的正確句子（即識別方法、分析方法等即識別方法、分析方法等）。2.2 文法和語言的定義文法和語言的定義2.2.1 2.2.1 基本概念和術(shù)語基本概念和術(shù)語1。字母表（符號表、符號集）字母表（符號表、符號集） 由若干元素（符號、字母）組成的有限非由若干元素（符號、字母）組成的有限非空集合?？占?。例：=a，b，c2。符號串符號串 用字母表中符號所組成的任何有限序列。用字母表中符號所組成的任何有限序列。 例：a, aa, ac, abc，.符號串的長度符號串的長度 = 符號串中所含符號的個數(shù)符號串中所含符號的個數(shù)例：例：aba的長度為的長度為3。記為：。記為：|aba|=3

5、空串空串 不含任何符號的符號串，記為不含任何符號的符號串，記為 。顯然，。顯然，| |= 0。本課約定本課約定 用用A、B、C、 等表示字母表或符號串集；用等表示字母表或符號串集；用a,b,c,S,T,U 等等表示符號；用表示符號；用s,t,u,x,y,z, , , 等表示符號串。等表示符號串。任何程序語言都有自己的字母表。1.計算機語言:由符號“0”和“1”組成的字母表: =0，1 2. Pascal語言字母表：=AZ, az, 09, +, -, *, /, , :, ,”,;，.， , (, ), , , , 3. C語言字母表：=AZ, az, 09, +, -, *, /, ,_,&

6、amp;, , ,:,”,;，.，?, (, ), , ,空格,!,#,% 2.2.1 基本概念和術(shù)語（續(xù)）3.符號串的前（后）綴及子串符號串的前（后）綴及子串 設(shè)設(shè) , , ，x是符號串，若是符號串，若x= ,則稱則稱 是是x的的子串子串；特別地，當(dāng)；特別地，當(dāng) = （ = ）時，稱）時，稱 是是x的的前（后）綴前（后）綴。（符號串s=banana）前 綴：,b,ba,ban,bana,banan,banana后 綴：banana,anana,nana,ana,na,a, 子 串: banana,anana,banan,anan, 4.符號串相等符號串相等：若x、y是集合上的兩個符號串，則x

7、y iff（當(dāng)且僅當(dāng)）組成x的每一個符號和組成y的每一個每一個符號依次相等。 6.符號串集合的乘積運算符號串集合的乘積運算：令A(yù)、B為符號串集合，定義AB xy |xA,yB例：Aa,b,B=c,d, AB= ？ ac，ad，bc，bd 因為xxx，所以A=A=A5.符號串的聯(lián)接符號串的聯(lián)接：若x、y是定義在是上的符號串，且xXY，yYX，則x和y的聯(lián)接 xyXYYX也是上的符號串。 注意：一般xyyx，而xx2.2.1 基本概念和術(shù)語（續(xù)）8.8.符號串集合的閉包運算符號串集合的閉包運算：設(shè)A是符號串集合，定義 A A1 A2 A3 An 稱為集合A的正閉包。 A* A0 A稱為集合A的閉包

8、。例：A=x,y A？ A* ？7. 符號串集合的冪運算符號串集合的冪運算：有符號串集合A，定義A0 =,A1=A,A2=AA,A3=AAA, AnAn-1A=AAn-1 ，n0 x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A1 A2 A3, x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A0 A1 A2 A32.2.1 基本概念和術(shù)語（續(xù)） 為什么對符號、符號串、符號串集合以及它們?yōu)槭裁磳Ψ?、符號串、符號串集合以及它們的運算感興趣？的運算感興趣？若若A為某語言的基本字符集為某語言的基本字符集 Aa,b,z,0,1,9, +,_/, (

9、, ), =B為單詞集為單詞集 B =begin, end, if, then,else,for, 則則B A* 。語言的句子是定義在語言的句子是定義在B上的符號串。上的符號串。若令若令C為句子集合，則為句子集合，則C B * , 程序程序 C形式語言：是一個字母表上按照某種規(guī)則構(gòu)成的所有的串的集合，它用文法和自動機所描述的沒有語義的語言。（形式語言是數(shù)學(xué)范疇）2.2.2 u我們從我們從“產(chǎn)生語言產(chǎn)生語言”的角度的角度出發(fā)出發(fā),討論文法和語言的形式討論文法和語言的形式定義。定義。u產(chǎn)生語言產(chǎn)生語言指制定出有限條指制定出有限條規(guī)則，借助它們就能產(chǎn)生出規(guī)則，借助它們就能產(chǎn)生出些語言的句子。些語言的

10、句子。u我們以幾個英語句子構(gòu)成的我們以幾個英語句子構(gòu)成的語言為例進(jìn)行討論。并設(shè)每語言為例進(jìn)行討論。并設(shè)每個句子都是個句子都是“主主-謂謂-賓賓”結(jié)結(jié)構(gòu)。構(gòu)。u語法規(guī)則見右。其中，每個語法規(guī)則見右。其中，每個用用括起來的部分是所要定括起來的部分是所要定義語言中的一個義語言中的一個語法實體語法實體（稱為語法單位、語法結(jié)構(gòu)、（稱為語法單位、語法結(jié)構(gòu)、語法范疇、語法變量等語法范疇、語法變量等）。）?！?=”是用于定義語法結(jié)構(gòu)是用于定義語法結(jié)構(gòu)的符號，其含義（并讀作）的符號，其含義（并讀作）“定義為定義為”.語法規(guī)則也稱為語法規(guī)則也稱為產(chǎn)生式產(chǎn)生式(Production):= := the :=:=:=

11、monkey:=banana:=eat:=has:= the:= a2.2.2 u 現(xiàn)在，我們討論如何用上述規(guī)則現(xiàn)在，我們討論如何用上述規(guī)則推導(dǎo)推導(dǎo)出相應(yīng)語言的全部出相應(yīng)語言的全部句子句子。u推導(dǎo)推導(dǎo) 從語言最大的一個從語言最大的一個語法范疇語法范疇（本例中是（本例中是 ）開始，反復(fù)用語法規(guī)則中開始，反復(fù)用語法規(guī)則中“:=:=” ” 右側(cè)的符號串取代其左側(cè)右側(cè)的符號串取代其左側(cè)符號，直到所得的符號串中不再含有可被替換符號，直到所得的符號串中不再含有可被替換語法范疇語法范疇。每。每次替換稱為一步（直接）次替換稱為一步（直接）推導(dǎo)推導(dǎo)，并用符號，并用符號“”表示。例如，表示。例如，u 我們首先用規(guī)

12、則我們首先用規(guī)則進(jìn)行第一步推導(dǎo)進(jìn)行第一步推導(dǎo)( (derivationderivation) )，就可得到，就可得到 ，記為記為 u 所得的符號串所得的符號串 含有兩個含有兩個語法范疇語法范疇，可，可對其中任一個（例如對對其中任一個（例如對 ）進(jìn)行新的）進(jìn)行新的推導(dǎo)推導(dǎo)（替換）：（替換）：u u 重復(fù)上述過程，可得到一個推導(dǎo)序列（見下頁）。重復(fù)上述過程，可得到一個推導(dǎo)序列（見下頁）。用語法規(guī)則進(jìn)行推導(dǎo)所得的推導(dǎo)序列推導(dǎo)步驟推導(dǎo)步驟 所用規(guī)則所用規(guī)則所得的符號串所得的符號串 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey ea

13、t a 8 the monkey eat a banana2.2 .2 u 從前面的推導(dǎo)看，從出發(fā)，經(jīng)8 8步推導(dǎo)步推導(dǎo)得到了一個英語句子。故前面的推導(dǎo)稱為長度為長度為8 8的推導(dǎo)的推導(dǎo)。u 若不關(guān)心推導(dǎo)的中間過程，可將從一符號串到另一符號串的推導(dǎo)用記號名詞冠詞動詞句子步的推導(dǎo)記為例如上例中經(jīng)過表示monkeythe5,u 在前面的語法規(guī)則定義中，有些語法范疇（如、）有若干條不同的規(guī)則來定義它，為簡明起見，我們可以將它們寫在同一個左部語法范疇下，將其定義值用符號“ ”（讀作）隔開。如、 、 的定義規(guī)則可簡記為u 前面的語法規(guī)則可以產(chǎn)生16個不同的句子，。u 應(yīng)指出，所產(chǎn)生的句子中，有些句子的含

14、義是荒謬的（如 the banana eat a monkey和the banana eat the banana等）。然而，若不考慮語義，則我們就必須承認(rèn)它們是語法上合法的句子。 定義1. 文法GS=(VN，VT，P，S) VN ：非終結(jié)符號集 VT ：終結(jié)符號集 P：產(chǎn)生式或規(guī)則的集合 S：開始符號（識別符號） SVNVVN VT稱為文法的字匯表規(guī)則：U xU VN, xV*非終結(jié)符是指在文法的語法范疇，出現(xiàn)在產(chǎn)生式P中，通常用大寫字母或用大寫字母或用“”括起來的符號串括起來的符號串表示，終結(jié)符是指不需要進(jìn)一步定義的基本符號，通常用小寫字母小寫字母表示文法的定義文法的定義P = ； ； ；

15、 0； 1； 9；E = ；例：無符號整數(shù)的文法：G=（Vn，Vt，P，E）Vn, Vt = 0,1,2,3,9 我 我我是 我是 我是大學(xué)生 | 你你| |我我| |他他 王民王民| |大學(xué)生大學(xué)生| |工人工人| |英語英語 是是| |學(xué)習(xí)學(xué)習(xí) | 推導(dǎo)方法：推導(dǎo)方法：從一個要識別的符號開始推導(dǎo)，即用相應(yīng)規(guī)則的右部來替代規(guī)則的左部，每次僅用一條規(guī)則去進(jìn)行推導(dǎo)。 定義：設(shè)文法GS=(VN，VT，P，S)，若UuP，x、yV* ，則xUyV*若用規(guī)則Uu 的右部u替換U，即xuy V*, 則稱xuy是xUy的直接推導(dǎo)。xUy是xuy的直接規(guī)約。記為xUy=xuy(推導(dǎo)) 和 xuy xUy(規(guī)

16、約)推導(dǎo)的形式定義推導(dǎo)的形式定義= 1 1 0= 當(dāng)符號串已沒有非終結(jié)符號時，推導(dǎo)就必須終止。例如：例如：G (1) ； (2) (3) (4) 0;0;(5) 1;1; (13) 9;9; 定義3：文法G，U0,U1,U2,，Un V+ if v= U0 = U1 = U2 = = Unw (n0) 則稱v推導(dǎo)出w,或w規(guī)約到v，或v經(jīng)+推導(dǎo)出w，或w+規(guī)約到v，分別記為： v w 或w v=例：= = = =1 =1 0即 10= 定義4：文法G，v，w V+ if v w ,或v=w，則v w則稱v經(jīng)*推導(dǎo)出w，或w經(jīng)*規(guī)約到v，= *= 定義6：文法GS （1）句型句型：x是句型 S

17、x,且xV*；（2）句子句子：x是句子 S x, 且xVT*；（3）語言語言：L（GS）=x| xVT*, S x ；+文法GS所產(chǎn)生的所有句子的集合 形式語言理論可以證明以下兩點： （1）G L（G）； （2）L(G)G1，G2，Gn； 已知文法，求語言，通過推導(dǎo)； 已知語言，構(gòu)造文法，無形式化方法，更多是憑經(jīng)驗。*語言的形式定義語言的形式定義例：abna|n1,構(gòu)造其文法 G1S： SaBa, Bb|bB G2S： SaBa, Bb|Bb 定義7. G和G是兩個不同的文法，若 L(G) = L(G) , 則G和G為等價文法。1.遞歸規(guī)則遞歸規(guī)則：規(guī)則右部有與左部相同的符號 對于 U xUy

18、 若x=,即U Uy，左遞歸； 若y=,即U xU，右遞歸； 2.遞歸文法遞歸文法：文法G，存在U Vn if U=U, 則G為遞歸文法； if U=U, 則G為左遞歸文法； if U=U, 則G為右遞歸文法；+2.2.4 文法的遞歸性文法的遞歸性4. 遞歸文法的優(yōu)點：可用有窮條規(guī)則，定義無窮語言 例：對于前面給出的無符號整數(shù)的文法是有遞歸文法，用13條規(guī)則就可以定義出所有的無符號整數(shù)。若不用遞歸文法，那將要用多少條規(guī)則呢？!3. 左遞歸文法的缺點：不能用自頂向下的方法來進(jìn)行語法分析會造成死循環(huán)（后面將詳細(xì)論述）2.3 句型的分析句型的分析u 句型的分析句型的分析：構(gòu)造一算法，用以判斷所給的符

19、號串：構(gòu)造一算法，用以判斷所給的符號串是否為某文法的句型（句子）是否為某文法的句型（句子）u 常見分析方法有常見分析方法有自頂向下分析自頂向下分析和和自底向上分析自底向上分析兩類；兩類；u 自頂向下自頂向下 從開始符出發(fā)試圖推導(dǎo)出給定的符號串；從開始符出發(fā)試圖推導(dǎo)出給定的符號串；u 自底向上自底向上 推導(dǎo)的逆過程（稱歸約）：從已給的符推導(dǎo)的逆過程（稱歸約）：從已給的符號串出發(fā)，試圖將其歸約為開始符。號串出發(fā)，試圖將其歸約為開始符。2.3.1 規(guī)范推導(dǎo)和規(guī)范歸約規(guī)范推導(dǎo)和規(guī)范歸約u 對于一文法而言，從開始符到某句型的對于一文法而言，從開始符到某句型的推導(dǎo)過程可能不唯一推導(dǎo)過程可能不唯一。例如，文

20、法例如，文法GE中從中從 E 到到 i+i*i 的推導(dǎo)有：的推導(dǎo)有：(1)E E+T E+T*F T+T*F T+T*i F+T*i i+T*i i+F*ii+i*i(2)E E+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*F i+i*i(3)E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i(4) 規(guī)范推導(dǎo)u 最左（右）推導(dǎo)最左（右）推導(dǎo)：在推導(dǎo)序列的每一步直接推導(dǎo)中，被替在推導(dǎo)序列的每一步直接推導(dǎo)中，被替換的總是當(dāng)前句型中最左（右）的非終結(jié)符。換的總是當(dāng)前句型中最左（右）的非終結(jié)符。u 形式上，形式上，從符號串從符號串

21、 到符號串到符號串 的推導(dǎo)序列的推導(dǎo)序列u * xUy xuy * 總有總有 x VT* (y VT*) 時，稱為時，稱為最左（右）推導(dǎo)最左（右）推導(dǎo)u 定義：最左（右）推導(dǎo)所得句型稱為定義：最左（右）推導(dǎo)所得句型稱為左（右）句型；左（右）句型；最右最右推導(dǎo)推導(dǎo)稱為稱為規(guī)范推導(dǎo)規(guī)范推導(dǎo)；右句型右句型稱為稱為規(guī)范句型規(guī)范句型。最左推導(dǎo)：若符號串中有兩個以上的非終結(jié)符時，先推左邊的。最右推導(dǎo)：若符號串中有兩個以上的非終結(jié)符時，先推右邊的。最右推導(dǎo)稱為規(guī)范推導(dǎo)最右推導(dǎo)稱為規(guī)范推導(dǎo)句子、句型的推導(dǎo)方法u 每個每個句子句子都有相應(yīng)的最左和最右推導(dǎo)，因此，都有相應(yīng)的最左和最右推導(dǎo)，因此，句子即是句子即是左

22、句型左句型也是也是右句型右句型（規(guī)范句型）（規(guī)范句型）u 并不是每個句型都有最左和最右推導(dǎo)并不是每個句型都有最左和最右推導(dǎo)u 例如，例如，E E + + E+i E+i* *T T即不是左句型，也不是右句型即不是左句型，也不是右句型u 對于給定的符號串對于給定的符號串w，采用，采用自頂向下自頂向下的分析來判斷的分析來判斷w是否為是否為L(GS)的句子的常見方法是：的句子的常見方法是：試圖建立從開始符試圖建立從開始符 S到到w最左最左推導(dǎo)推導(dǎo):S* w u顯然，每步推導(dǎo)時，對應(yīng)于最左非終結(jié)符相應(yīng)的產(chǎn)生式可能會顯然，每步推導(dǎo)時，對應(yīng)于最左非終結(jié)符相應(yīng)的產(chǎn)生式可能會有多個，若無特殊的辦法，只能一個一

23、個地試探。因此，推導(dǎo)有多個，若無特殊的辦法，只能一個一個地試探。因此，推導(dǎo)過程可能是過程可能是帶回溯帶回溯的的。u 為提高效率，就應(yīng)盡量避免回溯為提高效率，就應(yīng)盡量避免回溯自底向上的語法分析自底向上的語法分析u 就是從已給的符號串就是從已給的符號串w出發(fā)，試圖以相反的方向為出發(fā)，試圖以相反的方向為w建立建立一個規(guī)范推導(dǎo)，最終得到文法的開始符。一個規(guī)范推導(dǎo)，最終得到文法的開始符。u 推導(dǎo)的逆過程稱作推導(dǎo)的逆過程稱作歸約歸約，它是把當(dāng)前的符號串，它是把當(dāng)前的符號串中的構(gòu)成中的構(gòu)成文法某個產(chǎn)生式文法某個產(chǎn)生式A右部的子串右部的子串 替換成產(chǎn)生式的左部符號替換成產(chǎn)生式的左部符號A，得到一個新的符號串，

24、得到一個新的符號串 A 。這樣的一步動作，稱為進(jìn)行。這樣的一步動作，稱為進(jìn)行了一步了一步歸約歸約。u 例如，符號串例如，符號串F+i*i中的中的F可按產(chǎn)生式可按產(chǎn)生式TF歸約為歸約為T，從而得，從而得到新的符號串到新的符號串T+i*i。u 若從給定的符號串若從給定的符號串w出發(fā)，一步步地將其歸約，最終得到文出發(fā)，一步步地將其歸約，最終得到文法的開始符號，則說明法的開始符號，則說明w是該文法定義的一個句子。歸約成是該文法定義的一個句子。歸約成功，否則，歸約失敗。功，否則，歸約失敗。u 若歸約的每一步都?xì)w約的是當(dāng)前符號串中最左邊的某產(chǎn)生式若歸約的每一步都?xì)w約的是當(dāng)前符號串中最左邊的某產(chǎn)生式的右部，

25、則稱該歸約是的右部，則稱該歸約是規(guī)范歸約規(guī)范歸約（即（即最左歸約最左歸約）。）。u 規(guī)范歸約是規(guī)范推導(dǎo)的逆過程規(guī)范歸約是規(guī)范推導(dǎo)的逆過程。由上表可以看出，歸約過程是由上表可以看出，歸約過程是最左最左歸約，它恰好是歸約，它恰好是規(guī)規(guī)范推導(dǎo)的逆過程范推導(dǎo)的逆過程。這正是把最左歸約定義為規(guī)范歸約。這正是把最左歸約定義為規(guī)范歸約的原因。的原因。關(guān)于歸約的一點說明u 注意，前面例子中歸約的第五步中，當(dāng)前的符號串為注意，前面例子中歸約的第五步中，當(dāng)前的符號串為 E+T*i，除了可將除了可將i歸約成歸約成F外，還可將外，還可將E+T或或T歸約成歸約成E，分別得到符號，分別得到符號串串E*i和和E+E*i。但

26、是，若真按這兩個方案進(jìn)行歸約，則當(dāng)我。但是，若真按這兩個方案進(jìn)行歸約，則當(dāng)我們把其歸約成們把其歸約成E*E或或E+E*E時，就再也歸約不下去了。這就告時，就再也歸約不下去了。這就告訴我們在第五步時，唯一正確的歸約是將訴我們在第五步時，唯一正確的歸約是將i歸約為歸約為F，也就是說，也就是說，i是唯一可被歸約的最左子串。是唯一可被歸約的最左子串。u 那么，對于規(guī)范歸約的每一步，如何確定符號串中的當(dāng)前應(yīng)被那么，對于規(guī)范歸約的每一步，如何確定符號串中的當(dāng)前應(yīng)被歸約的最左子串呢？歸約的最左子串呢？2.3.2 2.3.2 語法樹和二義性語法樹和二義性u語法樹用于直接地描述一個句型右句子的語法結(jié)構(gòu)語法樹用于

27、直接地描述一個句型右句子的語法結(jié)構(gòu)u語法樹是一有向樹（連通的）語法樹是一有向樹（連通的）1）有且僅有一個無任何前驅(qū)的結(jié)點，稱為根）有且僅有一個無任何前驅(qū)的結(jié)點，稱為根 （S）；）；2）除根外，每個結(jié)點恰有一個直接前驅(qū)；）除根外，每個結(jié)點恰有一個直接前驅(qū)；3）對于任一結(jié)點）對于任一結(jié)點m，從根到從根到m可達(dá)可達(dá);4) 每個結(jié)點的后繼是有序的（從左到右）每個結(jié)點的后繼是有序的（從左到右）設(shè)設(shè)G=(VN,VT,P,S)是一文法，則滿足下述條件的樹稱為語法樹：是一文法，則滿足下述條件的樹稱為語法樹：1）每個結(jié)點有一標(biāo)記）每個結(jié)點有一標(biāo)記X， X V；2）根的標(biāo)記為）根的標(biāo)記為S（開始符）；（開始符）；

28、3）若結(jié)點）若結(jié)點X有后繼，則有后繼，則X VN；4）A有有k個后繼，自左至右為個后繼，自左至右為X1, X2, , Xk，則，則A X1X2Xk P語法樹的所有葉結(jié)點自語法樹的所有葉結(jié)點自左至右排列構(gòu)成了文法左至右排列構(gòu)成了文法G的一個句型的一個句型 對一語法樹而言，其構(gòu)對一語法樹而言，其構(gòu)造過程不同對應(yīng)了不同造過程不同對應(yīng)了不同的推導(dǎo)（歸約）過程的推導(dǎo)（歸約）過程 例如，文法例如，文法GE的句型的句型 i+i*i相應(yīng)的語法樹見右圖相應(yīng)的語法樹見右圖。EE+TTFiT*FFiiu 存在這樣的文法存在這樣的文法G，其某個句子，其某個句子w L(G),可對應(yīng)結(jié)構(gòu)不同的可對應(yīng)結(jié)構(gòu)不同的語法樹，即語

29、法樹，即w對應(yīng)了多個不同的最左（右）推導(dǎo)，這類文法稱對應(yīng)了多個不同的最左（右）推導(dǎo)，這類文法稱為為。u 例如，例如，G3E：EE+E|E*E|(E)|i 的句型的句型及文法及文法u Cif B then C|if B then C else CC S的句型：的句型：if B1 then if B2 then S1 else S2u 上面兩個句型均有兩個不同的語法推導(dǎo)樹（見下頁），所以，上面兩個句型均有兩個不同的語法推導(dǎo)樹（見下頁），所以，它們是二義性文法它們是二義性文法文法的二義性EEEEE+*iiiEEEEE+*iiiif B1 then C else C S1 S2Cif B2 then

30、CCif B1 then CS1 S2if B1 then C else C關(guān)于二義性文法u 應(yīng)指出應(yīng)指出，二義性，二義性是一種常見的語法現(xiàn)象，然而，對于編譯程序是一種常見的語法現(xiàn)象，然而，對于編譯程序而言，而言，二義性文法二義性文法是是有害有害的。的。u 為解決二義性文法帶來的不確定性問題，通常的方法一是為解決二義性文法帶來的不確定性問題，通常的方法一是修改修改文法文法，例如，文法例如，文法G3可用本章（可用本章（P20 (2.2)式式）定義的文法）定義的文法G2E取代，而取代，而G2不是二義性的不是二義性的。u 二是二是利用附加條件利用附加條件。例如，例如， i+ii+i* *i i的歸約

31、過程中，若規(guī)定的歸約過程中，若規(guī)定* *比比+ +優(yōu)先級高，則可強制性地讓系統(tǒng)先按優(yōu)先級高，則可強制性地讓系統(tǒng)先按E E* *E E進(jìn)行歸約，而不是先進(jìn)行歸約，而不是先按按E+EE+E進(jìn)行歸約；進(jìn)行歸約；又比如，若又比如，若強制規(guī)定強制規(guī)定elseelse只能和距其最近的只能和距其最近的尚未被匹配的尚未被匹配的thenthen進(jìn)行匹配，就可解決進(jìn)行匹配，就可解決elseelse懸空的問題。懸空的問題。2.3.3 短語和句柄短語和句柄u問題問題: : 在自底向上在自底向上( (簡記為簡記為 ) )的語法分析中的語法分析中, ,對于每一步直接歸約對于每一步直接歸約, ,應(yīng)如何正確地確定當(dāng)應(yīng)如何正確

32、地確定當(dāng)前句型中應(yīng)被歸約的前句型中應(yīng)被歸約的最左子串最左子串? ?u考慮文法考慮文法G G2 2EE的句型的句型 = E+T= E+T* *F+iF+i, ,從開始符從開始符E E 推導(dǎo)出推導(dǎo)出 的語法樹見右圖的語法樹見右圖u該樹中含有若干子樹該樹中含有若干子樹, ,如如T T(2)(2)為根的子樹對應(yīng)為根的子樹對應(yīng)的葉結(jié)點為的葉結(jié)點為T T(3)(3)* *F F(3),(3),由于它是一直接子樹由于它是一直接子樹, ,文文法中必有產(chǎn)生式法中必有產(chǎn)生式T-TT-T* *F F; ;因此因此, ,稱稱T T* *F F是句型是句型 相對于產(chǎn)生式相對于產(chǎn)生式T-TT-T* *F F的的直接短語直

33、接短語. .同理同理, ,F F(1)(1)對應(yīng)的對應(yīng)的直接短語直接短語為為i i. .u以以E E(1)(1)為根的子樹相應(yīng)的葉結(jié)點為為根的子樹相應(yīng)的葉結(jié)點為 E E(2)(2)+T+T(3)(3)* *F F(3)(3), ,所以所以, ,稱為句型稱為句型 相對于非終結(jié)相對于非終結(jié)符符E E 的的短語短語. .同理同理, ,i i是相對于是相對于T T(1)(1)的的短語短語短語、直接短語及句柄的定義短語、直接短語及句柄的定義u例如，對句型例如，對句型 = E+T= E+T* *F+iF+i，由定義，有：由定義，有：(1)E(1)E* * E+T+i( E+T+i( =E+,A=T, =E

34、+,A=T, =+i)=+i)及及T TT T* *F(=F(= ),),故故T T* *F F是是 相對于產(chǎn)生相對于產(chǎn)生式式T-TT-T* *F F的的直接短語直接短語; ;(2)E(2)E* * E+T E+T* *F+F FF+F Fi,i,i i是是 相對于產(chǎn)生式相對于產(chǎn)生式F-iF-i的的直接短語直接短語; ;(3)E(3)E* * E+i E+i與與 E E + + E+T E+T* *F,F,E+TE+T* *F F是是相對于非終結(jié)符相對于非終結(jié)符E E的的短語短語; ;(4)E(4)E* * E E及及E E* * E+T E+T* *F+i(= F+i(= ), ), 是是

35、相對于相對于E E的的短語短語注注: :由定義可知由定義可知, ,直接短語也是短語直接短語也是短語, ,但短語不一定是直接短語但短語不一定是直接短語. .)()(),(,8 . 2*直接短語的短語產(chǎn)生式相對于非終結(jié)符是句型則稱及有對于若的一個句型其中是文法設(shè)定義AAAAASVAVVSGN歸約時被替換子串的選擇u從句型 =E+T=E+T* *F+iF+i的語法樹可知,E+T絕不是它的一個直接短語,因為雖然E-E+T是G2的一個產(chǎn)生式,但不存在從E到E*F+i的推導(dǎo),所以,當(dāng)判斷一符串是否為某一句型的短語時,須檢查定義2.8的兩個條件是否同時滿足.u采用采用 分析時分析時, ,每步每步歸約歸約就是

36、將一個產(chǎn)生式就是將一個產(chǎn)生式右部右部替換替換其其左部左部, ,也就是把也就是把該句型的語法樹中的該句型的語法樹中的一棵直接子樹的末端結(jié)點剪去一棵直接子樹的末端結(jié)點剪去. .即每次歸約的符即每次歸約的符號串必是當(dāng)前句型的一個直接短語號串必是當(dāng)前句型的一個直接短語. .u但是但是, ,對一句型而言對一句型而言, ,其其直接短語可能不唯一直接短語可能不唯一. .為了讓分析能夠機械地為了讓分析能夠機械地進(jìn)行進(jìn)行, ,我們只考慮規(guī)范歸約我們只考慮規(guī)范歸約( (最左歸約最左歸約),),即歸約過程替換的是歸左直接即歸約過程替換的是歸左直接短語短語. .u我們以L(G2)的句子i+i*i+i為例,給出其最右推

37、導(dǎo)(規(guī)范歸約的逆過程),來說明每次規(guī)范歸約的子符號串句柄的定義句柄的定義uEE+T E+F E+i E+T +i E+T*F+i E+T*i+i E+F*i+i E+i*i+i T+i*i+i F+i*i+i i+i*i+i u上面的推導(dǎo)過程的逆過程就是規(guī)范歸約的上面的推導(dǎo)過程的逆過程就是規(guī)范歸約的過程。從其逆過程可看出，每步歸約的均過程。從其逆過程可看出，每步歸約的均是是當(dāng)前句型當(dāng)前句型的的最左直接短語最左直接短語（最左直接子（最左直接子樹的葉結(jié)點）。我們把它稱為樹的葉結(jié)點）。我們把它稱為當(dāng)前句型當(dāng)前句型的的句柄句柄。u定義定義2.92.9 一個句型的最左直接短語稱為此一個句型的最左直接短語

38、稱為此句型的句型的句柄句柄。u問題問題：如何確定一規(guī)范句型的句柄？句柄如何確定一規(guī)范句型的句柄？句柄應(yīng)被歸約成哪個非終結(jié)符？應(yīng)被歸約成哪個非終結(jié)符？EE + TE + TT * FTFiFFiii1234567891011( 3 ) 子樹與短語 子樹：語法樹中的某個結(jié)點（子樹的根）連同它向下派生的部分所組成。 某子樹的末端結(jié)點按自左向右順序為句型中的符號串，則該符號串為該句型的相對于該子樹根的短語。定理定理定義：簡單子樹：僅有父子兩代的子樹。 句柄：該語法樹的最左簡單子樹的末端結(jié)點從左到右排列的字符串是該句型的句柄。 某簡單子樹的末端結(jié)點按自左向右順序為句型中的符號串，則該符號串為該句型的相對

39、于該簡單子樹根的直接短語。定理定理 只需畫出句型的語法樹，然后根據(jù)子樹找 短語短語直接短語直接短語句柄句柄。句型推導(dǎo)過程句型語法樹的生長過程 由推導(dǎo)構(gòu)造語法樹由推導(dǎo)構(gòu)造語法樹1從識別符號開始，自左向右建立推導(dǎo)序列。由根結(jié)點開始，自上而下建立語法樹。語法樹與推導(dǎo) 由語法樹構(gòu)造推導(dǎo)由語法樹構(gòu)造推導(dǎo)2自上而下地修剪子樹的末端結(jié)點，直至把整棵樹剪掉（留根），每剪一次對應(yīng)一次規(guī)約。從句型開始，自右向左地逐步進(jìn)行規(guī)約，建立推導(dǎo)序列。2.4 2.4 文法的化簡與改造文法的化簡與改造2.4.1 無用符號和無用產(chǎn)生式的刪除無用符號和無用產(chǎn)生式的刪除設(shè)設(shè)G=(VN,VT,P,S)是一文法是一文法,X VN VT,

40、X稱為是稱為是有用的有用的,若若X至少至少出現(xiàn)在一個句子的推導(dǎo)過程中出現(xiàn)在一個句子的推導(dǎo)過程中,即即X滿足滿足:(1) 存在存在 , V* ,有有 S* X (2.12)(2)存在存在w VT*,使使 X * w(2.13)否則否則,稱稱X是是無用的無用的.若一產(chǎn)生式含有無用符號若一產(chǎn)生式含有無用符號,則此產(chǎn)生式稱為則此產(chǎn)生式稱為無用無用產(chǎn)生式產(chǎn)生式.u 無用產(chǎn)生式給語法分析帶來了許多麻煩無用產(chǎn)生式給語法分析帶來了許多麻煩,應(yīng)予以刪除應(yīng)予以刪除.消除無用產(chǎn)生式的算法消除無用產(chǎn)生式的算法算法算法2.1 將文法將文法G = (VN,VT,P,S),改造為改造為G1=(VN,VT,P,S),使得使得

41、L(G)=L(G1)(1)置置VN,P為空為空;(2)對于對于P中每個產(chǎn)生式中每個產(chǎn)生式A,若若 (VN VT)*,則將則將A加入加入VN中中;(3)重復(fù)重復(fù)(2),直到直到VN不再增大不再增大;(4)對于每個對于每個A P,若若 (VN VT)*,則置則置A 于于P中中.算法算法2.2 任給文法任給文法G= (VN,VT,P,S),構(gòu)造構(gòu)造G=(VN,VT,P,S), 使使 x (VN VT), , (VN VT)*, 有有 S * x (1)置置VT為空為空,VN=S;(2)對于對于 A P,若若 A VN則置則置 中所有非終結(jié)中所有非終結(jié)符入符入VN ,所有終結(jié)符入所有終結(jié)符入VT ;(

42、3)重復(fù)重復(fù)(2),直到直到V不再增大不再增大;(4)令令P=A | A P, (VN VT)*,A VN消除無用產(chǎn)生式的例子消除無用產(chǎn)生式的例子例例 G=(S,U,V,W,a,b,c,P,S),其中其中,P: SaS | W | U Ua V bV |ac W aW現(xiàn)對現(xiàn)對G執(zhí)行執(zhí)行算法算法2.1:1.由由Ua 和和Vac右部都是終結(jié)右部都是終結(jié)符符,VN=U,V;2.對于對于SU,由由U VN 有有VN=S,U,V;此外再無可放入此外再無可放入VN的符號的符號;P1為為S aS | U Ua V bV |ac現(xiàn)對現(xiàn)對G1執(zhí)行執(zhí)行算法算法2.2:1.置置VN =S;2.由由SU及及U a將將

43、U及及a分別放分別放入入VN (=S,U)和和VT (=a)中中;3.此外此外, VN 和和VT不再增大不再增大;4.最后結(jié)果為最后結(jié)果為:S aS | U Ua注意注意,在刪除無用符和無用產(chǎn)生式在刪除無用符和無用產(chǎn)生式時時, ,應(yīng)先執(zhí)行算法應(yīng)先執(zhí)行算法2.12.1再執(zhí)行再執(zhí)行算法算法2.2,2.2,就可得到就可得到“干凈干凈”的文法的文法; ;若先執(zhí)行算法若先執(zhí)行算法2.2,2.2,再再執(zhí)行算法執(zhí)行算法2.12.1所得文法不一定所得文法不一定“干凈干凈”2.4.2 -產(chǎn)生式的消除u -產(chǎn)生式產(chǎn)生式是指右部為一空符號串是指右部為一空符號串 的產(chǎn)生式。因為某些語法分析的產(chǎn)生式。因為某些語法分析算

44、法要求不含算法要求不含，此時應(yīng)消除之，此時應(yīng)消除之u 若一語言不含若一語言不含 （即（即L(G),則可將其完全消除；則可將其完全消除；u 若若L(G),則可將文法改造為只有開始符則可將文法改造為只有開始符S可推導(dǎo)出可推導(dǎo)出 (即即S P),而且而且,S不出現(xiàn)在任何產(chǎn)生式的右部不出現(xiàn)在任何產(chǎn)生式的右部,此外再無其它此外再無其它 -產(chǎn)生產(chǎn)生式式.u 本節(jié)中的本節(jié)中的算法算法2.3可用于找出所有可推導(dǎo)出可用于找出所有可推導(dǎo)出 的非終結(jié)符的非終結(jié)符W=A| A* , A VNu 執(zhí)行完執(zhí)行完算法算法2.3,通過檢驗通過檢驗S W與否可知與否可知L(G)與否與否;u 算法算法2.4可消除可消除L(G)情

45、況時的情況時的 -產(chǎn)生式產(chǎn)生式;u 算法算法2.5可消除可消除L(G)情況時的情況時的 -產(chǎn)生式產(chǎn)生式.2.5 文法和語言的文法和語言的ChomskyChomsky分類分類u文法的四元組表示是由文法的四元組表示是由N.ChomskyN.Chomsky于于19561956年描述形式語言時給出年描述形式語言時給出的。他還對產(chǎn)生式的形式給予不同的限制而定義了的。他還對產(chǎn)生式的形式給予不同的限制而定義了四類基本文法四類基本文法。u0 0型文法型文法: :若若P P中任一產(chǎn)生式都有一般形式中任一產(chǎn)生式都有一般形式 V+ V+ V V* * 且對且對 ， 不加任何限制，則稱不加任何限制，則稱GG為為0 0型文法型文法（短語結(jié)構(gòu)文法，記為短語結(jié)構(gòu)文法，記為PSG: PSG: Phrase Structure GrammarPhrase Structure Grammar) )。由。由0 0型文法生成（或者說：定義）型文法生成（或者說：定義）的語言稱為的語言稱為0 0型型（遞歸可枚舉遞歸可枚舉）語言語言。它可由。它可由圖靈圖靈（TuringTuring）機機識識別。別。u例如：例如：S SACaB CaACaB CaaaC CBaaC CBDB CBDB CBE aDE aDDa Da ADADAC aEAC aEEa AEEa AE 就