第二章文法與語(yǔ)言

1、1第二章文法和語(yǔ)言第二章文法和語(yǔ)言2編譯程序必須首先理解高級(jí)語(yǔ)言的結(jié)構(gòu)！編譯程序必須首先理解高級(jí)語(yǔ)言的結(jié)構(gòu)！ 高級(jí)語(yǔ)言高級(jí)語(yǔ)言書寫的程序書寫的程序 編譯程序編譯程序出錯(cuò)信息出錯(cuò)信息低級(jí)語(yǔ)言程序低級(jí)語(yǔ)言程序3第二章第二章 文法和語(yǔ)言文法和語(yǔ)言2.1 語(yǔ)言的定義語(yǔ)言的定義2.2 形式化語(yǔ)言的基本概念形式化語(yǔ)言的基本概念2.3 文法的定義、分類和構(gòu)造文法的定義、分類和構(gòu)造2.4 文法的二義性文法的二義性2.5 語(yǔ)言的形式化定義語(yǔ)言的形式化定義2.6 語(yǔ)言的分類語(yǔ)言的分類42.1語(yǔ)言的定義n語(yǔ)言特征語(yǔ)言特征自然語(yǔ)言自然語(yǔ)言( (Natural Language)Natural Language)是人與

2、人的交流工具是人與人的交流工具不同的語(yǔ)言有不同的語(yǔ)法不同的語(yǔ)言有不同的語(yǔ)法語(yǔ)義語(yǔ)義( (semantics):semantics):環(huán)境、背景知識(shí)、語(yǔ)氣、環(huán)境、背景知識(shí)、語(yǔ)氣、二義性二義性難以形式化難以形式化計(jì)算機(jī)語(yǔ)言計(jì)算機(jī)語(yǔ)言( (Computer Language)Computer Language)計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具嚴(yán)格的語(yǔ)法嚴(yán)格的語(yǔ)法( (Grammar)Grammar)、語(yǔ)義語(yǔ)義( (semantics) semantics) 易于形式化易于形式化5n常用的高級(jí)語(yǔ)言常用的高級(jí)語(yǔ)言 FORTRAN 數(shù)值計(jì)算數(shù)值計(jì)算 COBOL事務(wù)處理事務(wù)處理 PA

3、SCAL基于過(guò)程的程序設(shè)計(jì)基于過(guò)程的程序設(shè)計(jì) ADA大型程序、嵌入式實(shí)時(shí)系統(tǒng)大型程序、嵌入式實(shí)時(shí)系統(tǒng) ALGOL描述算法的語(yǔ)言描述算法的語(yǔ)言 C/C+系統(tǒng)程序設(shè)計(jì)系統(tǒng)程序設(shè)計(jì) JavaInternet程序設(shè)計(jì)程序設(shè)計(jì) Swift OS X和和IOS的應(yīng)用程序的應(yīng)用程序6n與機(jī)器語(yǔ)言或匯編語(yǔ)言比較與機(jī)器語(yǔ)言或匯編語(yǔ)言比較，高級(jí)語(yǔ)言高級(jí)語(yǔ)言的優(yōu)點(diǎn)：的優(yōu)點(diǎn)： 較接近于自然語(yǔ)言和數(shù)學(xué)語(yǔ)言較接近于自然語(yǔ)言和數(shù)學(xué)語(yǔ)言，比較直觀、比較直觀、自然和易于理解自然和易于理解; 便于驗(yàn)證其正確性便于驗(yàn)證其正確性，易于改錯(cuò)易于改錯(cuò); 編寫效率高編寫效率高; 易于移植易于移植.7程序的基本結(jié)構(gòu)程序的基本結(jié)構(gòu)n程序程序=

4、 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法算法n軟件軟件 = 程序程序+配套文檔配套文檔語(yǔ)言語(yǔ)言對(duì)數(shù)據(jù)的運(yùn)算對(duì)數(shù)據(jù)的運(yùn)算描述數(shù)據(jù)描述數(shù)據(jù)8 高級(jí)程序語(yǔ)言的組成高級(jí)程序語(yǔ)言的組成 語(yǔ)法：由一組規(guī)則組成，形成一個(gè)符合語(yǔ)法規(guī)語(yǔ)法：由一組規(guī)則組成，形成一個(gè)符合語(yǔ)法規(guī)范的程序。規(guī)則包括兩部分，一部分叫范的程序。規(guī)則包括兩部分，一部分叫詞法規(guī)詞法規(guī)則則，一部分叫，一部分叫語(yǔ)法規(guī)則（狹義）語(yǔ)法規(guī)則（狹義） 語(yǔ)義：由一組規(guī)則組成，定義一個(gè)程序的意義語(yǔ)義：由一組規(guī)則組成，定義一個(gè)程序的意義9 語(yǔ)法語(yǔ)法n詞法規(guī)則詞法規(guī)則：?jiǎn)卧~符號(hào)單詞符號(hào)的形成規(guī)則的形成規(guī)則。單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最基本結(jié)構(gòu)單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最

5、基本結(jié)構(gòu)。包括：常量、標(biāo)識(shí)符、關(guān)鍵字、運(yùn)算符、分隔符等。包括：常量、標(biāo)識(shí)符、關(guān)鍵字、運(yùn)算符、分隔符等。（C C語(yǔ)言標(biāo)識(shí)符的詞法規(guī)則是？）語(yǔ)言標(biāo)識(shí)符的詞法規(guī)則是？）n語(yǔ)法規(guī)則語(yǔ)法規(guī)則：語(yǔ)法單位語(yǔ)法單位的形成規(guī)則的形成規(guī)則。語(yǔ)法單位通常包括：表達(dá)式、語(yǔ)句、函數(shù)、程序等。語(yǔ)法單位通常包括：表達(dá)式、語(yǔ)句、函數(shù)、程序等。Conclusion:n語(yǔ)法規(guī)則和詞法規(guī)則定義了程序的的語(yǔ)法規(guī)則和詞法規(guī)則定義了程序的的形式結(jié)構(gòu)形式結(jié)構(gòu)，是判斷，是判斷輸入字符串是否構(gòu)成一個(gè)輸入字符串是否構(gòu)成一個(gè)形式上正確形式上正確程序的依據(jù)。程序的依據(jù)。n定義語(yǔ)法單位的意義屬于語(yǔ)義問(wèn)題。定義語(yǔ)法單位的意義屬于語(yǔ)義問(wèn)題。10語(yǔ)義語(yǔ)義n

