1、編譯原理編譯原理(第三版第三版) 陳火旺等編著22022-5-25第二章第二章 高級語言及其語法描述高級語言及其語法描述 n常用的高級語言常用的高級語言 FORTRANFORTRAN數(shù)值計(jì)算數(shù)值計(jì)算 COBOLCOBOL事務(wù)處理事務(wù)處理 PASCALPASCAL結(jié)構(gòu)程序設(shè)計(jì)結(jié)構(gòu)程序設(shè)計(jì) ADAADA大型程序、嵌入式實(shí)時系統(tǒng)大型程序、嵌入式實(shí)時系統(tǒng) PROLOGPROLOG邏輯程序設(shè)計(jì)邏輯程序設(shè)計(jì) ALGOLALGOL算法語言算法語言 C/C+C/C+系統(tǒng)程序設(shè)計(jì)系統(tǒng)程序設(shè)計(jì) JavaJavaInternetInternet程序設(shè)計(jì)程序設(shè)計(jì)32022-5-25n與機(jī)器語言或匯編語言比較與機(jī)器語言

2、或匯編語言比較，高級語言高級語言的的優(yōu)點(diǎn)優(yōu)點(diǎn)：較接近于數(shù)學(xué)語言和工程語言較接近于數(shù)學(xué)語言和工程語言，比較直觀、比較直觀、自然和易于理解自然和易于理解; ;便于驗(yàn)證其正確性便于驗(yàn)證其正確性，易于改錯易于改錯; ;編寫效率高編寫效率高; ;易于移植易于移植. .42022-5-252.12.1 程序語言的定義程序語言的定義n程序語言由兩方面定義：程序語言由兩方面定義：語法語法語義語義 ( (語用語用- -語言成分的使用方法語言成分的使用方法) )52022-5-25一一. 語法語法n程序本質(zhì)上是一定字符集上的字符串。程序本質(zhì)上是一定字符集上的字符串。n語法語法：一組規(guī)則：一組規(guī)則，用它可以形成和產(chǎn)

3、生一用它可以形成和產(chǎn)生一個個合式合式(well-formed)的程序的程序。62022-5-25n詞法規(guī)則詞法規(guī)則：單詞符號的形成規(guī)則：單詞符號的形成規(guī)則。單詞符號是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)單詞符號是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識符、基本字、算符、界符一般包括：常數(shù)、標(biāo)識符、基本字、算符、界符等。等。描述工具：有限自動機(jī)描述工具：有限自動機(jī)n語法規(guī)則語法規(guī)則：語法單位的形成規(guī)則：語法單位的形成規(guī)則。語法單位通常包括：表達(dá)式、語句、分程序、過語法單位通常包括：表達(dá)式、語句、分程序、過程、函數(shù)、程序等程、函數(shù)、程序等; ;描述工具：上下文無關(guān)文法描述工具：上下文無關(guān)文法

4、72022-5-25 Ei EiEE+EEE+EEEEE* *E EE(E)E(E)n語法規(guī)則和詞法規(guī)則定義了程序的的形語法規(guī)則和詞法規(guī)則定義了程序的的形式結(jié)構(gòu)。定義語法單位的意義屬于語義式結(jié)構(gòu)。定義語法單位的意義屬于語義問題。問題。82022-5-25二二. . 語義語義n語義語義：一組規(guī)則：一組規(guī)則，用它可以定義一個程用它可以定義一個程序的意義序的意義。n描述方法：描述方法：自然語言描述：隱藏錯誤、二義性和不完整自然語言描述：隱藏錯誤、二義性和不完整性性形式描述：形式描述：F 操作語義操作語義(PL/1)(PL/1)F 指稱語義指稱語義(ADA)(ADA)F 代數(shù)語義代數(shù)語義(PASCAL

5、)(PASCAL)92022-5-25三程序語言的基本功能和層次結(jié)構(gòu)三程序語言的基本功能和層次結(jié)構(gòu)n程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運(yùn)算。的運(yùn)算。n所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。理過程。102022-5-25程序的層次結(jié)構(gòu)：程序的層次結(jié)構(gòu)：程序程序| |子程序或分程序、過程、函數(shù)子程序或分程序、過程、函數(shù)| |語句語句| |表達(dá)式表達(dá)式| |數(shù)據(jù)引用數(shù)據(jù)引用 算符算符 函數(shù)調(diào)用函數(shù)調(diào)用112022-5-25程序語言每個組成成分的邏輯和實(shí)現(xiàn)意義程序語言每個組成成分的邏輯和實(shí)現(xiàn)意義 n抽象的邏輯的意義抽象的

