《編譯原理實(shí)踐及應(yīng)用》第2章文法基礎(chǔ)

1、編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 形式語(yǔ)言基本知識(shí)形式語(yǔ)言基本知識(shí) 第二章第二章 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 本章要求本章要求 主要內(nèi)容：符號(hào)串，文法的概念及分主要內(nèi)容：符號(hào)串，文法的概念及分 類(lèi)，語(yǔ)言的定義過(guò)程類(lèi)，語(yǔ)言的定義過(guò)程 重點(diǎn)掌握：上下文無(wú)關(guān)文法、推導(dǎo)、重點(diǎn)掌握：上下文無(wú)關(guān)文法、推導(dǎo)、 句型、句子、語(yǔ)言，語(yǔ)法樹(shù)、二義性句型、句子、語(yǔ)言，語(yǔ)法樹(shù)、二義性 文法、文法的語(yǔ)言生成過(guò)程文法、文法的語(yǔ)言生成過(guò)程 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 以C和PASCAL為例復(fù)習(xí)高級(jí)語(yǔ)言 1 語(yǔ)言的基本字符集的定義(字母, 數(shù)字, 界符) 2 單詞集的定義 3 數(shù)據(jù)類(lèi)型的定義 4 表達(dá)式的定

2、義 5 語(yǔ)句的定義 6 程序定義 PASCAL和C的主要區(qū)別 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 2.1 程序語(yǔ)言定義的基本概念程序語(yǔ)言定義的基本概念 1. 字母表字母表：是元素的有窮非空集合 2. 符號(hào)符號(hào)：字母表中的每個(gè)元素，因此字母表也稱(chēng) 為符號(hào)集。 不同的語(yǔ)言可以有不同的字母表，例如英文的字 母表中26個(gè)字母、數(shù)字及標(biāo)點(diǎn)符號(hào)等。 PASCAL語(yǔ)言的字母表是由字母、數(shù)字、若干專(zhuān) 用符號(hào)組成。 符號(hào)是該語(yǔ)言能識(shí)別的符號(hào)，字母表是該語(yǔ)言能 識(shí)別的所有符號(hào)的全體（字符集）。 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 基本概念基本概念( (續(xù)續(xù)) ) 3. 符號(hào)串符號(hào)串: 由字母表中的符號(hào)組成的任何有

3、窮 序列稱(chēng)為符號(hào)串，例如00 11 10 是字母表 =0， 1上的符號(hào)串. 字母表A=a,b,c上的一些符號(hào)串有： a,b,c,ab,aaca等。 在符號(hào)串中，符號(hào)的順序是很重要的，符號(hào)串 ab就不同于ba,abca和aabc也不同。 符號(hào)串 STR表示“由符號(hào)S、T和R，并按此順序組成. 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 基本概念(續(xù)) 4. 符號(hào)串的運(yùn)算符號(hào)串的運(yùn)算 a. 字符串的連接連接： 字符串稱(chēng)為字符串和的連接 符號(hào)串的長(zhǎng)度符號(hào)串的長(zhǎng)度 :符號(hào)串中符號(hào)的個(gè)數(shù)，例如: 某符號(hào)串中有m個(gè)符號(hào),則稱(chēng)其長(zhǎng)度為m，表示 為x=m，如001110的長(zhǎng)度是6。 空符號(hào)串空符號(hào)串: 即不包含任何符

4、號(hào)的符號(hào)串，用表 示，其長(zhǎng)度為0， 即=0。 用 *表示上所有的符號(hào)串的全體(長(zhǎng)度為0，1， 2，)。 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 集合的運(yùn)算 b. *的子集U、V的積積 ： UV = | U & V 長(zhǎng)度相加 即: 集合UV中的符號(hào)串是由U和V的符號(hào)串連接而成。 U = aa,bb V=00,11 則UV=? c. 集合的方冪方冪：n個(gè)相同符號(hào)連接 Vn =VVVV . V 規(guī)定V0 = d. 閉包、正閉包閉包、正閉包的運(yùn)算 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 例：例：=a,b=a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aa

