編譯原理21 文法和語(yǔ)言

1、12.1 2.1 文法和語(yǔ)言文法和語(yǔ)言v 0 概述概述v 1 形式語(yǔ)言基礎(chǔ)形式語(yǔ)言基礎(chǔ)v 2 文法的直觀理解文法的直觀理解v 3 文法和語(yǔ)言的定義文法和語(yǔ)言的定義v 4 文法的類型文法的類型v 5 語(yǔ)法樹(shù)與二義性語(yǔ)法樹(shù)與二義性v 6 句型的分析句型的分析20 0 概述概述顯然，用高級(jí)語(yǔ)言編程比用低級(jí)語(yǔ)言來(lái)得方便，顯然，用高級(jí)語(yǔ)言編程比用低級(jí)語(yǔ)言來(lái)得方便，但要解決兩個(gè)問(wèn)題：但要解決兩個(gè)問(wèn)題：1.1.計(jì)算機(jī)怎樣懂得高級(jí)語(yǔ)言程序，這就需要一計(jì)算機(jī)怎樣懂得高級(jí)語(yǔ)言程序，這就需要一個(gè)翻譯程序?qū)崿F(xiàn)從源程序到目標(biāo)程序的轉(zhuǎn)換。個(gè)翻譯程序?qū)崿F(xiàn)從源程序到目標(biāo)程序的轉(zhuǎn)換。2.2.用什么方法來(lái)精確定義高級(jí)語(yǔ)言，即怎樣

2、精用什么方法來(lái)精確定義高級(jí)語(yǔ)言，即怎樣精確描述高級(jí)語(yǔ)言。確描述高級(jí)語(yǔ)言。要構(gòu)造一個(gè)編譯程序，應(yīng)深刻理解被編譯的源要構(gòu)造一個(gè)編譯程序，應(yīng)深刻理解被編譯的源語(yǔ)言的結(jié)構(gòu)（即詞法和語(yǔ)法）及其含義（即語(yǔ)義），語(yǔ)言的結(jié)構(gòu)（即詞法和語(yǔ)法）及其含義（即語(yǔ)義），同時(shí)要弄清源語(yǔ)言的語(yǔ)法規(guī)則和語(yǔ)義規(guī)則是采用什同時(shí)要弄清源語(yǔ)言的語(yǔ)法規(guī)則和語(yǔ)義規(guī)則是采用什么理論或什么方法來(lái)描述的。么理論或什么方法來(lái)描述的。3當(dāng)我們表述一種語(yǔ)言時(shí)，無(wú)非是要說(shuō)明這種語(yǔ)言的當(dāng)我們表述一種語(yǔ)言時(shí)，無(wú)非是要說(shuō)明這種語(yǔ)言的句子，如果語(yǔ)言只含有窮多個(gè)句子，則只需列出句子的句子，如果語(yǔ)言只含有窮多個(gè)句子，則只需列出句子的有窮集就行了，但對(duì)于含有無(wú)窮句

3、子的語(yǔ)言來(lái)講，就存有窮集就行了，但對(duì)于含有無(wú)窮句子的語(yǔ)言來(lái)講，就存在著如何給出它的有窮表示的問(wèn)題。在著如何給出它的有窮表示的問(wèn)題。以自然語(yǔ)言為例，人們無(wú)法列出全部句子，但是人以自然語(yǔ)言為例，人們無(wú)法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來(lái)說(shuō)明們可以給出一些規(guī)則，用這些規(guī)則來(lái)說(shuō)明(或者定義或者定義)句句子的組成結(jié)構(gòu)，比如漢語(yǔ)句子可以是由主語(yǔ)后隨謂語(yǔ)而子的組成結(jié)構(gòu)，比如漢語(yǔ)句子可以是由主語(yǔ)后隨謂語(yǔ)而成，構(gòu)成謂語(yǔ)的是動(dòng)詞和直接賓語(yǔ)。成，構(gòu)成謂語(yǔ)的是動(dòng)詞和直接賓語(yǔ)。4任何語(yǔ)言均可看作一個(gè)集合。這個(gè)集合中的每任何語(yǔ)言均可看作一個(gè)集合。這個(gè)集合中的每個(gè)元素都是在個(gè)元素都是在一定符號(hào)集（字母表）

4、上的一個(gè)符號(hào)一定符號(hào)集（字母表）上的一個(gè)符號(hào)串串。對(duì)于自然語(yǔ)言來(lái)說(shuō)，它們是定義在某個(gè)字母表對(duì)于自然語(yǔ)言來(lái)說(shuō)，它們是定義在某個(gè)字母表上的上的句子的集合句子的集合。對(duì)于程序語(yǔ)言來(lái)說(shuō)，它們也是定義在某個(gè)字母對(duì)于程序語(yǔ)言來(lái)說(shuō)，它們也是定義在某個(gè)字母表上的表上的句子句子的集合。的集合。這里的句子，就是一個(gè)源程序這里的句子，就是一個(gè)源程序。 通常，源程序是由關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)通常，源程序是由關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符以及一些界限符組成。算符以及一些界限符組成。這些語(yǔ)法成分統(tǒng)稱為單詞或單詞符號(hào)。這些語(yǔ)法成分統(tǒng)稱為單詞或單詞符號(hào)。單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最基本單位。單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的

