編譯原理課件：Chapter-2 文法和語言的概念和表示

1、第二章 文法和語言的概念和表示2.1 預(yù)備知識 - 形式語言基礎(chǔ)2.2 文法和語言的定義2.3 幾個重要概念2.4 文法的表示：擴充的BNF范式和語 法圖2.5 文法和語言的分類12.1 預(yù)備知識一、字母表和符號串 字母表：符號的非空有限集 例：=a，b，c 符號：字母表中的元素 例： a，b，c 符號串：符號的有窮序列 例：a, aa, ac, abc，. 空符號串：無任何符號的符號串() 符號串集合：由符號串構(gòu)成的集合。符號串的形式定義 有字母表，定義： （1）是上的符號串； （2）若x是上的符號串，且a ，則ax或xa是上的符號串； （3）y是上的符號串，iff（當且僅當）y可由（1）和

2、（2）產(chǎn)生。2二、符號串和符號串集合的運算 1.符號串相等：若x、y是集合上的兩個符號串，則xyiff（當且僅當）組成x的每一個符號和組成y的每一個符號依次相等。 2.符號串的長度：x為符號串，其長度|x|等于組成該符 號串的符號個數(shù)。 例： xSTV ， |x|=3。3 ac，ad，bc，bd 因為xxx，所以A = A = A例：Aa,b, B=c,d, AB= ？ 4. 符號串集合的乘積運算：令A(yù)、B為符號串集合，定義 AB xy |xA, yB3.符號串的聯(lián)接：若x、y是定義在上的符號串，且xXY，yYX，則 x 和 y 的聯(lián)接 xyXYYX也是上的符號串。 注意：一般xyyx，而xx

3、46.符號串集合的閉包運算：設(shè)A是符號串集合，定義 A A1 A2 A3 An 稱為集合A的正閉包。 A* A0 A稱為集合A的閉包。例：A=x,y A？ A* ？ 5. 符號串集合的冪運算：有符號串集合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 A35 為什么對符號、符號串、符號串集合以及它們的運算感興趣？若A為某語言的基本字符集 Aa,b,z,0,1,9, +,_

4、/, ( , ), =B為單詞集 B =begin, end, if, then,else,for, 則B A* 。語言的句子是定義在B上的符號串。若令C為句子集合，則C B * , 程序 C。62.2文法的非形式討論 1.什么是文法：文法是對語言結(jié)構(gòu)的定義與描述。即從形式上用于描述和規(guī)定語言結(jié)構(gòu)的稱為“文法”（或稱為“語法”）。 例：有一句子：“我是大學生” 。這是一個在語法、語義上都正確的句子，該句子的結(jié)構(gòu)（稱為語法結(jié)構(gòu)）是由它的語法決定的 。在本例中它為“主謂結(jié)構(gòu)”。如何定義句子的合法性？有窮語言無窮語言7 2.語法規(guī)則：我們通過建立一組規(guī)則，來描述句子的語法結(jié)構(gòu)。規(guī)定用“:=”表示“由

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

6、he big elephant ate the peanut.:=:= :=the:=big:=elephant:=:=ate:= :=peanut11 = = = 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:=最左推導(dǎo)！12 = = = =

7、peanut = the peanut = ate the peanut = ate the peanut = elephant ate the peanut = big elephant ate the peanut = the big elephant ate the peanut:=:= :=the:=big:=elephant | peanut:=:=ate:=最右推導(dǎo)！13上述推導(dǎo)可寫成 = the big elephant ate the peanut+說明： (1) 有若干語法成分同時存在時，我們總是從最左的語法成 分進行推導(dǎo)，這稱之為最左推導(dǎo)。類似地還有最右推導(dǎo)（一般推 導(dǎo)）。

