形式語(yǔ)言與自動(dòng)機(jī)理論基礎(chǔ)1

1、編譯編譯原理原理第二章第二章 程序語(yǔ)言程序語(yǔ)言22021-11-11第二章第二章 程序程序語(yǔ)言語(yǔ)言 v常用的高級(jí)程序常用的高級(jí)程序 FORTRANFORTRAN數(shù)值計(jì)算數(shù)值計(jì)算 COBOLCOBOL事務(wù)處理事務(wù)處理 PASCALPASCAL結(jié)構(gòu)程序設(shè)計(jì)結(jié)構(gòu)程序設(shè)計(jì) ADAADA大型程序、嵌入式實(shí)時(shí)系統(tǒng)大型程序、嵌入式實(shí)時(shí)系統(tǒng) PROLOGPROLOG邏輯程序設(shè)計(jì)邏輯程序設(shè)計(jì) ALGOLALGOL算法語(yǔ)言算法語(yǔ)言 C/C+C/C+系統(tǒng)程序設(shè)計(jì)系統(tǒng)程序設(shè)計(jì) JavaJavaInternetInternet程序設(shè)計(jì)程序設(shè)計(jì)32021-11-11v與機(jī)器語(yǔ)言或匯編語(yǔ)言比較與機(jī)器語(yǔ)言或匯編語(yǔ)言比較，高級(jí)

2、語(yǔ)言的高級(jí)語(yǔ)言的優(yōu)點(diǎn)優(yōu)點(diǎn)： 較接近于數(shù)學(xué)語(yǔ)言和工程語(yǔ)言較接近于數(shù)學(xué)語(yǔ)言和工程語(yǔ)言，比較直觀、自比較直觀、自然和易于理解然和易于理解; ; 便于驗(yàn)證其正確性便于驗(yàn)證其正確性，易于改錯(cuò)易于改錯(cuò); ; 編寫(xiě)效率高編寫(xiě)效率高; ; 易于移植易于移植. .4n 自然語(yǔ)言自然語(yǔ)言（Natural LanguageNatural Language）是人類(lèi)在社）是人類(lèi)在社會(huì)生活中發(fā)展起來(lái)的，用于日常相互交流的符會(huì)生活中發(fā)展起來(lái)的，用于日常相互交流的符號(hào)系統(tǒng)。號(hào)系統(tǒng)。n 形式語(yǔ)言形式語(yǔ)言（Formal LanguageFormal Language）是為了特定）是為了特定應(yīng)用而設(shè)計(jì)的人工語(yǔ)言，形式語(yǔ)言是用精確的

3、應(yīng)用而設(shè)計(jì)的人工語(yǔ)言，形式語(yǔ)言是用精確的數(shù)學(xué)或機(jī)器可處理的公式定義的語(yǔ)言，公式由數(shù)學(xué)或機(jī)器可處理的公式定義的語(yǔ)言，公式由人們公認(rèn)的數(shù)學(xué)和邏輯符號(hào)組成。人們公認(rèn)的數(shù)學(xué)和邏輯符號(hào)組成。5n語(yǔ)法和語(yǔ)義語(yǔ)法和語(yǔ)義一個(gè)程序設(shè)計(jì)語(yǔ)言是一個(gè)一個(gè)程序設(shè)計(jì)語(yǔ)言是一個(gè)記號(hào)系統(tǒng)記號(hào)系統(tǒng)，它的完整，它的完整定義包括語(yǔ)法和語(yǔ)義兩個(gè)方面。定義包括語(yǔ)法和語(yǔ)義兩個(gè)方面。語(yǔ)法（語(yǔ)法（GrammarGrammar）是一組規(guī)則，用它可以產(chǎn)生是一組規(guī)則，用它可以產(chǎn)生一個(gè)與其所包含的符號(hào)含義無(wú)關(guān)的合法程序一個(gè)與其所包含的符號(hào)含義無(wú)關(guān)的合法程序, ,語(yǔ)法是語(yǔ)言的形式。語(yǔ)法是語(yǔ)言的形式。語(yǔ)義語(yǔ)義(Semantic )(Semantic )