5、最基本單位。語(yǔ)言的單詞符號(hào)是由詞法規(guī)則所確定的，即詞法規(guī)語(yǔ)言的單詞符號(hào)是由詞法規(guī)則所確定的，即詞法規(guī)則規(guī)定了單詞符號(hào)的形成規(guī)則。則規(guī)定了單詞符號(hào)的形成規(guī)則。5語(yǔ)言概述語(yǔ)言概述語(yǔ)言是由句子組成的集合，或說(shuō)是由一組符號(hào)串語(yǔ)言是由句子組成的集合，或說(shuō)是由一組符號(hào)串所構(gòu)成的集合。所構(gòu)成的集合。漢語(yǔ)漢語(yǔ)所有符合漢語(yǔ)語(yǔ)法的句子的全體所有符合漢語(yǔ)語(yǔ)法的句子的全體英語(yǔ)英語(yǔ)所有符合英語(yǔ)語(yǔ)法的句子的全體所有符合英語(yǔ)語(yǔ)法的句子的全體程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言所有該語(yǔ)言的源程序的全體所有該語(yǔ)言的源程序的全體 每個(gè)句子構(gòu)成的規(guī)律每個(gè)句子構(gòu)成的規(guī)律研究語(yǔ)言研究語(yǔ)言 每個(gè)句子的含義每個(gè)句子的含義 每個(gè)句子和使用者的關(guān)系每個(gè)句

6、子和使用者的關(guān)系6研究程序設(shè)計(jì)語(yǔ)言研究程序設(shè)計(jì)語(yǔ)言 每個(gè)程序構(gòu)成的規(guī)律每個(gè)程序構(gòu)成的規(guī)律 每個(gè)程序的含義每個(gè)程序的含義 每個(gè)程序和使用者的關(guān)系每個(gè)程序和使用者的關(guān)系語(yǔ)言研究的三個(gè)方面語(yǔ)言研究的三個(gè)方面 語(yǔ)法語(yǔ)法 Syntax 語(yǔ)義語(yǔ)義 Semantics 語(yǔ)用語(yǔ)用 Pragmatics7語(yǔ)法語(yǔ)法 表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律。組合規(guī)律。語(yǔ)義語(yǔ)義 表示各個(gè)記號(hào)的特定含義。（各個(gè)記表示各個(gè)記號(hào)的特定含義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系）號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系）語(yǔ)用語(yǔ)用 表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的

7、來(lái)源、使用和影響。的來(lái)源、使用和影響。8如果不考慮語(yǔ)義和語(yǔ)用，即只從語(yǔ)法這一側(cè)面來(lái)看語(yǔ)如果不考慮語(yǔ)義和語(yǔ)用，即只從語(yǔ)法這一側(cè)面來(lái)看語(yǔ)言，這種意義下的語(yǔ)言稱作形式語(yǔ)言。言，這種意義下的語(yǔ)言稱作形式語(yǔ)言。形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)?！靶问叫问健笔侵高@樣的事實(shí)：語(yǔ)言的所有規(guī)則只以什麼是指這樣的事實(shí)：語(yǔ)言的所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。符號(hào)串能出現(xiàn)的方式來(lái)陳述。形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。性的研究。是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。9一、一、

8、形式語(yǔ)言基礎(chǔ)形式語(yǔ)言基礎(chǔ)基本概念基本概念: :一、字母表和符號(hào)串一、字母表和符號(hào)串1.1.字母表：字母表：符號(hào)的非空有限集合符號(hào)的非空有限集合 例：例： = =aa，b b，cc2.2.符號(hào)：符號(hào)：字母表中的元素字母表中的元素 例：例： a a，b b，c c3.3.符號(hào)串：符號(hào)串：符號(hào)的有窮序列符號(hào)的有窮序列 例：例：a, a, aaaa, ac, , ac, abcabc，. 特別地特別地, ,空符號(hào)串：空符號(hào)串：無(wú)任何符號(hào)的符號(hào)串無(wú)任何符號(hào)的符號(hào)串( () ) 10符號(hào)串的形式定義符號(hào)串的形式定義 有字母表有字母表 ，定義：，定義：（1 1）是是 上的符號(hào)串；上的符號(hào)串；（2 2）若）若

