同濟大學(xué)編譯原理 第二章 高級語言及其語法描述

1、第二章 高級語言及其語法描述概述n要學(xué)習(xí)和構(gòu)造編譯程序，理解和定義高級語言是要學(xué)習(xí)和構(gòu)造編譯程序，理解和定義高級語言是必不可少的必不可少的n本章概述高級語言的結(jié)構(gòu)和主要共同特征，重點本章概述高級語言的結(jié)構(gòu)和主要共同特征，重點介紹程序設(shè)計語言的語法描述方法介紹程序設(shè)計語言的語法描述方法內(nèi)容線索n程序設(shè)計語言的定義程序設(shè)計語言的定義n高級語言的一般特性高級語言的一般特性n程序語言的語法描述程序語言的語法描述程序設(shè)計語言的定義n程序設(shè)計語言是為書寫計算機程序而人為設(shè)計的程序設(shè)計語言是為書寫計算機程序而人為設(shè)計的符號語言。符號語言。機器語言機器語言匯編語言匯編語言高級語言高級語言各級語言的比較比較比較

2、 機器語言機器語言匯編語言匯編語言高級語言高級語言硬件識別硬件識別是唯一可以識別是唯一可以識別的語言的語言不可識別不可識別不可識別不可識別是否可直接是否可直接執(zhí)行執(zhí)行可直接執(zhí)行可直接執(zhí)行不可，需匯編、不可，需匯編、連接連接不可，需編譯不可，需編譯/ /解釋、解釋、連接連接特點特點面向機器面向機器占用內(nèi)存少占用內(nèi)存少執(zhí)行速度快執(zhí)行速度快使用不方便使用不方便面向機器面向機器占用內(nèi)存少占用內(nèi)存少執(zhí)行速度快執(zhí)行速度快較為直觀較為直觀與機器語言一與機器語言一一對應(yīng)一對應(yīng)n面向問題面向問題/ /對象對象n占用內(nèi)存大占用內(nèi)存大n執(zhí)行速度相對慢執(zhí)行速度相對慢n標準化程度高標準化程度高n便于程序交換，使便于程序

3、交換，使用方便用方便定位定位低級語言，極少低級語言，極少使用使用低級語言，很低級語言，很少使用少使用高級語言，種類多，高級語言，種類多，常用常用程序語言的內(nèi)涵語法語法語義語義語用語用表示構(gòu)成語言句子的各個記號之間的表示構(gòu)成語言句子的各個記號之間的組合規(guī)律組合規(guī)律( (構(gòu)成規(guī)則構(gòu)成規(guī)則) )。表示按照各種表示方法所表示的各個表示按照各種表示方法所表示的各個記號的特定含義（各個記號和記號所記號的特定含義（各個記號和記號所表示的對象之間的關(guān)系）。表示的對象之間的關(guān)系）。表示各個記號或語言詞句與其使用之表示各個記號或語言詞句與其使用之間的關(guān)系。間的關(guān)系。 舉例：C語言的賦值語句語法語法語義語義語用語用

4、賦值語句由一賦值語句由一個變量，后隨個變量，后隨一個符號一個符號“=”，再在后面跟一再在后面跟一個表達式所構(gòu)個表達式所構(gòu)成。成。賦值語句賦值語句先對該語句的右部先對該語句的右部表達式求值，然后表達式求值，然后把所得結(jié)果與語句把所得結(jié)果與語句左部的變量相結(jié)合，左部的變量相結(jié)合，并取代該變量原有并取代該變量原有的值。的值。賦值語句可用賦值語句可用來計算和保存來計算和保存表達式的值。表達式的值。語法n語言的語法是指可以形成和產(chǎn)生合式程序的一組規(guī)則。它語言的語法是指可以形成和產(chǎn)生合式程序的一組規(guī)則。它包括包括詞法規(guī)則詞法規(guī)則和和語法規(guī)則語法規(guī)則。詞法規(guī)則是指程序中單詞符號的形成規(guī)則。單詞符號一般包括：

5、詞法規(guī)則是指程序中單詞符號的形成規(guī)則。單詞符號一般包括：標識符、基本字、常量、算符和界符。標識符、基本字、常量、算符和界符。語法規(guī)則是指程序中語法單位的形成規(guī)則。程序語言的語法單位語法規(guī)則是指程序中語法單位的形成規(guī)則。程序語言的語法單位有：表達式、語句、分程序、過程、函數(shù)、程序。有：表達式、語句、分程序、過程、函數(shù)、程序。n描述方式：詞法規(guī)則和語法規(guī)則都可以用自然語言、語法描述方式：詞法規(guī)則和語法規(guī)則都可以用自然語言、語法圖、圖、BNF范式、或文法等描述。范式、或文法等描述。語法描述方式（1）（1）自然語言）自然語言例例1. 標識符是由字母后跟若干個（包括標識符是由字母后跟若干個（包括0個）字

6、母或數(shù)字的符號串組個）字母或數(shù)字的符號串組成的。成的。例例2. 賦值語句由一個變量，后隨一個符號賦值語句由一個變量，后隨一個符號“=”，再在后面跟一個表，再在后面跟一個表達式所構(gòu)成。達式所構(gòu)成。（2）語法圖）語法圖是用圖解形式描述程序設(shè)計語言語法規(guī)則的工具。是用圖解形式描述程序設(shè)計語言語法規(guī)則的工具。例例1. 標識符的構(gòu)成規(guī)則用語法圖描述為：標識符的構(gòu)成規(guī)則用語法圖描述為：標識符標識符字母字母數(shù)字數(shù)字字母字母語法描述方式（2）（3）BNF范式范式巴科斯范式巴科斯范式(BNF: Backus-Naur Form 的縮寫的縮寫)是由是由 John Backus 和和 Peter Naur 首先引入