6、邏輯的意義數(shù)學(xué)意義數(shù)學(xué)意義 n計(jì)算機(jī)實(shí)現(xiàn)的意義計(jì)算機(jī)實(shí)現(xiàn)的意義具體實(shí)現(xiàn)具體實(shí)現(xiàn)122022-5-252.2 2.2 高級語言的一般特性高級語言的一般特性 2.2.1 2.2.1 高級語言的分類高級語言的分類 強(qiáng)制式語言強(qiáng)制式語言(Imperative Languge)(Imperative Languge)也稱過程式語也稱過程式語言：命令驅(qū)動，面向語句言：命令驅(qū)動，面向語句nFORTRANFORTRAN、C C、PascalPascal，Ada Ada 應(yīng)用式語言應(yīng)用式語言（Applicative LanguageApplicative Language）：注重程）：注重程序所表示的功能，而不

7、是一個語句接一個語句地序所表示的功能，而不是一個語句接一個語句地執(zhí)行執(zhí)行nLISPLISP、ML ML 132022-5-25基于規(guī)則的語言基于規(guī)則的語言（Rule-based LanguageRule-based Language）：檢查）：檢查一定的條件，當(dāng)它滿足值，則執(zhí)行適當(dāng)?shù)膭幼饕欢ǖ臈l件，當(dāng)它滿足值，則執(zhí)行適當(dāng)?shù)膭幼鱪Prolog Prolog 面向?qū)ο笳Z言面向?qū)ο笳Z言（Object-Oriented LanguageObject-Oriented Language）：）：封裝性封裝性、繼承性繼承性和和多態(tài)性多態(tài)性nSmalltalkSmalltalk，C+C+，Java Java

8、142022-5-252.2.2 2.2.2 程序結(jié)構(gòu)程序結(jié)構(gòu)n FORTRANFORTRAN一個程序由一個主程序段和若干輔程序段組成。一個程序由一個主程序段和若干輔程序段組成。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。每個程序段有一系列的說明語句和執(zhí)行語句組成。每個程序段有一系列的說明語句和執(zhí)行語句組成。各段可以獨(dú)立編譯。各段可以獨(dú)立編譯。 模塊結(jié)構(gòu)，沒有嵌套和遞歸模塊結(jié)構(gòu)，沒有嵌套和遞歸各程序段中的名字相互獨(dú)立各程序段中的名字相互獨(dú)立，同一個標(biāo)識符在不，同一個標(biāo)識符在不同的程序段中代表不同的名字同的程序段中代表不同的名字。152022-5-25主程序主程序

9、 PROGRAM PROGRAM end end輔程序輔程序1 1 SUBROUTINE SUBROUTINE end end輔程序輔程序2 2 FUNCTION FUNCTION end end162022-5-25nPASCALPASCAL程序本身可以看成是一個操作系程序本身可以看成是一個操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。一個一個PASCAL過程：過程：過程頭；過程頭；說明段（由一系列的說明語句組成）；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；執(zhí)行體（由一系列的執(zhí)行語句組成）；end172022-5-25作用域

10、作用域：一個名字能被使用的區(qū)域范圍：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。稱作這個名字的作用域。允許同一個標(biāo)識符在不同的過程中代表允許同一個標(biāo)識符在不同的過程中代表不同的名字。不同的名字。名字作用域規(guī)則名字作用域規(guī)則- 最近嵌套原則最近嵌套原則 n一個在子程序一個在子程序B1中說明的名字中說明的名字X只在只在B1中中有效（局部于有效（局部于B1）；）；n如果如果B2是是B1的一個內(nèi)層子程序且的一個內(nèi)層子程序且B2中對中對標(biāo)識符標(biāo)識符X沒有新的說明，則原來的名字沒有新的說明，則原來的名字X在在B2中仍然有效。如果中仍然有效。如果B2對對X重新作了說明，重新作了說明，那么，那么，B2對對