5、a,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab, 使用使用 * 表示表示 上的一切符號(hào)串（包括上的一切符號(hào)串（包括）組成）組成 的集合。的集合。 稱(chēng)為稱(chēng)為的閉包的閉包。 上的上的除除外外的所有符號(hào)串組成的集合記為的所有符號(hào)串組成的集合記為 + 。 稱(chēng)為稱(chēng)為的正閉包的正閉包。 . 32 =+ V=0,1 V* = ? V+ = ? . 32 = * 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 2.2 上下文無(wú)關(guān)文法及其語(yǔ)言上下文無(wú)關(guān)文法及其語(yǔ)言 文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。 是一種工具，它可用于嚴(yán)格定義句子的結(jié) 構(gòu)；用有窮的

6、規(guī)則刻劃無(wú)窮的集合 文法是被用來(lái)精確而無(wú)歧義地描述語(yǔ)言的 句子的構(gòu)成方式. 文法描述語(yǔ)言的時(shí)候不考慮語(yǔ)言的含義。 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 引引 例例 例1：有如下規(guī)則 (表示由組成) | 我 大學(xué)生 是 | 現(xiàn)要求根據(jù)如上規(guī)則得出句子：我是大學(xué)生 = = = =我是大學(xué)生 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 句子“我是大學(xué)生”也可以如下圖示分 析 在有規(guī)則的情況下，每一次用上述規(guī)則的右邊去替 換左邊，得到“我是大學(xué)生”是符合上述規(guī)則的句 子 大學(xué)生大學(xué)生 我我 是是 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 上下文無(wú)關(guān)文法的形式定義上下文無(wú)關(guān)文法的形式定義 由四部分組成： 終結(jié)符號(hào)：是組

7、成該語(yǔ)言的最基本的符號(hào)， 是不可再分的基本符號(hào),如保留字、標(biāo)識(shí)符等。 非終結(jié)符號(hào)：規(guī)則中用尖括號(hào)括起來(lái)的符號(hào)， 表示一些語(yǔ)法成分，可以推導(dǎo)出其他的語(yǔ)法成 分,表示一定符號(hào)串的集合，是一個(gè)類(lèi)，如表 達(dá)式。 開(kāi)始符號(hào)：規(guī)則中的一個(gè)特殊的非終結(jié)符號(hào)， 語(yǔ)言中的句子都從它開(kāi)始推導(dǎo),如程序、句子 產(chǎn)生式：定義語(yǔ)法成分的規(guī)則，其中： 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 文法的形式定義文法的形式定義( (續(xù)續(xù)) ) 一個(gè)文法G抽象地表示為四元組 G=（Vn,Vt,P,S） 其中Vn表示非終結(jié)符號(hào) Vt表示終結(jié)符號(hào)，VnVt=(字母表)， VnVt= S是開(kāi)始符號(hào)， P是產(chǎn)生式，形如：(V+且至少含有 一個(gè)非

8、終結(jié)符號(hào)，V*) 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 上例中： G=（Vn,Vt,P,） Vn=（， ，） Vt= (我，是，大學(xué)生) P = | 我 大學(xué)生 是 | 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 產(chǎn)生式的形式為：A 左部符號(hào)， 非終結(jié)符 右部，可以含有非 終結(jié)符和終結(jié)符 又稱(chēng)為一條規(guī)則 有時(shí)一個(gè)產(chǎn)生式不足以描述該語(yǔ)法范疇，就用多個(gè)產(chǎn)生式， 如算術(shù)表達(dá)式的描述為：(遞歸定義) E E + E E E * E E i 相同左部的一個(gè)右部又稱(chēng)一個(gè)候選式 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 上下文無(wú)關(guān)上下文無(wú)關(guān)文法所定義的語(yǔ)法成分獨(dú)立于它可 能出現(xiàn)的環(huán)境，即不考慮上下文。 編譯原理實(shí)踐及應(yīng)用第

