編譯原理—第3章文法和語(yǔ)言.ppt

第3章:文法和語(yǔ)言的概念和表示,3.0 概述 3.1 形式語(yǔ)言基礎(chǔ) 3.2 文法的直觀理解 3.3 文法和語(yǔ)言的定義 3.4 文法的類型 3.5 語(yǔ)法樹(shù)與二義性 3.6 句型的分析,3.0 概述,用高級(jí)語(yǔ)言編程比用低級(jí)語(yǔ)言方便，但要解決兩個(gè)問(wèn)題： (1)計(jì)算機(jī)怎樣懂得高級(jí)語(yǔ)言程序，這就需要一個(gè)翻譯程序?qū)崿F(xiàn)從源程序到目 標(biāo)程序的轉(zhuǎn)換。 (2)用什么方法來(lái)精確定義高級(jí)語(yǔ)言，即怎樣精確描述高級(jí)語(yǔ)言。 要構(gòu)造一個(gè)編譯程序，應(yīng)深刻理解被編譯的源語(yǔ)言的結(jié)構(gòu)（即詞法和語(yǔ)法） 及其含義（即語(yǔ)義），同時(shí)要弄清源語(yǔ)言的語(yǔ)法規(guī)則和語(yǔ)義規(guī)則是采用什么理 論或什么方法來(lái)描述的。,本章目的 為語(yǔ)言的語(yǔ)法描述尋求工具，該工具要對(duì)程序設(shè)計(jì)語(yǔ)言給出精確無(wú)二義的語(yǔ)法描述。（嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀） 形式工具-形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)?！靶问健笔侵高@樣的事實(shí)：語(yǔ)言的所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。,語(yǔ)言概述,研究程序設(shè)計(jì)語(yǔ)言 每個(gè)程序構(gòu)成的規(guī)律 每個(gè)程序的含義 每個(gè)程序和使用者的關(guān)系 語(yǔ)言研究的三個(gè)方面 語(yǔ)法 Syntax 語(yǔ)義 Semantics 語(yǔ)用 Pragmatics,語(yǔ)法 表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律。 語(yǔ)義 表示各個(gè)記號(hào)的特定含義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系） 語(yǔ)用 表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來(lái)源、使用和影響。,每種語(yǔ)言具有兩個(gè)可開(kāi)始的特性，即語(yǔ)言的形式和該形式相關(guān)聯(lián)的意義。 語(yǔ)言的實(shí)例若在語(yǔ)法上是正確的，其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來(lái)看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的，前者稱為語(yǔ)言的語(yǔ)義，后者是其語(yǔ)用意義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就是利用這兩方面意義間的差異。,如果不考慮語(yǔ)義和語(yǔ)用，即只從語(yǔ)法這一側(cè)面來(lái)看語(yǔ)言，這種意義下的語(yǔ)言稱作形式語(yǔ)言。形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。“形式”是指這樣的事實(shí)：語(yǔ)言的所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。,任何語(yǔ)言均可看作一個(gè)集合。這個(gè)集合中的每個(gè)元素都是在一定符號(hào)集 （字母表）上的一個(gè)符號(hào)串。 對(duì)于自然語(yǔ)言來(lái)說(shuō)，它們是定義在某個(gè)字母表上的句子的集合。 對(duì)于程序語(yǔ)言來(lái)說(shuō)，它們也是定義在某個(gè)字母表上的句子的集合。這里 的句子，就是一個(gè)源程序。 通常，源程序是由關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符以及一些界限符組成。 這些語(yǔ)法成分統(tǒng)稱為單詞或單詞符號(hào)。 單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最基本單位。語(yǔ)言的單詞符號(hào)是由詞法 規(guī)則所確定的，即詞法規(guī)則規(guī)定了單詞符號(hào)的形成規(guī)則。,當(dāng)我們表述一種語(yǔ)言時(shí)，無(wú)非是要說(shuō)明這種語(yǔ)言的句子，如果語(yǔ)言只含有窮多個(gè)句子，則只需列出句子的有窮集就行了，但對(duì)于含有無(wú)窮句子的語(yǔ)言來(lái)講，就存在著如何給出它的有窮表示的問(wèn)題。 以自然語(yǔ)言為例，人們無(wú)法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來(lái)說(shuō)明(或者定義)句子的組成結(jié)構(gòu)，比如漢語(yǔ)句子可以是由主語(yǔ)后隨謂語(yǔ)而成，構(gòu)成謂語(yǔ)的是動(dòng)詞和直接賓語(yǔ)。,“我是大學(xué)生”。是漢語(yǔ)的一個(gè)句子 用語(yǔ)法來(lái)描述：,句子=主語(yǔ)謂語(yǔ) 主語(yǔ)=代詞名詞 代詞=我你他 名詞=王明大學(xué)生工人英語(yǔ) 謂語(yǔ)=動(dòng)詞直接賓語(yǔ) 動(dòng)詞=是學(xué)習(xí) 直接賓語(yǔ)=代詞名詞,有了一組規(guī)則以后，按照如下方式用它們導(dǎo)出句子：開(kāi)始去找=左端的帶有句子的規(guī)則并把它由=右端的符號(hào)串代替，這個(gè)動(dòng)作表示成： 句子 主語(yǔ)謂語(yǔ)，然后在得到的串主語(yǔ)謂語(yǔ)中，選取主語(yǔ)或謂語(yǔ)，再用相應(yīng)規(guī)則的=右端代替之。比如，選取了主語(yǔ)，并采用規(guī)則主語(yǔ)=代詞， 那么得到：主語(yǔ)謂語(yǔ) 代詞謂語(yǔ)， 重復(fù)做下去， 句子：“我是大學(xué)生”的全部動(dòng)作過(guò)程是： 句子 主語(yǔ)謂語(yǔ) 代詞謂語(yǔ) 我謂語(yǔ) 我動(dòng)詞直接賓語(yǔ) 我是直接賓語(yǔ) 我是名詞 我是大學(xué)生,“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說(shuō)它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說(shuō)，這些規(guī)則看成是一種元語(yǔ)言，用它描述漢語(yǔ)。這里僅僅涉及漢語(yǔ)句子的結(jié)構(gòu)描述。其中一種描述元語(yǔ)言稱為文法。,3.1 形式語(yǔ)言基礎(chǔ),基本概念: 一、字母表和符號(hào)串 1.字母表：符號(hào)的非空有限集合 例：=a，b，c 2.符號(hào)：字母表中的元素 例： a，b，c 3.符號(hào)串：符號(hào)的有窮序列 例：a, aa, ac, abc， 特別地,空符號(hào)串：無(wú)任何符號(hào)的符號(hào)串(),符號(hào)串的形式定義 有字母表，定義： （1）是上的符號(hào)串； （2）若x是上的符號(hào)串，且a ，則ax或xa是上的符號(hào)串； （3）y是上的符號(hào)串，iff（當(dāng)且僅當(dāng)）y可由（1）和（2）產(chǎn)生。,4.符號(hào)串集合：由符號(hào)串構(gòu)成的集合。,二、符號(hào)串和符號(hào)串集合的運(yùn)算,5.符號(hào)串相等：若x、y是集合上的兩個(gè)符號(hào)串，則xy iff（當(dāng)且僅當(dāng)）組成x的每一個(gè)符號(hào)和組成y的每一個(gè)符號(hào)依次相等。 6.符號(hào)串的長(zhǎng)度：x為符號(hào)串，其長(zhǎng)度|x|等于組成該符 號(hào)串的符號(hào)個(gè)數(shù)。 例： xSTV ， |x|=3 特別地, | =0,例：Aa,b,B=c,d, AB= ？,8. 符號(hào)串集合的乘積運(yùn)算：令A(yù)、B為符號(hào)串集合，定義 AB xy |xA，yB,ac，ad，bc，bd 因?yàn)閤xx，所以A= A =A,7.符號(hào)串的聯(lián)接：若x、y是定義在是上的符號(hào)串，且xXY，yYX，則x和y的聯(lián)接 xyXYYX也是上的符號(hào)串。 注意：一般xyyx，而xxx,9. 方冪運(yùn)算： 符號(hào)串集合的方冪 符號(hào)串的方冪 有任一符號(hào)串集合A，定義 : 有任一符號(hào)串X，定義: A0 =, X0 = A1=A, X1 = X A2=AA, X2=XX A3=AAA, X3=XXX AnAn-1A=AAn-1 Xn=XX X A A A n個(gè) n個(gè) 其中:n0,10.符號(hào)串集合的閉包運(yùn)算：設(shè)A是符號(hào)串集合，定義 A = A1 A2 A3 An 稱為集合A的正則閉包。 A* = A0 A1 A2 A3 An = A0 A 稱為集合A的星閉包。,例：A=x,y A？ A* ？,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 A3,為什么對(duì)符號(hào)、符號(hào)串、符號(hào)串集合以及它們的運(yùn)算感興趣？ 若A為某語(yǔ)言的基本字符集 Aa,b,z,0,1,9, +,_/, ( , ), = B為單詞集 B =begin, end, if, then,else,for, 則B A* 。 語(yǔ)言的句子是定義在B上的符號(hào)串。 若令C為句子集合，則C B * , 程序 C,3.2文法的直觀理解,1.什么是文法： 文法是對(duì)語(yǔ)言結(jié)構(gòu)的定義與描述。即從形式上用于描述和規(guī)定語(yǔ)言結(jié)構(gòu)的稱為“文法”（或稱為“語(yǔ)法”）。,例：有一句子：“我是大學(xué)生” 。這是一個(gè)在語(yǔ)法、語(yǔ)義上都正確定句子，該句子的結(jié)構(gòu)（稱為語(yǔ)法結(jié)構(gòu)）是由它的語(yǔ)法決定的 。在本例中它為“主謂結(jié)構(gòu)”。,如何定義句子的合法性？ 有窮語(yǔ)言 無(wú)窮語(yǔ)言,2.語(yǔ)法規(guī)則： 我們通過(guò)建立一組規(guī)則（產(chǎn)生式），來(lái)描述句子 的語(yǔ)法結(jié)構(gòu)。規(guī)定用“:=”表示“由組成”。,:= :=| :=你|我|他 := 王民|大學(xué)生|工人|英語(yǔ) := :=是|學(xué)習(xí) :=|,由產(chǎn)生式推導(dǎo)句子：, = = 這種推導(dǎo)一直進(jìn)行下去，直到所有帶的符號(hào)都由終結(jié)符號(hào)替代為止。,有了一組產(chǎn)生式之后，可以按照一定的方式用它們?nèi)ネ茖?dǎo)或產(chǎn)生句子。 推導(dǎo)方法：從一個(gè)要開(kāi)始的符號(hào)開(kāi)始推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部來(lái)替代產(chǎn)生式的左部，每次僅用一條產(chǎn)生式去進(jìn)行推導(dǎo)。, , ,我,我,我是,我是,我是大學(xué)生,:= :=| :=你|我|他 := 王民|大學(xué)生|工人|英語(yǔ) := :=是|學(xué)習(xí) :=|,推導(dǎo)方法：從一個(gè)要開(kāi)始的符號(hào) 開(kāi)始推導(dǎo)，即用相應(yīng)產(chǎn)生式的 右部來(lái)替代產(chǎn)生式的左部，每 次僅用一條產(chǎn)生式去進(jìn)行推導(dǎo)。,例：給定一組語(yǔ)法規(guī)則，考察一個(gè)句子：“我是大學(xué)生”的推導(dǎo)過(guò)程。,例：有一英語(yǔ)句子：The big elephant ate the peanut. := := :=the :=big :=elephant := :=ate := :=peanut, = ,= ,= the ,= the big ,= the big elephant ,= the big elephant ,= the big elephant ate ,= the big elephant ate ,= the big elephant ate the ,= the big elephant ate the peanut,:= := :=the :=big :=elephant | peanut := :=ate :=,The big elephant ate the peanut.,說(shuō)明： (1) 有若干語(yǔ)法成分同時(shí)存在時(shí)，我們總是從最左的語(yǔ)法成 分進(jìn)行推導(dǎo)，這稱之為最左推導(dǎo)，類似的有最右推導(dǎo)（一般推 導(dǎo)）。 (2) 從一組產(chǎn)生式可推出不同的句子，如以上產(chǎn)生式還可推 出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子， 它們 在語(yǔ)法上都正確，但在語(yǔ)義上都不正確。,所謂文法是在形式上對(duì)句子結(jié)構(gòu)的定義與描述，而未 涉及語(yǔ)義問(wèn)題。,4.語(yǔ)法樹(shù)：我們用語(yǔ)法樹(shù)來(lái)描述一個(gè)句子的語(yǔ)法結(jié)構(gòu)。,語(yǔ)法成分（在形式 語(yǔ)言中又稱“非終 結(jié)符”）,單詞符號(hào)（在形 式語(yǔ)言中又稱 “終結(jié)符號(hào)”),3.3.1文法的定義,3.3 文法和語(yǔ)言的形式定義,定義1: 文法G=（VN，VT，P，Z） VN ：非終結(jié)符號(hào)集 VT ：終結(jié)符號(hào)集 P：產(chǎn)生式或規(guī)則的集合 Z：開(kāi)始符號(hào)（識(shí)別符號(hào)） ZVN,VVNVT 稱為文法的字匯表,產(chǎn)生式：U : x U VN, xV*,其中: 產(chǎn)生式：產(chǎn)生式是一個(gè)有序?qū)?U, x), 通常寫(xiě)為: U : x 或U x； | U| = 1 |x| 0 非終結(jié)符號(hào)：出現(xiàn)在產(chǎn)生式的左部,且能推出符號(hào)或符號(hào)串的 那些符號(hào)。其全體構(gòu)成非終結(jié)符號(hào)集，記為VN 。 終結(jié)符號(hào)：不出現(xiàn)在產(chǎn)生式的左部,且不能推出符號(hào)或符號(hào)串 的那些符號(hào)。其全體構(gòu)成終結(jié)符號(hào)集，記為VT 。,P = ； ； ； 0； 1； 9； Z = ；,例：無(wú)符號(hào)整數(shù)的文法： G=（VN，VT，P，Z） VN, VT = 0,1,2,3,9,幾點(diǎn)說(shuō)明：,產(chǎn)生式左邊符號(hào)構(gòu)成集合VN，且 Z VN,文法的BNF表示,3.3.2 推導(dǎo)與歸約,定義2： 直接推導(dǎo)：文法G：vx Uy，wxuy, 其中x、y V* ，UVN, u V*, 若U : uP，則v w，即x Uy xuy 。 若xy，有U : u，則U u,換句話說(shuō)，x和y是符號(hào)串，若使用一次產(chǎn)生式可以從x變換出y，則稱x直接推導(dǎo)出y(或者說(shuō)y是x的直接推導(dǎo)），記為x y。,當(dāng)符號(hào)串已沒(méi)有非終結(jié)符號(hào)時(shí)，推導(dǎo)就必須終止。因?yàn)?終結(jié)符不可能出現(xiàn)在產(chǎn)生式左部，所以將在產(chǎn)生式左部出現(xiàn)的 符號(hào)稱為非終結(jié)符號(hào)。,例如：GN： N ND | D D 0| 1| 2| 3| 4| 5| 6| 7| 8| 9, N=109,定義3： +推導(dǎo)：x和y是符號(hào)串，若使用若干次產(chǎn)生式可以從x變換出y，則稱x推導(dǎo)出y(或者說(shuō)y是x的推導(dǎo)），記為x y。,例：,則有：,* N=109,則有：,* N=N,直觀意義：規(guī)范推導(dǎo)最右推導(dǎo),定義5： 最右推導(dǎo)：若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，對(duì)推導(dǎo)的每一步堅(jiān)持把中的最右非終結(jié)符進(jìn)行替換，稱為最右推導(dǎo)。 最左推導(dǎo)：若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，對(duì)推導(dǎo)的每一步堅(jiān)持把中的最左非終結(jié)符進(jìn)行替換，稱為最左推導(dǎo)。,定義6： 推導(dǎo)的逆過(guò)程稱之為歸約。,例：x =y,可稱為x直接推導(dǎo)出y，也可稱為y直接歸約出x。, x =y ,可稱為x推導(dǎo)出y，也可稱為y歸約出x。,3.3.3 語(yǔ)言的形式定義,文法GZ所產(chǎn)生的 所有句子的集合,即：句型是由文法開(kāi)始符號(hào)推導(dǎo)出來(lái)的 由終結(jié)符和非終結(jié)符組成的符號(hào)串。,即：句子是由文法開(kāi)始符號(hào)推導(dǎo)出來(lái)的 由終結(jié)符組成的符號(hào)串。,例：abna|n1,構(gòu)造其文法 G1Z： ZaBa, Bb|bB G2Z： ZaBa, Bb|Bb,定義8: G和G是兩個(gè)不同的文法，若 L(G) = L(G) , 則G和G為等價(jià)文法。,編譯感興趣的問(wèn)題是:,給定x, G, 求x L(G) ?,x,算法1,算法2,x L(G) ?,G,y,n,出錯(cuò)處理,停機(jī),3.3.4 遞歸文法,1.遞歸產(chǎn)生式：產(chǎn)生式右部有與左部相同的符號(hào) 對(duì)于 U:= xUy 若x=,即U:= Uy，左遞歸； 若y=,即U:= xU，右遞歸；,4. 遞歸文法的優(yōu)點(diǎn)：可用有窮條產(chǎn)生式，定義無(wú)窮語(yǔ)言,例：對(duì)于前面給出的無(wú)符號(hào)整數(shù)的文法是有遞歸文法，用13條產(chǎn)生式就可以定義出所有的無(wú)符號(hào)整數(shù)。若不用遞歸文法，那將要用多少條產(chǎn)生式呢？,!,3. 左遞歸文法的缺點(diǎn)：不能用自頂向下的方法來(lái)進(jìn)行語(yǔ)法分析,會(huì)造成死循環(huán)（后面將詳細(xì)論述）,3.4 文法分類,形式語(yǔ)言：用文法和自動(dòng)機(jī)所描述的沒(méi)有語(yǔ)義的語(yǔ)言。,文法定義：?jiǎn)棠匪够鶎⑺形姆ǘ级x為一個(gè)四元組： G=（VN，VT，P，Z） VN：非終結(jié)符號(hào)集 VT：終結(jié)符號(hào)集 P：產(chǎn)生式或規(guī)則的集合 Z：開(kāi)始符號(hào)（開(kāi)始符號(hào)） ZVN,文法和語(yǔ)言分類：0型、1型、2型、3型 這幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制。,定義9：0型文法： P： u:=v 其中uV* ，vV*,0型語(yǔ)言：L0 這種語(yǔ)言可以用圖靈機(jī)(Turing)接受.,0型文法稱為短語(yǔ)結(jié)構(gòu)文法。產(chǎn)生式的左部和右部都可 以是符號(hào)串，一個(gè)短語(yǔ)可以產(chǎn)生另一個(gè)短語(yǔ)。,定義10： 1型文法： P： xUy:= xuy 其中 UVN， x、y、uV*,1型語(yǔ)言：L1 這種語(yǔ)言可以由一種線性界限自動(dòng)機(jī)接受.,稱為上下文敏感或上下文有關(guān)。也即只有在x、y這樣的 上下文中才能把U改寫(xiě)為u,定義10： 1型文法： P： u:= v u v u, v V*,定義11：2型文法： P： U:= u 其中 UVN， uV*,2型語(yǔ)言：L2 這種語(yǔ)言可以由下推自動(dòng)機(jī)接受.,稱為上下文無(wú)關(guān)文法。也即把U改寫(xiě)為u時(shí)，不必考慮上下文。 注意：2型文法與BNF表示相等價(jià)。,（右線性） P： U:=t 或 U:=tW 其中 U、WVN tVT,3型語(yǔ)言：L3 又稱正則語(yǔ)言、正則集合 這種語(yǔ)言可以由有窮自動(dòng)機(jī)接受.,3型文法又被稱為正則文法。它是對(duì)2型文法進(jìn)行進(jìn)一步限制。,（左線性） P： U:=t 或 U:=Wt 其中 U、WVN tVT,定義12： 3型文法：,3.5 語(yǔ)法樹(shù)與二義性文法,3.5.1 推導(dǎo)與語(yǔ)法樹(shù),（1）語(yǔ)法樹(shù)：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由 結(jié)點(diǎn)和有向邊組成。,結(jié)點(diǎn)：符號(hào) 根結(jié)點(diǎn)：開(kāi)始符號(hào) 中間結(jié)點(diǎn)：非終結(jié)符 葉結(jié)點(diǎn)：終結(jié)符或非終結(jié)符,有向邊：表示結(jié)點(diǎn)間的派生關(guān)系。,注意一個(gè)重要事實(shí)：文法所能產(chǎn)生的句子，可以 用不同的推導(dǎo)原則（使用產(chǎn)生式順序不同）將其 推導(dǎo)出來(lái)。語(yǔ)法樹(shù)的生成規(guī)律不同，但最終生成的語(yǔ) 法樹(shù)形狀完全相同。某些文法有此性質(zhì)，而某些文法 不具此性質(zhì)。,( 2 ) 句型的推導(dǎo)及語(yǔ)法樹(shù)的生成（自頂向下）,一般推導(dǎo)：,( 3 ) 子樹(shù)與簡(jiǎn)單子樹(shù),子樹(shù)：語(yǔ)法樹(shù)中的某個(gè)結(jié)點(diǎn)（子樹(shù)的根）連同它向下派生的部分所組成。,簡(jiǎn)單子樹(shù)：只有單層分枝的子樹(shù)稱為簡(jiǎn)單子樹(shù)。,( 4 ) 樹(shù)與推導(dǎo),句型推導(dǎo)過(guò)程 句型語(yǔ)法樹(shù)的生長(zhǎng)過(guò)程,例：給定文法G和句型10,考察語(yǔ)法樹(shù)與推導(dǎo)過(guò)程。,規(guī)范推導(dǎo),規(guī)范歸約與規(guī)范推導(dǎo)互為逆過(guò)程,定義14：通過(guò)規(guī)范推導(dǎo)或規(guī)范歸約所得到的句型稱為規(guī)范句型。,不是規(guī)范推導(dǎo),3.5.2 文法的二義性,定義14.1： 若對(duì)于一個(gè)文法的某一句子存在兩棵不同的語(yǔ)法樹(shù)， 則該文法是二義性文法，否則是無(wú)二義性文法。,換而言之，無(wú)二義性文法的句子只有一棵語(yǔ)法樹(shù)，盡管推導(dǎo)過(guò)程可以不同。,下面舉一個(gè)二義性文法的例子： GE: E:= E+E | E*E | (E) | i VN =E VT = +, * , ( , ) , i ,對(duì)于句子Sii * i L（GE ），存在不同的規(guī)范推導(dǎo)：,這兩種不同的推導(dǎo)對(duì)應(yīng)了兩種不同的語(yǔ)法樹(shù),GE: E:= E+E | E*E | (E) | i,定義14.2： 若一個(gè)文法的某句子存在兩個(gè)不同的規(guī)范推導(dǎo)，則 該文法是二義性的，否則是無(wú)二義性的。,以上是自頂向下來(lái)看文法的二義性，我們還可以自底向上來(lái)看文法的二義性。 上例中，規(guī)范句型E+E*i 是由ii * i通過(guò)兩步規(guī)范規(guī)約得到的，但對(duì)于同一個(gè)句型E+E* i，它有兩個(gè)不同的句柄（對(duì)應(yīng)上述兩棵不同的語(yǔ)法樹(shù)）：i 和 EE。因此語(yǔ)法的二義性意味著句型的句柄不唯一。,句柄：i,句柄：EE,若文法是二義性的，則在編譯時(shí)就會(huì)產(chǎn)生不確定性，遺憾的是在理論上已經(jīng)證明：文法的二義性是不可判定的，即不可能構(gòu)造出一個(gè)算法，通過(guò)有限步驟來(lái)判定任一文法是否有二義性。,現(xiàn)在的解決辦法是：提出一些限制條件，稱為無(wú)二義性的充分條件，當(dāng)文法滿足這些條件時(shí)，就可以判定文法是無(wú)二義性的。,由于無(wú)二義性文法比較簡(jiǎn)單，我們也可以采用另一種解決辦法：即不改變二義性文法，而是確定一種編譯算法，使該算法滿足無(wú)二義性充分條件。,定義14.3 若一個(gè)文法的某規(guī)范句型的句柄不唯一，則該文法 是二義性的，否則是無(wú)二義性的。,例:算術(shù)表達(dá)式的文法：,E:= E+E | E*E | (E) | i,E:= E+T | T T := T*F | F F := (E) | i,例:Pascal 語(yǔ)言條件語(yǔ)句的文法,:= If then | If then else := | |.,3.6 句型的分析,任務(wù)：給定GZ: S VT*, 判定是否有 S L (GE ) ?,這是詞法分析和語(yǔ)法分析所要做的工作，將在第三、四章中詳細(xì)介紹。,3.6.1 句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄,*,直觀理解：短語(yǔ)是前面句型中的某個(gè)非終結(jié)符所能推出的符號(hào)串。,定義17. 任一句型的最左簡(jiǎn)單短語(yǔ)稱為該句型的句柄。,注意：短語(yǔ)、簡(jiǎn)單短語(yǔ)是相對(duì)于句型而言，一個(gè)句型 可能有多個(gè)短語(yǔ)、簡(jiǎn)單短語(yǔ)，句柄只能有一個(gè)。,例：給定文法G： ET | E+T |