7、的用來描述計算機語言語法的符首先引入的用來描述計算機語言語法的符號集。號集?，F(xiàn)在，新的編程語言幾乎都使用巴科斯范式來定義編程語言的語現(xiàn)在，新的編程語言幾乎都使用巴科斯范式來定義編程語言的語法規(guī)則。法規(guī)則。 簡單算術(shù)表達式的BNF范式 + * () in或者或者 + | * | () | i附：BNF表示n表示為表示為 n非終結(jié)符用非終結(jié)符用“”括起來括起來n終結(jié)符：基本符號集終結(jié)符：基本符號集n其他其他(1|2|n)1|2|n1|2|n mn | 語義n對于一個語言來說，不僅要給出它的詞法、語法規(guī)則，而對于一個語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義。這就

8、是語義問且要定義它的單詞符號和語法單位的意義。這就是語義問題。題。n語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意義。義。n我們采用的方法為：基于屬性文法的語法制導(dǎo)翻譯方法。我們采用的方法為：基于屬性文法的語法制導(dǎo)翻譯方法。程序語言的功能n一個程序語言的基本功能一個程序語言的基本功能是描述是描述數(shù)據(jù)數(shù)據(jù)和和對數(shù)據(jù)的運對數(shù)據(jù)的運算算。n所謂程序，從本質(zhì)上來說所謂程序，從本質(zhì)上來說是描述一定數(shù)據(jù)的處理過是描述一定數(shù)據(jù)的處理過程。程。n在現(xiàn)今的程序語言中，一在現(xiàn)今的程序語言中，一個程序大體可以視為如圖個程序大體可以視為如圖所示的層次結(jié)構(gòu)所示的層次

9、結(jié)構(gòu)數(shù)據(jù)引用算符函數(shù)調(diào)用表達式語句子程序/ 分程序程序內(nèi)容線索程序設(shè)計語言的定義程序設(shè)計語言的定義n高級語言的一般特性高級語言的一般特性n程序語言的語法描述程序語言的語法描述高級語言的分類(1) 過程式：過程式：Imperative Language形式：語句序列形式：語句序列舉例：舉例：Fortran、C、Pascal (2) 函數(shù)式：函數(shù)式：Applicative Language形式：形式：func1(func(n)舉例：舉例：Lisp(3) 基于規(guī)則：基于規(guī)則：Rule-Based Language形式：形式：bird(x) :- fly(x) & feather(x)舉例：舉

10、例：Prolog(4) 面向?qū)ο螅好嫦驅(qū)ο螅篛bject-Oriented Language形式：形式：class, 舉例：舉例：Smalltalk、C+、Java高級語言的一般特性n程序結(jié)構(gòu)程序結(jié)構(gòu)n數(shù)據(jù)類型與操作數(shù)據(jù)類型與操作n語句與控制結(jié)構(gòu)語句與控制結(jié)構(gòu)程序結(jié)構(gòu)單層結(jié)構(gòu)nFortran程序結(jié)構(gòu)程序結(jié)構(gòu) 主程序若干個輔程序段（子程序、函數(shù)）主程序若干個輔程序段（子程序、函數(shù)） Program Main Read(I,J) Call max(I,J,K) Write(100, K)100 Format() end subroutine max(x,y,z) integer x,y,z if

11、xy then zx else z y end程序結(jié)構(gòu)多層結(jié)構(gòu)nPascal程序結(jié)構(gòu)程序結(jié)構(gòu) 程序允許嵌套定義程序允許嵌套定義Program P; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer;Var v:integer); var c,d:integer; begin end begin end begin . end初等類型、復(fù)合類型到抽象數(shù)據(jù)類型n類型本不存在類型本不存在內(nèi)存里存儲的內(nèi)容，你認為它是什么，它就是什么內(nèi)存里存儲的內(nèi)容，你認為它是什么，它就是什么n高級語言設(shè)計了初等數(shù)

12、據(jù)類型：整型、浮點型、字符型等。不同的語高級語言設(shè)計了初等數(shù)據(jù)類型：整型、浮點型、字符型等。不同的語言也會定義不同的初等類型等。言也會定義不同的初等類型等。初等數(shù)據(jù)類型并不能方便地解決所有問題初等數(shù)據(jù)類型并不能方便地解決所有問題n復(fù)合數(shù)據(jù)類型是初等數(shù)據(jù)類型迭代派生而來復(fù)合數(shù)據(jù)類型是初等數(shù)據(jù)類型迭代派生而來典型的代表就是典型的代表就是 “結(jié)構(gòu)結(jié)構(gòu)”，數(shù)組也可算作此類，數(shù)組也可算作此類n抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADT)在復(fù)合數(shù)據(jù)類型的基礎(chǔ)上增加了對數(shù)據(jù)的操作在復(fù)合數(shù)據(jù)類型的基礎(chǔ)上增加了對數(shù)據(jù)的操作抽象數(shù)據(jù)類型進而進化為抽象數(shù)據(jù)類型進而進化為 “類類(Class)”類型n每個被計算對象都帶有自己

13、的類型，以類型作為每個被計算對象都帶有自己的類型，以類型作為值的屬性的概括，因此每個類型都意味著一個值值的屬性的概括，因此每個類型都意味著一個值的集合。的集合。n不同類型的值具有不同的操作運算不同類型的值具有不同的操作運算n類型是一個值的集合和定義在這個值集上的一組類型是一個值的集合和定義在這個值集上的一組操作的總稱。操作的總稱。如如C語言中的整型變量語言中的整型變量(int)，其值集為某個區(qū)間上的整，其值集為某個區(qū)間上的整數(shù)，定義在其上的操作為數(shù)，定義在其上的操作為+, -, *, /等等抽象數(shù)據(jù)類型n一個抽象數(shù)據(jù)類型（一個抽象數(shù)據(jù)類型（Abstract Data Type，ADT）定義為：