9、2章文 法基礎(chǔ) 算術(shù)表達(dá)式的文法定義算術(shù)表達(dá)式的文法定義 變量是表達(dá)式 表達(dá)式 + 表達(dá)式是表達(dá)式 表達(dá)式 * 表達(dá)式是表達(dá)式 (表達(dá)式) 是 表達(dá)式 E E + E E E * E E ( E ) E i E E+E | E*E | (E) | i 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 上下文無(wú)關(guān)文法產(chǎn)生句子的方法上下文無(wú)關(guān)文法產(chǎn)生句子的方法:從文法的開(kāi)始 符號(hào)出發(fā),反復(fù)連續(xù)使用產(chǎn)生式,對(duì)左邊的非終 結(jié)符進(jìn)行替換和展開(kāi) 例：表達(dá)式定義規(guī)則 E E + E E E * E E ( E ) E i ( i+i ) E=( E ) =( E+E ) =( i+E ) =( i + i ) 編譯原理實(shí)

10、踐及應(yīng)用第2章文 法基礎(chǔ) 推導(dǎo): 連續(xù)使用產(chǎn)生式右部去替換左部某 個(gè)非終結(jié)符的過(guò)程,得到的連續(xù)序列稱(chēng)為一 個(gè)推導(dǎo)。 直接推導(dǎo)：又稱(chēng)一步推導(dǎo)(用 符號(hào)=表示), 就是用某條規(guī)則的右部去替換該規(guī)則的左 部 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 幾個(gè)概念的形式定義幾個(gè)概念的形式定義 直接推導(dǎo): 如果是文法 G=（Vn,Vt,P,S） 的產(chǎn)生式，和是*中的任意符號(hào)，若有符號(hào) 串v,w滿足： v=,w=,則說(shuō)v直接產(chǎn)生w，(w是v的 直接推導(dǎo))記作：v=w 例：S01, 0S0=0010(直接推導(dǎo),) 如果存在v=w0=w1=w2.=Wn=w(n0)，則稱(chēng)v 推導(dǎo)出w（長(zhǎng)度為n），記作v=w(至少一步)

11、若有=w或v=w，則記作v=w(0步或若干步) * + 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 例3 : G = (E, i, +, *, (, ) , P , E) (1.1) P： E E+E | E*E | (E) | i 表達(dá)式(i)和(i+i)*i的推導(dǎo)： E (E) (i) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i E E 0步推導(dǎo) E (i + i)*i 6步推導(dǎo) E (i + i)*i 6步推導(dǎo) E (E) 直接推導(dǎo) 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 句型句型：設(shè)(s)是一文法，如果符號(hào)串x是從開(kāi)始符 號(hào)推導(dǎo)出來(lái)的，即

12、有s=x,則稱(chēng)x是文法G(s)的一個(gè) 句型。 即: 任何由開(kāi)始符推導(dǎo)出來(lái)的符號(hào)串都是句型。 句子句子：若x僅由終結(jié)符號(hào)組成，則稱(chēng)x為G(S)的句子 * 練習(xí)練習(xí) 文法文法G：SaAcB | Bd AAaB | c BbScA | b 寫(xiě)出句型寫(xiě)出句型aAcbBdcc和句子和句子acabcbbdcc的的 推導(dǎo)過(guò)程。推導(dǎo)過(guò)程。 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 文法文法G所產(chǎn)生的語(yǔ)言所產(chǎn)生的語(yǔ)言定義為： L(G)=x|S=x,其中S為文法的開(kāi)始符號(hào)，xVt* 。 即: 一個(gè)文法G可以推導(dǎo)出的所有句子構(gòu)成的一個(gè)集 合, 就確定了一個(gè)語(yǔ)言。 * 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 例2.1 (P30

13、) 考慮文法G1: 它定義了什么語(yǔ)言。 S bA A aA|a 推導(dǎo)過(guò)程 ：S=bA =ba S=bA =baA=baa . S=bA =baA= =baa 歸納得： L(G1) = ban | n1 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 練習(xí)：文法(A,B,S,a,b,c,P,S) S Ac|aB A ab B bc 寫(xiě)出(G)的全部元素 L(G) = abc 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 例2.2(P30) 考慮文法G2: 它定義的語(yǔ)言是： S AB A aA|a B bB|b L(G2) = ambn |m,n1 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 思考：構(gòu)造一個(gè)文法G3使得： L(

14、G3) = anbn |n1 S aSb S ab a,b的個(gè)數(shù)相同,則文法G3為： 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 文法等價(jià)：文法等價(jià)： 若文法G1和文法G2所產(chǎn)生的語(yǔ)言相同，即L(G1) = L(G2)，則稱(chēng)文法G1和文法G2等價(jià)等價(jià)。 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 例：有如下兩個(gè)文法，判斷它們是否等價(jià)？ G1=（S，0，S，S0S，S0） G2=（S，0，S，SS0，S0） S0 S0S00 S0S 00S 0000 L(G1) = 0n | n1 對(duì)于對(duì)于G2： 對(duì)于對(duì)于G1 ： SS0 S00 0000 L(G2) = 0n | n1 G1G2，但L(G1) = L(G2)