8、 (2) 除了最左和最右推導(dǎo)，還可能存在其它形式的推導(dǎo)。 (3) 從一組規(guī)則可推出不同的句子，如以上規(guī)則還可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它們在語法上都正確，但在語義上都不正確。 所謂文法是在形式上對句子結(jié)構(gòu)的定義與描述，而未涉及語義問題。14 4.語法樹：我們用語法樹來描述一個句子的語法結(jié)構(gòu)。Thebigelephantatethepeanut語法成分（在形式語言中又稱“非終結(jié)符”）單詞符號（在形式語言中又稱“終結(jié)符號”)152.3.1 文法的定義2.3 文法和語言的形式定義 定義1. 文法G=（Vn，Vt，P，Z） Vn：非終結(jié)符號集 Vt：終結(jié)符號集 P：產(chǎn)生

9、式或規(guī)則的集合 Z：開始符號（識別符號） ZVn VVn Vt稱為文法的字匯表規(guī)則：U : xU Vn, xV*補: 規(guī)則的定義規(guī)則是一個有序?qū)?U, x), 通常寫為: U : x 或U x | U| = 1 |x| 016P = 0 1 9 Z = 例：無符號整數(shù)的文法：G=（Vn，Vt，P，Z）Vn, Vt = 0,1,2,3,917幾點說明：產(chǎn)生式左邊符號構(gòu)成集合Vn，且 Z Vn有些產(chǎn)生式具有相同的左部，可以合在一起。例、 | 0 | 1 | 2 | 3 | | 9 文法的BNF表示給定一個文法，實際只需給出產(chǎn)生式集合，并指定識別符號。（識別符號一般約定為第一條規(guī)則的左部符號）例、

10、G | 0 | 1 | 2 | 3 | | 9182.3.2 推導(dǎo)的形式定義 定義2：文法G：vx Uy，wxuy, 其中x、y V* ，UVn, uV*, 若U : uP，則v w。 若xy，有U : u，則U uGG根據(jù)文法和推導(dǎo)定義，可推出終結(jié)符號串，所謂文法能推出句子來。例如：G (1) (2) (3) (4) 0(5) 1 (13) 919= 1 1 0(5)=(1)=(3)(4)=(2) 當符號串已沒有非終結(jié)符號時，推導(dǎo)就必須終止。因為終結(jié)符不可能出現(xiàn)在規(guī)則左部，所以將在規(guī)則左部出現(xiàn)的符號稱為非終結(jié)符號。例如：G (1) (2) (3) (4) 0(5) 1 (13) 920 定義

11、3：文法G，U0, U1, U2, ，Un V+ if v= U0 U1 U2 Unw 則v w= G= G= G= G= G例：= = = =1 =1 0即 10= G= G21 若有v=U0=U1=U2=Un=w, 則 v=w 。 +直觀意義：規(guī)范推導(dǎo)最右推導(dǎo)最右推導(dǎo)：若符號串中有兩個以上的非終結(jié)符時，先推右邊的。最左推導(dǎo)：若符號串中有兩個以上的非終結(jié)符時，先推左邊的。 定義4：文法G， v，w V+ if v w ,或v:=w，則v w 。 *= G= G 定義5：規(guī)范推導(dǎo)：有xUy = xuy, if y Vt* ,則此推導(dǎo)為規(guī)范的，記為xUy = xuy 。| *= G =|=222

12、.3.3 語言的形式定義 定義6：文法GZ （1）句型：x是句型 Z x,且xV*；（2）句子：x是句子 Z x, 且xVt*；（3）語言：L(GZ) = x| xVt*, Z x ；+文法GZ所產(chǎn)生的所有句子的集合 形式語言理論可以證明以下兩點： （1）G L(G)； （2）L(G)G1，G2，Gn； 已知文法，求語言，通過推導(dǎo)； 已知語言，構(gòu)造文法，無形式化方法，更多是憑經(jīng)驗。*23例：abna | n1，構(gòu)造其文法 G1Z： ZaBa Bb|bB G2Z： ZaBa Bb|Bb 定義7. G和G是兩個不同的文法，若 L(G) = L(G) , 則G和G為等價文法。24編譯感興趣的問題是:

13、給定x, G, 求x L(G) ?x算法1算法2x L(G) ?Gyn出錯處理停機252.3.4 遞歸文法1.遞歸規(guī)則：規(guī)則右部有與左部相同的符號 對于 U:= xUy 若x=,即U:= Uy，左遞歸； 若y=,即U:= xU，右遞歸。 2.遞歸文法：文法G，存在U Vn if U=U, 則G為遞歸文法(自嵌入遞歸)； if U=U, 則G為左遞歸文法； if U=U, 則G為右遞歸文法。+264. 遞歸文法的優(yōu)點：可用有窮條規(guī)則，定義無窮語言 例：對于前面給出的無符號整數(shù)的文法是有遞歸文法，用13條規(guī)則就可以定義出所有的無符號整數(shù)。若不用遞歸文法，那將要用多少條規(guī)則呢？!3. 左遞歸文法的缺

14、點：不能用自頂向下的方法來進行語法分析會造成死循環(huán)（后面將詳細論述）272.3.5 句型的短語、簡單短語和句柄定義8. 給定文法GZ, w:=xuyV+，為該文法的句型, 若 Z= xUy, 且U=u, 則u是句型w相對于U的短語； 若 Z= xUy, 且U=u, 則u是句型w相對于U的簡單短語。 其中U Vn，u V+，x, y V* 直觀理解：短語是前面句型中的某個非終結(jié)符所能推出的符號串。28定義9. 任一句型的最左簡單短語稱為該句型的句柄。 給定句型找句柄的步驟： 短語 簡單短語 句柄注意：短語、簡單短語是相對于句型而言。一個句型可能有多個短語、簡單短語，但句柄只能有一個。292.4

15、語法樹與二義性文法2.4.1 推導(dǎo)與語法樹（1）語法樹：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由結(jié)點和有向邊組成。 結(jié)點：符號 根結(jié)點：識別符號 中間結(jié)點：非終結(jié)符 葉結(jié)點：終結(jié)符或非終結(jié)符 有向邊：表示結(jié)點間的派生關(guān)系。 ZUVabcd30 注意一個重要事實：文法所能產(chǎn)生的句子，可以 用不同的推導(dǎo)原則（使用產(chǎn)生式順序不同）將其 推導(dǎo)出來。語法樹的生成規(guī)律不同，但最終生成的語 法樹形狀完全相同。某些文法有此性質(zhì)，而某些文法 不具有此性質(zhì)。( 2 ) 句型的推導(dǎo)及語法樹的生成（自頂向下）給定GZ，句型w： 可建立推導(dǎo)序列，Z=w 可建立語法樹，以Z為樹根結(jié)點，每步推導(dǎo)生成語法樹的一枝，最終可生成

16、句型的語法樹。G*31 (1)(2)(3)1(5)(4)0一般推導(dǎo)：32 (1)(2)(3)1(4)(5)0最左推導(dǎo)：33 (1)(2)(4)1(5)(3)0最右推導(dǎo)：34( 3 ) 子樹與短語 子樹：語法樹中的某個結(jié)點（子樹的根）連同它向下派生的部分所組成。 某子樹的末端結(jié)點按自左向右順序為句型中的符號串，則該符號串為該句型的相對于該子樹根的短語。定理 只需畫出句型的語法樹，然后根據(jù)子樹找短語簡單短語句柄。35( 4 ) 樹與推導(dǎo)句型推導(dǎo)過程句型語法樹的生長過程 由推導(dǎo)構(gòu)造語法樹1從識別符號開始，自右向左建立推導(dǎo)序列。由根結(jié)點開始，自上而下建立語法樹。36例：G句型10= =0 0= 0=1

17、10=規(guī)范推導(dǎo)37 由語法樹構(gòu)造推導(dǎo)2自下而上地修剪子樹的末端結(jié)點，直至把整棵樹剪掉（留根），每剪一次對應(yīng)一次規(guī)約。從句型開始，自左向右地逐步進行規(guī)約，建立推導(dǎo)序列。定義12. 對句型中最左簡單短語（句柄）進行的規(guī)約稱為 規(guī)范規(guī)約。3801= = 0=10 0=規(guī)范規(guī)約與規(guī)范推導(dǎo)互為逆過程39定義13.通過規(guī)范推導(dǎo)或規(guī)范規(guī)約所得到的句型稱為規(guī)范句型。 在上例中， 就不是規(guī)范句型，因為：=不是規(guī)范推導(dǎo)！402.4.2 文法的二義性 定義14.1 若對于一個文法的某一句子存在兩棵不同的語法樹，則該文法是二義性文法，否則是無二義性文法。 換而言之，無二義性文法的句子只有一棵語法樹，盡管推導(dǎo)過程可以不