14、）定義為：（1）一個數(shù)據(jù)對象集，數(shù)據(jù)對象由一個或多個類型定義；）一個數(shù)據(jù)對象集，數(shù)據(jù)對象由一個或多個類型定義；（2）一個作用于這些數(shù)據(jù)對象的抽象操作集；）一個作用于這些數(shù)據(jù)對象的抽象操作集；（3）完全封裝，用戶除了能使用該類型的操作來處理這類數(shù)據(jù)對象）完全封裝，用戶除了能使用該類型的操作來處理這類數(shù)據(jù)對象之外，不能作其他的處理。之外，不能作其他的處理。 n抽象數(shù)據(jù)類型有兩個重要特征：抽象數(shù)據(jù)類型有兩個重要特征：信息隱蔽信息隱蔽和和數(shù)據(jù)封裝數(shù)據(jù)封裝，使，使用與實現(xiàn)相分離用與實現(xiàn)相分離抽象數(shù)據(jù)類型First Come First Service（queue）InQueueOutQueueIsEmp

15、tyOverflowQueue（ADT）對外操作接口對外操作接口結(jié)構(gòu)數(shù)據(jù)維護接口結(jié)構(gòu)數(shù)據(jù)維護接口結(jié)構(gòu)數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)的物理實現(xiàn)物理實現(xiàn)抽象數(shù)據(jù)類型（續(xù)）First Come First Service（queue）InQueueOutQueueIsEmptyOverflowQueue（ADT）對外操作接口對外操作接口結(jié)構(gòu)數(shù)據(jù)維護接口結(jié)構(gòu)數(shù)據(jù)維護接口結(jié)構(gòu)數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)的物理實現(xiàn)物理實現(xiàn)抽象數(shù)據(jù)類型的特點n數(shù)據(jù)抽象用數(shù)據(jù)抽象用ADT描述程序處理的實體時，強調(diào)的描述程序處理的實體時，強調(diào)的是其是其本質(zhì)的特征本質(zhì)的特征、其、其所能完成的功能所能完成的功能以及以及它和外它和外部用戶的接口部用戶的接口（即外

16、界使用它的方法）。（即外界使用它的方法）。n數(shù)據(jù)封裝將實體的外部特性和其內(nèi)部實現(xiàn)細節(jié)分數(shù)據(jù)封裝將實體的外部特性和其內(nèi)部實現(xiàn)細節(jié)分離，并且對外部用戶隱藏其內(nèi)部實現(xiàn)細節(jié)。離，并且對外部用戶隱藏其內(nèi)部實現(xiàn)細節(jié)。數(shù)據(jù)抽象的優(yōu)點n程序組織和修改程序組織和修改n可讀性、可靠性、可維護性可讀性、可靠性、可維護性通過隱藏數(shù)據(jù)表示，用戶代碼不能直接訪問該通過隱藏數(shù)據(jù)表示，用戶代碼不能直接訪問該類型對象，不依賴于其表示，因此可以修改該類型對象，不依賴于其表示，因此可以修改該類型對象的表示而不影響用戶代碼類型對象的表示而不影響用戶代碼語句與控制結(jié)構(gòu)n表達式表達式n語句語句簡單語句簡單語句：不含其它語句成分的基本句。

17、不含其它語句成分的基本句。n說明語句說明語句n賦值語句賦值語句n控制語句控制語句n過程調(diào)用語句過程調(diào)用語句復(fù)合語句：句中有句的語句復(fù)合語句：句中有句的語句表達式n表達式：一個表達式是由運算量（亦稱操作數(shù)，即數(shù)據(jù)引表達式：一個表達式是由運算量（亦稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。用或函數(shù)調(diào)用）和算符組成的。n對于大多數(shù)程序語言來說，表達式的形成規(guī)則可概括為：對于大多數(shù)程序語言來說，表達式的形成規(guī)則可概括為：（1）變量（包括下標變量）、常數(shù)是表達式；）變量（包括下標變量）、常數(shù)是表達式；（2）若）若E1、E2為表達式，為表達式，為二元算符，則為二元算符，則 E1 E2為表達式；為表達式

18、；（3）若）若E為表達式，為表達式， 為一元算符，則為一元算符，則E為表達式；為表達式；（4）若）若E為表達式，則為表達式，則( E )是表達式。是表達式。語句n不同程序語言含有不同形式和功能的各種語句。不同程序語言含有不同形式和功能的各種語句。n從功能上說語句大體可分從功能上說語句大體可分執(zhí)行性語句執(zhí)行性語句和和說明性語說明性語句句兩大類：兩大類：說明性語句旨在定義不同數(shù)據(jù)類型的變量或運算。說明性語句旨在定義不同數(shù)據(jù)類型的變量或運算。執(zhí)行性語句旨在描述程序的動作。執(zhí)行性語句旨在描述程序的動作。n執(zhí)行性語句又可分為賦值語句、控制語句和輸入執(zhí)行性語句又可分為賦值語句、控制語句和輸入/輸出語句輸出

19、語句n從形式上說，語句可分為從形式上說，語句可分為簡單句簡單句、復(fù)合句復(fù)合句和和分程分程序序等。等。賦值語句A:= Bn意義是：意義是：“把把B的值的值送入送入A所代表的單元所代表的單元” 在賦值句中，賦值號在賦值句中，賦值號：=左右兩邊的變量名扮演著兩種不同的左右兩邊的變量名扮演著兩種不同的角色。對賦值號右邊的角色。對賦值號右邊的B我們需要的是它的值；對于左邊的我們需要的是它的值；對于左邊的A我們我們需要的是它們的所代表的存儲單元（的地址）。需要的是它們的所代表的存儲單元（的地址）。n為了區(qū)分一個名字的這兩種特征，我們把一個名字所代表為了區(qū)分一個名字的這兩種特征，我們把一個名字所代表的那個存