11、X的任何引用都是指重新說明的任何引用都是指重新說明過的這個過的這個X。182022-5-25program main var A, B : real; procedure P1 var B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A(integer)192022-5-25PASCAL提供了豐富的數(shù)據(jù)類型和運(yùn)算提供了豐富的數(shù)據(jù)類型和運(yùn)算方式，它允許用戶動態(tài)地申請和退還存方式，它允許用戶動態(tài)地申請和退還存貯空間。貯空間。202022-5-25nADA程序包程序包(pa

12、ckage)：把數(shù)據(jù)和操作代碼封裝在：把數(shù)據(jù)和操作代碼封裝在一起，支持?jǐn)?shù)據(jù)抽象。一起，支持?jǐn)?shù)據(jù)抽象。一個程序包分為兩部分：一個程序包分為兩部分：n可見的規(guī)范說明部分，它定義了程序包外面可以訪可見的規(guī)范說明部分，它定義了程序包外面可以訪問的對象。問的對象。n程序包體，它實(shí)際定義程序包的實(shí)現(xiàn)細(xì)節(jié)。程序包體，它實(shí)際定義程序包的實(shí)現(xiàn)細(xì)節(jié)。212022-5-25package STACKS is type ELEM is private; type STACK is limited private; procedure push (S: in out STACK; E: in ELEM); proced

13、ure pop (S: in out STACK; E: out ELEM); end STACK;package body STACKS is procedure push(S: in out STACK; E: in ELEM); begin 實(shí)現(xiàn)細(xì)節(jié)實(shí)現(xiàn)細(xì)節(jié) end push; procedure pop (S: in out STACK; E: out ELEM); begin 實(shí)現(xiàn)細(xì)節(jié)實(shí)現(xiàn)細(xì)節(jié) end pop;end; 222022-5-25nJAVAJava是一種面向?qū)ο蟮母呒壵Z言是一種面向?qū)ο蟮母呒壵Z言n類（類（Class）n繼承繼承(Inheritance)n多態(tài)性多態(tài)性(Po

14、lymorphism)和動態(tài)綁定和動態(tài)綁定(Dynamic binding)232022-5-25class Car int color_number; int door_number; int speed; push_break ( ) add_oil ( ) class Trash_Car extends car double amount; fill_trash ( ) 242022-5-252.2.3 2.2.3 數(shù)據(jù)類型與操作數(shù)據(jù)類型與操作 n一個數(shù)據(jù)類型通常包括以下三種要素：一個數(shù)據(jù)類型通常包括以下三種要素：用于區(qū)別這種類型數(shù)據(jù)對象的用于區(qū)別這種類型數(shù)據(jù)對象的屬性屬性這種類型的數(shù)據(jù)

15、對象可以具有的這種類型的數(shù)據(jù)對象可以具有的值值可以作用于這種類型的數(shù)據(jù)對象的可以作用于這種類型的數(shù)據(jù)對象的操作操作252022-5-252.2.3 2.2.3 數(shù)據(jù)類型與操作數(shù)據(jù)類型與操作 一初等數(shù)據(jù)類型一初等數(shù)據(jù)類型數(shù)值類型：整型、實(shí)型、復(fù)數(shù)、雙精度，運(yùn)算：數(shù)值類型：整型、實(shí)型、復(fù)數(shù)、雙精度，運(yùn)算：+ +，- -，* *，/ / 等等邏輯類型：布爾運(yùn)算：邏輯類型：布爾運(yùn)算：，字符類型：符號處理字符類型：符號處理指針類型指針類型262022-5-25標(biāo)識符與名字標(biāo)識符與名字n標(biāo)識符標(biāo)識符：以字母開頭的：以字母開頭的，由字母數(shù)字組成由字母數(shù)字組成的字符串的字符串。n標(biāo)識符標(biāo)識符與與名字名字兩者有

