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

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