15、，文法G1和G2等價(jià) 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 例3 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表達(dá)式 (i+i)*i的推導(dǎo)過(guò)程： (1) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i (2) E E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*i l 得到一個(gè)語(yǔ)言，是通過(guò)利用所有的產(chǎn)生式推導(dǎo) 出所有可能的句子，構(gòu)成一個(gè)集合。 l 但是一個(gè)句型到另一個(gè)句型(句子)的推導(dǎo)過(guò)程 不是唯一的。 編譯原理實(shí)踐及應(yīng)用

16、第2章文 法基礎(chǔ) 最左推導(dǎo)最左推導(dǎo): 在整個(gè)推導(dǎo)過(guò)程中,任何一步推導(dǎo) =都是對(duì)中最左邊的非終結(jié)符進(jìn)行替換。 最右推導(dǎo)最右推導(dǎo): 在推導(dǎo)之前確定推導(dǎo)的順序，是對(duì)句子進(jìn)行確 定性分析所必須的 例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i (i+i)*i的最左推導(dǎo)過(guò)程： E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i 最右推導(dǎo)過(guò)程： E E*E E*i (E + E)*i (E+ i)*i (i + i)*i 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 2.3 語(yǔ)法樹(shù)

17、和文法的二義性語(yǔ)法樹(shù)和文法的二義性 語(yǔ)法樹(shù)語(yǔ)法樹(shù)：推導(dǎo)的形式化表示推導(dǎo)的形式化表示，有助于理解句子 語(yǔ)法結(jié)構(gòu)的層次 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，該標(biāo)記屬字母集中的 一個(gè)符號(hào)，根由開(kāi)始符號(hào)標(biāo)記。 當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)， 就產(chǎn)生相應(yīng)的下一層的結(jié)點(diǎn)，候選式中自左至 右的每個(gè)符號(hào)對(duì)應(yīng)一個(gè)新的結(jié)點(diǎn)，并標(biāo)記它， 畫(huà)出其與父結(jié)點(diǎn)之間的連線。 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 例：對(duì)文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的語(yǔ)法樹(shù)： 在語(yǔ)法樹(shù)的推導(dǎo)過(guò)程中 的任何時(shí)刻，沒(méi)有后代 的端末結(jié)點(diǎn)自

18、左至右排 列起來(lái)就是一個(gè)句型 一棵語(yǔ)法樹(shù)表示了一個(gè) 句型很多可能的不同推 導(dǎo)過(guò)程。(包括最左推導(dǎo) 和最右推導(dǎo)) 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子 ( i * i + i)的語(yǔ)法樹(shù)： (1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i) (2) E (E) (E * E) (i*E) (i * E + E) (i * i + E) (i *i + i) 并不是任何情況下一個(gè)句型就唯一地對(duì)應(yīng)一棵語(yǔ)法樹(shù)。 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 2.3 文法的二義性文法的二義性 定義定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng) 兩棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二二 義義的 對(duì)二義文法中的某個(gè)句子的分析不是唯 一的，因此總是希望文法是無(wú)二義的。 但是二義文法有時(shí)也是有用的。 編譯原理實(shí)踐及應(yīng)用第2章文 法基礎(chǔ) 上下文無(wú)關(guān)語(yǔ)言的限制上下文無(wú)關(guān)語(yǔ)言的限制 文法中不含產(chǎn)生式PP 每個(gè)非終結(jié)符P必須都有用處，ie:對(duì)于P不 存在永不終結(jié)的回路