9、x x是是 上的符號(hào)串，且上的符號(hào)串，且a a ，則，則axax或或xaxa是是 上的符號(hào)串；上的符號(hào)串；（3 3）y y是是 上的符號(hào)串，當(dāng)且僅當(dāng)上的符號(hào)串，當(dāng)且僅當(dāng)y y可由（可由（1 1）和（）和（2 2）產(chǎn)生。產(chǎn)生。 4.4.符號(hào)串集合：符號(hào)串集合：由符號(hào)串構(gòu)成的集合。由符號(hào)串構(gòu)成的集合。11v 重要約定：重要約定： 小寫字母小寫字母 s, t, u, , z 表示符號(hào)串表示符號(hào)串 大寫字母大寫字母 A, B, C, , Z 表示符號(hào)串集合表示符號(hào)串集合12二.符號(hào)串的運(yùn)算1.符號(hào)串相等：符號(hào)串相等：設(shè)設(shè) x 、y 是字母表是字母表 上的兩個(gè)符號(hào)串，若上的兩個(gè)符號(hào)串，若 x 與與 y

10、的諸符號(hào)的諸符號(hào)依次依次相等，則該兩符號(hào)串相等，記為相等，則該兩符號(hào)串相等，記為 x = y例：例：x=ab, y=ba, x=y?132.符號(hào)串長(zhǎng)度：符號(hào)串長(zhǎng)度：設(shè)設(shè) x 是字母表是字母表 上的符號(hào)串，符號(hào)串中包含上的符號(hào)串，符號(hào)串中包含符號(hào)的符號(hào)的個(gè)數(shù)個(gè)數(shù)稱為符號(hào)串稱為符號(hào)串 x 的長(zhǎng)度，用的長(zhǎng)度，用 x 表示表示 例例: (1). | abc | = ? (2). | | = ? (3). | a x | = | x a | = | x | + 1 ( a )143. 符號(hào)串的連結(jié)：符號(hào)串的連結(jié)：設(shè)設(shè) x 與與 y 是字母表是字母表 上的兩個(gè)符號(hào)串，上的兩個(gè)符號(hào)串，把把 y 的所有符號(hào)相

11、繼寫在的所有符號(hào)相繼寫在 x 的符號(hào)之后所得到的符號(hào)串的符號(hào)之后所得到的符號(hào)串稱為稱為x 與與 y 的連結(jié)，用的連結(jié)，用 x y 表示表示注意注意: | x y | = | x | + | y | x = x = x x y y x ( 一般說(shuō)來(lái)一般說(shuō)來(lái) )15(1) . 若若 x = abcd , 則則 = ? X4 .符號(hào)串的逆符號(hào)串的逆：設(shè)設(shè) x 是字母表是字母表 上的符號(hào)串，其逆為符號(hào)串上的符號(hào)串，其逆為符號(hào)串 x 的倒置，的倒置，記為記為 。X(2). = 165.符號(hào)串的前綴、后綴和子串：符號(hào)串的前綴、后綴和子串：設(shè)設(shè) x、y、z 是字母表是字母表 上的上的符號(hào)串，則稱符號(hào)串，則稱

12、 x 為符號(hào)串為符號(hào)串 x y 的的前綴前綴，y 是符號(hào)是符號(hào) 串串 x y 的的后綴后綴， x、y 、 z 、xy 、yz 是符號(hào)串是符號(hào)串 x y z 的的子串子串例例: abcd前綴、后綴、子串是什么？前綴、后綴、子串是什么？176.符號(hào)串集合的乘積：符號(hào)串集合的乘積：設(shè)設(shè)A、B為兩個(gè)符號(hào)串集合，其乘積為為兩個(gè)符號(hào)串集合，其乘積為 AB=xy|x A,y B例例: (1). 若若 A = ab, cd , B = ef, gh ，AB？ (2). x = x = x A = A = A187.空集：空集：不含任何元素的集合，記為不含任何元素的集合，記為 注意注意: (1). A = A

13、= (2). 198.符號(hào)串的冪：符號(hào)串的冪：設(shè)設(shè) x 是字母表是字母表 上的符號(hào)串，則上的符號(hào)串，則 x 的冪運(yùn)算的冪運(yùn)算為為x 0 = x 1=x x 2=xx x n=x n-1x (xx n-1)例例: 若若 x = ab 則則: x 0 = ?, x 1 = ?, x 2 = ?, , x n = ?209.符號(hào)串集合的冪：符號(hào)串集合的冪：設(shè)設(shè) A 是符號(hào)串集合，則符號(hào)串是符號(hào)串集合，則符號(hào)串 A 的冪運(yùn)的冪運(yùn)算為：算為： A0= A1=A A2=AA An=A n-1A (AA n-1)例例: 若若 A = ab, cd ,則則: A 0 = ?, A 1 = ?, A 2 = ?

14、, 21注意注意:A*=A0A+ A+=AA*=A*A 若若 A = a, b 則則: A*= , a, b, aa, ab, ba, bb, aaa, A+= a, b, aa, ab, ba, bb, aaa, 10.符號(hào)串集合的閉包運(yùn)算：符號(hào)串集合的閉包運(yùn)算：設(shè)設(shè)A是符號(hào)串集合，定義是符號(hào)串集合，定義 A = A1 A2 A3 An 稱為集合稱為集合A的的正閉包正閉包。 A* = A0 A1 A2 A3 An = A0 A 稱為集合稱為集合A的的閉包閉包。22 為什么對(duì)符號(hào)、符號(hào)串、符號(hào)串集合以及它們的運(yùn)算感興趣？為什么對(duì)符號(hào)、符號(hào)串、符號(hào)串集合以及它們的運(yùn)算感興趣？若若A為某語(yǔ)言的基本

