編譯原理—第3章文法和語言.ppt

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