20、儲單元（地址）稱為該名字的的那個存儲單元（地址）稱為該名字的左值左值；把一個名字；把一個名字的值稱為該名字的的值稱為該名字的右值右值?？刂普Z句n多數(shù)語言中所含的控制語句有：多數(shù)語言中所含的控制語句有：無條件轉(zhuǎn)移語句無條件轉(zhuǎn)移語句: goto L條件語句：條件語句： if B then S if B then S1 else S2循環(huán)語句：循環(huán)語句： while B do S repeat S until B for i:=E1 step E2 until E3 do S過程調(diào)用語句：過程調(diào)用語句： call P( X1,X2,Xn)返回語句：返回語句： return(E)說明語句n說明語句旨在

21、定義名字的性質(zhì)。說明語句旨在定義名字的性質(zhì)。n編譯程序把這些性質(zhì)登記在符號表中，并檢查程編譯程序把這些性質(zhì)登記在符號表中，并檢查程序中名字的引用和說明是否相一致。序中名字的引用和說明是否相一致。內(nèi)容線索程序設(shè)計語言的定義程序設(shè)計語言的定義高級語言的一般特性高級語言的一般特性n程序語言的語法描述程序語言的語法描述概述n對于高級程序語言及編譯程序而言，語言的語法對于高級程序語言及編譯程序而言，語言的語法定義是非常重要的。本節(jié)將介紹語法結(jié)構(gòu)的形式定義是非常重要的。本節(jié)將介紹語法結(jié)構(gòu)的形式描述問題。描述問題。編譯原理編譯原理= =形式語言理論形式語言理論+ +編譯技術(shù)編譯技術(shù)形式語言n自然語言自然語言

22、人們平時說話時所使用的一種語言，不同的國家和民族有著不同人們平時說話時所使用的一種語言，不同的國家和民族有著不同的語言。的語言。n形式語言形式語言通過人們公認的符號、表達方式所描述的一種語言，是一種通用通過人們公認的符號、表達方式所描述的一種語言，是一種通用語言，沒有國籍之分。語言，沒有國籍之分。形式語言是某個形式語言是某個字母表上的字符串的集合字母表上的字符串的集合，有一定的描述范圍。，有一定的描述范圍。為什么用形式語言n形式語言的最初起因：形式語言的最初起因： 語言學(xué)家喬姆斯基（語言學(xué)家喬姆斯基（Chomsky）想用一套形）想用一套形式化方法來描述語言。式化方法來描述語言。n形式語言在自然

23、語言研究中起步，在計算機科學(xué)中得到廣泛應(yīng)用。形式語言在自然語言研究中起步，在計算機科學(xué)中得到廣泛應(yīng)用。最初的應(yīng)用：編譯最初的應(yīng)用：編譯 現(xiàn)在已廣泛應(yīng)用在人工智能、圖像處理、通信協(xié)議、通信軟件等多個領(lǐng)現(xiàn)在已廣泛應(yīng)用在人工智能、圖像處理、通信協(xié)議、通信軟件等多個領(lǐng)域域在計算機理論科學(xué)方面：在計算機理論科學(xué)方面：n是可計算理論（算法是可計算理論（算法在有限步驟內(nèi)求得解、算法復(fù)雜性、停機問題、）、在有限步驟內(nèi)求得解、算法復(fù)雜性、停機問題、）、定理自動證明、程序轉(zhuǎn)換（程序自動生成）、模式識別等的基礎(chǔ)。定理自動證明、程序轉(zhuǎn)換（程序自動生成）、模式識別等的基礎(chǔ)。形式語言與自動機理論的發(fā)展n1956年，喬姆斯

24、基（年，喬姆斯基（Chomsky）從產(chǎn)生的角度研究語言）從產(chǎn)生的角度研究語言文法文法n1951-1956年間，克林（年間，克林（Kleene）從識別的角度研究語言）從識別的角度研究語言自動機自動機n1959年，喬姆斯基不僅確定了文法和自動機分別從生成年，喬姆斯基不僅確定了文法和自動機分別從生成和識別的角度去表達語言，而且證明了文法與自動機的等和識別的角度去表達語言，而且證明了文法與自動機的等價性。價性。形式語言真正誕生形式語言真正誕生相關(guān)概念和知識n概念概念字母表、符號、符號串、串長度、空符號串字母表、符號、符號串、串長度、空符號串、子符號串、前綴、后綴、符號串集合、子符號串、前綴、后綴、符號

25、串集合n注意區(qū)分注意區(qū)分： 、（連接）（連接）積積定義為定義為:nUV= U & V 閉包、正則閉包閉包、正則閉包n規(guī)定規(guī)定 V0 = .n V* = V0 V1 V2 ，稱，稱 V*是是V的的閉包閉包。n記記V+ = VV*, 稱稱 V+是是V的的正則閉包正則閉包。 。閉包n定理定理. 若若A是符號串集合，則是符號串集合，則A*=(A*)* 。 1niiMp則則 xAM，因此推得，因此推得 xA*，所以所以 (A*)* A*，故故 A*=(A*)*。 證明證明：顯然：顯然 A* (A*)* , 現(xiàn)證現(xiàn)證 (A*)* A* 任給符號串任給符號串 x(A*)*，則存在，則存在n，使得，使

26、得 x(A*)n， 必存在必存在n個子串個子串x1 ,xn ， 使得使得x= x1xn ，且，且 xiA* (i=1,n)。 由由xiA* ，必存在整數(shù)，必存在整數(shù)pi ,使得使得xiApi ， 令令 文法（Grammar）n所謂所謂文法文法是用來定義語言的一個數(shù)學(xué)模型。是用來定義語言的一個數(shù)學(xué)模型。n表示語言的方法：表示語言的方法：若語言若語言L是有限集合，可用列舉法是有限集合，可用列舉法若若L是無限集合（集合中的每個元素有限長度），用其他方法。是無限集合（集合中的每個元素有限長度），用其他方法。方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語言的每個句子方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則