15、字符集為某語(yǔ)言的基本字符集 Aa,b,z,0,1,9, +,_/, ( , ), =B為單詞集為單詞集 B =begin, end, if, then,else,for, +,_/, ( , ), 則則B A* 。語(yǔ)言的句子是定義在語(yǔ)言的句子是定義在B上的符號(hào)串上的符號(hào)串。若令若令C為句子集合，則為句子集合，則C B * , 程序程序 C23二、文法的直觀理解二、文法的直觀理解1.1.什么是文法：什么是文法： 文法是對(duì)語(yǔ)言結(jié)構(gòu)的定義與描述。即從形式上用于描述文法是對(duì)語(yǔ)言結(jié)構(gòu)的定義與描述。即從形式上用于描述和規(guī)定語(yǔ)言結(jié)構(gòu)的稱為和規(guī)定語(yǔ)言結(jié)構(gòu)的稱為“文法文法”（或稱為（或稱為“語(yǔ)法語(yǔ)法”）。）。

16、例：有一句子：例：有一句子：“我是大學(xué)生我是大學(xué)生” 。這是一個(gè)在語(yǔ)法、語(yǔ)這是一個(gè)在語(yǔ)法、語(yǔ)義上都正確定句子，該句子的結(jié)構(gòu)（稱為語(yǔ)法結(jié)構(gòu)）是由它義上都正確定句子，該句子的結(jié)構(gòu)（稱為語(yǔ)法結(jié)構(gòu)）是由它的語(yǔ)法決定的的語(yǔ)法決定的 。在本例中它為。在本例中它為“主謂結(jié)構(gòu)主謂結(jié)構(gòu)”。如何定義句子的合法性如何定義句子的合法性？有窮語(yǔ)言有窮語(yǔ)言無(wú)窮語(yǔ)言無(wú)窮語(yǔ)言24 2.2.語(yǔ)法規(guī)則：語(yǔ)法規(guī)則： 我們通過(guò)建立一組規(guī)則（產(chǎn)生式），來(lái)描述句子我們通過(guò)建立一組規(guī)則（產(chǎn)生式），來(lái)描述句子的的語(yǔ)法結(jié)構(gòu)語(yǔ)法結(jié)構(gòu)。規(guī)定用。規(guī)定用“”或或“:=:=”表示表示“由由組成組成”。 | 你你| |我我| |他他 王民王民| |大學(xué)生

17、大學(xué)生| |工人工人| |英語(yǔ)英語(yǔ) 是是| |學(xué)習(xí)學(xué)習(xí) | 253.3.由產(chǎn)生式推導(dǎo)句子：由產(chǎn)生式推導(dǎo)句子： 這種推導(dǎo)一直進(jìn)行下去，直到所有帶這種推導(dǎo)一直進(jìn)行下去，直到所有帶的符號(hào)都由終結(jié)符號(hào)的符號(hào)都由終結(jié)符號(hào)替代為止。替代為止。 有了一組產(chǎn)生式之后，可以按照一定的方式用它們?nèi)ネ茖?dǎo)或有了一組產(chǎn)生式之后，可以按照一定的方式用它們?nèi)ネ茖?dǎo)或產(chǎn)生句子。產(chǎn)生句子。 推導(dǎo)方法：推導(dǎo)方法：從一個(gè)初始的符號(hào)開(kāi)始推導(dǎo)，即用相應(yīng)產(chǎn)生式的從一個(gè)初始的符號(hào)開(kāi)始推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部右部來(lái)替代產(chǎn)生式的來(lái)替代產(chǎn)生式的左部左部，每次僅用一條產(chǎn)生式去進(jìn)行推導(dǎo)。，每次僅用一條產(chǎn)生式去進(jìn)行推導(dǎo)。26 我我 我我 我我是是 我

18、是我是 我是大學(xué)生我是大學(xué)生 | 你你| |我我| |他他 王民王民| |大學(xué)生大學(xué)生| |工人工人| |英語(yǔ)英語(yǔ) 是是| |學(xué)習(xí)學(xué)習(xí) | 推導(dǎo)方法：推導(dǎo)方法：從一個(gè)初始的符號(hào)從一個(gè)初始的符號(hào)開(kāi)始推導(dǎo)，即用相應(yīng)產(chǎn)生式的開(kāi)始推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部右部來(lái)替代產(chǎn)生式的來(lái)替代產(chǎn)生式的左部左部，每，每次僅用一條產(chǎn)生式去進(jìn)行推導(dǎo)。次僅用一條產(chǎn)生式去進(jìn)行推導(dǎo)。例：例：給定給定一組語(yǔ)法規(guī)則，考一組語(yǔ)法規(guī)則，考察一個(gè)句子：察一個(gè)句子：“我是大學(xué)生我是大學(xué)生”的推導(dǎo)過(guò)程。的推導(dǎo)過(guò)程。271文法的定義文法的定義三三 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義 定義定義1: 文法是產(chǎn)生式的有窮集合文法是產(chǎn)生式的有窮