6、語(yǔ)義：一組規(guī)則語(yǔ)義：一組規(guī)則，定義一個(gè)程序的意義定義一個(gè)程序的意義。n目前，沒(méi)有一種公認(rèn)的語(yǔ)義形式系統(tǒng)，借助它目前，沒(méi)有一種公認(rèn)的語(yǔ)義形式系統(tǒng)，借助它可以自動(dòng)的構(gòu)造出實(shí)用的編譯程序可以自動(dòng)的構(gòu)造出實(shí)用的編譯程序n目前大多數(shù)的編譯程序采用的目前大多數(shù)的編譯程序采用的“基于屬性文法基于屬性文法的語(yǔ)法制導(dǎo)翻譯方法的語(yǔ)法制導(dǎo)翻譯方法”，但還不是一種，但還不是一種完全的完全的形式系統(tǒng)形式系統(tǒng)，只是，只是半形式化半形式化的描述。的描述。11形式語(yǔ)言的產(chǎn)生背景：形式語(yǔ)言的產(chǎn)生背景：n語(yǔ)言學(xué)家語(yǔ)言學(xué)家ChomskyChomsky最初從最初從語(yǔ)言產(chǎn)生語(yǔ)言產(chǎn)生的角度研究語(yǔ)言。的角度研究語(yǔ)言。19561956年，通

7、過(guò)抽象，他年，通過(guò)抽象，他1 1）將語(yǔ)言形式地定義為是）將語(yǔ)言形式地定義為是由一個(gè)字母表中的字母由一個(gè)字母表中的字母組成的一些串的集合組成的一些串的集合。2 2）在字母表上按照一定的規(guī)則定義一個(gè)）在字母表上按照一定的規(guī)則定義一個(gè)文法文法（Grammar）3 3）該文法所能產(chǎn)生的所有句子組成的集合就是該）該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的文法產(chǎn)生的語(yǔ)言語(yǔ)言。1.2 形式語(yǔ)言的定義12形式語(yǔ)言的產(chǎn)生背景：形式語(yǔ)言的產(chǎn)生背景：n克林（克林（KleeneKleene）在）在19511951年到年到19561956年間，從年間，從識(shí)別語(yǔ)言識(shí)別語(yǔ)言的的角度研究語(yǔ)言，給出了語(yǔ)言的另一種描述。

8、角度研究語(yǔ)言，給出了語(yǔ)言的另一種描述?？肆质窃谘芯可锏纳窠?jīng)細(xì)胞中，建立了克林是在研究生物的神經(jīng)細(xì)胞中，建立了自動(dòng)機(jī)自動(dòng)機(jī)模型，模型，他用這種模型來(lái)識(shí)別語(yǔ)言：他用這種模型來(lái)識(shí)別語(yǔ)言：1 1）按照一定的規(guī)則可以構(gòu)造一個(gè)自動(dòng)機(jī)，該自）按照一定的規(guī)則可以構(gòu)造一個(gè)自動(dòng)機(jī)，該自 動(dòng)機(jī)就對(duì)應(yīng)了一個(gè)語(yǔ)言動(dòng)機(jī)就對(duì)應(yīng)了一個(gè)語(yǔ)言2 2）這個(gè)語(yǔ)言由該自動(dòng)機(jī)所能識(shí)別的所有句子組成。）這個(gè)語(yǔ)言由該自動(dòng)機(jī)所能識(shí)別的所有句子組成。1.2 形式語(yǔ)言的定義13n19591959年，年，ChomskyChomsky通過(guò)深入研究，將他本人的研究成通過(guò)深入研究，將他本人的研究成果與克林的研究成果結(jié)合了起來(lái)，果與克林的研究成果結(jié)合了起

9、來(lái)，不僅確定了文法不僅確定了文法和自動(dòng)機(jī)分別從生成和識(shí)別的角度去表達(dá)語(yǔ)言，而和自動(dòng)機(jī)分別從生成和識(shí)別的角度去表達(dá)語(yǔ)言，而且證明了文法與自動(dòng)機(jī)的等價(jià)性。且證明了文法與自動(dòng)機(jī)的等價(jià)性。 形式語(yǔ)言的產(chǎn)生背景（續(xù)）14n2020世紀(jì)世紀(jì)5050年代，用巴科斯范式年代，用巴科斯范式（Backus Nour Form 或或 Backus Normal Form，簡(jiǎn)記為，簡(jiǎn)記為BNF）成功地對(duì)高成功地對(duì)高級(jí)語(yǔ)言級(jí)語(yǔ)言ALGOL-60ALGOL-60進(jìn)行了描述，這一成功使得形式語(yǔ)進(jìn)行了描述，這一成功使得形式語(yǔ)言在言在2020世紀(jì)世紀(jì)6060年代得到了大力的發(fā)展。年代得到了大力的發(fā)展。n巴科斯范式就是上下文無(wú)關(guān)

