第二章 高級語言及其語法描述

1、第二章第二章 高級語言及其語法描述高級語言及其語法描述 n常用的高級語言常用的高級語言 FORTRANFORTRAN數(shù)值計算數(shù)值計算 COBOLCOBOL事務(wù)處理事務(wù)處理 PASCALPASCAL結(jié)構(gòu)程序設(shè)計結(jié)構(gòu)程序設(shè)計 ADAADA大型程序、嵌入式實時系統(tǒng)大型程序、嵌入式實時系統(tǒng) PROLOGPROLOG邏輯程序設(shè)計邏輯程序設(shè)計 ALGOLALGOL算法語言算法語言 C/C+C/C+系統(tǒng)程序設(shè)計系統(tǒng)程序設(shè)計 JavaJavaInternetInternet程序設(shè)計程序設(shè)計n與機器語言或匯編語言比較，高級語言與機器語言或匯編語言比較，高級語言的優(yōu)點：的優(yōu)點：較接近于數(shù)學語言和工程語言，比較直觀

2、、較接近于數(shù)學語言和工程語言，比較直觀、自然和易于理解自然和易于理解; ;便于驗證其正確性，易于改錯便于驗證其正確性，易于改錯; ;編寫效率高編寫效率高; ;易于移植易于移植. .2.12.1 程序語言的定義程序語言的定義n程序語言由兩方面定義：程序語言由兩方面定義：語法語法語義語義語用語用一一. 語法語法n程序本質(zhì)上是一定字符集上的字符串。程序本質(zhì)上是一定字符集上的字符串。n語法語法：一組規(guī)則，用它可以形成和產(chǎn)生一：一組規(guī)則，用它可以形成和產(chǎn)生一個個合式合式(well-formed)的程序。的程序。語語 法法n詞法規(guī)則詞法規(guī)則：單詞符號的形成規(guī)則。：單詞符號的形成規(guī)則。單詞符號是語言中具有獨

3、立意義的最基本結(jié)構(gòu)。單詞符號是語言中具有獨立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標識符、基本字、算符、界一般包括：常數(shù)、標識符、基本字、算符、界符等。符等。描述工具：有限自動機描述工具：有限自動機n語法規(guī)則語法規(guī)則：語法單位的形成規(guī)則。：語法單位的形成規(guī)則。語法單位通常包括：表達式、語句、分程序、語法單位通常包括：表達式、語句、分程序、過程、函數(shù)、程序等過程、函數(shù)、程序等; ;描述工具：上下文無關(guān)文法描述工具：上下文無關(guān)文法n Ei EiEE+EEE+EEEEE* *E EE(E)E(E)n語法規(guī)則和詞法規(guī)則定義了程序的的形語法規(guī)則和詞法規(guī)則定義了程序的的形式結(jié)構(gòu)。定義語法單位的意義屬于語義式結(jié)

4、構(gòu)。定義語法單位的意義屬于語義問題。問題。二二. . 語義語義n語義語義：一組規(guī)則，用它可以定義一個程：一組規(guī)則，用它可以定義一個程序的意義。序的意義。n描述方法：描述方法：自然語言描述：隱藏錯誤、二義性和不完整自然語言描述：隱藏錯誤、二義性和不完整性性形式描述：形式描述：F 操作語義操作語義F 指稱語義指稱語義F 代數(shù)語義代數(shù)語義F 公理語義公理語義三程序語言的基本功能和層次結(jié)構(gòu)三程序語言的基本功能和層次結(jié)構(gòu)n程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運算。的運算。n所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。理過程。程序的

5、層次結(jié)構(gòu)程序的層次結(jié)構(gòu)程序程序| |子程序或分程序、過程、函數(shù)子程序或分程序、過程、函數(shù)| |語句語句| |表達式表達式| |數(shù)據(jù)引用數(shù)據(jù)引用 算符算符 函數(shù)調(diào)用函數(shù)調(diào)用程序語言每個組成成分的邏輯和實現(xiàn)意義程序語言每個組成成分的邏輯和實現(xiàn)意義 n抽象的邏輯的意義抽象的邏輯的意義數(shù)學意義數(shù)學意義 n計算機實現(xiàn)的意義計算機實現(xiàn)的意義具體實現(xiàn)具體實現(xiàn)2.2 2.2 高級語言的一般特性高級語言的一般特性 n高級語言的分類高級語言的分類 強制式語言強制式語言(Imperative Languge)(Imperative Languge)也稱過程式語也稱過程式語言：命令驅(qū)動，面向語句言：命令驅(qū)動，面向語句