19、集合,通常定義為四元組通常定義為四元組: G=（VN，VT，P，S） VN ：非終結(jié)符號(hào)集：非終結(jié)符號(hào)集 VT ：終結(jié)符號(hào)集：終結(jié)符號(hào)集 P：產(chǎn)生式或規(guī)則的集合：產(chǎn)生式或規(guī)則的集合 S：開(kāi)始符號(hào)（識(shí)別符號(hào)）：開(kāi)始符號(hào)（識(shí)別符號(hào)） SVNVVNVT稱為文法的符號(hào)集稱為文法的符號(hào)集產(chǎn)生式：產(chǎn)生式：U : xU VN, xV*其中其中: 產(chǎn)生式：產(chǎn)生式：產(chǎn)生式是一個(gè)有序?qū)Ξa(chǎn)生式是一個(gè)有序?qū)?U, x), 通常寫為通常寫為: U : x 或或U x； | U| = 1 |x| 0非終結(jié)符號(hào)：非終結(jié)符號(hào)：出現(xiàn)在產(chǎn)生式的左部出現(xiàn)在產(chǎn)生式的左部,且能推出符號(hào)或符號(hào)串的且能推出符號(hào)或符號(hào)串的那些符號(hào)。其全體構(gòu)

20、成非終結(jié)符號(hào)集，記為那些符號(hào)。其全體構(gòu)成非終結(jié)符號(hào)集，記為VN 。終結(jié)符號(hào)：終結(jié)符號(hào)：不出現(xiàn)在產(chǎn)生式的左部不出現(xiàn)在產(chǎn)生式的左部,且不能推出符號(hào)或符號(hào)串且不能推出符號(hào)或符號(hào)串的那些符號(hào)。其全體構(gòu)成終結(jié)符號(hào)集，記為的那些符號(hào)。其全體構(gòu)成終結(jié)符號(hào)集，記為VT 。28P = ； ； ； 00； 11； 99； S = ；例：無(wú)符號(hào)整數(shù)的文法：例：無(wú)符號(hào)整數(shù)的文法：G=（VN，VT，P，Z）VN, VT = 0,1,2,3,929幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明：產(chǎn)生式左邊符號(hào)構(gòu)成集合產(chǎn)生式左邊符號(hào)構(gòu)成集合VN，且，且 S VN有些產(chǎn)生式具有相同的左部，可以合在一起有些產(chǎn)生式具有相同的左部，可以合在一起例、例、 ； |

21、 ； 00 | 1 | 2 | 3 | | 9 文法的文法的BNF表示表示給定一個(gè)給定一個(gè) 文法，實(shí)際只需給出產(chǎn)生式集合，并指定開(kāi)始符號(hào)文法，實(shí)際只需給出產(chǎn)生式集合，并指定開(kāi)始符號(hào)例例: G ； | ； 00 | 1 | 2 | 3 | | 930v例例 文法文法G=（VN，VT，P，S），），其中其中VN = S ，VT = 0, 1 ，P= S0S1, S01 思考：思考：S？ 31v例例文法文法G=（VN，VT，P，S），），其中其中VN =標(biāo)識(shí)符，字母，數(shù)字標(biāo)識(shí)符，字母，數(shù)字 ，S=VT =a,b,c,x,y,z,0,1,9P a z 0 9 思考：思考：S？322 推導(dǎo)與歸約推導(dǎo)與歸

