編譯原理ppt課件

1、 2010年年9月月.第2章 形式語言概論 （主要介紹形式語言理論中的一些基本概念和基礎(chǔ)知識，包括、語言、語法樹和分析方法等） 2010年年9月月.2.1 字母表和符號串2.2 文法及其分類2.3 語言和語法樹2.4 關(guān)于文法和語言的幾點說明2.5 分析方法簡介2.6 小結(jié) 2010年年9月月.2.1 字母表和符號串一、字母表和符號串一、字母表和符號串 字母表字母表：符號的非空有限集 例：=a，b，c 符號符號：字母表中的元素 例： a，b，c 符號串符號串：符號的有窮序列 例：a, aa, ac, abc，. 空符號串空符號串：無任何符號的符號串(） 符號串集合符號串集合：由符號串構(gòu)成的集合

2、。符號串的形式定義符號串的形式定義 有字母表，定義： （1）是上的符號串； （2）若x是上的符號串，且a ，則ax或xa是上的符號串； （3）y是上的符號串，iff（當(dāng)且僅當(dāng)）y可由（1）和（2）產(chǎn)生。 2010年年9月月.二、符號串和符號串集合的運算二、符號串和符號串集合的運算 1.符號串相等符號串相等：若x、y是集合上的兩個符號串，則xyiff（當(dāng)且僅當(dāng)）組成x的每一個符號和組成y的每一個每一個符號依次相等。 2.符號串的長度符號串的長度：x為符號串，其長度|x|等于組成該符 號串的符號個數(shù)。 例： xCCTV ， |x|=4 特別有|0，即空符號串的長度等于零。 2010年年9月月.例：

3、Aa,b,B=c,d, AB= ？ 4. 符號串集合的乘積運算符號串集合的乘積運算：令A(yù)、B為符號串集合，定義 AB xy |xA,yB注意：注意：因為xxx，所以A=A=A A=A= 其中，為空集 3. 3.符號串的聯(lián)接符號串的聯(lián)接：若x、y是定義在是上的符號串，且xXY，yYX，則x和y的聯(lián)接 xyXYYX也是上的符號串。 注意：一般xyyx，而xxac，ad，bc，bd 2010年年9月月.5. 5. 符號串的方冪運算符號串的方冪運算 同一符號串的連接可以寫成方冪形式。 設(shè)x是一符號串，則定義 x0= x1=x x2=xx x3=x2x=xx2=xxx xn=xxn-1= xxx n n

4、 個個例如： x=abc 則 x2=abcabc x3=abcabcabc6. 6. 符號串集合的冪運算符號串集合的冪運算 有符號串集合A，定義 A0 =, A1=A, A2=AA, A3=AAA, AnAn-1A=AAn-1 ，n0例如：A=a,bc 則A2=AA=aa, abc, bca, bcbc A3=A2A=aaa, abca, bcaa, aabc, abcbc, bcabc, bcbca, bcbcbc 2010年年9月月.6.6.符號串集合的閉包運算符號串集合的閉包運算 設(shè)A是符號串集合，定義 A A1 A2 A3 An 稱為集合A的正閉包。 A* A0 A稱為集合A的自反閉包

5、。 顯然有 A+=AA*=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 2010年年9月月.為什么對符號、符號串、符號串集合以及它們的運算感興趣？為什么對符號、符號串、符號串集合以及它們的運算感興趣？若A為某語言的基本字符集 Aa,b,z,0,1,9, +, /, ( , ), =B為單詞集 B =begin, end, if, then,else,for, 則B A* 。語言的句子是定義在B上的符號串。若令C為

6、句子集合，則C B * , 程序 C 2010年年9月月.2.2 文法及其分類文法的非形式討論文法的非形式討論 1.什么是文法：文法是對語言結(jié)構(gòu)的定義與描述。即從形式上用于描述和規(guī)定語言結(jié)構(gòu)的稱為“文法”（或稱為“語法”）。 例：有一句子：“我是大學(xué)生” 。這是一個在語法、語義上都正確定句子，該句子的結(jié)構(gòu)（稱為語法結(jié)構(gòu)）是由它的語法決定的 。在本例中它為“主謂結(jié)構(gòu)”。 2010年年9月月. 2.2.語法規(guī)則語法規(guī)則：我們通過建立一組規(guī)則，來描述句子的語法結(jié)構(gòu)結(jié)構(gòu)。規(guī)定用“:=”表示“由組成”或“定義為”。:=:=| :=你|我|他:= 王民|大學(xué)生|工人|英語:=:=是|學(xué)習(xí):=| 2010年

7、年9月月.3. 由規(guī)則推導(dǎo)推導(dǎo)句子：有了一組規(guī)則之后，可以按照一定的方式用它們?nèi)ネ茖?dǎo)或產(chǎn)生句子。 推導(dǎo)方法：從一個要識別的符號開始推導(dǎo)，即用相應(yīng)規(guī)則的右部來替代規(guī)則的左部，每次僅用一條規(guī)則去進(jìn)行推導(dǎo)。 = = 這種推導(dǎo)一直進(jìn)行下去，直到所有帶的符號都由終結(jié)符號替代為止。 2010年年9月月. = = = 我 =我 =我是 =我是 =我是大學(xué)生:=:= :=:=| := :=你你| |我我| |他他 :=:= 王民王民| |大學(xué)生大學(xué)生| |工人工人| |英語英語 :=:= :=:=是是| |學(xué)習(xí)學(xué)習(xí) :=:=| 推導(dǎo)方法：推導(dǎo)方法：從一個要識別的符號開始推導(dǎo)，即用相應(yīng)規(guī)則的右部來替代規(guī)則的左部