10、文法巴科斯范式就是上下文無(wú)關(guān)文法（Context Free Grammar）的一種表示形式。的一種表示形式。形式語(yǔ)言的產(chǎn)生背景（續(xù)）15n計(jì)算思維的培養(yǎng)計(jì)算思維的培養(yǎng) n連續(xù)數(shù)學(xué)連續(xù)數(shù)學(xué)、離散數(shù)學(xué)離散數(shù)學(xué)、計(jì)算模型計(jì)算模型等三部分內(nèi)等三部分內(nèi)容按階段對(duì)應(yīng)大學(xué)學(xué)習(xí)期間的思維方式和能容按階段對(duì)應(yīng)大學(xué)學(xué)習(xí)期間的思維方式和能力的變化與提高過(guò)程的三個(gè)步驟力的變化與提高過(guò)程的三個(gè)步驟形式語(yǔ)言的意義16計(jì)算思維能力的培養(yǎng)過(guò)程計(jì)算思維能力的培養(yǎng)過(guò)程 中學(xué)數(shù)學(xué)中學(xué)數(shù)學(xué)高等數(shù)學(xué)高等數(shù)學(xué) 離散數(shù)學(xué)離散數(shù)學(xué) 具體具體. .靜止靜止變量變量. .運(yùn)動(dòng)運(yùn)動(dòng)離散離散. .抽象抽象 形式形式. .模型模型 ( (基本運(yùn)算系統(tǒng)

11、基本運(yùn)算系統(tǒng)) ) ( (計(jì)算系統(tǒng)計(jì)算系統(tǒng)) ) 實(shí)實(shí) 數(shù)數(shù) 抽象抽象 集合集合 單一、具體的計(jì)算單一、具體的計(jì)算 一般、形式化的計(jì)算一般、形式化的計(jì)算 （實(shí)例計(jì)算）（實(shí)例計(jì)算） （模型化計(jì)算）（模型化計(jì)算） 形式語(yǔ)言與形式語(yǔ)言與自動(dòng)機(jī)理論自動(dòng)機(jī)理論運(yùn)算運(yùn)算范圍范圍特征特征高水平計(jì)算專業(yè)人才的計(jì)算思維能力的漸進(jìn)培養(yǎng)高水平計(jì)算專業(yè)人才的計(jì)算思維能力的漸進(jìn)培養(yǎng)17n字母表字母表n單個(gè)符號(hào)串單個(gè)符號(hào)串n符號(hào)串集合符號(hào)串集合n語(yǔ)言語(yǔ)言1.3 形式語(yǔ)言的專有名詞18n字母表字母表（Alphabet）是一個(gè)是一個(gè)非空有窮非空有窮集合，集合，字母表中的元素稱為該字母表的一個(gè)字母字母表中的元素稱為該字母表的一

12、個(gè)字母（Letter），），也叫字符或符號(hào)（也叫字符或符號(hào)（Character）。）。n例例 以下是不同的字母表：以下是不同的字母表：na，b，c，dna，b，c，zn0，1nASCII碼字母表碼字母表nC語(yǔ)言字母表語(yǔ)言字母表=字母，數(shù)字，其他符號(hào)字母，數(shù)字，其他符號(hào)字母表字母表19a，b ，aa，bb符號(hào)串符號(hào)串20符號(hào)串的運(yùn)算符號(hào)串的運(yùn)算2122符號(hào)串集合的運(yùn)算符號(hào)串集合的運(yùn)算2324 0,1+ = 0，1，00，01，10，11，000，001，010，011，100， a，b，c，d+ = a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，

13、aba，abb，abc25 0,1 * = ，0，1，00，01，10，11，000，001，010， 011，100， a，b，c，d * = ，a，b，c，d，aa，ab，ac，ad， ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc， 26形式語(yǔ)言理論認(rèn)為語(yǔ)言是字符串的集合形式語(yǔ)言理論認(rèn)為語(yǔ)言是字符串的集合設(shè)設(shè)是一個(gè)字母表，是一個(gè)字母表， L *（閉包），（閉包），L稱為稱為字母表字母表上的一個(gè)上的一個(gè)語(yǔ)言語(yǔ)言（Language） xL x叫做叫做L的一個(gè)的一個(gè)句子句子。例：例： 字母表字母表0，1上的語(yǔ)言上的語(yǔ)言0，100，110，1，00，110，1，0

14、0，11，01，1000，11*01，10*27如何實(shí)現(xiàn)語(yǔ)言的形式化描述？如何實(shí)現(xiàn)語(yǔ)言的形式化描述？ - -文法文法28n文法的定義文法的定義n產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則n語(yǔ)法樹的構(gòu)造語(yǔ)法樹的構(gòu)造n文法的構(gòu)造文法的構(gòu)造n文法的分類文法的分類1.4 文法29 1 1）考慮一個(gè)英文句子考慮一個(gè)英文句子文法要素的提取文法要素的提取分析分析：The grey wolf will eat the goat謂語(yǔ)謂語(yǔ)主語(yǔ)主語(yǔ)形容詞形容詞名詞名詞動(dòng)詞動(dòng)詞直接賓語(yǔ)直接賓語(yǔ)助動(dòng)詞助動(dòng)詞句子句子動(dòng)原動(dòng)原冠詞冠詞名詞名詞The grey wolf will eat the goat冠詞冠詞30 句子句子 主語(yǔ)主語(yǔ) 謂語(yǔ)謂語(yǔ)