22、約 定義定義2： 直接推導(dǎo)：文法直接推導(dǎo)：文法G：vx Uy，wxuy, 其中其中x、y V* ，UVN, u V*, 若若U uP，則，則v w，即，即x Uy xuy 。 若若xy，有，有U u，則，則U u 換句話說(shuō)，換句話說(shuō)，x和和y是符號(hào)串，若使用一次產(chǎn)生式是符號(hào)串，若使用一次產(chǎn)生式可以從可以從x變換出變換出y，則稱，則稱x直接推導(dǎo)出直接推導(dǎo)出y(或者說(shuō)或者說(shuō)y是是x的直接推導(dǎo)），記為的直接推導(dǎo)），記為x y。33 當(dāng)符號(hào)串已沒(méi)有非終結(jié)符號(hào)時(shí)，推導(dǎo)就必須終止。當(dāng)符號(hào)串已沒(méi)有非終結(jié)符號(hào)時(shí)，推導(dǎo)就必須終止。例如：例如：GN： N ND | D D 0| 1| 2| 3| 4| 5| 6|

23、 7| 8| 9N ND NDD ND9 N09 D09 109 (6) (1) (3)(4) (2)(5) 34 N 109定義定義3：+ +推導(dǎo)：推導(dǎo)：x和和y是符號(hào)串，若使用若干次產(chǎn)生式可以從是符號(hào)串，若使用若干次產(chǎn)生式可以從x變換出變換出y，則稱則稱x推導(dǎo)出推導(dǎo)出y(或者說(shuō)或者說(shuō)y是是x的推導(dǎo)），記為的推導(dǎo)），記為 x y。例：例：則有：則有： 定義定義4： * *推導(dǎo)：推導(dǎo)：x和和y是符號(hào)串，若使用是符號(hào)串，若使用0次或若干次產(chǎn)生式可以從次或若干次產(chǎn)生式可以從x變變換出換出y，則稱，則稱x*推導(dǎo)出推導(dǎo)出y(或者說(shuō)或者說(shuō)y是是x的的*推導(dǎo)），記為推導(dǎo)），記為x y。* *N 109則有

24、：則有： *N N或者說(shuō)：或者說(shuō)：若有直接推導(dǎo)序列：若有直接推導(dǎo)序列： x=U0 U1 U2 Un=y,則則 x y 。+N ND NDD ND9 N09 D09 109 (6) (1) (3)(4) (2)(5) 35直觀意義：規(guī)范推導(dǎo)最右推導(dǎo)直觀意義：規(guī)范推導(dǎo)最右推導(dǎo) 定義定義5： 最右推導(dǎo)：最右推導(dǎo)：若符號(hào)串若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，對(duì)推中有兩個(gè)以上的非終結(jié)符時(shí)，對(duì)推導(dǎo)的每一步堅(jiān)持把導(dǎo)的每一步堅(jiān)持把中的最右中的最右非終結(jié)符進(jìn)行替換，稱為最非終結(jié)符進(jìn)行替換，稱為最右右推推導(dǎo)。導(dǎo)。 最左推導(dǎo)：最左推導(dǎo)：若符號(hào)串若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，對(duì)推中有兩個(gè)以上的非終結(jié)符時(shí)，對(duì)推導(dǎo)的每

25、一步堅(jiān)持把導(dǎo)的每一步堅(jiān)持把中的最左中的最左非終結(jié)符進(jìn)行替換，稱為最非終結(jié)符進(jìn)行替換，稱為最左左推推導(dǎo)。導(dǎo)。 定義定義6： 推導(dǎo)的逆過(guò)程稱之為推導(dǎo)的逆過(guò)程稱之為歸約歸約。例：例：x y,可稱為可稱為x直接推導(dǎo)出直接推導(dǎo)出y，也可稱為，也可稱為y直接歸約出直接歸約出x。 x y ,可稱為可稱為x推導(dǎo)出推導(dǎo)出y，也可稱為，也可稱為y歸約出歸約出x。363 語(yǔ)言的形式定義語(yǔ)言的形式定義文法文法GSGS所產(chǎn)生的所產(chǎn)生的所有句子的集合所有句子的集合 定義定義7：文法文法GS （1）句型句型：x是句型是句型 S x,且且xV*；*（2）句子句子：x是句子是句子 S x, 且且xVT*；*（3）語(yǔ)言語(yǔ)言：L（

26、GS）=x| S x， xVT* ；即：即：句型是由文法開(kāi)始符號(hào)推導(dǎo)出來(lái)的句型是由文法開(kāi)始符號(hào)推導(dǎo)出來(lái)的由終結(jié)符和非終結(jié)符組成的符號(hào)串。由終結(jié)符和非終結(jié)符組成的符號(hào)串。即：即：句子是由文法開(kāi)始符號(hào)推導(dǎo)出來(lái)的句子是由文法開(kāi)始符號(hào)推導(dǎo)出來(lái)的由終結(jié)符組成的符號(hào)串。由終結(jié)符組成的符號(hào)串。37例：例：abna|n1,構(gòu)造其文法構(gòu)造其文法 G1Z： ZaBa, Bb|bB G2Z： ZaBa, Bb|Bb 定義定義8: G和和G是兩個(gè)不同的文法，若是兩個(gè)不同的文法，若 L(G) = L(G) , 則則G和和G為為等價(jià)文法等價(jià)文法。38編譯感興趣的問(wèn)題是編譯感興趣的問(wèn)題是: :p給定給定x, G, 求求x

27、L(G) ?x算法算法1算法算法2x L(G) ?Gyn出錯(cuò)處理出錯(cuò)處理停機(jī)停機(jī)394 遞歸文法遞歸文法1.遞歸產(chǎn)生式遞歸產(chǎn)生式：產(chǎn)生式右部有與左部相同的符號(hào)：產(chǎn)生式右部有與左部相同的符號(hào) 對(duì)于對(duì)于 U xUy 若若x=,即即U Uy，左遞歸；，左遞歸； 若若y=,即即U xU，右右遞歸；遞歸； 2.遞歸文法遞歸文法：文法文法G，存在，存在U VN if U U, 則則G為遞歸文法；為遞歸文法； if U U, 則則G為左遞歸文法；為左遞歸文法； if U U, 則則G為右遞歸文法；為右遞歸文法；+404. 遞歸文法的優(yōu)點(diǎn)：可用有窮條產(chǎn)生式，定義無(wú)窮語(yǔ)言遞歸文法的優(yōu)點(diǎn)：可用有窮條產(chǎn)生式，定義無(wú)

28、窮語(yǔ)言!3. 左左遞歸文法的缺點(diǎn)：不能用自頂向下的方法來(lái)進(jìn)行語(yǔ)法分析遞歸文法的缺點(diǎn)：不能用自頂向下的方法來(lái)進(jìn)行語(yǔ)法分析會(huì)造成死循環(huán)（后面將詳細(xì)論述）會(huì)造成死循環(huán)（后面將詳細(xì)論述）41四四 文法分類文法分類 形式語(yǔ)言：用文法和自動(dòng)機(jī)所描述的沒(méi)有語(yǔ)義的語(yǔ)言。形式語(yǔ)言：用文法和自動(dòng)機(jī)所描述的沒(méi)有語(yǔ)義的語(yǔ)言。 文法定義：?jiǎn)棠匪够鶎⑺形姆ǘ级x為一個(gè)文法定義：?jiǎn)棠匪够鶎⑺形姆ǘ级x為一個(gè)四元組四元組：G=（VN，VT，P，S） VN：非終結(jié)符號(hào)集：非終結(jié)符號(hào)集 VT：終結(jié)符號(hào)集：終結(jié)符號(hào)集 P：產(chǎn)生式或規(guī)則的集合：產(chǎn)生式或規(guī)則的集合 S：開(kāi)始符號(hào)（開(kāi)始符號(hào)）：開(kāi)始符號(hào)（開(kāi)始符號(hào)） ZVN 語(yǔ)言定義：

29、語(yǔ)言定義： L（GS）=x| S x , xVT*, *42 文法和語(yǔ)言分類：文法和語(yǔ)言分類：0型、型、1型、型、2型、型、3型型 這幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制。這幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制。定義定義9：設(shè)設(shè)G（VN，VT，P，S），如果它的），如果它的每個(gè)每個(gè)產(chǎn)生式產(chǎn)生式、是這樣一種結(jié)構(gòu)：是這樣一種結(jié)構(gòu)：(VNVT)*且且至少包至少包含一個(gè)含一個(gè)非終結(jié)符，非終結(jié)符， (VNVT)*，則，則G是一個(gè)是一個(gè)0型文法型文法（短語(yǔ)文法、無(wú)限制文法短語(yǔ)文法、無(wú)限制文法）43定義定義10：設(shè)設(shè)G（VN，VT，P，S）如果在P中所有的規(guī)則都有如下形式A這里的AVN，,(VNUV

30、T)*(VNUVT)+僅S除外，此時(shí)S不出現(xiàn)在任何規(guī)則的右手端。則稱文法G為1型文法或上下文有關(guān)文法。SaRcRaRT|bbTcbbccbTTbbUTUTUUUUcVUcVccUVVVbVcbbccbVVbbWVWVWWWWcTWcTccWTTT44定義定義11：設(shè)設(shè)G（VN，VT，P，S），如果它的），如果它的每個(gè)每個(gè)產(chǎn)生式產(chǎn)生式A均滿足：均滿足：A是是一個(gè)一個(gè)非終結(jié)符，非終結(jié)符， V*，則文法，則文法G是是2型文法型文法（上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法）這個(gè)例子可以產(chǎn)生變量x,y,z的算術(shù)表達(dá)式：S-T+S|T-S|TT-T*T|T/T|(S)|x|y|z例如字串(x+y)*x-z*y/(x

31、+x)就可以用這個(gè)文法來(lái)產(chǎn)生。 45（右線性）（右線性） AB或或A其中其中 A是是一個(gè)一個(gè)非終結(jié)符，非終結(jié)符， VT，則文法，則文法G是是3型文法型文法（正則文法正則文法）（左線性）（左線性） AB或或A定義定義12：設(shè)設(shè)G（VN，VT，P，S），如果它的），如果它的每個(gè)每個(gè)產(chǎn)生式產(chǎn)生式限制為形如：限制為形如：例：文法例：文法GS：S 0A|1B|0A 0A|1B|0SB 1B|1|046根據(jù)上述討論，根據(jù)上述討論，L0 L1 L2 L30型文法可以產(chǎn)生型文法可以產(chǎn)生L0、L1、L2、L3，但，但2型文法只能產(chǎn)型文法只能產(chǎn)生生L2、L3，不能產(chǎn)生，不能產(chǎn)生L1。47五五 語(yǔ)法樹(shù)與二義性文法語(yǔ)

32、法樹(shù)與二義性文法上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語(yǔ)言的上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)，比如描述算術(shù)表達(dá)式、描述各種語(yǔ)句等語(yǔ)法結(jié)構(gòu)，比如描述算術(shù)表達(dá)式、描述各種語(yǔ)句等例例3.6：文法：文法G=(E,+,*,i,(,),P,E)其中其中P為：為：EiEE+EEE*E E (E)ifthen| ifthenelse 48給定文法給定文法G=（VN，VT，P，S），），對(duì)于對(duì)于G的任何句型都的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)、語(yǔ)法分析樹(shù)、分能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)、語(yǔ)法分析樹(shù)、分析樹(shù)）。析樹(shù)）。這棵樹(shù)滿足下列這棵樹(shù)滿足下列4個(gè)條件：個(gè)條件：（1）每個(gè)結(jié)