4、是語(yǔ)言的內(nèi)容，是語(yǔ)言的內(nèi)容，以語(yǔ)法為媒以語(yǔ)法為媒介來(lái)說(shuō)明語(yǔ)義是語(yǔ)言的實(shí)質(zhì)介來(lái)說(shuō)明語(yǔ)義是語(yǔ)言的實(shí)質(zhì)。62021-11-11v詞法規(guī)則詞法規(guī)則：?jiǎn)卧~符號(hào)的形成規(guī)則：?jiǎn)卧~符號(hào)的形成規(guī)則。 單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最基本結(jié)構(gòu)單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符一般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等。等。 描述工具：有限自動(dòng)機(jī)描述工具：有限自動(dòng)機(jī)v語(yǔ)法規(guī)則語(yǔ)法規(guī)則：語(yǔ)法單位的形成規(guī)則：語(yǔ)法單位的形成規(guī)則。 語(yǔ)法單位通常包括：表達(dá)式、語(yǔ)句、分程序、過(guò)語(yǔ)法單位通常包括：表達(dá)式、語(yǔ)句、分程序、過(guò)程、函數(shù)、程序等程、函數(shù)、程序等; ; 描述工具：上下文

5、無(wú)關(guān)文法描述工具：上下文無(wú)關(guān)文法72021-11-11三程序語(yǔ)言的基本功能和層次結(jié)構(gòu)三程序語(yǔ)言的基本功能和層次結(jié)構(gòu)v程序語(yǔ)言的基本功能：程序語(yǔ)言的基本功能：描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。v所謂程序，本質(zhì)上說(shuō)是所謂程序，本質(zhì)上說(shuō)是描述一定數(shù)據(jù)的處理過(guò)程描述一定數(shù)據(jù)的處理過(guò)程。82021-11-11程序的層次結(jié)構(gòu)：程序的層次結(jié)構(gòu)：程序程序| |子程序或分程序、過(guò)程、函數(shù)子程序或分程序、過(guò)程、函數(shù)| |語(yǔ)句語(yǔ)句| |表達(dá)式表達(dá)式|數(shù)據(jù)引用數(shù)據(jù)引用 算符算符 函數(shù)調(diào)用函數(shù)調(diào)用92021-11-112.1 2.1 高級(jí)語(yǔ)言的一般特性高級(jí)語(yǔ)言的一般特性 2.1.1 2.1.1 高級(jí)語(yǔ)言的分

6、類(lèi)高級(jí)語(yǔ)言的分類(lèi) 強(qiáng)制式語(yǔ)言強(qiáng)制式語(yǔ)言(Imperative Languge)(Imperative Languge)也稱(chēng)過(guò)程式語(yǔ)也稱(chēng)過(guò)程式語(yǔ)言：命令驅(qū)動(dòng)，面向語(yǔ)句言：命令驅(qū)動(dòng)，面向語(yǔ)句 FORTRANFORTRAN、C C、PascalPascal，Ada Ada 應(yīng)用式語(yǔ)言應(yīng)用式語(yǔ)言（Applicative LanguageApplicative Language）：注重程）：注重程序所表示的功能，而不是一個(gè)語(yǔ)句接一個(gè)語(yǔ)句地序所表示的功能，而不是一個(gè)語(yǔ)句接一個(gè)語(yǔ)句地執(zhí)行執(zhí)行 LISPLISP、ML ML 102021-11-11 基于規(guī)則的語(yǔ)言基于規(guī)則的語(yǔ)言（Rule-based Lang

7、uageRule-based Language）：檢查）：檢查一定的條件，當(dāng)它滿(mǎn)足值，則執(zhí)行適當(dāng)?shù)膭?dòng)作一定的條件，當(dāng)它滿(mǎn)足值，則執(zhí)行適當(dāng)?shù)膭?dòng)作 Prolog Prolog 面向?qū)ο笳Z(yǔ)言面向?qū)ο笳Z(yǔ)言（Object-Oriented LanguageObject-Oriented Language）：）：封裝性封裝性、繼承性繼承性和和多態(tài)性多態(tài)性 SmalltalkSmalltalk，C+C+，Java Java 112021-11-11程序結(jié)構(gòu)程序結(jié)構(gòu)v FORTRANFORTRAN 一個(gè)程序由一個(gè)主程序段和若干輔程序段組成。一個(gè)程序由一個(gè)主程序段和若干輔程序段組成。 輔程序段可以是子程序、函數(shù)

8、段或數(shù)據(jù)塊。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。 每個(gè)程序段有一系列的說(shuō)明語(yǔ)句和執(zhí)行語(yǔ)句組成。每個(gè)程序段有一系列的說(shuō)明語(yǔ)句和執(zhí)行語(yǔ)句組成。各段可以獨(dú)立編譯。各段可以獨(dú)立編譯。 模塊結(jié)構(gòu)，沒(méi)有嵌套和遞歸模塊結(jié)構(gòu)，沒(méi)有嵌套和遞歸 各程序段中的名字相互獨(dú)立各程序段中的名字相互獨(dú)立，同一個(gè)標(biāo)識(shí)符在不，同一個(gè)標(biāo)識(shí)符在不同的程序段中代表不同的名字同的程序段中代表不同的名字。122021-11-11主程序主程序 PROGRAM PROGRAM end end輔程序輔程序1 1 SUBROUTINE SUBROUTINE end end輔程序輔程序2 2 FUNCTION FUNCTION end end1