6、nFORTRANFORTRAN、C C、PascalPascal，Ada Ada 應用式語言應用式語言（Applicative LanguageApplicative Language）：注重程）：注重程序所表示的功能，而不是一個語句接一個語句地序所表示的功能，而不是一個語句接一個語句地執(zhí)行執(zhí)行nLISPLISP、ML ML 2.2 2.2 高級語言的一般特性高級語言的一般特性 2.2.1 2.2.1 高級語言的分類高級語言的分類 基于規(guī)則的語言基于規(guī)則的語言（Rule-based LanguageRule-based Language）：檢查）：檢查一定的條件，當它滿足值，則執(zhí)行適當?shù)膭幼饕?/p>

7、定的條件，當它滿足值，則執(zhí)行適當?shù)膭幼鱪Prolog Prolog 面向?qū)ο笳Z言面向?qū)ο笳Z言（Object-Oriented LanguageObject-Oriented Language）：）：封裝性封裝性、繼承性繼承性和和多態(tài)性多態(tài)性nSmalltalkSmalltalk，C+C+，Java Java 2.2 2.2 高級語言的一般特性高級語言的一般特性2.2.2 2.2.2 程序結(jié)構(gòu)程序結(jié)構(gòu)n FORTRANFORTRAN一個程序由一個主程序段和若干輔程序段組成。一個程序由一個主程序段和若干輔程序段組成。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。每個程

8、序段有一系列的說明語句和執(zhí)行語句組成。每個程序段有一系列的說明語句和執(zhí)行語句組成。各段可以獨立編譯。各段可以獨立編譯。 模塊結(jié)構(gòu)，沒有嵌套和遞歸模塊結(jié)構(gòu)，沒有嵌套和遞歸各程序段中的名字相互獨立各程序段中的名字相互獨立，同一個標識符在不，同一個標識符在不同的程序段中代表不同的名字同的程序段中代表不同的名字。主程序主程序 PROGRAM PROGRAM end end輔程序輔程序1 1 SUBROUTINE SUBROUTINE end end輔程序輔程序2 2 FUNCTION FUNCTION end endnPASCALPASCAL程序本身可以看成是一個操作系程序本身可以看成是一個操作系統(tǒng)所

9、調(diào)用的過程，過程可以嵌套和遞歸。統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。一個一個PASCAL過程：過程：過程頭；過程頭；說明段（由一系列的說明語句組成）；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；執(zhí)行體（由一系列的執(zhí)行語句組成）；end作用域作用域：一個名字能被使用的區(qū)域范圍：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。稱作這個名字的作用域。允許同一個標識符在不同的過程中代表允許同一個標識符在不同的過程中代表不同的名字。不同的名字。名字作用域規(guī)則名字作用域規(guī)則- 最近嵌套原則最近嵌套原則 n一個在子程序一個在子程序B1中說明的名字中說明的名字X只在只在B1中

10、中有效（局部于有效（局部于B1）；）；n如果如果B2是是B1的一個內(nèi)層子程序且的一個內(nèi)層子程序且B2中對中對標識符標識符X沒有新的說明，則原來的名字沒有新的說明，則原來的名字X在在B2中仍然有效。如果中仍然有效。如果B2對對X重新作了說明，重新作了說明，那么，那么，B2對對X的任何引用都是指重新說明的任何引用都是指重新說明過的這個過的這個X。program main var A, B : real; procedure P1 var B:boolean; begin end procedure P2 var A:integer; begin endbegin endPASCAL提供了豐富的數(shù)據(jù)

11、類型和運算提供了豐富的數(shù)據(jù)類型和運算方式，它允許用戶動態(tài)地申請和退還存方式，它允許用戶動態(tài)地申請和退還存貯空間。貯空間。nADA程序包程序包(package)：把數(shù)據(jù)和操作代碼封裝在：把數(shù)據(jù)和操作代碼封裝在一起，支持數(shù)據(jù)抽象。一起，支持數(shù)據(jù)抽象。一個程序包分為兩部分：一個程序包分為兩部分：n可見的規(guī)范說明部分，它定義了程序包外面可以訪可見的規(guī)范說明部分，它定義了程序包外面可以訪問的對象。問的對象。n程序包體，它實際定義程序包的實現(xiàn)細節(jié)。程序包體，它實際定義程序包的實現(xiàn)細節(jié)。package STACKS is type ELEM is private; type STACK is limited