16、本質(zhì)區(qū)別：兩者有本質(zhì)區(qū)別：標(biāo)識符標(biāo)識符是語法概念是語法概念名字名字有確切的意義和屬性有確切的意義和屬性272022-5-25標(biāo)識符與名字標(biāo)識符與名字n名字：名字：值：單元中的內(nèi)容值：單元中的內(nèi)容屬性：類型和作用域?qū)傩裕侯愋秃妥饔糜騨名字的性質(zhì)的說明方式：名字的性質(zhì)的說明方式：由說明語句來明確規(guī)定的由說明語句來明確規(guī)定的隱含說明：隱含說明：FORTRAN FORTRAN 以以I,J,K,I,J,K,N N為首的名字為首的名字代表整型，否則為實(shí)型。代表整型，否則為實(shí)型。動態(tài)動態(tài)確定：確定：“走到哪里，是什么，算什么走到哪里，是什么，算什么”（運(yùn)行時才能確定）（運(yùn)行時才能確定） 282022-5-2

17、5二二 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)1 1 數(shù)組數(shù)組n邏輯上，數(shù)組是由同一類型數(shù)據(jù)所組成邏輯上，數(shù)組是由同一類型數(shù)據(jù)所組成的某種的某種n n維矩形結(jié)構(gòu)，沿著每一維的距離，維矩形結(jié)構(gòu)，沿著每一維的距離，稱為稱為下標(biāo)下標(biāo)。數(shù)組可變與不可變：編譯時能否確定其存貯數(shù)組可變與不可變：編譯時能否確定其存貯空間的大小?？臻g的大小。訪問：給出數(shù)組名和下標(biāo)值訪問：給出數(shù)組名和下標(biāo)值存放方式存放方式: : 按行存放按行存放, ,按列存放按列存放292022-5-25數(shù)組元素地址計(jì)算數(shù)組元素地址計(jì)算n數(shù)組數(shù)組A10,20A10,20的的A1A1，11為為a a，各維下標(biāo)各維下標(biāo)為為1 1開始，按行存放，那么開始，按行存放，那么

18、AiAi，jj地址地址為：為： a+(i-1)a+(i-1)* *20+(j-1)20+(j-1)302022-5-25內(nèi)情向量內(nèi)情向量n把數(shù)組的有關(guān)信息記錄在一個把數(shù)組的有關(guān)信息記錄在一個“內(nèi)情向內(nèi)情向量量”中，每個數(shù)組的內(nèi)情向量必須包括：中，每個數(shù)組的內(nèi)情向量必須包括：維數(shù)，各維的上、下限，首地址，以維數(shù)，各維的上、下限，首地址，以及數(shù)組（元素）的類型。及數(shù)組（元素）的類型。l1 u1 d1 l2 u2 d2 ln un dn n C type a 312022-5-252 2 記錄記錄n邏輯上說，記錄結(jié)構(gòu)由已知類型的數(shù)據(jù)組邏輯上說，記錄結(jié)構(gòu)由已知類型的數(shù)據(jù)組合在一起的一種結(jié)構(gòu)。合在一起的

19、一種結(jié)構(gòu)。record char NAME20; integer AGE; bool MARRIED; CARD1000n訪問：復(fù)合名訪問：復(fù)合名 CARDk.NAMECARDk.NAMEn存儲：連續(xù)存放存儲：連續(xù)存放n域的地址計(jì)算：相對于記錄結(jié)構(gòu)起點(diǎn)的相域的地址計(jì)算：相對于記錄結(jié)構(gòu)起點(diǎn)的相對數(shù)對數(shù)OFFSETOFFSET。322022-5-253 3 字符串、表格、棧字符串、表格、棧n字符串：符號處理、公式處理字符串：符號處理、公式處理n表格：本質(zhì)上是一種記錄結(jié)構(gòu)表格：本質(zhì)上是一種記錄結(jié)構(gòu)n線性表：一組順序化的記錄結(jié)構(gòu)線性表：一組順序化的記錄結(jié)構(gòu)n棧：一種線性表，后進(jìn)先出，棧：一種線性表，后