9、32021-11-11vJAVA Java是一種面向?qū)ο蟮母呒?jí)語(yǔ)言是一種面向?qū)ο蟮母呒?jí)語(yǔ)言 類(lèi)（類(lèi)（Class） 繼承繼承(Inheritance) 多態(tài)性多態(tài)性(Polymorphism)和動(dòng)態(tài)綁定和動(dòng)態(tài)綁定(Dynamic binding)142021-11-11class Car int color_number; int door_number; int speed; push_break ( ) add_oil ( ) class Trash_Car extends car double amount; fill_trash ( ) 2.22.2節(jié)節(jié) 中間語(yǔ)言中間語(yǔ)言v后延至后延至第

10、八章語(yǔ)法制導(dǎo)翻譯第八章語(yǔ)法制導(dǎo)翻譯第三章第三章 語(yǔ)言分析基礎(chǔ)語(yǔ)言分析基礎(chǔ)17 基本基本概念概念1.1.字母表字母表（alphabet )alphabet )v 字母表是元素的字母表是元素的非空有窮非空有窮集合集合, ,字母表中的一個(gè)字母表中的一個(gè)元素稱(chēng)為該字母表的一個(gè)元素稱(chēng)為該字母表的一個(gè)字母字母（letterletter）, ,也可叫也可叫做做符號(hào)符號(hào)（symbolsymbol）或者）或者字符字符(character)(character)。v注意：字母表具有非空性和有窮性。注意：字母表具有非空性和有窮性。v字母表有時(shí)也稱(chēng)為符號(hào)表字母表有時(shí)也稱(chēng)為符號(hào)表, ,通常用通常用表示。表示。 182.

11、2.符號(hào)串符號(hào)串v由字母表中的符號(hào)組成的由字母表中的符號(hào)組成的任何有窮序列任何有窮序列稱(chēng)為字母表稱(chēng)為字母表上的符號(hào)串。符號(hào)串還可以稱(chēng)為上的符號(hào)串。符號(hào)串還可以稱(chēng)為“字符串字符串”、“字字”或或“句子句子”，一般用，一般用 ， ，.，x x，y y，z z，表示。表示。v表示表示空串?？沾?。對(duì)任一字母表對(duì)任一字母表，都，都有有 是是上的符號(hào)上的符號(hào)串。串。v空串集空串集 不同于空集不同于空集 。 = a = a，b b， c c，dd193 3. .符號(hào)串連接符號(hào)串連接l 設(shè)設(shè) 和和 均是字母表均是字母表上的符號(hào)串，上的符號(hào)串， 和和 的連接是的連接是把把 的所有符號(hào)順次地接在的所有符號(hào)順次地接

12、在 的所有符號(hào)之后所得到的的所有符號(hào)之后所得到的符號(hào)串。記為符號(hào)串。記為: : 。例如例如: : 設(shè)設(shè) = abc , = abc , = de , = de ,則則 和和 的連接的連接: : = abcde = abcdel由于由于 是不包含任何符號(hào)的字符串，是不包含任何符號(hào)的字符串，特別有：特別有： = = = = l 連接運(yùn)算不滿(mǎn)足交換律。連接運(yùn)算不滿(mǎn)足交換律。 204 4. .符號(hào)串的方冪符號(hào)串的方冪 設(shè)設(shè)x x是字母表是字母表上的符號(hào)串，把上的符號(hào)串，把x x自身連接自身連接n n次得次得到的符號(hào)串到的符號(hào)串z, z, 即即z = xxxx (nz = xxxx (n個(gè)個(gè)x),x),

13、稱(chēng)作符號(hào)串稱(chēng)作符號(hào)串x x的的n n次冪，記作次冪，記作 z = xz = xn n 。根據(jù)定義有：。根據(jù)定義有： x x0 0 = = x x1 1 = x = x x x2 2 = xx = xxx xn n = x = xn-1n-1x = xxx = xxn-1n-1 = xxxx (n = xxxx (n個(gè)個(gè)x)x)例例 設(shè)設(shè)x = 001x = 001，則有，則有: x: x0 0 = = x x1 1 = 001 = 001 x x2 2 = 001001 = 001001 x x3 3 = 001001001 = 001001001 215 5. .符號(hào)串集的乘積符號(hào)串集的乘積