15、 主語(yǔ)主語(yǔ) 冠詞冠詞 形容詞形容詞名詞名詞 冠詞冠詞the the 形容詞形容詞 greygrey 謂語(yǔ)謂語(yǔ) 動(dòng)詞動(dòng)詞 直接賓語(yǔ)直接賓語(yǔ) 動(dòng)詞動(dòng)詞 助動(dòng)詞助動(dòng)詞 動(dòng)詞原動(dòng)詞原形形 助動(dòng)詞助動(dòng)詞will will 動(dòng)詞原動(dòng)詞原形形 eat eat 直接賓語(yǔ)直接賓語(yǔ) 冠詞冠詞 名詞名詞 名詞名詞wolf wolf 名詞名詞goatgoat英語(yǔ)句子的組成規(guī)則英語(yǔ)句子的組成規(guī)則31終結(jié)符號(hào)集終結(jié)符號(hào)集VT = the，grey,wolf,will, eat, goat非終結(jié)符號(hào)集非終結(jié)符號(hào)集VN = 句子句子 ， 主語(yǔ)主語(yǔ) , 謂語(yǔ)謂語(yǔ) , 冠詞冠詞 ， 形容詞形容詞 , 名詞名詞 , 動(dòng)詞動(dòng)詞 ,

16、直接賓語(yǔ)直接賓語(yǔ) , 助動(dòng)詞助動(dòng)詞 , 動(dòng)詞原動(dòng)詞原形形 語(yǔ)法規(guī)則集語(yǔ)法規(guī)則集P = 句子句子 主語(yǔ)主語(yǔ) 謂語(yǔ)謂語(yǔ) ， 開始符號(hào)開始符號(hào)S = 句子句子 問(wèn)題：有了語(yǔ)法，如何判定某一句子是否屬于某問(wèn)題：有了語(yǔ)法，如何判定某一句子是否屬于某語(yǔ)言？語(yǔ)言？引入四個(gè)符號(hào)描述語(yǔ)法引入四個(gè)符號(hào)描述語(yǔ)法32 句子句子 主語(yǔ)主語(yǔ) 謂語(yǔ)謂語(yǔ) 冠詞冠詞 形容詞形容詞 名詞名詞 謂語(yǔ)謂語(yǔ) the 形容詞形容詞 名詞名詞 謂語(yǔ)謂語(yǔ) the grey 名詞名詞 謂語(yǔ)謂語(yǔ) the grey wolf 謂語(yǔ)謂語(yǔ) the grey wolf 動(dòng)詞動(dòng)詞 直接賓語(yǔ)直接賓語(yǔ) . the grey wolf will eat the

17、 goat根據(jù)規(guī)則：根據(jù)規(guī)則：推導(dǎo)推導(dǎo)句子句子- -從產(chǎn)生語(yǔ)言的角度從產(chǎn)生語(yǔ)言的角度33 1）the grey wolf will eat the cat 2）the wolf will eat the goat 3）the grey goat will eat the wolf 4）the grey goat will eat the grey wolf下面句子下面句子1 1）是否符合該語(yǔ)法？）是否符合該語(yǔ)法？ 2 2）是否符合語(yǔ)義？）是否符合語(yǔ)義？34既符合語(yǔ)法又符合語(yǔ)義的句子是：既符合語(yǔ)法又符合語(yǔ)義的句子是： the grey wolf will eat the goat352）漢語(yǔ)的產(chǎn)

18、生式規(guī)則可以定義如下：）漢語(yǔ)的產(chǎn)生式規(guī)則可以定義如下：句子句子 =主語(yǔ)主語(yǔ)謂語(yǔ)謂語(yǔ)主語(yǔ)主語(yǔ) =代詞代詞名詞名詞代詞代詞 =我我你你他他名詞名詞 =教師教師大學(xué)生大學(xué)生醫(yī)生醫(yī)生工人工人謂語(yǔ)謂語(yǔ) =動(dòng)詞動(dòng)詞直接賓語(yǔ)直接賓語(yǔ)動(dòng)詞動(dòng)詞 =是是學(xué)習(xí)學(xué)習(xí)勞動(dòng)勞動(dòng)直接賓語(yǔ)直接賓語(yǔ) =代詞代詞名詞名詞 判斷判斷“我是大學(xué)生我是大學(xué)生”這個(gè)句子是否滿足漢這個(gè)句子是否滿足漢語(yǔ)的語(yǔ)法？語(yǔ)的語(yǔ)法？36句子：句子：“我是大學(xué)生我是大學(xué)生”的的推導(dǎo)推導(dǎo)過(guò)程是：過(guò)程是：句子句子 主語(yǔ)主語(yǔ)謂語(yǔ)謂語(yǔ) 代詞代詞謂語(yǔ)謂語(yǔ) 我我謂語(yǔ)謂語(yǔ) 我我動(dòng)詞動(dòng)詞直接賓語(yǔ)直接賓語(yǔ) 我是我是直接賓語(yǔ)直接賓語(yǔ) 我是我是名詞名詞 我是大學(xué)生我是大學(xué)生

19、“我是大學(xué)生我是大學(xué)生” 構(gòu)成符合上述規(guī)則。構(gòu)成符合上述規(guī)則?！拔掖髮W(xué)生是我大學(xué)生是”不符合上述規(guī)則。不符合上述規(guī)則。（無(wú)法根據(jù)規(guī)則推導(dǎo)）（無(wú)法根據(jù)規(guī)則推導(dǎo)）373）C語(yǔ)言變量說(shuō)明舉例：語(yǔ)言變量說(shuō)明舉例：Grammar: 1. :=2. :=int3. :=float4. :=char5. :=a6. :=b7. :=c8. :=d38考察如何應(yīng)用文法來(lái)生成句子考察如何應(yīng)用文法來(lái)生成句子 推導(dǎo)推導(dǎo) = (規(guī)則規(guī)則1) = int (規(guī)則規(guī)則2) = int a (規(guī)則規(guī)則5) 推導(dǎo)推導(dǎo) = (規(guī)則規(guī)則1) = float (規(guī)則規(guī)則3) = float c (規(guī)則規(guī)則7) 兩個(gè)變量說(shuō)明：兩個(gè)變