20、進(jìn)先出，POP, PUSHPOP, PUSH332022-5-25三三 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 n一個抽象數(shù)據(jù)類型包括：一個抽象數(shù)據(jù)類型包括：數(shù)據(jù)對象的一個集合；數(shù)據(jù)對象的一個集合；作用于這些數(shù)據(jù)對象的抽象運(yùn)算的集合；作用于這些數(shù)據(jù)對象的抽象運(yùn)算的集合；這種類型對象的封裝，即，除了使用類型中所定義這種類型對象的封裝，即，除了使用類型中所定義的運(yùn)算外，用戶不能對這些對象進(jìn)行操作。的運(yùn)算外，用戶不能對這些對象進(jìn)行操作。n程序設(shè)計(jì)語言對抽象數(shù)據(jù)類型的支持程序設(shè)計(jì)語言對抽象數(shù)據(jù)類型的支持Ada語言通過程序包（語言通過程序包（package）提供了數(shù)據(jù)封裝）提供了數(shù)據(jù)封裝的支持的支持Smalltalk

21、、C+和和Java語言則通過類（語言則通過類（Class）對）對抽象數(shù)據(jù)類型提供支持。抽象數(shù)據(jù)類型提供支持。 342022-5-252.2.4 2.2.4 語句與控制結(jié)構(gòu)語句與控制結(jié)構(gòu)一表達(dá)式一表達(dá)式表達(dá)式由運(yùn)算量（也稱操作數(shù)，即數(shù)據(jù)引用或表達(dá)式由運(yùn)算量（也稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符（操作符）組成。函數(shù)調(diào)用）和算符（操作符）組成。形式：中綴、前綴、后綴形式：中綴、前綴、后綴 X X* *Y -A PY -A P352022-5-25n表達(dá)式形成規(guī)則（表達(dá)式形成規(guī)則（p23）（1 1）變量（包括下標(biāo)變量）、常數(shù)是表達(dá)式；）變量（包括下標(biāo)變量）、常數(shù)是表達(dá)式；（2 2）若）若E1E1、

22、E2E2為表達(dá)式，為表達(dá)式，為二元算符，則為二元算符，則 E1 E2 E1 E2 為表達(dá)式；為表達(dá)式；（3 3）若）若E E為表達(dá)式，為表達(dá)式，為一元算符，則為一元算符，則EE為表達(dá)式；為表達(dá)式；（4 4）若）若E E為表達(dá)式，則（為表達(dá)式，則（E)E)是表達(dá)式。是表達(dá)式。362022-5-25算符的優(yōu)先次序算符的優(yōu)先次序n一般的規(guī)定一般的規(guī)定PASCALPASCAL：左結(jié)合左結(jié)合A+B+C=(A+B)+CFORTRANFORTRAN：對于滿足左、右結(jié)合的算符可任：對于滿足左、右結(jié)合的算符可任取一種，如取一種，如A+B+CA+B+C就可以處理成就可以處理成(A+B)+C(A+B)+C，也，也可

23、以處理成可以處理成A+(B+C)A+(B+C)。n注意兩點(diǎn)注意兩點(diǎn)：代數(shù)性質(zhì)能引用到什么程度視具體的語言不代數(shù)性質(zhì)能引用到什么程度視具體的語言不同而不同；同而不同；在數(shù)學(xué)上成立的代數(shù)性質(zhì)在計(jì)算機(jī)上未必完在數(shù)學(xué)上成立的代數(shù)性質(zhì)在計(jì)算機(jī)上未必完全成立。全成立。372022-5-25二語句二語句n賦值語句：賦值語句： A := BA := B 名字特征：名字特征： ( (了解了解) )左值左值：該名字代表的那個單元（地址）稱為該：該名字代表的那個單元（地址）稱為該名字的左值。名字的左值。( (所代表的存貯單元的地址所代表的存貯單元的地址) )右值右值：一個名字的值稱為該名字的右值。：一個名字的值稱為

24、該名字的右值。( (所所代表的存貯單元的內(nèi)容代表的存貯單元的內(nèi)容) )382022-5-25n控制語句：控制語句： l無條件轉(zhuǎn)移語句無條件轉(zhuǎn)移語句 goto Ll條件語句條件語句 if B then S if B then S1 else S2l循環(huán)語句循環(huán)語句 while B do S repeat S until B for i:=E1 step E2 until E3 do Sl過程調(diào)用語句過程調(diào)用語句 call P(X1, X2, . ,Xn)l返回語句返回語句 return (E)392022-5-25n說明語句：定義各種不同數(shù)據(jù)類型的變量說明語句：定義各種不同數(shù)據(jù)類型的變量或運(yùn)算，