14、 設(shè)設(shè)A A、B B 是兩個(gè)符號(hào)串集合，是兩個(gè)符號(hào)串集合，ABAB表示表示A A與與B B的乘的乘積，具體定義為：積，具體定義為： AB = xy | ( xA ) ( yB ) , AB = xy | ( xA ) ( yB ) , 運(yùn)算結(jié)果仍然表示符號(hào)串的集合。運(yùn)算結(jié)果仍然表示符號(hào)串的集合。 例例2.3 2.3 設(shè)設(shè) A = a, bc A = a, bc ， B = de, f ,B = de, f ,則：則： AB = ade, af, bcde, bcf AB = ade, af, bcde, bcf 特別有：特別有：1 1、A = AA = A = = ，其中其中表示空集。表示空集

15、。 2 2、 A = AA = A = = A A226 6. .符號(hào)串集合的方冪符號(hào)串集合的方冪 設(shè)設(shè)A A為符號(hào)串的集合，則稱(chēng)為符號(hào)串的集合，則稱(chēng)i i為符號(hào)串集的方冪。具體定義如下：為符號(hào)串集的方冪。具體定義如下： 1 1 A A2 2 AAAA n n n-1n-1A A AAAA (n AAAA (n個(gè)）個(gè)）例：例： a,b a,b 則：則：0 0 1 1 a,b a,b 2 2 AA AA aa,ab,ba,bb aa,ab,ba,bb 3 3 A A2 2A A aaa,aab,abaaaa,aab,aba, ,abbabb, ,baa,bab,bba,bbb baa,bab,b

16、ba,bbb n n n-1n-1A A AAAA AAAA237 7. .符號(hào)串集合的正閉包符號(hào)串集合的正閉包 設(shè)設(shè)A A為符號(hào)串的集合，則稱(chēng)為符號(hào)串的集合，則稱(chēng)為符號(hào)串集的正為符號(hào)串集的正閉包具體定義如下：閉包具體定義如下： 1 1 A A2 2 A A3 3 248 8. .符號(hào)串集合的星符號(hào)串集合的星閉包（閉包（自反閉包自反閉包） 設(shè)設(shè)A A為符號(hào)串的集合，則稱(chēng)為符號(hào)串的集合，則稱(chēng)為符號(hào)串集的為符號(hào)串集的星閉包具體定義如下：星閉包具體定義如下： A A0 0 1 1 A A2 2 A A3 3 注意注意: : A A 請(qǐng)證明請(qǐng)證明25例例: :設(shè)設(shè)A = ab, cdA = ab, c

17、d，則，則 : : A A+ + = ab, cd, = ab, cd, abab, abcd, cdab, cdcdabab, abcd, cdab, cdcd, , ababab, ababcd, ababab, ababcd, A A* * = = , ab, cd, abab, abcd, cdab, cdcd, , ab, cd, abab, abcd, cdab, cdcd, ababab, ababcd, ababab, ababcd, 程序題程序題字母表字母表為為 aa，bb1.1. 長(zhǎng)度小于長(zhǎng)度小于5 5的字符串的個(gè)數(shù)的字符串的個(gè)數(shù)2.2. 請(qǐng)列出所有字符串請(qǐng)列出所有字符串提

18、示：遞歸方法提示：遞歸方法具體要求見(jiàn)賽課內(nèi)容。具體要求見(jiàn)賽課內(nèi)容。提問(wèn)提問(wèn)v設(shè)設(shè)A = ab, cdA = ab, cd1.1. A A0 0 2.2. 2 23.3. 4.4. A A+ + 本節(jié)重點(diǎn)本節(jié)重點(diǎn)v文法文法v語(yǔ)言語(yǔ)言v句型、句子句型、句子v相關(guān)概念相關(guān)概念v文法與語(yǔ)言文法與語(yǔ)言2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義一一、文法的定義、文法的定義文法：文法：描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（即語(yǔ)法規(guī)則）。描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（即語(yǔ)法規(guī)則）。描述語(yǔ)法規(guī)則描述語(yǔ)法規(guī)則例：例：英語(yǔ)中，一般句子是由英語(yǔ)中，一般句子是由主主謂賓謂賓三三部分部分構(gòu)成。構(gòu)成。302021-11-

19、11vHe gave me a book.He gave me a book.v、產(chǎn)生句子的規(guī)則、產(chǎn)生句子的規(guī)則從產(chǎn)生語(yǔ)言的角度從產(chǎn)生語(yǔ)言的角度 He He me me book book a a gave gave2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義312021-11-11 He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a bookB B、句子的派生（推導(dǎo)）句子的派生（推導(dǎo)）根據(jù)規(guī)則根據(jù)規(guī)則322021-11-112. 2. 文法和語(yǔ)言的形式定義文法和

20、語(yǔ)言的形式定義用圖表示：用圖表示：He gave me a book.He gave me a book.2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義C C、句子的語(yǔ)義要求句子的語(yǔ)義要求 he gave me a book. he gave he a book. me gave me a book. me gave he a book.符合語(yǔ)法且符合語(yǔ)義的句子僅是：符合語(yǔ)法且符合語(yǔ)義的句子僅是： He gave me a book. He He產(chǎn)生式產(chǎn)生式A A-(A)(A)A A-a a等價(jià)于等價(jià)于 A-(A)|aA-(A)|a產(chǎn)生式形式簡(jiǎn)單，內(nèi)容豐富產(chǎn)生式形式簡(jiǎn)單，內(nèi)容豐富定義表達(dá)

21、式、句子等定義表達(dá)式、句子等a, (a), (a), (a)a, (a), (a), (a)都是有意義的都是有意義的文法文法 A-(A)|aA-(A)|a嵌套性質(zhì)嵌套性質(zhì)三類(lèi)符號(hào)三類(lèi)符號(hào)1. 1. 元符號(hào)元符號(hào) - |- |2. 2. 非終結(jié)符非終結(jié)符 可以被替換，至少出現(xiàn)在左邊可以被替換，至少出現(xiàn)在左邊一次一次3. 3. 終結(jié)符終結(jié)符 不可被替換，不能單獨(dú)出現(xiàn)在不可被替換，不能單獨(dú)出現(xiàn)在產(chǎn)生式的左側(cè)產(chǎn)生式的左側(cè)概念：概念：產(chǎn)生式產(chǎn)生式 -|1. 1. ， ， 符號(hào)串符號(hào)串2. 2. 為產(chǎn)生式的左部為產(chǎn)生式的左部3. 3. |為產(chǎn)生式的右部為產(chǎn)生式的右部4. 4. ， 為候選式為候選式文法一般

22、由多個(gè)產(chǎn)生式組成文法一般由多個(gè)產(chǎn)生式組成372021-11-11 He me book a gave如何準(zhǔn)確定義一個(gè)文法如何準(zhǔn)確定義一個(gè)文法產(chǎn)生式類(lèi)型產(chǎn)生式類(lèi)型1. 1. 基本式基本式 A- A- ， 為終結(jié)符串，該語(yǔ)法為終結(jié)符串，該語(yǔ)法所定義的語(yǔ)言，只有一個(gè)字符串所定義的語(yǔ)言，只有一個(gè)字符串2. 2. A- BA- B， ， 為終結(jié)符，為終結(jié)符，B B為非終結(jié)符為非終結(jié)符3. 3. 遞歸式，遞歸式， A-A | A-A | 或者或者 A-A| A-A| 4. 4. 成對(duì)符號(hào)遞歸，成對(duì)符號(hào)遞歸， A- A| A- A| 2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義3 3、文法、文法的形

23、式定義的形式定義是一個(gè)四元組（是一個(gè)四元組（，），）終結(jié)符號(hào)集，非空有限集終結(jié)符號(hào)集，非空有限集非終結(jié)符號(hào)集，非空有限集非終結(jié)符號(hào)集，非空有限集 終結(jié)符號(hào)：終結(jié)符號(hào)：描述單詞符號(hào)描述單詞符號(hào), ,組成語(yǔ)言的基本符號(hào)，是一個(gè)組成語(yǔ)言的基本符號(hào)，是一個(gè) 語(yǔ)言的不可再分的基本符號(hào)。語(yǔ)言的不可再分的基本符號(hào)。例如：基本字，標(biāo)識(shí)符，常數(shù)，算符，界符等例如：基本字，標(biāo)識(shí)符，常數(shù)，算符，界符等非終結(jié)符：非終結(jié)符：代表語(yǔ)法范疇，一個(gè)非終結(jié)符代表一個(gè)一定的語(yǔ)代表語(yǔ)法范疇，一個(gè)非終結(jié)符代表一個(gè)一定的語(yǔ) 法概念，每個(gè)非終結(jié)符表示一定符號(hào)串的集合。法概念，每個(gè)非終結(jié)符表示一定符號(hào)串的集合。例如：算術(shù)表達(dá)式，布爾表達(dá)式

24、，賦值句，分程序，過(guò)程等例如：算術(shù)表達(dá)式，布爾表達(dá)式，賦值句，分程序，過(guò)程等2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義開(kāi)始符號(hào)，一個(gè)特殊的非終結(jié)符號(hào)開(kāi)始符號(hào)，一個(gè)特殊的非終結(jié)符號(hào)產(chǎn)生式集合，有限集產(chǎn)生式集合，有限集產(chǎn)生式：定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則產(chǎn)生式：定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則形式：形式：A AVN, (VTVN)*注：注： “”: “定義為定義為”“”： “或或” 非終結(jié)符號(hào)非終結(jié)符號(hào):用大寫(xiě)字母、用大寫(xiě)字母、或漢語(yǔ)組代表或漢語(yǔ)組代表 終結(jié)符終結(jié)符:用小寫(xiě)字母用小寫(xiě)字母代表代表至少必須在某個(gè)產(chǎn)生至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次式的左部出現(xiàn)一次412021-11-11非終結(jié)符非

25、終結(jié)符終結(jié)符終結(jié)符2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義分析分析：He gave me a book.He gave me a book.2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義終結(jié)符號(hào)集終結(jié)符號(hào)集 VT=He, gave, me, a, book非終結(jié)符號(hào)集非終結(jié)符號(hào)集 VN=, , ,語(yǔ)法規(guī)則集語(yǔ)法規(guī)則集 P= ,開(kāi)始符號(hào)開(kāi)始符號(hào) S=分析句子：分析句子：He gave me a book. .2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義例例1 1：文法文法：E Ei | EAEi | EAE A A+|+|* *非終結(jié)符號(hào)：非終結(jié)符號(hào)：開(kāi)始符號(hào)：開(kāi)始符號(hào)

26、：終結(jié)符號(hào)：終結(jié)符號(hào)：E，AE+，*，iGE 或者或者 G(E)Identifier 標(biāo)示符標(biāo)示符Expression 表達(dá)式表達(dá)式語(yǔ)言，滿(mǎn)足一些格式要求的符號(hào)串的集合語(yǔ)言，滿(mǎn)足一些格式要求的符號(hào)串的集合格式格式 文法文法2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義例例2：算術(shù)表達(dá)式的文法：算術(shù)表達(dá)式的文法標(biāo)識(shí)符標(biāo)識(shí)符(id)(常量、變量常量、變量)是表達(dá)式是表達(dá)式(E)；表達(dá)式加一個(gè)表達(dá)式是表達(dá)式；表達(dá)式加一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式減一個(gè)表達(dá)式是表達(dá)式；表達(dá)式減一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式；表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式；表達(dá)式除一個(gè)表達(dá)式是表達(dá)式；表達(dá)式除一個(gè)表達(dá)

27、式是表達(dá)式；表達(dá)式加上括號(hào)是表達(dá)式；表達(dá)式加上括號(hào)是表達(dá)式； Eid EE+E EE-E EE*E EE/E E(E)P: Eid|E+E|E-E|E*E|E/E|(E)Identifier 標(biāo)示符標(biāo)示符2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義、文法與語(yǔ)言的關(guān)系、文法與語(yǔ)言的關(guān)系中心思想：從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)連續(xù)使用產(chǎn)中心思想：從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)連續(xù)使用產(chǎn) 生式，對(duì)非終結(jié)符施行替換和展開(kāi)生式，對(duì)非終結(jié)符施行替換和展開(kāi)。一一個(gè)文法個(gè)文法如何定義一個(gè)語(yǔ)言呢？如何定義一個(gè)語(yǔ)言呢？給定一個(gè)句子，如何判斷其是否符合所給定的文法？給定一個(gè)句子，如何判斷其是否符合所給定的文法？2.