20、量說(shuō)明： int a； float c； 符合符合C語(yǔ)言語(yǔ)言【變量說(shuō)明變量說(shuō)明】的語(yǔ)法規(guī)則。的語(yǔ)法規(guī)則。39文法文法G為一個(gè)四元組為一個(gè)四元組: = (T，N，)nT：終結(jié)符終結(jié)符(Terminal)集集nN：非終結(jié)符非終結(jié)符(Variable)集，集，TN= 語(yǔ)法成分語(yǔ)法成分代表某個(gè)語(yǔ)言的各種子結(jié)構(gòu)代表某個(gè)語(yǔ)言的各種子結(jié)構(gòu)n：開始符號(hào)：開始符號(hào)(Start Symbol)，SN 代表文法所定義的語(yǔ)言，代表文法所定義的語(yǔ)言，至少至少在產(chǎn)生式左側(cè)在產(chǎn)生式左側(cè)出現(xiàn)一次出現(xiàn)一次文法文法G G的形式定義的形式定義40：產(chǎn)生式：產(chǎn)生式(Product)集合集合產(chǎn)生式：產(chǎn)生式：（或者表示成（或者表示成 :

21、=） 產(chǎn)生式含義：產(chǎn)生式含義：定義定義為為(或者或者表示表示由由組成組成)。(TN)+，且且中至少有一個(gè)元素屬于中至少有一個(gè)元素屬于N (TN)*稱為產(chǎn)生式稱為產(chǎn)生式的的左部左部(Left Part)稱為產(chǎn)生式稱為產(chǎn)生式的的右部右部(Right Part)Attention：文法的核心是產(chǎn)生式規(guī)則集合。：文法的核心是產(chǎn)生式規(guī)則集合。文法文法G G 的形式定義的形式定義( (續(xù)續(xù)) )41產(chǎn)生式規(guī)則舉例（產(chǎn)生式規(guī)則舉例（1）42產(chǎn)生式規(guī)則舉例（產(chǎn)生式規(guī)則舉例（2）434445例：字符串集合（語(yǔ)言）例：字符串集合（語(yǔ)言）abna|n1,構(gòu)造其文法構(gòu)造其文法 G1Z： ZaBa, Bb|bB 右遞歸

22、文法右遞歸文法 G2Z： ZaBa, Bb|Bb 左遞歸文法左遞歸文法4647推導(dǎo)推導(dǎo) 歸約（互逆過(guò)程）歸約（互逆過(guò)程）48推導(dǎo)推導(dǎo) 歸約（互逆過(guò)程）歸約（互逆過(guò)程）4950推導(dǎo)的例子推導(dǎo)的例子：1、文法的產(chǎn)生式規(guī)則如下：、文法的產(chǎn)生式規(guī)則如下： id + id * id ？51E E + E 規(guī)則（規(guī)則（1） id + E 規(guī)則（規(guī)則（4） id + E * E 規(guī)則（規(guī)則（2） id + id * E規(guī)則（規(guī)則（4） id + id * id規(guī)則（規(guī)則（4）該推導(dǎo)是最左推導(dǎo)還是最右推導(dǎo)該推導(dǎo)是最左推導(dǎo)還是最右推導(dǎo)?推導(dǎo)的例子：推導(dǎo)的例子：52id+id*id的不同推導(dǎo)的不同推導(dǎo) EE+E|

23、E*E|(E)|id53 當(dāng)符號(hào)串已沒(méi)有非終結(jié)符號(hào)時(shí)，推導(dǎo)就必須終止。當(dāng)符號(hào)串已沒(méi)有非終結(jié)符號(hào)時(shí)，推導(dǎo)就必須終止。 該例子是最左推導(dǎo)還是最右推導(dǎo)？該例子是最左推導(dǎo)還是最右推導(dǎo)？例例2：GN： N ND | D D 0| 1| 2| 3| 4| 5| 6| 7| 8| 9N ND NDD ND9 N09 D09 109 (6) (1) (3)(4) (2)(5) 推導(dǎo)的例子（續(xù)）推導(dǎo)的例子（續(xù)） ：54S S u uS S u u+ +S S u u+ +55設(shè)設(shè)GS是給定文法是給定文法, xuyV+為該文法的句型為該文法的句型 如果滿足下面兩個(gè)條件如果滿足下面兩個(gè)條件: S xUy； U u；

24、 則稱句型則稱句型xuy 中的子串中的子串u是句型是句型xuy的短語(yǔ)。的短語(yǔ)。*56 給定文法給定文法GS, w=xuyV+ 是該文法的句型是該文法的句型, 若若 S xUy, 且且U u, 則則u是句型是句型w相對(duì)于相對(duì)于U的直接短語(yǔ)。的直接短語(yǔ)。 其中其中U VN，u V+，x,y V* 任一句型的任一句型的最左直接短語(yǔ)最左直接短語(yǔ)稱為該句型的稱為該句型的句柄句柄。57 給定句型找句柄的步驟：給定句型找句柄的步驟： 短語(yǔ)短語(yǔ) 直接短語(yǔ)直接短語(yǔ) 句柄句柄注意：注意：短語(yǔ)、直接短語(yǔ)是相對(duì)于某一個(gè)句型而言短語(yǔ)、直接短語(yǔ)是相對(duì)于某一個(gè)句型而言 一個(gè)句型可能有多個(gè)短語(yǔ)、直接短語(yǔ)，一個(gè)句型可能有多個(gè)短