25、定義名字的性質(zhì)?；蜻\(yùn)算，定義名字的性質(zhì)。402022-5-25簡單句和復(fù)合句簡單句和復(fù)合句n簡單句：不包含其他語句成分的基本句簡單句：不包含其他語句成分的基本句n復(fù)合句：句中有句的語句復(fù)合句：句中有句的語句412022-5-25復(fù)習(xí)：程序語言的定義復(fù)習(xí)：程序語言的定義n程序語言由兩方面定義：程序語言由兩方面定義：語法語法：一組規(guī)則：一組規(guī)則，用它可以形成和產(chǎn)生一個合用它可以形成和產(chǎn)生一個合式式(well-formed)的程序的程序n詞法規(guī)則詞法規(guī)則：單詞符號的形成規(guī)則：單詞符號的形成規(guī)則。常數(shù)、標(biāo)識符、基本字、算符、界符等。常數(shù)、標(biāo)識符、基本字、算符、界符等。有限自動機(jī)有限自動機(jī)n語法規(guī)則語法

26、規(guī)則：語法單位的形成規(guī)則：語法單位的形成規(guī)則。表達(dá)式、語句、分程序、過程、函數(shù)、程序等表達(dá)式、語句、分程序、過程、函數(shù)、程序等; ;上下文無關(guān)文法上下文無關(guān)文法語義語義: :一組規(guī)則一組規(guī)則，用它可以定義一個程序的意義用它可以定義一個程序的意義422022-5-25復(fù)習(xí)：程序語言的基本功能和層次結(jié)構(gòu)復(fù)習(xí)：程序語言的基本功能和層次結(jié)構(gòu)n程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運(yùn)算。程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運(yùn)算。n所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。程序程序| |子程序或分程序、過程、函數(shù)子程序或分程序、過程、函數(shù)| |語句語句| |

27、表達(dá)式表達(dá)式| |數(shù)據(jù)引用數(shù)據(jù)引用 算符算符 函數(shù)調(diào)用函數(shù)調(diào)用432022-5-25復(fù)習(xí)：復(fù)習(xí)：高級語言的一般特性高級語言的一般特性 n高級語言的分類高級語言的分類 n程序結(jié)構(gòu)程序結(jié)構(gòu)n數(shù)據(jù)類型與操作數(shù)據(jù)類型與操作初等數(shù)據(jù)類型初等數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n語句與控制結(jié)構(gòu)語句與控制結(jié)構(gòu)442022-5-252.32.3 程序語言的語法描述程序語言的語法描述 n幾個概念幾個概念: :考慮一個考慮一個有窮有窮 字母表字母表 字符集字符集其中每一個元素稱為一個其中每一個元素稱為一個字符字符上的上的字字( (也叫也叫字符串字符串) )是指由是指由中的字符所中的字符所構(gòu)成的一個有窮

28、序列構(gòu)成的一個有窮序列不包含任何字符的序列稱為不包含任何字符的序列稱為空字空字，記為，記為用用* *表示表示上的所有字的全體上的所有字的全體, ,包含空字包含空字例如例如: : 設(shè)設(shè) =a=a，bb，則，則 * *=,a,b,aa,ab,ba,bb,aaa,.,a,b,aa,ab,ba,bb,aaa,. 452022-5-25n*的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U & V n設(shè)：設(shè)：U a, aa V b, bb 那么：那么：UV = ab, abb, aab, aabb VU = ？462022-5-25n*的子集的子集U和和V的的連接連接（積積）定義為）定義

29、為UV | U & V nV自身的自身的 n次次積積記為記為Vn = VVVn規(guī)定規(guī)定V0 = ，令，令 V* = V0 V1 V2 V3 稱稱V*是是V的的閉包閉包;n記記 VVV* ，稱，稱V+是是V的正規(guī)閉包。的正規(guī)閉包。472022-5-25n設(shè)：設(shè)：U a, aa n那么：那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, n注意：注意：空集空集 、 、 、| |482022-5-252.3.1 2.3.1 上下文無關(guān)文法上下文無關(guān)文法n文法文法： 描述語言的語法結(jié)構(gòu)的形式規(guī)則描述語言的語法結(jié)構(gòu)的形式規(guī)則nHe gave me a b