27、產(chǎn)生出語言的每個句子方法二：機器識別系統(tǒng)：當一個字符串能被一個語言的識別系統(tǒng)接受，方法二：機器識別系統(tǒng)：當一個字符串能被一個語言的識別系統(tǒng)接受，則這個字符串是該語言的一個句子，否則不屬于該語言。則這個字符串是該語言的一個句子，否則不屬于該語言。Chomsky文法體系nChomsky文法體系中，任何一種文法必須包含文法體系中，任何一種文法必須包含兩個不同的有限符號的集合兩個不同的有限符號的集合n非終結(jié)符集合非終結(jié)符集合VNn終結(jié)符集合終結(jié)符集合VT一個起始符一個起始符S一個形式規(guī)則的有限集合一個形式規(guī)則的有限集合 （產(chǎn)生式集合）。（產(chǎn)生式集合）。n注意注意中的產(chǎn)生式是用來產(chǎn)生語言句子的規(guī)則，而中

28、的產(chǎn)生式是用來產(chǎn)生語言句子的規(guī)則，而句子句子則是僅由終結(jié)符組成則是僅由終結(jié)符組成的字符串。的字符串。這些字符串必須從一個起始符這些字符串必須從一個起始符S開始，不斷使用中的產(chǎn)生式而導(dǎo)出來。開始，不斷使用中的產(chǎn)生式而導(dǎo)出來。文法的核心是產(chǎn)生式的集合，它決定了語言中句子的產(chǎn)生。文法的核心是產(chǎn)生式的集合，它決定了語言中句子的產(chǎn)生。文法的術(shù)語與知識n推導(dǎo)推導(dǎo)直接推導(dǎo)直接推導(dǎo)最左推導(dǎo)、最右推導(dǎo)最左推導(dǎo)、最右推導(dǎo)n歸約歸約最左歸約、最右歸約最左歸約、最右歸約n句型、句子和語言句型、句子和語言n文法體系文法體系3型文法、型文法、2型文法型文法文法的形式定義n文法文法G是一個四元組是一個四元組G=(VN, V

29、T, S, )，其中，其中VN ：非終結(jié)符的有限集合：非終結(jié)符的有限集合VT ：終結(jié)符的有限集合，：終結(jié)符的有限集合， VN VT = S ：開始符號且：開始符號且S VN 。 ：形式為：形式為 P的產(chǎn)生式的有限集合，的產(chǎn)生式的有限集合， 且且P(VNVT)* VN (VNVT)* ， (VNVT)* 文法示例n文法文法G1 =(N, 0, 1, N, N0N, N1N, N0, N1) 其中：其中：VN = N VT = 0, 1 S = N = N0N, N1N, N0, N1 文法的解釋（1）n非終結(jié)符號非終結(jié)符號：需要進一步定義的符號，不會出現(xiàn)在程序中。：需要進一步定義的符號，不會出現(xiàn)

30、在程序中。用來代表語法范疇。如用來代表語法范疇。如“算術(shù)表達式算術(shù)表達式”、“布爾表達式布爾表達式”、“過過程程”等。等。一個非終結(jié)符代表一個一定的語法概念，因此非終結(jié)符是一個類一個非終結(jié)符代表一個一定的語法概念，因此非終結(jié)符是一個類（或集合）記號，而不是個體記號。（或集合）記號，而不是個體記號。n終結(jié)符號終結(jié)符號：不需要再定義，會出現(xiàn)在程序中。：不需要再定義，會出現(xiàn)在程序中。組成語言的基本符號，即在程序語言中的單詞符號，如標識符，組成語言的基本符號，即在程序語言中的單詞符號，如標識符，常數(shù)，算符和界符等常數(shù)，算符和界符等n開始符號開始符號S至少在某個產(chǎn)生式的左部出現(xiàn)一次至少在某個產(chǎn)生式的左部

31、出現(xiàn)一次. 文法的解釋（2）n產(chǎn)生式產(chǎn)生式（規(guī)則）：定義語法單位的一種書寫規(guī)則（規(guī)則）：定義語法單位的一種書寫規(guī)則它的形式為：它的形式為：P （或（或P:= ） 其中其中“”讀作讀作“定義為定義為”， P，為符號串，箭頭左邊稱為產(chǎn)為符號串，箭頭左邊稱為產(chǎn)生式左部，箭頭右邊稱為產(chǎn)生式右部。生式左部，箭頭右邊稱為產(chǎn)生式右部。 例例：S0S1，0S01若干個左部相同的產(chǎn)生式如若干個左部相同的產(chǎn)生式如 P1 , P2 , P3 , . , Pn 可合并成一個可合并成一個,縮寫為縮寫為 P1|2|3|.|n , 其中其中,每個每個i 稱為是稱為是P的一個的一個候選式候選式.習(xí)慣寫法nVN:大寫字母大寫字

32、母A、B、C、S等等nVT: 小寫字母，小寫字母，09，+、 等運算符，等運算符，n、:文法符號串文法符號串,(VTVN)*nS:開始符號，第一個產(chǎn)生式中出現(xiàn)開始符號，第一個產(chǎn)生式中出現(xiàn)n :定義符號（推出）定義符號（推出）n|：或：或文法的約定n為了簡化，文法表示為了簡化，文法表示只寫出產(chǎn)生式部分只寫出產(chǎn)生式部分約定第一個產(chǎn)生式的左部符號為初始符號約定第一個產(chǎn)生式的左部符號為初始符號 或或 在產(chǎn)生式前寫上在產(chǎn)生式前寫上“GA”，其中，其中G為文法名，為文法名，A為初始符為初始符號號. 例例. 文法文法GN: N0N, N1N, N0, N1 文法文法GE: EE+EE*E(E)i如何由文法產(chǎn)