28、 2. 文法和語(yǔ)言的形式定義（提問(wèn)）文法和語(yǔ)言的形式定義（提問(wèn)）( () ) ( (+ +) ) ( (+ +) ) ( (+ +) )例：例：Eid | E+E | E-E | E*E | E/E | (E) (i+i)注：注：我們可以從出發(fā)，進(jìn)行一系列的推導(dǎo)，推出種種不我們可以從出發(fā)，進(jìn)行一系列的推導(dǎo)，推出種種不 同的算術(shù)表達(dá)式出來(lái)同的算術(shù)表達(dá)式出來(lái)該推導(dǎo)過(guò)程證明了（該推導(dǎo)過(guò)程證明了（+ +）是文法所定義的一個(gè)算術(shù)）是文法所定義的一個(gè)算術(shù)表達(dá)式。表達(dá)式。你能推出哪些表達(dá)式？你能推出哪些表達(dá)式？2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義“”：若若 ，則稱(chēng)該序列是從，則稱(chēng)該序列是從至

29、至的一個(gè)推導(dǎo)（的一個(gè)推導(dǎo)（可推導(dǎo)出可推導(dǎo)出） ： ：+*表示表示“直接推出直接推出”，即僅推出一步。，即僅推出一步。AA ,僅當(dāng)僅當(dāng) 是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式，且且,(,() )* * “推導(dǎo)推導(dǎo)”：從從出發(fā)，經(jīng)過(guò)出發(fā)，經(jīng)過(guò)步步或或若干步若干步，可推導(dǎo)出，可推導(dǎo)出從從出發(fā)，經(jīng)出發(fā)，經(jīng)一步一步或或若干步若干步，可推導(dǎo)出，可推導(dǎo)出注：符號(hào)的含義注：符號(hào)的含義文法所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言，文法所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言，記為（）記為（）*2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義+5 5、語(yǔ)言、語(yǔ)言與自然語(yǔ)言相聯(lián)系與自然語(yǔ)言相聯(lián)系設(shè)是一個(gè)文法，是其開(kāi)始符號(hào)，設(shè)是一個(gè)文法，是其開(kāi)始符