30、ook. He He me me book book a a gave gave492022-5-25 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 book502022-5-25n上下文無關(guān)文法的定義上下文無關(guān)文法的定義： 一個上下文無關(guān)文法一個上下文無關(guān)文法G G是一個四元式是一個四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中V VT T：終結(jié)符集合：終結(jié)符集合( (非空非空) )V VN N：非終結(jié)符集合：非終結(jié)符集合( (非空非空

31、) )，且，且V VT T V VN N= =S S：文法的開始符號，：文法的開始符號，S S V VN NP P：產(chǎn)生式集合：產(chǎn)生式集合( (有限有限) )，每個產(chǎn)生式形式為，每個產(chǎn)生式形式為P P， P P V VN N， ( (V VT T V VN N) )* *開始符開始符S S至少必須在某個產(chǎn)生式的左部出現(xiàn)至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。一次。組成語言的不可再分基本符號能派生出符號或符號串的那些符號512022-5-25n例，定義只含例，定義只含+，*的算術(shù)表達(dá)式的文法的算術(shù)表達(dá)式的文法 G = ， 其中，其中，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成：E iE E+EE E*EE

32、 (E)522022-5-25n幾點(diǎn)規(guī)定：幾點(diǎn)規(guī)定：“ ”也可以用也可以用“:=表示，表示， 這種表示稱為巴這種表示稱為巴科斯范式科斯范式(BNF) P 1 P 2 可縮寫為可縮寫為 P 1| 2| n P n 其中，其中，“|”讀成讀成“或或”，稱為，稱為P的一個候選式。的一個候選式。表示一個文法時，通常只給出開始符號和產(chǎn)生式，表示一個文法時，通常只給出開始符號和產(chǎn)生式，如上例，可表示為：如上例，可表示為：G(E)： E i | E+E | E*E | (E)532022-5-25n幾點(diǎn)規(guī)定：幾點(diǎn)規(guī)定：“ ”也可以用也可以用“:=表示，表示， 這種表示稱為巴這種表示稱為巴科斯范式科斯范式(B

33、NF) P 1 P 2 可縮寫為可縮寫為 P 1| 2| n P n 其中，其中，“|”讀成讀成“或或”，稱為，稱為P的一個候選式。的一個候選式。表示一個文法時，通常只給出開始符號和產(chǎn)生式，表示一個文法時，通常只給出開始符號和產(chǎn)生式，如上例，可表示為：如上例，可表示為：G(E)： E i | E+E | E*E | (E)n例，定義只含例，定義只含+，*的算術(shù)表達(dá)式的文法的算術(shù)表達(dá)式的文法 G=， 其中，其中，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成：E iE E+EE E*EE (E)542022-5-25n定義：稱定義：稱 A 直接推出直接推出，即，即 A 僅當(dāng)僅當(dāng)A 是一個產(chǎn)生式，是一個產(chǎn)生

34、式， 且且 ， (VT VN)* 。n如果如果 1 2 n，則我們稱這個序，則我們稱這個序列是從列是從 1到到 n的一個的一個推導(dǎo)推導(dǎo)。若存在一個從。若存在一個從 1到到 n的推導(dǎo)，則稱的推導(dǎo)，則稱 1可以可以推導(dǎo)推導(dǎo)出出 n 。n對文法對文法G(E)： E i | E+E | E*E | (E)E (E) (E+E) (i+E) (i+i)552022-5-25n通常，用通常，用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過一步或若干步，可以推出一步或若干步，可以推出 n n。（。（推導(dǎo)推導(dǎo)）n*1 用用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過0 0步或步或若干步，可以推出若干步，可以