33、生語言的句子？n基本思想基本思想：從識別符號開始，把當前產(chǎn)生的：從識別符號開始，把當前產(chǎn)生的符號串中的符號串中的非終結(jié)符號非終結(jié)符號替換為相應(yīng)產(chǎn)生式右替換為相應(yīng)產(chǎn)生式右部的部的符號串符號串，直到最終全由，直到最終全由終結(jié)符號終結(jié)符號組成。組成。這種替換過程稱為推導(dǎo)或產(chǎn)生句子的過程，這種替換過程稱為推導(dǎo)或產(chǎn)生句子的過程，每一步稱為每一步稱為直接推導(dǎo)直接推導(dǎo)或或直接產(chǎn)生直接產(chǎn)生。直接推導(dǎo)與歸約n直接推導(dǎo)直接推導(dǎo)如果如果A是一個產(chǎn)生式，而是一個產(chǎn)生式，而，（VTVN）*，則，則將產(chǎn)生式將產(chǎn)生式A用于符號串用于符號串A 得到符號串得到符號串，記為，記為A ， 稱稱A直接推出直接推出。n歸約是推導(dǎo)的逆過

34、程歸約是推導(dǎo)的逆過程若存在若存在A ，則稱，則稱能夠直接歸約成能夠直接歸約成A 。推導(dǎo)n推導(dǎo)：設(shè)推導(dǎo)：設(shè)1,2,n (n0)(VTVN)*，且有，且有 1 2 n 則稱這個序列是從則稱這個序列是從1到到n的一個推導(dǎo)。的一個推導(dǎo)。n若存在從若存在從1到到n的一個推導(dǎo)，則稱的一個推導(dǎo)，則稱1可推導(dǎo)出可推導(dǎo)出n。n 1 n (經(jīng)一步或若干步推導(dǎo)）經(jīng)一步或若干步推導(dǎo)） n 1 n （經(jīng)（經(jīng)0步或若干步推導(dǎo)）步或若干步推導(dǎo)）+*最左（右）推導(dǎo)（歸約）n若在推導(dǎo)關(guān)系中，每次最先替換最左（右）若在推導(dǎo)關(guān)系中，每次最先替換最左（右）的非終結(jié)符，則稱為的非終結(jié)符，則稱為最左（右）推導(dǎo)最左（右）推導(dǎo)；n若在歸約過

35、程中，每次最先歸約最左（右）若在歸約過程中，每次最先歸約最左（右）的非終結(jié)符，則稱為的非終結(jié)符，則稱為最左（右）歸約最左（右）歸約。n例例. 文法文法GS: SAB AA0|1B B0|S1， 請給出句子請給出句子101001的最左和最右推導(dǎo)。的最左和最右推導(dǎo)。最右推導(dǎo)：最右推導(dǎo)： S AB AS1 AAB1 AA01 A1B01 A1001 1B1001 101001最左推導(dǎo)：最左推導(dǎo)： S AB 1BB 10B 10S1 10AB1 101BB1 1010B1 101001句型、句子和語言n句型句型：假定：假定G是一個文法，是一個文法，S是它的開始符號，如是它的開始符號，如果果S ，則稱，

36、則稱是文法是文法G的一個句型。的一個句型。 例例 (E+E), (i+E), (i+i), E 都是都是GE的句型。的句型。n句子句子：僅由終結(jié)符組成的句型稱為句子。：僅由終結(jié)符組成的句型稱為句子。 例例 (ii+i), (i+i) 都是都是GE的句子。的句子。n語言語言：文法：文法G所產(chǎn)生句子的全體，即：所產(chǎn)生句子的全體，即： L(G) =|S ，VT*+例例. 設(shè)有文法設(shè)有文法G1S: S bA , AaA | a 試求此文法所描述的語言。試求此文法所描述的語言。 解：因為從開始符號解：因為從開始符號S出發(fā)可推出下列句子：出發(fā)可推出下列句子： S bA ba S bA baA baa S

37、bA baA baaA baaa S bA baA baaa 所以，所以，L(G1)= ban | n 1例例.設(shè)文法設(shè)文法G2S ：S AB A aA|a B bB|b該文法所描述的語言是什么？該文法所描述的語言是什么？解：從文法開始符號解：從文法開始符號S出發(fā)，可推出下列句子：出發(fā)，可推出下列句子：S AB abS AB aAB aaB aabS AB aAB aaB aabB aabbB aabbbS AB aaabbbmn所以，所以，L(G2)=ambn | m,n 1 例例. 試對如下語言試對如下語言L(G3) = anbn |n=1構(gòu)造文法構(gòu)造文法G3。解：解： L(G3)由以下一

38、些符號由以下一些符號串串x組成：組成： n=1, x=abn=2, x=aabbn=3, x=aaabbbL(G3)=ab,aabb,aaabbb,由此可見，集合由此可見，集合L（G3）有如下特點：有如下特點：n每個符號串呈對稱形式，每個符號串呈對稱形式，即即a,b成對出現(xiàn)；成對出現(xiàn)；nL(G3)為無窮集合，描述為無窮集合，描述它的規(guī)則中含遞歸定義；它的規(guī)則中含遞歸定義；n文法中終結(jié)符只有文法中終結(jié)符只有a,b。因此可用以下兩條產(chǎn)生式定義語言因此可用以下兩條產(chǎn)生式定義語言L(G3) S aSb|ab即：即：G3=（S，a,b，S aSb|ab，S)例例. 文法文法G ： 0|1|2|3|4|5

39、|6|7|8|9 語言語言L(G)為非負整數(shù)。為非負整數(shù)。例例. 寫一文法寫一文法G3，使其描述的語言為正奇數(shù)集合。，使其描述的語言為正奇數(shù)集合。 令令G3 = VN,VT,P, ，其中，其中， VT =0,1,2,3,4,5,6,7,8,9， VN =, , , , S： P： 13579 02468 思考思考 ：如果要求開頭元素非零，如何改造？：如果要求開頭元素非零，如何改造？ 123456789 13579 02468或者：或者： S A BA B BCD C 0 E A D E A E 2468 A 13579Chomsky文法體系3012文法、形式語言和自動機的對應(yīng)關(guān)系遞歸可枚遞歸可