18、同。下面舉一個二義性文法的例子： GE: E:= E+E | E*E | (E) | i Vn=EVt= +, * , ( , ) , i 41 對于句子 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 * i42 定義14.2 若一個文法的某句子存在兩個不同的規(guī)范推導(dǎo)，則該文法是二義性的，否則是無二義性的。 以上是自頂向下來看文法的二義性，我們還可以自底向上來看文

19、法的二義性。上例中，規(guī)范句型E+E*i 是由ii * i通過兩步規(guī)范規(guī)約得到的，但對于同一個句型E+E* i，它有兩個不同的句柄（對應(yīng)上述兩棵不同的語法樹）：i 和 EE。因此語法的二義性意味著句型的句柄不唯一。43EEE+EE*iEEE*EE+i句柄：i句柄：EE 定義14.3 若一個文法的某規(guī)范句型的句柄不唯一，則該文法是二義性的，否則是無二義性的。44 若文法是二義性的，則在編譯時就會產(chǎn)生不確定性。遺憾的是在理論上已經(jīng)證明：文法的二義性是不可判定的，即不可能構(gòu)造出一個算法，通過有限步驟來判定任一文法是否有二義性。 現(xiàn)在的解決辦法是：提出一些限制條件，稱為無二義性的充分條件。當文法滿足這些

20、條件時，就可以判定文法是無二義性的。 由于無二義性文法比較簡單，我們也可以采用另一種解決辦法：即不改變二義性文法，而是確定一種編譯算法，使該算法滿足無二義性充分條件。45例:算術(shù)表達式的文法E:= E + E | E * E | ( E ) | iE := E + T | TT := T * F | FF := ( E ) | i例:Pascal 條件語句的文法:= If then | If then else := | |.462.5 句子的分析 任務(wù)：給定GZ: S Vt*, 判定是否有 S L (GE ) ?這是詞法分析和語法分析所要做的工作，將在第三、四章中詳細介紹。472.6 有關(guān)文

21、法的實用限制 若文法中有如U:=U的規(guī)則，則這就是有害規(guī)則，它會引起二義性。 例如存在U:=U， U:= a | b,則有兩棵語法樹：UaUUa48 多余規(guī)則：（1）在推導(dǎo)文法的所有句子中，始終用不到的規(guī)則。即該規(guī)則的左部非終結(jié)符不出現(xiàn)在任何句型中。（2）在推導(dǎo)句子的過程中，一旦使用了該規(guī)則，將推不出任何終結(jié)符號串。即該規(guī)則中含有推不出任何終結(jié)符號串的非終結(jié)符。 例如給定GZ，若其中關(guān)于U的規(guī)則只有如下一條： U:=xUy 該規(guī)則是多余規(guī)則。若還有U:=a，則此規(guī)則并非多余若某文法中無有害規(guī)則或多余規(guī)則，則稱該文法是壓縮過的。492.7 文法的其它表示法 1、擴充的BNF表示(Backus Normal Form) BNF的元符號： , :=, | 擴充的BNF的元符號： , :=, |, , , , (, ) 2、語法圖 字母 字母 數(shù)字 數(shù)字 標識符無符號整數(shù)502.8 文法和語言分類 形式語言：用文法和自動機所描述的沒有語義的語言。 文法定義：喬姆斯基將所有文法都定義為一個四元組：G=（Vn，Vt，P，Z） Vn：非終結(jié)符號集 Vt：終結(jié)符號集 P：產(chǎn)生式或規(guī)則的集合 Z：開始符號（識別符號） ZVn 語言定義： L(GZ) = x | xVt*, Z = x +51 文