《編譯原理實踐及應用》第2章文法基礎

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

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

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

4、號的符號串，用表 示，其長度為0， 即=0。 用 *表示上所有的符號串的全體(長度為0，1， 2，)。 編譯原理實踐及應用第2章文 法基礎 集合的運算 b. *的子集U、V的積積 ： UV = | U & V 長度相加 即: 集合UV中的符號串是由U和V的符號串連接而成。 U = aa,bb V=00,11 則UV=? c. 集合的方冪方冪：n個相同符號連接 Vn =VVVV . V 規(guī)定V0 = d. 閉包、正閉包閉包、正閉包的運算 編譯原理實踐及應用第2章文 法基礎 例：例：=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, 使用使用 * 表示表示 上的一切符號串（包括上的一切符號串（包括）組成）組成 的集合。的集合。 稱為稱為的閉包的閉包。 上的上的除除外外的所有符號串組成的集合記為的所有符號串組成的集合記為 + 。 稱為稱為的正閉包的正閉包。 . 32 =+ V=0,1 V* = ? V+ = ? . 32 = * 編譯原理實踐及應用第2章文 法基礎 2.2 上下文無關文法及其語言上下文無關文法及其語言 文法是描述語言的語法結構的形式規(guī)則。 是一種工具，它可用于嚴格定義句子的結 構；用有窮的

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

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

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

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

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

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

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

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

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

15、，文法G1和G2等價 編譯原理實踐及應用第2章文 法基礎 例3 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表達式 (i+i)*i的推導過程： (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 得到一個語言，是通過利用所有的產(chǎn)生式推導 出所有可能的句子，構成一個集合。 l 但是一個句型到另一個句型(句子)的推導過程 不是唯一的。 編譯原理實踐及應用

16、第2章文 法基礎 最左推導最左推導: 在整個推導過程中,任何一步推導 =都是對中最左邊的非終結符進行替換。 最右推導最右推導: 在推導之前確定推導的順序，是對句子進行確 定性分析所必須的 例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i (i+i)*i的最左推導過程： E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i 最右推導過程： E E*E E*i (E + E)*i (E+ i)*i (i + i)*i 編譯原理實踐及應用第2章文 法基礎 2.3 語法樹

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

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