25、語(yǔ)、直接短語(yǔ)， 只有一個(gè)句柄只有一個(gè)句柄58 句 子 主語(yǔ) 系詞 定語(yǔ) 名詞 Physics 冠詞 the 前置詞 of are They 連接詞 and 名詞 students 名詞 teachers 名詞 Department. 表語(yǔ) 代詞 59語(yǔ)法分析樹表示句子語(yǔ)法分析樹表示句子結(jié)構(gòu)結(jié)構(gòu) (文法文法EE+E|E*E|(E)|id ）60如何根據(jù)推導(dǎo)過(guò)程生成語(yǔ)法樹？如何根據(jù)推導(dǎo)過(guò)程生成語(yǔ)法樹？句型推導(dǎo)過(guò)程句型推導(dǎo)過(guò)程 句型語(yǔ)法樹的生長(zhǎng)過(guò)程句型語(yǔ)法樹的生長(zhǎng)過(guò)程 由推導(dǎo)構(gòu)造語(yǔ)法樹由推導(dǎo)構(gòu)造語(yǔ)法樹1從從開始符號(hào)開始符號(hào)開始，建立開始，建立推導(dǎo)序列推導(dǎo)序列。由由根結(jié)點(diǎn)根結(jié)點(diǎn)開始，開始，自上而下自上

26、而下建立建立語(yǔ)法樹語(yǔ)法樹。61規(guī)范推導(dǎo)規(guī)范推導(dǎo)R R 0R0 0R110R62 由語(yǔ)法樹構(gòu)造歸約由語(yǔ)法樹構(gòu)造歸約2自下而上自下而上地修剪子樹的末端結(jié)點(diǎn)，直至把整棵地修剪子樹的末端結(jié)點(diǎn)，直至把整棵樹剪掉（留根），每剪一次對(duì)應(yīng)一次歸約。樹剪掉（留根），每剪一次對(duì)應(yīng)一次歸約。 從句型開始，逐步進(jìn)行從句型開始，逐步進(jìn)行歸約歸約，建立，建立歸約歸約序列。序列。63規(guī)范歸約與規(guī)范推導(dǎo)互為逆過(guò)程規(guī)范歸約與規(guī)范推導(dǎo)互為逆過(guò)程01R R 0R 0R10R64通過(guò)規(guī)范推導(dǎo)或規(guī)范歸約所得到的句型是通過(guò)規(guī)范推導(dǎo)或規(guī)范歸約所得到的句型是規(guī)范句型規(guī)范句型。不是規(guī)范推導(dǎo)不是規(guī)范推導(dǎo)在上例中，在上例中， 就不是規(guī)范句型，因?yàn)?/p>

27、：就不是規(guī)范句型，因?yàn)椋?RR656667例：例：給定文法給定文法G： ET | E+T | ET TF | T*F | TF Fi | (E) 符號(hào)串（符號(hào)串（T+i）*iF F是文法是文法G G的一個(gè)句型，求其短語(yǔ)、直接短語(yǔ)和句柄。的一個(gè)句型，求其短語(yǔ)、直接短語(yǔ)和句柄。E ET TT TF T*FF F*FF (E) *FF (T +T) *FF (T +F) *FF (T +i) *FF (T +i) *iF (T +i) *iF解：短語(yǔ)有解：短語(yǔ)有8個(gè)：個(gè)：1. E E，E（T+i）*iF 則有：則有：（T+i）*iF2. E TF，T（T+i）*i 則有：則有：（T+i）*i3. E

28、 T *iF，T（T+i） 則有：則有：（T+i）4. E (E) *iF，ET+i 則有：則有： T+i5. E (E +i) *iF，ET 則有：則有： T6. E (T +F) *iF，F(xiàn)i 則有：則有： 第一個(gè)第一個(gè)i7. E (T +i) *FF，F(xiàn)i 則有：則有： 第二個(gè)第二個(gè)i8. E (T +i) *FT，TF 則有：則有： F*+*+*+*+*+*+*+*+定義定義: 給定文法給定文法GZ, w=xuyV+，為該文法的句型，為該文法的句型, 若若 ZxUy, 且且U u, 則則u是句型是句型w相對(duì)于相對(duì)于U的短語(yǔ)；的短語(yǔ)； 若若 ZxUy, 且且U u, 則則u是句型是句型w

29、相對(duì)于相對(duì)于U的直接短語(yǔ)。的直接短語(yǔ)。 其中其中U VN，u V+，x,y V*68其直接短語(yǔ)有其直接短語(yǔ)有4個(gè)：個(gè)：1. E (E +i) *iF,EF,ET 則有：則有： T2. E (T +F) *iF,FF,Fi 則有：則有： 第一個(gè)第一個(gè)i i3. E (T +i) *FF,FF,Fi 則有：則有： 第二個(gè)第二個(gè)i i4. E (T +i) *FT T,T,TF 則有：則有：F F句柄有句柄有1 1個(gè)：個(gè)： T TEETT TT* *FF F(E E)F Fi iE+ +TT TF Fi i用語(yǔ)法樹求用語(yǔ)法樹求短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄的方法：的方法：1）每個(gè)句型都有一

30、棵語(yǔ)法樹；）每個(gè)句型都有一棵語(yǔ)法樹；2）每棵語(yǔ)法樹的葉（從左到右）組成一句型；）每棵語(yǔ)法樹的葉（從左到右）組成一句型；3）每個(gè)子樹）每個(gè)子樹 的葉（從左到右）組成一短語(yǔ)；的葉（從左到右）組成一短語(yǔ)；4）每個(gè)簡(jiǎn)單子樹）每個(gè)簡(jiǎn)單子樹 的葉（從左到右）組成一直接短語(yǔ)；的葉（從左到右）組成一直接短語(yǔ)；5）最左簡(jiǎn)單子樹）最左簡(jiǎn)單子樹 的葉（從左到右）組成一句柄。的葉（從左到右）組成一句柄。只需畫出句型的語(yǔ)法樹，然后根據(jù)子樹找短語(yǔ)只需畫出句型的語(yǔ)法樹，然后根據(jù)子樹找短語(yǔ)直接短語(yǔ)直接短語(yǔ)句柄。句柄。69文法的二義性（雙關(guān)）文法的二義性（雙關(guān)）70 EE+E a+E a+E*E a+a*E a+a*a E E