33、點(diǎn)都有一個(gè)）每個(gè)結(jié)點(diǎn)都有一個(gè)V中的符號(hào)作標(biāo)記中的符號(hào)作標(biāo)記（2）根的標(biāo)記是開(kāi)始符號(hào)）根的標(biāo)記是開(kāi)始符號(hào)S（3）若一結(jié)點(diǎn)若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則，則AVN（4）如果結(jié)點(diǎn)如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,n2,nk，其標(biāo)記分別為其標(biāo)記分別為A1,A2,Ak，那么那么AA1A2Ak一定是一定是P中的一個(gè)產(chǎn)生式中的一個(gè)產(chǎn)生式49例：文法例：文法G=(S，A,a,b,P,E)其中其中P為：為：(1)SaAS(2)ASbA(3)ASS (4)S a (5)A ba圖圖3.1的推導(dǎo)樹(shù)是文法的推導(dǎo)

34、樹(shù)是文法G的的句型句型aabbaa的推導(dǎo)過(guò)程的推導(dǎo)過(guò)程把把a(bǔ)abbaa叫做推導(dǎo)樹(shù)的結(jié)果，叫做推導(dǎo)樹(shù)的結(jié)果，把推導(dǎo)樹(shù)叫做句型把推導(dǎo)樹(shù)叫做句型aabbaa的語(yǔ)法樹(shù)的語(yǔ)法樹(shù)圖圖3.1 推導(dǎo)樹(shù)推導(dǎo)樹(shù) 50文法文法G的句型的句型aabbaa的推導(dǎo)過(guò)程：的推導(dǎo)過(guò)程：（1）SaASaAaaSbAaaSbbaaaabbaa（2）SaASaSbASaabASaabbaSaabbaa（3）SaASaSbASaSbAaaabAaaabbaa如果在推導(dǎo)的任何一步如果在推導(dǎo)的任何一步 ，其中其中、是句型，都是句型，都是對(duì)是對(duì)中的最左（最右）非終結(jié)符進(jìn)行替換，則稱這種推中的最左（最右）非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為導(dǎo)為