8、，每次僅用一條規(guī)則去進(jìn)行推導(dǎo)。 2010年年9月月.例：有一英語句子：The big elephant ate the peanut.:=:= :=the:=big:=elephant:=:=ate:= :=peanut 2010年年9月月. = = = 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:=:= :=:= := :

9、=the :=:=big :=:=elephant | peanut :=:= :=:=ate :=:= 2010年年9月月.上述推導(dǎo)可寫成 = the big elephant ate the peanut+說明： (1) 有若干語法成分同時存在時，我們總是從最左的語法成 分進(jìn)行推導(dǎo)，這稱之為最左推導(dǎo)，類似的有最右推導(dǎo)（一般推 導(dǎo)）。 (2) 從一組規(guī)則可推出不同的句子，如以上規(guī)則還可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它們 在語法上都正確，但在語義上都不正確。 所謂文法文法是在形式上對句子結(jié)構(gòu)的定義與描述，而未涉及語義問題。 2010年年9月月.產(chǎn)生式的定義產(chǎn)生式的定

10、義 設(shè)VN、 VT分別是非空有限的非終結(jié)符號集和終結(jié)符號集，V=VNVT ,VNVT=。 一個產(chǎn)生式是一個有序偶對（,）,其中V+,V*，通常表示為或:=。 稱為產(chǎn)生式的左部，稱為產(chǎn)生式的右部。 產(chǎn)生式又稱為重寫規(guī)則，它意味著能將一個符號串用另一個符號串替換。 2010年年9月月. 文法G =（VN，VT，P，S） VN：非終結(jié)符號集 VT：終結(jié)符號集 P：產(chǎn)生式或規(guī)則的集合 S：開始符號（識別符號） SVN 文法的定義文法的定義規(guī)則：U : xU VN, xV*如果產(chǎn)生式集中的產(chǎn)生式有共同的左部，如 :=，:=則可將其簡寫成:=| 2010年年9月月.P = Z ； ； ； ； 0； 1；

