編譯原理21文法和語言

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

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

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

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

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

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

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

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

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

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

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

12、 x 為符號串為符號串 x y 的的前綴前綴，y 是符號是符號 串串 x y 的的后綴后綴， x、y 、 z 、xy 、yz 是符號串是符號串 x y z 的的子串子串例例: abcd前綴、后綴、子串是什么？前綴、后綴、子串是什么？176.符號串集合的乘積：符號串集合的乘積：設(shè)設(shè)A、B為兩個符號串集合，其乘積為為兩個符號串集合，其乘積為 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.符號串的冪：符號串的冪：設(shè)設(shè) x 是字母表是字母表 上的符號串，則上的符號串，則 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.符號串集合的冪：符號串集合的冪：設(shè)設(shè) A 是符號串集合，則符號串是符號串集合，則符號串 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.符號串集合的閉包運(yùn)算：符號串集合的閉包運(yùn)算：設(shè)設(shè)A是符號串集合，定義是符號串集合，定義 A = A1 A2 A3 An 稱為集合稱為集合A的的正閉包正閉包。 A* = A0 A1 A2 A3 An = A0 A 稱為集合稱為集合A的的閉包閉包。22 為什么對符號、符號串、符號串集合以及它們的運(yùn)算感興趣？為什么對符號、符號串、符號串集合以及它們的運(yùn)算感興趣？若若A為某語言的基本

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

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

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

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

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

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

21、 ； 00 | 1 | 2 | 3 | | 9 文法的文法的BNF表示表示給定一個給定一個 文法，實(shí)際只需給出產(chǎn)生式集合，并指定開始符號文法，實(shí)際只需給出產(chǎn)生式集合，并指定開始符號例例: 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ù)字標(biāo)識符，字母，數(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 換句話說，換句話說，x和和y是符號串，若使用一次產(chǎn)生式是符號串，若使用一次產(chǎn)生式可以從可以從x變換出變換出y，則稱，則稱x直接推導(dǎo)出直接推導(dǎo)出y(或者說或者說y是是x的直接推導(dǎo)），記為的直接推導(dǎo)），記為x y。33 當(dāng)符號串已沒有非終結(jié)符號時，推導(dǎo)就必須終止。當(dāng)符號串已沒有非終結(jié)符號時，推導(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是符號串，若使用若干次產(chǎn)生式可以從是符號串，若使用若干次產(chǎn)生式可以從x變換出變換出y，則稱則稱x推導(dǎo)出推導(dǎo)出y(或者說或者說y是是x的推導(dǎo)），記為的推導(dǎo)），記為 x y。例：例：則有：則有： 定義定義4： * *推導(dǎo)：推導(dǎo)：x和和y是符號串，若使用是符號串，若使用0次或若干次產(chǎn)生式可以從次或若干次產(chǎn)生式可以從x變變換出換出y，則稱，則稱x*推導(dǎo)出推導(dǎo)出y(或者說或者說y是是x的的*推導(dǎo)），記為推導(dǎo)），記為x y。* *N 109則有

24、：則有： *N N或者說：或者說：若有直接推導(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)：若符號串若符號串中有兩個以上的非終結(jié)符時，對推中有兩個以上的非終結(jié)符時，對推導(dǎo)的每一步堅(jiān)持把導(dǎo)的每一步堅(jiān)持把中的最右中的最右非終結(jié)符進(jìn)行替換，稱為最非終結(jié)符進(jìn)行替換，稱為最右右推推導(dǎo)。導(dǎo)。 最左推導(dǎo)：最左推導(dǎo)：若符號串若符號串中有兩個以上的非終結(jié)符時，對推中有兩個以上的非終結(jié)符時，對推導(dǎo)的每

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

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

27、L(G) ?x算法算法1算法算法2x L(G) ?Gyn出錯處理出錯處理停機(jī)停機(jī)394 遞歸文法遞歸文法1.遞歸產(chǎn)生式遞歸產(chǎn)生式：產(chǎn)生式右部有與左部相同的符號：產(chǎn)生式右部有與左部相同的符號 對于對于 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)生式，定義無窮語言遞歸文法的優(yōu)點(diǎn)：可用有窮條產(chǎn)生式，定義無

28、窮語言!3. 左左遞歸文法的缺點(diǎn)：不能用自頂向下的方法來進(jìn)行語法分析遞歸文法的缺點(diǎn)：不能用自頂向下的方法來進(jìn)行語法分析會造成死循環(huán)（后面將詳細(xì)論述）會造成死循環(huán)（后面將詳細(xì)論述）41四四 文法分類文法分類 形式語言：用文法和自動機(jī)所描述的沒有語義的語言。形式語言：用文法和自動機(jī)所描述的沒有語義的語言。 文法定義：喬姆斯基將所有文法都定義為一個文法定義：喬姆斯基將所有文法都定義為一個四元組四元組：G=（VN，VT，P，S） VN：非終結(jié)符號集：非終結(jié)符號集 VT：終結(jié)符號集：終結(jié)符號集 P：產(chǎn)生式或規(guī)則的集合：產(chǎn)生式或規(guī)則的集合 S：開始符號（開始符號）：開始符號（開始符號） ZVN 語言定義：

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

30、T)*(VNUVT)+僅S除外，此時S不出現(xiàn)在任何規(guī)則的右手端。則稱文法G為1型文法或上下文有關(guān)文法。SaRcRaRT|bbTcbbccbTTbbUTUTUUUUcVUcVccUVVVbVcbbccbVVbbWVWVWWWWcTWcTccWTTT44定義定義11：設(shè)設(shè)G（VN，VT，P，S），如果它的），如果它的每個每個產(chǎn)生式產(chǎn)生式A均滿足：均滿足：A是是一個一個非終結(jié)符，非終結(jié)符， V*，則文法，則文法G是是2型文法型文法（上下文無關(guān)文法上下文無關(guān)文法）這個例子可以產(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)就可以用這個文法來產(chǎn)生。 45（右線性）（右線性） AB或或A其中其中 A是是一個一個非終結(jié)符，非終結(jié)符， VT，則文法，則文法G是是3型文法型文法（正則文法正則文法）（左線性）（左線性） AB或或A定義定義12：設(shè)設(shè)G（VN，VT，P，S），如果它的），如果它的每個每個產(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五五 語法樹與二義性文法語

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

33、點(diǎn)都有一個）每個結(jié)點(diǎn)都有一個V中的符號作標(biāo)記中的符號作標(biāo)記（2）根的標(biāo)記是開始符號）根的標(biāo)記是開始符號S（3）若一結(jié)點(diǎn)若一結(jié)點(diǎn)n至少有一個它自己除外的子孫，并且有標(biāo)記至少有一個它自己除外的子孫，并且有標(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中的一個產(chǎn)生式中的一個產(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)樹是文法的推導(dǎo)

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

35、最左（最右）推導(dǎo)最左（最右）推導(dǎo)。在形式語言中，最右推導(dǎo)被稱為。在形式語言中，最右推導(dǎo)被稱為規(guī)范推導(dǎo)規(guī)范推導(dǎo)，由規(guī)范推導(dǎo)所得的句型稱為，由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型規(guī)范句型你會忘記我嗎？你會忘記我嗎？51例：例：GE:E iE E+EE E*EE (E)句型句型 i*i+i 的兩個：的兩個：推導(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一個句型是否只對應(yīng)唯一的一棵語法樹？一個句型是否只一個句型是否只對應(yīng)唯一的一棵語法樹？一個句型是否只有唯一的一個最左（最右）推導(dǎo)？有唯一的一個最左（最右）推導(dǎo)？ 不是不

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