40、枚舉語言舉語言圖靈機圖靈機0型文法型文法上下文有上下文有關(guān)語言關(guān)語言線性有界線性有界自動機自動機1型文法型文法上下文無上下文無關(guān)語言關(guān)語言下推自動下推自動機機2型文法型文法正規(guī)語言正規(guī)語言有限自動有限自動機機3型文法型文法語法分析樹和文法的二義性n語法分析樹，簡稱語法樹語法分析樹，簡稱語法樹n二義性二義性什么是語法樹？n語法樹是表示一個語法樹是表示一個句型推句型推導(dǎo)過程導(dǎo)過程的圖，是一棵倒立的圖，是一棵倒立的樹。的樹。結(jié)點結(jié)點邊邊根結(jié)點根結(jié)點末端結(jié)點末端結(jié)點末端分支：末端分支：A(a,b)和和B(c,d)兄弟結(jié)點兄弟結(jié)點SBBdbaAcdc從推導(dǎo)構(gòu)造語法樹n方法：把開始符號方法：把開始符號S

41、S做為語法樹的根結(jié)點，做為語法樹的根結(jié)點，對每一個直接推導(dǎo)畫一次結(jié)點的擴展，該對每一個直接推導(dǎo)畫一次結(jié)點的擴展，該結(jié)點是直接推導(dǎo)中被替換的非終結(jié)符號，結(jié)點是直接推導(dǎo)中被替換的非終結(jié)符號，其所有兒子結(jié)點所組成的符號串是推導(dǎo)中其所有兒子結(jié)點所組成的符號串是推導(dǎo)中所用產(chǎn)生式右部。直到推出或句型或句子所用產(chǎn)生式右部。直到推出或句型或句子或無法再推導(dǎo)時結(jié)束。或無法再推導(dǎo)時結(jié)束。示例文法n文法文法G =(S, A, B, a, b, c, d, S, SAB, AabB|ab, BcBd|cd) S abccdd ?S AB AcBd Accdd abccddS（1）SBA（2）SBBdAc（3）SBBd

42、baAcdc（5）SBBdAcdc（4）語法樹的構(gòu)造過程n給定文法給定文法G，G=(VN,VT, S, )，對于，對于G的任何句型都能構(gòu)造與之的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列特征：關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列特征：1、根結(jié)點的標記是開始符號、根結(jié)點的標記是開始符號S；2、每個結(jié)點的標記都是、每個結(jié)點的標記都是V中的一個符號；中的一個符號；3、若一棵子樹的根結(jié)點為、若一棵子樹的根結(jié)點為A，且其所有兒子結(jié)點的標記從左向右，且其所有兒子結(jié)點的標記從左向右的排列為的排列為A1A2AR，那么，那么 A A1A2.AR一定是一定是中的一條產(chǎn)中的一條產(chǎn)生式（規(guī)則）；生式

43、（規(guī)則）；4、若一標記為、若一標記為A的結(jié)點至少有一個兒子，則的結(jié)點至少有一個兒子，則AVN5、樹的葉結(jié)點符號所組成的符號串、樹的葉結(jié)點符號所組成的符號串W就是所給句型；若就是所給句型；若w中僅含中僅含終結(jié)符號，則終結(jié)符號，則w為文法為文法G所產(chǎn)生的句子。所產(chǎn)生的句子。語法樹的特征n例例. 文法文法 GE ： EE+TT TT*FF F(E)i 句型句型E+F*i推導(dǎo)：推導(dǎo)： E E+T E+T*F E+F*F E+F*i 對應(yīng)的語法樹如右圖對應(yīng)的語法樹如右圖 * i E E T + F T F 同一句型有不同的推導(dǎo)序列n設(shè)有文法設(shè)有文法GN1: N1N N ND|D D0|1|2 則句子則句

44、子12可由若干種不同的推導(dǎo)序列推導(dǎo)出可由若干種不同的推導(dǎo)序列推導(dǎo)出來：來： (1) N1 N ND N2 D2 12 (2) N1 N ND DD 1D 12n同一句型（句子）可以通過不同的推導(dǎo)序列推同一句型（句子）可以通過不同的推導(dǎo)序列推導(dǎo)出來。導(dǎo)出來。 EE+E i+E i+E*E i+i*E i+i*i E E*EE+E*E i+E*Ei+i*E i+i*iEE+EE*EiiiEE*E+EEiii最左推導(dǎo)及相應(yīng)語法樹最左推導(dǎo)及相應(yīng)語法樹同理，該句子的最右推導(dǎo)及相應(yīng)語法樹也不同同理，該句子的最右推導(dǎo)及相應(yīng)語法樹也不同文法文法GE：EE+EE*E(E)i 句子句子: i+i*i語法樹解釋n語

45、法樹表明了在推導(dǎo)過程中使用了哪條規(guī)則和使用在哪個語法樹表明了在推導(dǎo)過程中使用了哪條規(guī)則和使用在哪個非終結(jié)符號上，但它并沒有表明非終結(jié)符號上，但它并沒有表明使用規(guī)則（產(chǎn)生式）的順使用規(guī)則（產(chǎn)生式）的順序序。n一個句型是否只有唯一的一個最左一個句型是否只有唯一的一個最左(最右最右)推導(dǎo)呢推導(dǎo)呢? 否！否！n一個句型是否只對應(yīng)唯一的一棵語法樹呢一個句型是否只對應(yīng)唯一的一棵語法樹呢? 否！否！因為不同的最右（左）推導(dǎo)對應(yīng)不同的語法樹。因為不同的最右（左）推導(dǎo)對應(yīng)不同的語法樹。二義性n如果一個文法的句子（句型）存在兩棵語如果一個文法的句子（句型）存在兩棵語法樹法樹, ,那么那么, ,該該句子是二義性的句

46、子是二義性的。n如果一個文法包含二義性的句子如果一個文法包含二義性的句子, ,則稱這個則稱這個文法是二義性的文法是二義性的; ; 否則，該否則，該文法是無二義文法是無二義性的。性的。說明中國足球誰也贏不了中國足球誰也贏不了 中國乒乓球誰也贏不了中國乒乓球誰也贏不了1 . 一般來說，程序語言存在無二義性的文法描述，但是對一般來說，程序語言存在無二義性的文法描述，但是對于條件語句，經(jīng)常使用二義性文法描述它：于條件語句，經(jīng)常使用二義性文法描述它： S if expr then S if expr then S else S other二義性的句子二義性的句子: if e1 then if e2 th