11、9；例：無符號整數(shù)的文法：G=（VN，VT，P，E）VN, ,EVT = 0,1,2,3,9 2010年年9月月. 文法和語言分類文法和語言分類 Chomsky將文法分為四類：0型、1型、2型、3型 這幾類文法的差別在于對產(chǎn)生式施加不同的限制。 0型： P： := 其中(VNVT)，(VNVT)* 0型語言：L0 這種語言可以用圖靈機(Turing)接受. 0型文法稱為短語結(jié)構(gòu)文法。規(guī)則的左部和右部都可以是符號串，一個短語可以產(chǎn)生另一個短語。 2010年年9月月. 1型： P： 1A2:= 12 其中 1,2(VNVT)*, AVN, (VNVT)+ 1型語言：L1 這種語言可以由一種線性界限

12、自動機接受.稱為上下文有關(guān)文法或上下文敏感文法。也即只有在1,2這樣的上下文中才能把A改寫為。 2010年年9月月. 2型： P： A:= 其中 AVN， (VNVT)+ 2型語言：L2 這種語言可以由下推自動機接受. 稱為上下文無關(guān)文法。也即把A改寫為時，不必考慮上下文。 注意：2型文法與BNF表示相等價。 2010年年9月月.（左線性） P： A:=a 或 A:=Ba 其中 A、BVN aVT3型語言：L3 又稱正則語言、正則集合 這種語言可以由有窮自動機接受. 3型文法稱為正則文法。它是對2型文法進(jìn)行進(jìn)一步限制。（右線性） P： A:=a 或 A:=aB 其中 A、BVN aVT 3型文

13、法： 2010年年9月月.根據(jù)上述分析，L0 L1 L2 L3 0型文法可以產(chǎn)生L0、L1、L2、L3，但2型文法只能產(chǎn)生L2，不能產(chǎn)生L1。 從0型文法到3型文法，各文法描述語言的能力依次減弱。 2010年年9月月.2.3語言和語法樹和推導(dǎo)推導(dǎo)有關(guān)的內(nèi)容 直接推導(dǎo)直接推導(dǎo) 設(shè)文法G(VN, VT, P, S) (, )P ，, (VNVT)* 則稱符號串為符號串應(yīng)用產(chǎn)生式:=所得到的直接推導(dǎo)直接推導(dǎo)，記為= 特別有，當(dāng)時，有= 即每個產(chǎn)生式得右部都是它左部的直接推導(dǎo)。 2010年年9月月. 1 1 0(6)=(1)=(3)(5)=(2) 當(dāng)符號串已沒有非終結(jié)符號時，推導(dǎo)就必須終止。因為終結(jié)符

14、不可能出現(xiàn)在規(guī)則左部，所以將在規(guī)則左部出現(xiàn)的符號稱為非終結(jié)符號。例如：例如：G (1) ； (2) (3) (4) 0;0;(5) 1;1; (13) 9;9; 2010年年9月月. 推導(dǎo)推導(dǎo) 文法G，U0,U1,U2,，Un V+ if v= U0 U1 U2 Unu 則v u= G= G= G= G= G例：= = = =1 =1 0即 10= G 2010年年9月月. 多步推導(dǎo)多步推導(dǎo) 文法G，v，w V+ if v w ,或v=w，則v w *= G= G 規(guī)范推導(dǎo)規(guī)范推導(dǎo) 有xUy = xuy, if y Vt* ,則此推導(dǎo)為規(guī)范的，記為xUy = xuy|直觀意義：規(guī)范推導(dǎo)最右推導(dǎo)

15、最右推導(dǎo)：若符號串中有兩個以上的非終結(jié)符時，先推右邊的。最左推導(dǎo)：若符號串中有兩個以上的非終結(jié)符時，先推左邊的。 + 若有v=U0=U1=U2=Un=w,則 v=w 。 2010年年9月月. 句型、句子和語言句型、句子和語言文法GZ所產(chǎn)生的所有句子的集合 形式語言理論可以證明以下兩點： （1）G L（G）； （2）L(G)G1，G2，Gn； 已知文法，求語言，通過推導(dǎo)； 已知語言，構(gòu)造文法，無形式化方法，更多是憑經(jīng)驗。 文法GZ （1）句型句型：x是句型 Z x,且xV*；（2）句子句子：x是句子 Z x, 且xVT*；（3）語言語言：L（GZ）=x| xVT*, Z x ；+* 2010年年