30、號(hào)，, (VN)*,則則稱(chēng)為文法稱(chēng)為文法G的一個(gè)的一個(gè)句型句型僅含終結(jié)符號(hào)的句型是一個(gè)句子僅含終結(jié)符號(hào)的句型是一個(gè)句子“句子句子”：“語(yǔ)言語(yǔ)言”：“句型句型”：*492021-11-11 He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a book句型與句子句型與句子2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義6 6、最左右推導(dǎo)、最左右推導(dǎo)定義：任何一步定義：任何一步 都是對(duì)都是對(duì) 中的最左最右中的最左最右非終結(jié)符非終結(jié)符進(jìn)行進(jìn)行替換的。替換的。+ + +（）（）

31、 （+） （* *+ +） （* *+ +）（+ +）（）+ +（）（） （+ +） （）（） （）（） （）（） （）（）最左推導(dǎo)：最左推導(dǎo)：最右推導(dǎo)最右推導(dǎo)：Ei | E+E | E-E | E*E | E/E | (E)練習(xí)：練習(xí)：GS:GS: S Sa|a|(T)|(T) T TT,S|ST,S|S分別給出下列句子的最左和最右推導(dǎo)過(guò)程：分別給出下列句子的最左和最右推導(dǎo)過(guò)程： （1 1）（）（a,(a,a) a,(a,a) （2 2）(a,(a,)(a,(a,)（1 1）最左推導(dǎo)：）最左推導(dǎo)：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S) S=(T)=(T

32、,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)=(a,(S,S)=(a,(a,S)=(a,(a,a)（2 2）最左推導(dǎo)：）最左推導(dǎo)：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S) S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,)=(a,(S,S)=(a,(a,S)=(a,(a,)2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義7 7、例題、例題例、考慮一個(gè)文法例、考慮一個(gè)文法：定義了一個(gè)什么樣的語(yǔ)言？定義

33、了一個(gè)什么樣的語(yǔ)言？. （）（） ？2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義例、考慮文法例、考慮文法：定義了一個(gè)什么樣的語(yǔ)言？定義了一個(gè)什么樣的語(yǔ)言？分析：分析：與類(lèi)似與類(lèi)似由由可知，其必產(chǎn)生可知，其必產(chǎn)生，且以，且以此終結(jié)此終結(jié) ？（）（），提問(wèn)提問(wèn)G: E-E+E|EG: E-E+E|E* *E|(E)|iE|(E)|i1. 1. 上式什么含義上式什么含義2. 2. 終結(jié)符終結(jié)符集集V VT T3. 3. 非終結(jié)符非終結(jié)符集集V VN N4. 4. 開(kāi)始符號(hào)開(kāi)始符號(hào)S S5. 5. 請(qǐng)列舉其中三個(gè)請(qǐng)列舉其中三個(gè)句型句型6. 6. 請(qǐng)列舉其中三個(gè)請(qǐng)列舉其中三個(gè)句子句子7. 7.

34、形成的形成的語(yǔ)言語(yǔ)言是什么是什么8. 8. 最左推導(dǎo)（）最左推導(dǎo)（）9. 9. 最右推導(dǎo)（）最右推導(dǎo)（）2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義例：構(gòu)造例：構(gòu)造一個(gè)文法一個(gè)文法， 使使（ ）分析：分析：與與的區(qū)別在于，的區(qū)別在于，必須使、出現(xiàn)必須使、出現(xiàn)的的次數(shù)次數(shù)相等相等，故而、必須，故而、必須同時(shí)出現(xiàn)。同時(shí)出現(xiàn)。GG：2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義二、二、語(yǔ)法分析樹(shù)語(yǔ)法分析樹(shù)、語(yǔ)法樹(shù)（推導(dǎo)樹(shù)、生成樹(shù)或分析樹(shù)）語(yǔ)法樹(shù)（推導(dǎo)樹(shù)、生成樹(shù)或分析樹(shù)）用用樹(shù)的形式表示一個(gè)句型的推導(dǎo)生成樹(shù)的形式表示一個(gè)句型的推導(dǎo)生成，有助于理解，有助于理解一個(gè)句子語(yǔ)法結(jié)構(gòu)的層次一個(gè)句子

35、語(yǔ)法結(jié)構(gòu)的層次。樹(shù)根：開(kāi)始符號(hào)樹(shù)根：開(kāi)始符號(hào)中間結(jié)點(diǎn)：非終結(jié)符中間結(jié)點(diǎn)：非終結(jié)符葉結(jié)點(diǎn)：終結(jié)符葉結(jié)點(diǎn)：終結(jié)符非終結(jié)符非終結(jié)符一個(gè)非葉節(jié)點(diǎn)一個(gè)非葉節(jié)點(diǎn)A A按從左到右順序有按從左到右順序有n n個(gè)兒子節(jié)點(diǎn)個(gè)兒子節(jié)點(diǎn)B B1 1、B B2 2、B Bn n，則，則: A: AB B1 1B B2 2BBn n 一定是一定是G G的一個(gè)產(chǎn)生式。的一個(gè)產(chǎn)生式。572021-11-112. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義二、二、語(yǔ)法分析樹(shù)語(yǔ)法分析樹(shù)產(chǎn)生式：產(chǎn)生式： 句型句型句子句子2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義例例：（）的最左推導(dǎo)和最右推導(dǎo)）的最左推導(dǎo)和最右推導(dǎo)（根

36、）（根） （ E E ）+ +* * E Ei i | | E+E E+E | | E-E E-E | | E E* *E E | | E/E | (E/E | (E)E)E E (E)(E)( (E+EE+E) )( (E E* *E+EE+E) )(i (i* *E+EE+E) )(i (i* *i+Ei+E) )(i (i* *i+ii+i) )E E (E)(E)( (E+EE+E) )( (E+iE+i) )(E(E* *E+iE+i) )(E(E* *i+ii+i) )(i (i* *i+ii+i) ) 一棵語(yǔ)法樹(shù)是不同推導(dǎo)過(guò)程的共性抽象。一棵語(yǔ)法樹(shù)是不同推導(dǎo)過(guò)程的共性抽象。592

37、021-11-11v如果使用最左如果使用最左( (右右) )推導(dǎo)，則一個(gè)最左推導(dǎo)，則一個(gè)最左( (右右) )推導(dǎo)與推導(dǎo)與語(yǔ)法樹(shù)一一對(duì)應(yīng)。語(yǔ)法樹(shù)一一對(duì)應(yīng)。v一個(gè)句型是否只對(duì)應(yīng)唯一一棵語(yǔ)法樹(shù)？一個(gè)句型是否只對(duì)應(yīng)唯一一棵語(yǔ)法樹(shù)？Ei+*()EiiEEEEE+*()EiEEiiEE2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義2 2、二義文法、二義文法若若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的最左右推導(dǎo)，則該文法為二義文法最左右推導(dǎo)，則該文法為二義文法例：上述文法例：上述文法* *（）（）2. 2. 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義注意：注意：、區(qū)分：文法的二義性、區(qū)分：文法的二義性語(yǔ)言的二義性語(yǔ)言的二義性二義文法二義文法無(wú)二義文法無(wú)二義文法但（）（但（）（）例如：例如：+*（）（）：+*（）（）（）（）（）語(yǔ)言語(yǔ)言的二義性：一個(gè)的二義性：一個(gè)語(yǔ)言是二義性的語(yǔ)言是二義性的，如果對(duì)它，如果對(duì)它不存在無(wú)二義性的不存在無(wú)二義性的文法文法。表達(dá)式表達(dá)式 項(xiàng)項(xiàng)|表達(dá)式表達(dá)式+項(xiàng)項(xiàng)項(xiàng)項(xiàng) 因子因子 | 項(xiàng)項(xiàng)