35、推出 n n。（。（廣義推導(dǎo)廣義推導(dǎo)）* 所以所以 ： 即即 或或n1562022-5-25q定義：假定定義：假定G G是一個文法，是一個文法，S S 是它的開始符號。是它的開始符號。如果如果 ，則稱，則稱 是一個是一個句型句型。僅含終結(jié)。僅含終結(jié)符號的句型是一個符號的句型是一個句子句子。文法。文法G G所產(chǎn)生的句子的所產(chǎn)生的句子的全體是一個全體是一個語言語言，將它記為，將它記為 L(G)L(G)。*S ,|)(*TV SGL572022-5-25n例：例： (i*i+i)是文法是文法 G(E)： E i | E+E | E*E | (E) 的一個句子。的一個句子。 證明：證明： E (E)

36、(E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E，(E)，(E*E+E)，(i*i+i)是句型。是句型。582022-5-25q例：文法例：文法G1(A)：A c|AbG1(A)的語言的語言?L(G1)=c，cb，cbb，以以c開頭，后繼若干個開頭，后繼若干個b592022-5-25n例：文法例：文法G2(S)：S ABA aA|aB bB|bG2(S)的語言的語言?L(G2)=ambn|m，n0602022-5-25q例：給出產(chǎn)生語言為例：給出產(chǎn)生語言為anbn|n 1的文法。的文法。 G3(S)： S aSb S ab612022-5-25q例：給出產(chǎn)生語言為

37、例：給出產(chǎn)生語言為ambn|1 n m 2n的的文法。文法。 G4(S)： S aSb | aaSb S ab | aab 622022-5-25n從一個句型到另一個句型的推導(dǎo)往往不唯從一個句型到另一個句型的推導(dǎo)往往不唯一。一。 E+Ei+Ei+i E+EE+ii+in最左推導(dǎo)最左推導(dǎo)：任何一步：任何一步 都是對都是對 中的最中的最左非終結(jié)符進(jìn)行替換。左非終結(jié)符進(jìn)行替換。 最右推導(dǎo)最右推導(dǎo)：任何一步：任何一步 都是對都是對 中的最中的最右非終結(jié)符進(jìn)行替換。右非終結(jié)符進(jìn)行替換。632022-5-252.3.2 2.3.2 語法樹與二義性語法樹與二義性n用一張圖表示一個句型的推導(dǎo)用一張圖表示一個句

38、型的推導(dǎo), ,稱為語法樹。稱為語法樹。n(i(i* *i+i)i+i)的語法樹的語法樹Ei+*()EiiEEEEE (E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E (E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i) 一棵語法樹是不同推導(dǎo)過程的共性抽象。一棵語法樹是不同推導(dǎo)過程的共性抽象。G(E)： E i | E+E | E*E | (E)(i*i+i)642022-5-25n如果使用最左如果使用最左( (右右) )推導(dǎo)，則一個最左推導(dǎo)，則一個最左( (右右) )推導(dǎo)與語法樹一一對應(yīng)。推導(dǎo)與語法樹一一對應(yīng)。n一個句型是否只對應(yīng)唯一一棵語法樹？一個句

39、型是否只對應(yīng)唯一一棵語法樹？Ei+*()EiiEEEEE+*()EiEEiiEE652022-5-25n定義定義：如果一個文法存在某個句子對應(yīng)兩如果一個文法存在某個句子對應(yīng)兩顆不同的語法樹顆不同的語法樹，則說這個則說這個文法是二義的文法是二義的。G(E)： E i|E+E|E*E|(E) 是二義文法。是二義文法。n語言語言的二義性：一個的二義性：一個語言是二義性的語言是二義性的，如，如果對它不存在無二義性的果對它不存在無二義性的文法文法。可能存在可能存在G和和G，一個為二義的，一個為無二，一個為二義的，一個為無二義的。但義的。但L(G)=L(G)n二義性問題是不可判定問題，即不存在一二義性問題是不可判定問題，即不存在一個算法，它能在有限步驟內(nèi)，確切地判定個算法，它能在有限步驟內(nèi)，確切地判定一個文法是否是二義的。一個文法是否是二義的。n可以找到一組無二義文法的充分條件?？梢哉业揭唤M無二義文法的充分條件。662022-5-25二義文法：二義文法：G(E)： E i|E+E|E*E|(E)表達(dá)式表達(dá)式 項(xiàng)項(xiàng)|表達(dá)式表達(dá)式+項(xiàng)項(xiàng)項(xiàng)項(xiàng) 因子因子 | 項(xiàng)項(xiàng)*因子因子因子因子 (表達(dá)式表達(dá)式) | i無二義文法：無二義文法： G(E)：E T | E+T T F | T*F F (E) | i672022-5-25)EEEFFTTTTi+*(EFiiE