16、9月月. G1Z： ZaBa, Bb|bB G2Z： ZaBa, Bb|Bb等價文法等價文法 G和G是兩個不同的文法，若 L(G) = L(G) , 則G和G為等價文法。例：abna|n1,構(gòu)造其文法 2010年年9月月. 推導(dǎo)與語法樹推導(dǎo)與語法樹（1）語法樹：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由結(jié)點和有向邊組成。 結(jié)點：符號 根結(jié)點：識別符號識別符號 中間結(jié)點：非終結(jié)符非終結(jié)符 葉結(jié)點：終結(jié)符或非終結(jié)符終結(jié)符或非終結(jié)符 有向邊：表示結(jié)點間的派生關(guān)系。 ZUVabcd 2010年年9月月. 注意一個重要事實：文法所能產(chǎn)生的句子，可以 用不同的推導(dǎo)原則（使用產(chǎn)生式順序不同）將其 推導(dǎo)出來。語

17、法樹的生成規(guī)律不同，但最終生成的語 法樹形狀完全相同。某些文法有此性質(zhì)，而某些文法 不具此性質(zhì)。( 2 ) 句型的推導(dǎo)及語法樹的生成（自頂向下）給定GZ，句型w： 可建立推導(dǎo)序列，Z=w 可建立語法樹，以Z為樹根結(jié)點，每步推導(dǎo)生成語法樹的一枝，最終可生成句型的語法樹。G* 2010年年9月月. 1(1)(2)(3)(5)(4)0一般推導(dǎo)： 2010年年9月月.( 3 ) 樹與推導(dǎo)句型推導(dǎo)過程句型語法樹的生長過程 由推導(dǎo)構(gòu)造語法樹由推導(dǎo)構(gòu)造語法樹1從識別符號開始，自左向右建立推導(dǎo)序列。由根結(jié)點開始，自上而下建立語法樹。 2010年年9月月.例：G句型 10= =0 0= 0=110=規(guī)范推導(dǎo) 2

18、010年年9月月. 由語法樹構(gòu)造推導(dǎo)由語法樹構(gòu)造推導(dǎo)2自上而下地修剪子樹的末端結(jié)點，直至把整棵樹剪掉（留根），每剪一次對應(yīng)一次規(guī)約。從句型開始，自右向左地逐步進(jìn)行規(guī)約，建立推導(dǎo)序列。 注：注： 對句型中最左簡單短語（句柄）進(jìn)行的規(guī)約稱為 規(guī)范規(guī)約。 2010年年9月月.01= = 0=10 0=規(guī)范規(guī)約與規(guī)范推導(dǎo)互為逆過程 2010年年9月月.特別有特別有，通過規(guī)范推導(dǎo)或規(guī)范規(guī)約所得到的句型稱為規(guī)范句型。 在上例中， 就不是規(guī)范句型，因為：=不是規(guī)范推導(dǎo) 2010年年9月月.2.4關(guān)于文法和語言的幾點說明1. 1. 無用非終結(jié)符號無用非終結(jié)符號 如果文法的某個非終結(jié)符不出現(xiàn)在文法的任何一個句型