35、最左（最右）推導(dǎo)最左（最右）推導(dǎo)。在形式語(yǔ)言中，最右推導(dǎo)被稱為。在形式語(yǔ)言中，最右推導(dǎo)被稱為規(guī)范推導(dǎo)規(guī)范推導(dǎo)，由規(guī)范推導(dǎo)所得的句型稱為，由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型規(guī)范句型你會(huì)忘記我嗎？你會(huì)忘記我嗎？51例：例：GE:E iE E+EE E*EE (E)句型句型 i*i+i 的兩個(gè)：的兩個(gè)：推導(dǎo)推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)推導(dǎo)2：E E*E i*E i*E+E i*i+E i*i+i一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)？一個(gè)句型是否只一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)？一個(gè)句型是否只有唯一的一個(gè)最左（最右）推導(dǎo)？有唯一的一個(gè)最左（最右）推導(dǎo)？ 不是不

36、是52圖圖3.2推導(dǎo)推導(dǎo)1的語(yǔ)法樹(shù)的語(yǔ)法樹(shù)圖圖3.3推導(dǎo)推導(dǎo)2的語(yǔ)法樹(shù)的語(yǔ)法樹(shù)53若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)兩棵不同的語(yǔ)法樹(shù)，則稱這，則稱這個(gè)文法是個(gè)文法是二義的二義的?；蛘?，若一個(gè)文法存在某個(gè)句子有或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)兩個(gè)不同的最左（右）推導(dǎo)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是，則稱這個(gè)文法是二義的二義的54注意，注意，文法的二義性文法的二義性和和語(yǔ)言的二義性語(yǔ)言的二義性是兩個(gè)不同的概念。是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法因?yàn)榭赡苡袃蓚€(gè)不同的文法G和和G，其中其中G是二義的，但是二義的，但是卻有是卻有L(G)=L(G)產(chǎn)生某上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則稱此產(chǎn)生某上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則稱此語(yǔ)言是語(yǔ)言是先天二義的先天二義的你是怎么理你是怎么理解我的？解我的？55課堂習(xí)題與練習(xí)：課堂習(xí)題與練習(xí)：1、假設(shè)G是一個(gè)文