12、 private; procedure push (S: in out STACK; E: in ELEM); procedure pop (S: in out STACK; E: out ELEM); end STACK;package body STACKS is procedure push(S: in out STACK; E: in ELEM); begin 實現(xiàn)細節(jié)實現(xiàn)細節(jié) end push; procedure pop (S: in out STACK; E: out ELEM); begin 實現(xiàn)細節(jié)實現(xiàn)細節(jié) end pop;end; nJAVAJava是一種面向?qū)ο蟮母呒壵Z言

13、是一種面向?qū)ο蟮母呒壵Z言n類（類（Class）n繼承繼承(Inheritance)n多態(tài)性多態(tài)性(Polymorphism)和動態(tài)綁定和動態(tài)綁定(Dynamic binding)class Car int color_number; int door_number; int speed; push_break ( ) add_oil ( ) class Trash_Car extends car double amount; fill_trash ( ) 2.2.3 2.2.3 數(shù)據(jù)類型與操作數(shù)據(jù)類型與操作 n一個數(shù)據(jù)類型通常包括以下三種要素：一個數(shù)據(jù)類型通常包括以下三種要素：用于區(qū)別這種類型

14、數(shù)據(jù)對象的屬性用于區(qū)別這種類型數(shù)據(jù)對象的屬性這種類型的數(shù)據(jù)對象可以具有的值這種類型的數(shù)據(jù)對象可以具有的值可以作用于這種類型的數(shù)據(jù)對象的操作可以作用于這種類型的數(shù)據(jù)對象的操作2.2.3 2.2.3 數(shù)據(jù)類型與操作數(shù)據(jù)類型與操作 一初等數(shù)據(jù)類型一初等數(shù)據(jù)類型數(shù)值類型：整型、實型、復數(shù)、雙精度，數(shù)值類型：整型、實型、復數(shù)、雙精度， 運算：運算：+ +，- -，* *，/ /等等邏輯類型：布爾運算：邏輯類型：布爾運算：，字符類型：符號處理字符類型：符號處理指針類型指針類型標識符與名字標識符與名字n標識符標識符：以字母開頭的，由字母數(shù)字組成：以字母開頭的，由字母數(shù)字組成的字符串。的字符串。n標識符標識符

15、與與名字名字兩者有本質(zhì)區(qū)別：兩者有本質(zhì)區(qū)別：標識符標識符是語法概念是語法概念名字名字有確切的意義和屬性有確切的意義和屬性Jordan ?標識符！?標識符與名字標識符與名字n名字：名字：值：單元中的內(nèi)容值：單元中的內(nèi)容屬性：類型和作用域?qū)傩裕侯愋秃妥饔糜騨名字的性質(zhì)的說明方式：名字的性質(zhì)的說明方式：由說明語句來明確規(guī)定的由說明語句來明確規(guī)定的隱含說明：隱含說明：FORTRAN FORTRAN 以以I,J,K,NI,J,K,N為首的名字為首的名字代表整型，否則為實型。代表整型，否則為實型。動態(tài)確定：走到哪里，是什么，算什么動態(tài)確定：走到哪里，是什么，算什么 二二 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)1 1 數(shù)組數(shù)組n

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