19、中，并且不能從它推導(dǎo)出終結(jié)符號串，則稱該非終結(jié)符為無用非終結(jié)符號。設(shè)文法GA： A:=aaBbb B:=aBb | ab C:= Cd | c D:=Ef 此文法中的非終結(jié)符D與E ，不可能出現(xiàn)在任何一個句型中，而且不能從它們推導(dǎo)出終結(jié)符號，所以，D與E是無用非終結(jié)符。 2010年年9月月.2. 2. 不可達(dá)文法符號不可達(dá)文法符號 如果一個非終結(jié)符（非識別符號）不出現(xiàn)在文法的任何一條產(chǎn)生式的右部，則稱該非終結(jié)符號為不可達(dá)文法符號。 不可達(dá)文法符號和無用非終結(jié)符號都不能出現(xiàn)在文法的句型中，也就是說，它們對與生成文法的語言都毫無意義，或者說包含不可達(dá)文法符號或無用非終結(jié)符號的產(chǎn)生式對于文法來講都是

20、多余的。 實際上，形如U:=U的產(chǎn)生式也是多余產(chǎn)生式。這種產(chǎn)生式不僅對文法是不必要的，而且還可能引起文法的二義性。 2010年年9月月.3 3. 可空非終結(jié)符可空非終結(jié)符 2型文法的產(chǎn)生式形如 A:= 其中, AVN, (VNVT)+ 對2型文法進(jìn)行擴充，令 (VNVT)*，即允許出現(xiàn)如下產(chǎn)生式 A:= 此產(chǎn)生式稱為空產(chǎn)生式，A稱為可空非終結(jié)符。 2型文法添加空產(chǎn)生式之后，文法的語言除了增加一個空串之外，并沒有改變文法的類型?？债a(chǎn)生式往往會帶來方便，如消除左遞歸。 2010年年9月月.4. 4. 二義性二義性 若對于一個文法的某一句子存在兩棵不同的語法樹，則該文法是二義性文法，否則是無二義性文

21、法。 換而言之，無二義性文法的句子只有一棵語法樹，盡管推導(dǎo)過程可以不同。下面舉一個二義性文法的例子： GE: E:= E+E | E*E | (E) | i Vn=EVt= +, * , ( , ) , i 2010年年9月月. 對于句子Sii * i L（GE ），存在不同的規(guī)范推導(dǎo)：EEE+EE*iiiEEE*EE+iii這兩種不同的推導(dǎo)對應(yīng)了兩種不同的語法樹(1) E=E+E=E+E*E =E+E*i =E+i*i = ii * i(2) E= E*E = E*i = E+E*i = E+i*i = ii * i 2010年年9月月. 注：注：若一個文法的某句子存在兩個不同的規(guī)范推導(dǎo)，則

22、該文法是二義性的，否則是無二義性的。 若文法是二義性的，則在編譯時就會產(chǎn)生不確定性，遺憾的是在理論上已經(jīng)證明：文法的二義性是不可判定的，即不可能構(gòu)造出一個算法，通過有限步驟來判定任一文法是否有二義性。 現(xiàn)在的解決辦法是：提出一些限制條件，稱為無二義性的充分條件，當(dāng)文法滿足這些條件時，就可以判定文法是無二義性的。 2010年年9月月.例例: :算術(shù)表達(dá)式的文法算術(shù)表達(dá)式的文法E:= E+E | E*E | (E) | iE:= E+T | TT := T*F | FF := (E) | i例例:Pascal :Pascal 條件語句的文法條件語句的文法:= If then | If then e

23、lse := | |. 對該文法可以加以一定的限制，比如限制條件語句then之后不允許再是條件語句，或者從語義解釋方面限制條件語句中的else只能與其緊前面的還沒有和其它else配對的then 配對。 2010年年9月月.2.5分析方法簡介 任務(wù)：給定GZ: S Vt*, 判定是否有 S L (GE ) ?這是詞法分析和語法分析所要做的工作，將在第三、四、五章中詳細(xì)介紹。自上而下分析方法自上而下分析方法 自下而上分析方法自下而上分析方法 2010年年9月月. 自上而下分析方法 基本思想：從文法的識別符號出發(fā)，看是否能推導(dǎo)出待檢查的符號串，如果能推導(dǎo)出這個符號串，則表明此符號串是該文法的一個句型或句子，否則便不是。 或者說，以文法的識