31、*EE+E*E a+E*Ea+a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推導(dǎo)最左推導(dǎo)71 EE+E E+E*E E+E*a E+a*a a+a*a E E*EE*a E+E*aE+a*a a+a*aEE+EE*EaaaEE*E+EEaaa最右推導(dǎo)最右推導(dǎo)72同一個(gè)句子有兩棵語(yǔ)法分析樹同一個(gè)句子有兩棵語(yǔ)法分析樹731)高級(jí)程序設(shè)計(jì)語(yǔ)言存在無(wú)二義性文法高級(jí)程序設(shè)計(jì)語(yǔ)言存在無(wú)二義性文法對(duì)于條件語(yǔ)句，經(jīng)常使用二義性文法描述它：對(duì)于條件語(yǔ)句，經(jīng)常使用二義性文法描述它：S if expr then S if expr then S else S other該語(yǔ)法是二義性文法，該語(yǔ)法是二

32、義性文法，why? 因?yàn)榇嬖诙x性的句子因?yàn)榇嬖诙x性的句子: if e1 then if e2 then s1 else s2 文法二義性的幾點(diǎn)說(shuō)明文法二義性的幾點(diǎn)說(shuō)明74該句子對(duì)應(yīng)兩棵語(yǔ)法樹（最左推導(dǎo)）該句子對(duì)應(yīng)兩棵語(yǔ)法樹（最左推導(dǎo)）Sife1thenSife2thens1elses2Sife1thenSife2thens1elseS2即可理解為：即可理解為：if e1 then if e1 then （if e2 then s1 else s2if e2 then s1 else s2） 可理解為：可理解為：if e1 then if e1 then （if e2 then s1if e

33、2 then s1） else s2else s2因此該文法是二義性文法。因此該文法是二義性文法。75 Smatched_s unmatched_s matched_s if expr then matched_s else matched_s other unmatched_s if expr then S if expr then matched_s else unmatched_s 無(wú)二義性的文法無(wú)二義性的文法比較復(fù)雜，比較復(fù)雜，因此很多時(shí)候，因此很多時(shí)候，使用使用二二義性文法義性文法。等價(jià)轉(zhuǎn)換的無(wú)二義性等價(jià)轉(zhuǎn)換的無(wú)二義性if-else文法的產(chǎn)生式文法的產(chǎn)生式76文法二義性的判定：文法二

34、義性的判定：1 1）有些文法是非二義性，比如）有些文法是非二義性，比如LLLL（1 1）文法、）文法、LRLR文法、文法、算符優(yōu)先文法，而且這些文法都是可以判定的，算符優(yōu)先文法，而且這些文法都是可以判定的，所以只所以只要我們能夠證明文法是屬于上述某類文法，則該文法必要我們能夠證明文法是屬于上述某類文法，則該文法必然是非二義性的然是非二義性的；2 2）如果一個(gè)文法既有）如果一個(gè)文法既有左遞歸左遞歸，又有，又有右遞歸右遞歸的非終結(jié)符號(hào)的非終結(jié)符號(hào)A A，則文法必然是二義性的。，則文法必然是二義性的。3 3）現(xiàn)在的解決辦法是：提出一些現(xiàn)在的解決辦法是：提出一些限制條件限制條件，稱為無(wú)二義，稱為無(wú)二義

35、性的充分條件，當(dāng)文法滿足這些條件時(shí)，就可以判定文性的充分條件，當(dāng)文法滿足這些條件時(shí)，就可以判定文法是無(wú)二義性的。法是無(wú)二義性的。 Attention：不存在一種算法，能在有限的步驟內(nèi)確切的判斷一個(gè)文不存在一種算法，能在有限的步驟內(nèi)確切的判斷一個(gè)文法是否是二義性的。法是否是二義性的。77文法二義性與語(yǔ)言的二義性關(guān)系：文法二義性與語(yǔ)言的二義性關(guān)系： 如果一個(gè)二義性的文法，我們可以把它如果一個(gè)二義性的文法，我們可以把它等價(jià)變換等價(jià)變換成另成另外一個(gè)無(wú)二義性的文法，那么我們可以認(rèn)為該二義性文外一個(gè)無(wú)二義性的文法，那么我們可以認(rèn)為該二義性文法對(duì)應(yīng)的語(yǔ)言中，某些句子的二義性完全是二義性文法法對(duì)應(yīng)的語(yǔ)言中，

36、某些句子的二義性完全是二義性文法所帶來(lái)的，而所帶來(lái)的，而語(yǔ)言本身是非二義性語(yǔ)言本身是非二義性的。的。文法二義性文法二義性 語(yǔ)言二義性語(yǔ)言二義性二義性的語(yǔ)言：不存在非二義性的文法的語(yǔ)言。二義性的語(yǔ)言：不存在非二義性的文法的語(yǔ)言。78文法的分類文法的分類7980含義：只有在含義：只有在x、y這樣的上下文環(huán)境下才能把這樣的上下文環(huán)境下才能把U改寫為改寫為u81即把即把U改寫為改寫為u時(shí)，不必考慮上下文（用于語(yǔ)法分析）時(shí)，不必考慮上下文（用于語(yǔ)法分析）8283四種文法四種文法HierarchyAliasProduction formAutomation name 0-typeGrammar witho

37、ut limitation, V Turing Machine1-typeContext-sensitive grammarA , A VNLinear Bound Automation2-typeContext-free grammarA, A VNPushdown automation3-typeRegular grammar A B， A , A，BVN，VT*Finite automation84 四種文法之間的逐級(jí)四種文法之間的逐級(jí)“包含包含”關(guān)系如下：關(guān)系如下：2型文法型文法1型文法型文法0型文法型文法3型文法型文法文法對(duì)應(yīng)語(yǔ)言的包含關(guān)系文法對(duì)應(yīng)語(yǔ)言的包含關(guān)系 L0 L1 L2 L