17、j-1)20+(j-1)n數(shù)組元素地址計算公式數(shù)組元素地址計算公式內(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 2 2 記錄記錄n邏輯上說，記錄結(jié)構(gòu)由已知類型的數(shù)據(jù)組邏輯上說，記錄結(jié)構(gòu)由已知類型的數(shù)據(jù)組合在一起的一種結(jié)構(gòu)。合在一起的一種結(jié)構(gòu)。record char NAME20; integer AGE;

18、bool MARRIED; CARD1000n訪問：復合名訪問：復合名 CARDk.NAMECARDk.NAMEn存儲：連續(xù)存放存儲：連續(xù)存放n域的地址計算：相對于記錄結(jié)構(gòu)起點的相域的地址計算：相對于記錄結(jié)構(gòu)起點的相對數(shù)對數(shù)OFFSETOFFSET。3 3 字符串、表格、棧字符串、表格、棧n字符串：符號處理、公式處理字符串：符號處理、公式處理n表格：本質(zhì)上是一種記錄結(jié)構(gòu)表格：本質(zhì)上是一種記錄結(jié)構(gòu)n線性表：一組順序化的記錄結(jié)構(gòu)線性表：一組順序化的記錄結(jié)構(gòu)n棧：一種線性表，后進先出，棧：一種線性表，后進先出，POP, PUSHPOP, PUSH三三 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 n一個抽象數(shù)據(jù)類型包括

19、：一個抽象數(shù)據(jù)類型包括：數(shù)據(jù)對象的一個集合；數(shù)據(jù)對象的一個集合；作用于這些數(shù)據(jù)對象的抽象運算的集合；作用于這些數(shù)據(jù)對象的抽象運算的集合；這種類型對象的封裝，即，除了使用類型中所這種類型對象的封裝，即，除了使用類型中所定義的運算外，用戶不能對這些對象進行操作。定義的運算外，用戶不能對這些對象進行操作。n程序設(shè)計語言對抽象數(shù)據(jù)類型的支持程序設(shè)計語言對抽象數(shù)據(jù)類型的支持Ada語言通過程序包（語言通過程序包（package）提供了數(shù)據(jù)）提供了數(shù)據(jù)封裝的支持封裝的支持Smalltalk、C+和和Java語言則通過類（語言則通過類（Class）對抽象數(shù)據(jù)類型提供支持。對抽象數(shù)據(jù)類型提供支持。 2.2.4

20、2.2.4 語句與控制結(jié)構(gòu)語句與控制結(jié)構(gòu)一表達式一表達式表達式由運算量（也稱操作數(shù)，即數(shù)據(jù)引用或表達式由運算量（也稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符（操作符）組成。函數(shù)調(diào)用）和算符（操作符）組成。形式：中綴、前綴、后綴形式：中綴、前綴、后綴 X X* *Y -A PY -A P表達式形成規(guī)則表達式形成規(guī)則算符的優(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)

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

22、的內(nèi)容代表的存貯單元的內(nèi)容) )n控制語句：控制語句： 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)n說明語句：定義各種不同數(shù)據(jù)類型的變量說明語句：定義各種不同數(shù)據(jù)類型的變量或運算，定義名字的性質(zhì)。或運算，定義名字的性質(zhì)。簡單句和復合句簡單句和復合句n簡單句：不包

23、含其他語句成分的基本句簡單句：不包含其他語句成分的基本句n復合句：句中有句的語句復合句：句中有句的語句復習：程序語言的定義復習：程序語言的定義n程序語言由兩方面定義：程序語言由兩方面定義：語法語法：一組規(guī)則，用它可以形成和產(chǎn)生一個合式：一組規(guī)則，用它可以形成和產(chǎn)生一個合式(well-formed)的程序的程序n詞法規(guī)則詞法規(guī)則：單詞符號的形成規(guī)則。：單詞符號的形成規(guī)則。常數(shù)、標識符、基本字、算符、界符等。常數(shù)、標識符、基本字、算符、界符等。有限自動機有限自動機n語法規(guī)則語法規(guī)則：語法單位的形成規(guī)則。：語法單位的形成規(guī)則。表達式、語句、分程序、過程、函數(shù)、程序等表達式、語句、分程序、過程、函數(shù)、

24、程序等; ;上下文無關(guān)文法上下文無關(guān)文法語義語義: :一組規(guī)則，用它可以定義一個程序的意義一組規(guī)則，用它可以定義一個程序的意義復習：程序語言的基本功能和層次結(jié)構(gòu)復習：程序語言的基本功能和層次結(jié)構(gòu)n程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運算。程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運算。n所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。程序程序| |子程序或分程序、過程、函數(shù)子程序或分程序、過程、函數(shù)| |語句語句| |表達式表達式| |數(shù)據(jù)引用數(shù)據(jù)引用 算符算符 函數(shù)調(diào)用函數(shù)調(diào)用復習：復習：高級語言的一般特性高級語言的一般特性 n高級語言的分類高級語言的分