47、en s1 else s2可以用無二義文法來描述，但是可以用無二義文法來描述，但是比較復(fù)雜比較復(fù)雜2. 在能駕馭的情況下，使用在能駕馭的情況下，使用二義性文法。二義性文法。語言的二義性與文法的二義性問題n如語言如語言L找到一個文法是無二義的，則找到一個文法是無二義的，則L是無二義是無二義的；的；n如未找到一個文法是無二義的，也不能斷定如未找到一個文法是無二義的，也不能斷定L二義。二義。n產(chǎn)生某上下文無關(guān)語言的每一個文法都是二義的，則稱此產(chǎn)生某上下文無關(guān)語言的每一個文法都是二義的，則稱此語言是先天二義的語言是先天二義的. 例例. aibicj i,j 1 aibjcj i,j 1 存在一個二義性

48、的句子存在一個二義性的句子akbkckn文法的二義性是不可判定的。文法的二義性是不可判定的。 （因為文法的二義性由句子的語法樹決定，不可能對無窮（因為文法的二義性由句子的語法樹決定，不可能對無窮句子來判別）句子來判別）二義文法改造為無二義文法n 文法文法GE：EE+E E*E (E) i 是二義性的，是二義性的，如果規(guī)定如果規(guī)定“”和和“”的優(yōu)先性，并服從左結(jié)合，的優(yōu)先性，并服從左結(jié)合，上式就可以構(gòu)造出無二義性文法。上式就可以構(gòu)造出無二義性文法。文法文法GE: E T | ETT F | T+FF( E ) | i句子的推導(dǎo)過程唯一：如：句子的推導(dǎo)過程唯一：如：ii+i作業(yè)nP36689基本概

49、念n字母表字母表：元素的非空有窮集合。：元素的非空有窮集合。例：例：a, b, c,z （拉丁字母表）（拉丁字母表） , , , （希臘字母表）（希臘字母表） 0,1 （二進制數(shù)字字母表）（二進制數(shù)字字母表）n符號符號：字母表中的元素。如：字母表中的元素。如 a, b,基本概念n符號串符號串：字母表中的符號組成的任何有窮序列。：字母表中的符號組成的任何有窮序列。例例. 設(shè)字母表設(shè)字母表=a,b,c 其符號串有：其符號串有：a,b,c,ab,ac,aa,abc,符號串與符號組成的順序有關(guān)。符號串與符號組成的順序有關(guān)。n符號串的長度符號串的長度：符號串：符號串x中符號的數(shù)目中符號的數(shù)目, 用用|x

50、|表示表示n空符號串空符號串（空字）：不包含任何符號的符號串，（空字）：不包含任何符號的符號串， 記為記為。子符號串n設(shè)有非空符號串設(shè)有非空符號串u=xvy，則稱，則稱v為符號串為符號串u的的子符子符號串號串。例例. 符號串符號串x=a+b-(c+d) 則則 a, a+b- , (c+d)等都是等都是x的子符號串，的子符號串， 且其長度分別為：且其長度分別為：|a|=1, |a+b-|=4, |(c+d)|=5符號串的前綴與后綴n符號串的符號串的前綴前綴與與后綴后綴符號串左部的任意子串，稱為符號串的前綴；符號串左部的任意子串，稱為符號串的前綴；符號串右部的任意子串，稱為符號串的后綴。符號串右部

51、的任意子串，稱為符號串的后綴。例例. 字母表字母表A=a,b,c上的符號串上的符號串x=ab, 則則x的的前綴有：前綴有： 、a、ab；后綴有：后綴有： 、b、ab。基本概念n符號串集合符號串集合：若集合中所有元素都是某字母表：若集合中所有元素都是某字母表 上的符號串，則稱之為該字母表上的符號串集合。上的符號串，則稱之為該字母表上的符號串集合。用用 *表示表示 上的所有符號串的全體，空字也包括在其中。上的所有符號串的全體，空字也包括在其中。例例.若若 =a,b， 則則 *= ,a,b,aa,ab,bb,aaa,。 表示不含任何元素的表示不含任何元素的空集空集 n注意區(qū)分注意區(qū)分： 、（連接）積

52、n *的子集的子集U和和V中的（連接）中的（連接）積積定義為定義為: UV= U & V 即集合即集合UV中的符號串是由中的符號串是由U和和V的符號串連接而成的。的符號串連接而成的。例例. 設(shè)設(shè)U=a, b, V=， 則則UV= a, a, a, b, b, bn注意：一般注意：一般UV VU，但（，但（UV)W=U(VW).n次（連接）積nV自身的自身的n次次（連接）（連接）積積記為：記為：規(guī)定規(guī)定 V0 = .令：令： V* = V0 V1 V2 ，稱，稱 V*是是V的的閉包閉包。閉包閉包V*中的每個符號都是由中的每個符號都是由V中的符號串經(jīng)有限次連接中的符號串經(jīng)有限次連接而成的。而成的。記記V+ = VV*, 稱稱 V+是是V的的正則閉包正則閉包。 Vn = VVVV nChomsky文法體系分類n文法文法G=(VN, VT, S, )， ：P ，其中，其中 P(VNVT)* VN (VNVT)* ， (VNVT)*屬于屬于Chomsky文法體系文法體系n該體系對產(chǎn)生式的形式做了一些規(guī)定，分該體系對產(chǎn)生式的形式做了一些規(guī)定，分為四類，即為四類，即0型、型、1型、型、2型、型、3型文法型文法3型文法n也稱正規(guī)文法也稱正規(guī)文法右線性文法（右線性文法（Right-linear Grammar）：）： AB 或或 A，其中，其中 A、B VN, VT*。左