38、3 0型文法可以產(chǎn)生型文法可以產(chǎn)生L0、L1、L2、L3，但，但2型文法只能產(chǎn)型文法只能產(chǎn)生生L2、L3，不能產(chǎn)生，不能產(chǎn)生L1。85Chomsky體系總結(jié) = ( = (T T，N N，) )是一個(gè)文法是一個(gè)文法, , P P* * G G是是0 0型文法，型文法，L(G)L(G)是是0 0型語(yǔ)言；型語(yǔ)言； - -其能力相當(dāng)于圖靈機(jī)其能力相當(dāng)于圖靈機(jī)* * | |:G|:G是是1 1型文法，型文法，L(G)L(G)是是1 1型語(yǔ)言型語(yǔ)言( (除除);); - -其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)* * N N : G : G是是2 2型文法，型文法，L(G)L(G)是是2

39、2型語(yǔ)言型語(yǔ)言; ; - -其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)* * AaBAaB或或Aa: Aa: G G是右線性文法，是右線性文法， L(G)L(G)是是3 3型語(yǔ)言型語(yǔ)言ABaABa或或AA: : G G是左線性文法，是左線性文法，L(G)L(G)是是3 3型語(yǔ)言型語(yǔ)言 - -其識(shí)別系統(tǒng)是有限自動(dòng)機(jī)其識(shí)別系統(tǒng)是有限自動(dòng)機(jī)8687有害規(guī)則：造成二義性有害規(guī)則：造成二義性 例如存在例如存在U:=U， U:= a | b,則有兩棵語(yǔ)法樹：則有兩棵語(yǔ)法樹：UaUUa88多余規(guī)則：無(wú)用產(chǎn)生式與無(wú)用符號(hào)多余規(guī)則：無(wú)用產(chǎn)生式與無(wú)用符號(hào)E T | E + T | E TT F

40、| T * F | T / FF ( E ) | idE E | H + TT FH | TQ+PF | EQFM ( E ) | id無(wú)用符號(hào)：無(wú)用符號(hào)： 1)H、Q、P派生不出終極符號(hào)派生不出終極符號(hào) 2)從開始符號(hào)無(wú)法派生出來(lái)從開始符號(hào)無(wú)法派生出來(lái)M8990L(G1)=ai(a|b)|i=0 Example：LetG2(S,a,b,P,S) Where P includes: (0) S aSb (1) S abL(G2)=anbn|n=1Example：Let G1(S,a,b,P,S)Where P includes: (0) S aS (1) S a (2) S b文法文法 語(yǔ)言語(yǔ)

41、言91n明確描述對(duì)象明確描述對(duì)象語(yǔ)言語(yǔ)言合法的語(yǔ)言結(jié)構(gòu)合法的語(yǔ)言結(jié)構(gòu)n確定基本符號(hào)集確定基本符號(hào)集T Tn引入非終結(jié)符引入非終結(jié)符n n各種語(yǔ)法成分各種語(yǔ)法成分n定義句子的組成規(guī)則定義句子的組成規(guī)則BNFBNF范式或產(chǎn)生式范式或產(chǎn)生式語(yǔ)言語(yǔ)言 文法文法 ：文法的構(gòu)造文法的構(gòu)造92文法構(gòu)造舉例文法構(gòu)造舉例n基本結(jié)構(gòu)基本結(jié)構(gòu)a an n的構(gòu)造的構(gòu)造 1) n=0 SaS| 2) n=1 SaS|a93文法構(gòu)造舉例文法構(gòu)造舉例nx|x是長(zhǎng)度為偶數(shù)的是長(zhǎng)度為偶數(shù)的0、1串串 S00S|01S|10S|11S|nanbn |n1 SaSb|ab 什么文法？什么文法？nambn |m,n1 1) SAB

42、AaA|a BbB|b 2) SaS SaB BbB|b 如果改為如果改為m,n0 m,n0 習(xí)題習(xí)題2.62.694Constructing a grammar from a languageExample1：Let L1=a2nbn|n=1 and a,b VTTry to construct the grammar G1 from L1 Let n=1， L1 =aab n=2， L1 =aaaabb n=3， L1 =aaaaaabbb So we have：S aaSb S aab95Constructing a grammar from a languageExample 2：Le

43、t L2=aibjck | i,j,k=1 and a,b,c VT Try to construct the grammar G2 from L2 S aS S aB B bB B bC C cC | c 如果如果i=j, 如何構(gòu)造文法？如何構(gòu)造文法？ S AB A aAb|ab B cB | c96如果如果i=j=k,i=j=k,如何構(gòu)造文法？如何構(gòu)造文法？構(gòu)造語(yǔ)言構(gòu)造語(yǔ)言L=aL=an nb bn nc cn n|n0|n0的文法的文法SaBC|aSBCCBBCaBabbBbbbCbc Q: 這是什么文法？這是什么文法？97Constructing a grammar from a la

44、nguageExample 3：Let L3= | (a,b)* and there are as many as as bs in Try to construct the grammar G3 from L3 S S bB， S aA A bS|b ，A aAA B aS | a | bBBS S aSbSS bSaS 98Constructing a grammar from a languageExample 4：Let L4= | (0,1)* and the number of 1 appeared in is even Try to construct the grammar G4 from L4 Grammar: S S 0S， S 1A A 0A , A 1S99用文法用文法G1來(lái)定義下面的集合：來(lái)定義下面的集合：L1=n|n是非負(fù)整數(shù)是非負(fù)整數(shù)解題思路：顯而易見，該集合不能用枚舉法來(lái)定義。解題思路：顯而易見