25、類 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)2.3 2.3 程序語言的語法描述程序語言的語法描述 n幾個概念幾個概念: :考慮一個考慮一個有窮有窮 字母表字母表 字符集字符集其中每一個元素稱為一個其中每一個元素稱為一個字符字符上的上的字字( (也叫也叫字符串字符串) ) 是指由是指由中的字符所構(gòu)中的字符所構(gòu)成的一個有窮序列成的一個有窮序列不包含任何字符的序列稱為不包含任何字符的序列稱為空字空字，記為，記為用用* *表示表示上的所有字的全體上的所有字的全體, ,包含空字包含空字例如例如: : 設(shè)

26、設(shè) =a=a， bb，則，則 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.n*的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U & V n設(shè)：設(shè)：U a, aa V b, bb n那么：那么：UV= ab, abb, aab, aabb n*的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U & V nV自身的自身的 n次積記為次積記為Vn=VVVn規(guī)定規(guī)定V0= ，令，令 V*=V0V1V2V3 稱稱V*是是V的的閉包閉包;n記記 VVV* ，稱，稱V+是是V的正規(guī)閉包。的正規(guī)閉包。n設(shè)：

27、設(shè)：U a, aa n那么：那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, 2.3.1 2.3.1 上下文無關(guān)文法上下文無關(guān)文法n文法文法： 描述語言的語法結(jié)構(gòu)的形式規(guī)則描述語言的語法結(jié)構(gòu)的形式規(guī)則nHe gave me a book. He He me me book book a a gave gave 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 bookn上下文無關(guān)文法的定義：上下文無關(guān)文法的定義： 一個

28、上下文無關(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é)符集合( (非空非空) )，且，且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)一次。一次

29、。n例，定義只含例，定義只含+，*的算術(shù)表達式的文法的算術(shù)表達式的文法 G=， 其其中，中，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成：E iE E+EE E*EE (E)n幾點規(guī)定：幾點規(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

30、)n例，定義只含例，定義只含+，*的算術(shù)表達式的文法的算術(shù)表達式的文法 G=， 其中，其中，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成：E iE E+EE E*EE (E)n定義：稱定義：稱 A 直接推出直接推出，即，即 A 僅當僅當A 是一個產(chǎn)生式，是一個產(chǎn)生式， 且且 ， (VT VN)* 。n如果如果 1 2 n，則我們稱這個序，則我們稱這個序列是從列是從 1到到 n的一個的一個推導推導。若存在一個從。若存在一個從 1到到 n的推導，則稱的推導，則稱 1可以可以推導推導出出 n 。n對文法對文法G(E)： E i | E+E | E*E | (E)E (E) (E+E) (i+E) (i+i)

31、n通常，用通常，用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過一步或若干步，可以推出一步或若干步，可以推出 n n。n1n*1 用用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過0 0步或步或若干步，可以推出若干步，可以推出 n n。* 所以所以 ： 即即 或或*S ,|)(*TV SGLq定義：假定定義：假定G G是一個文法，是一個文法，S S 是它的開始符號。是它的開始符號。如果如果 ，則，則 稱是一個稱是一個句型句型。僅含終結(jié)符。僅含終結(jié)符號的句型是一個號的句型是一個句子句子。文法。文法G G所產(chǎn)生的句子的全所產(chǎn)生的句子的全體是一個體是一個語言語言，將它記為，將它記為 L(G)L(G)

32、。n例：例： (i*i+i)是文法是文法G(E)： E i | E+E | E*E | (E)的一個句子。的一個句子。 證明：證明： E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E，(E)，(E*E+E)，(i*i+i)是句型。是句型。q例：文法例：文法G1(A)：A c|AbG1(A)的語言的語言?L(G1)=c，cb，cbb，以以c開頭，后繼若干個開頭，后繼若干個bn例：文法例：文法G2(S)：S ABA aA|aB bB|bG2(S)的語言的語言?L(G2)=ambn|m，n0q例：給出產(chǎn)生語言為例：給出產(chǎn)生語言為anbn|n 1的文法。的文法

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

34、張圖表示一個句型的推導, ,稱為語法樹。稱為語法樹。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) 一棵語法樹是不同推導過程的共性抽象。一棵語法樹是不同推導過程的共性抽象。G(E)： E i | E+E | E*E | (E)(i*i+i)n如果使用最左如果使用最左( (右右) )推導，則一個最左推導，則一個最左( (右右) )推導與語法樹一一對應。推導與語法樹一一對應。n一個句型是否只對應唯一一棵語法樹？一個句型是否只

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