高級語言及其語法描述ppt課件

1、第二章第二章 高級言語及其語法描畫高級言語及其語法描畫 n常用的高級言語常用的高級言語n FORTRAN FORTRAN數(shù)值計算數(shù)值計算n COBOL COBOL事務(wù)處置事務(wù)處置n PASCAL PASCAL構(gòu)造程序設(shè)計構(gòu)造程序設(shè)計n ADA ADA大型程序、嵌入式實時系統(tǒng)大型程序、嵌入式實時系統(tǒng)n PROLOG PROLOG邏輯程序設(shè)計邏輯程序設(shè)計n ALGOL ALGOL算法言語算法言語n C C系統(tǒng)程序設(shè)計系統(tǒng)程序設(shè)計n Java JavaInternetInternet程序設(shè)計程序設(shè)計n與機器言語或匯編言語比較，高級言語與機器言語或匯編言語比較，高級言語的優(yōu)點：的優(yōu)點：n較接近于數(shù)學(xué)言

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

3、號的構(gòu)成規(guī)那么。詞法規(guī)那么：單詞符號的構(gòu)成規(guī)那么。n單詞符號是言語中具有獨立意義的最根本單詞符號是言語中具有獨立意義的最根本構(gòu)造。普通包括：常數(shù)、標(biāo)識符、根本字、構(gòu)造。普通包括：常數(shù)、標(biāo)識符、根本字、算符、界符等。算符、界符等。n描畫工具：有限自動機描畫工具：有限自動機n語法規(guī)那么：語法單位的構(gòu)成規(guī)那么。語法規(guī)那么：語法單位的構(gòu)成規(guī)那么。n語法單位通常包括：表達式、語句、分程語法單位通常包括：表達式、語句、分程序、過程、函數(shù)、程序等序、過程、函數(shù)、程序等; ;n描畫工具：上下文無關(guān)文法描畫工具：上下文無關(guān)文法n Ei EinEE+EEE+EnEEEE* *E EnE(E)E(E)n語法規(guī)那么和

4、詞法規(guī)那么定義了程序的語法規(guī)那么和詞法規(guī)那么定義了程序的的方式構(gòu)造。定義語法單位的意義屬于的方式構(gòu)造。定義語法單位的意義屬于語義問題。語義問題。二二. . 語義語義n語義：一組規(guī)那么，用它可以定義一個語義：一組規(guī)那么，用它可以定義一個程序的意義。程序的意義。n描畫方法：描畫方法：n自然言語描畫：隱藏錯誤、二義性和不自然言語描畫：隱藏錯誤、二義性和不完好性完好性n方式描畫：方式描畫：n 操作語義操作語義(PL/1)(PL/1)n 指稱語義指稱語義(ADA)(ADA)n 代數(shù)語義代數(shù)語義(PASCAL)(PASCAL)三程序文語的根本功能和層次構(gòu)造三程序文語的根本功能和層次構(gòu)造n程序文語的根本功能

5、：描畫數(shù)據(jù)和對數(shù)據(jù)程序文語的根本功能：描畫數(shù)據(jù)和對數(shù)據(jù)的運算。的運算。n所謂程序，本質(zhì)上說是描畫一定數(shù)據(jù)的處所謂程序，本質(zhì)上說是描畫一定數(shù)據(jù)的處置過程。置過程。程序的層次構(gòu)造程序的層次構(gòu)造程序程序| |子程序或分程序、過程、函數(shù)子程序或分程序、過程、函數(shù)| |語句語句| |表達式表達式| |數(shù)據(jù)援用數(shù)據(jù)援用 算符算符 函數(shù)調(diào)用函數(shù)調(diào)用程序文語每個組成成分的邏輯和實現(xiàn)意義程序文語每個組成成分的邏輯和實現(xiàn)意義 n籠統(tǒng)的邏輯的意義籠統(tǒng)的邏輯的意義n數(shù)學(xué)意義數(shù)學(xué)意義 n計算機實現(xiàn)的意義計算機實現(xiàn)的意義n詳細實現(xiàn)詳細實現(xiàn)2.2 2.2 高級言語的普通特性高級言語的普通特性 n高級言語的分類高級言語的分類

6、 n強迫式言語強迫式言語(Imperative Languge)也稱過程式也稱過程式言語：命令驅(qū)動，面向語句言語：命令驅(qū)動，面向語句nFORTRAN、C、Pascal，Ada n運用式言語運用式言語Applicative Language：注：注重程序所表示的功能，而不是一個語句接一個重程序所表示的功能，而不是一個語句接一個語句地執(zhí)行語句地執(zhí)行nLISP、ML 2.2 2.2 高級言語的普通特性高級言語的普通特性 2.2.1 2.2.1 高級言語的分類高級言語的分類 基于規(guī)那么的言語基于規(guī)那么的言語Rule-based LanguageRule-based Language：檢查一定的條件，當(dāng)

7、它滿足值，那么執(zhí)行適當(dāng)檢查一定的條件，當(dāng)它滿足值，那么執(zhí)行適當(dāng)?shù)膭幼鞯膭幼鱌rolog Prolog 面向?qū)ο笱哉Z面向?qū)ο笱哉ZObject-Oriented LanguageObject-Oriented Language：封裝性、承繼性和多態(tài)性封裝性、承繼性和多態(tài)性SmalltalkSmalltalk，C+C+，Java Java 2.2 2.2 高級言語的普通特性高級言語的普通特性2.2.2 2.2.2 程序構(gòu)造程序構(gòu)造 FORTRAN FORTRAN一個程序由一個主程序段和假設(shè)干輔程序一個程序由一個主程序段和假設(shè)干輔程序段組成。段組成。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。輔程序段可以是

8、子程序、函數(shù)段或數(shù)據(jù)塊。每個程序段有一系列的闡明語句和執(zhí)行語每個程序段有一系列的闡明語句和執(zhí)行語句組成。各段可以獨立編譯。句組成。各段可以獨立編譯。 模塊構(gòu)造，沒有嵌套和遞歸模塊構(gòu)造，沒有嵌套和遞歸各程序段中的名字相互獨立，同一個標(biāo)識各程序段中的名字相互獨立，同一個標(biāo)識符在不同的程序段中代表不同的名字。符在不同的程序段中代表不同的名字。主程序主程序 PROGRAM PROGRAM end end輔程序輔程序1 SUBROUTINE 1 SUBROUTINE end end輔程序輔程序2 FUNCTION 2 FUNCTION end endnPASCALnPASCAL程序本身可以看成是一個操作

9、程序本身可以看成是一個操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。歸。n一個一個PASCAL過程：過程：n過程頭；過程頭；n闡明段由一系列的闡明語句組成；闡明段由一系列的闡明語句組成；nbeginn執(zhí)行體由一系列的執(zhí)行語句組成；執(zhí)行體由一系列的執(zhí)行語句組成；nend作用域：一個名字能被運用的區(qū)域范圍作用域：一個名字能被運用的區(qū)域范圍稱作這個名字的作用域。稱作這個名字的作用域。允許同一個標(biāo)識符在不同的過程中代表允許同一個標(biāo)識符在不同的過程中代表不同的名字。不同的名字。名字作用域規(guī)那么名字作用域規(guī)那么-最近嵌套原那么最近嵌套原那么 一個在子程序一個在子程序B1B1中

10、闡明的名字中闡明的名字X X只在只在B1B1中有效部分于中有效部分于B1B1；假設(shè)假設(shè)B2B2是是B1B1的一個內(nèi)層子程序且的一個內(nèi)層子程序且B2B2中對中對標(biāo)識符標(biāo)識符X X沒有新的闡明，那么原來的名沒有新的闡明，那么原來的名字字X X在在B2B2中依然有效。假設(shè)中依然有效。假設(shè)B2B2對對X X重新作重新作了闡明，那么，了闡明，那么，B2B2對對X X的任何援用都是的任何援用都是指重新闡明過的這個指重新闡明過的這個X X。program main var A, B : real; procedure P1 var B:boolean; begin end procedure P2 var

11、A:integer; begin endbegin endA(real)B(real)B(bool)A(integr)PASCAL提供了豐富的數(shù)據(jù)類型和運算提供了豐富的數(shù)據(jù)類型和運算方式，它允許用戶動態(tài)地懇求和退還存方式，它允許用戶動態(tài)地懇求和退還存貯空間。貯空間。nADAn程序包程序包(package)：把數(shù)據(jù)和操作代碼封裝：把數(shù)據(jù)和操作代碼封裝在一同，支持?jǐn)?shù)據(jù)籠統(tǒng)。在一同，支持?jǐn)?shù)據(jù)籠統(tǒng)。n一個程序包分為兩部分：一個程序包分為兩部分：n可見的規(guī)范闡明部分，它定義了程序包外可見的規(guī)范闡明部分，它定義了程序包外面可以訪問的對象。面可以訪問的對象。n程序包體，它實踐定義程序包的實現(xiàn)細節(jié)。程序包體，

12、它實踐定義程序包的實現(xiàn)細節(jié)。package STACKS is type ELEM is private; type STACK is limited 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

13、 out STACK; E: out ELEM); begin 實現(xiàn)細節(jié)實現(xiàn)細節(jié) end pop;end; nJAVAnJava是一種面向?qū)ο蟮母呒壯哉Z是一種面向?qū)ο蟮母呒壯哉Zn類類Classn承繼承繼(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 (

14、 ) 2.2.3 2.2.3 數(shù)據(jù)類型與操作數(shù)據(jù)類型與操作 n一個數(shù)據(jù)類型通常包括以下三種要素：一個數(shù)據(jù)類型通常包括以下三種要素：n用于區(qū)別這種類型數(shù)據(jù)對象的屬性用于區(qū)別這種類型數(shù)據(jù)對象的屬性n這種類型的數(shù)據(jù)對象可以具有的值這種類型的數(shù)據(jù)對象可以具有的值n可以作用于這種類型的數(shù)據(jù)對象的操作可以作用于這種類型的數(shù)據(jù)對象的操作2.2.3 2.2.3 數(shù)據(jù)類型與操作數(shù)據(jù)類型與操作 一初等數(shù)據(jù)類型一初等數(shù)據(jù)類型數(shù)值類型：整型、實型、復(fù)數(shù)、雙精度，數(shù)值類型：整型、實型、復(fù)數(shù)、雙精度， 運算：運算：+ +，- -，* *，/ /等等邏輯類型：布爾運算：邏輯類型：布爾運算：，字符類型：符號處置字符類型：符號

15、處置指針類型指針類型標(biāo)識符與名字標(biāo)識符與名字n標(biāo)識符：以字母開頭的，由字母數(shù)字組成標(biāo)識符：以字母開頭的，由字母數(shù)字組成的字符串。的字符串。n標(biāo)識符與名字兩者有本質(zhì)區(qū)別：標(biāo)識符與名字兩者有本質(zhì)區(qū)別：n標(biāo)識符是語法概念標(biāo)識符是語法概念n名字有確切的意義和屬性名字有確切的意義和屬性Jordan ?標(biāo)識符！?標(biāo)識符與名字標(biāo)識符與名字n名字：名字：n值：單元中的內(nèi)容值：單元中的內(nèi)容n屬性：類型和作用域?qū)傩裕侯愋秃妥饔糜騨名字的性質(zhì)的闡明方式：名字的性質(zhì)的闡明方式：n由闡明語句來明確規(guī)定的由闡明語句來明確規(guī)定的n隱含闡明：隱含闡明：FORTRAN FORTRAN 以以I,J,K,NI,J,K,N為首的為首

16、的名字代表整型，否那么為實型。名字代表整型，否那么為實型。n動態(tài)確定：走到哪里，是什么，算什么動態(tài)確定：走到哪里，是什么，算什么 二二 數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造1 1 數(shù)組數(shù)組邏輯上，數(shù)組是由同一類型數(shù)據(jù)所組成的邏輯上，數(shù)組是由同一類型數(shù)據(jù)所組成的某種某種n n維矩形構(gòu)造，沿著每一維的間隔，維矩形構(gòu)造，沿著每一維的間隔，稱為下標(biāo)。稱為下標(biāo)。數(shù)組可變與不可變：編譯時能否確定其存數(shù)組可變與不可變：編譯時能否確定其存貯空間的大小。貯空間的大小。訪問：給出數(shù)組名和下標(biāo)值訪問：給出數(shù)組名和下標(biāo)值存放方式存放方式: : 按行存放按行存放, ,按列存放按列存放數(shù)組元素地址計算數(shù)組元素地址計算n數(shù)組數(shù)組A10,20A

17、10,20的的A1A1，11為為a a，各維下標(biāo)，各維下標(biāo)為為1 1，按行存放，那么，按行存放，那么AiAi，jj地址為：地址為：na+(i-1)a+(i-1)* *20+(j-1)20+(j-1)n數(shù)組元素地址計算公式數(shù)組元素地址計算公式設(shè) A為dddn12的 n維 數(shù) 組 ， 各 維 下 限均 為li， 各 維 上 限 均 為ui，duliii 1， 按 行 存 放 ， 則 數(shù) 組 元 素A iiin(,)11的地 址 D為 ： VARPARTCONSPARTididdiddiaDnnnnn)1()1()1()1(13221 其 中 ： nnnnnnnnnnnidiididiididdid

18、diVARPARTdddddCCaCONSPART)(11332211322132 內(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邏輯上說，記錄構(gòu)造由知類型的數(shù)據(jù)組合邏輯上說，記錄構(gòu)造由知類型的數(shù)據(jù)組合在一同的一種構(gòu)造。在一同的一種構(gòu)造。nrecord char NAME20; record cha

19、r NAME20; n integer AGE; integer AGE; n bool MARRIED;bool MARRIED;n CARD1000 CARD1000n訪問：復(fù)合名訪問：復(fù)合名 CARDk.NAME CARDk.NAMEn存儲：延續(xù)存放存儲：延續(xù)存放n域的地址計算：相對于記錄構(gòu)造起點的相域的地址計算：相對于記錄構(gòu)造起點的相對數(shù)對數(shù)OFFSETOFFSET。3 3 字符串、表格、棧字符串、表格、棧n字符串：符號處置、公式處置字符串：符號處置、公式處置n表格：本質(zhì)上是一種記錄構(gòu)造表格：本質(zhì)上是一種記錄構(gòu)造n線性表：一組順序化的記錄構(gòu)造線性表：一組順序化的記錄構(gòu)造n棧：一種線性表

20、，后進先出，棧：一種線性表，后進先出，POP, PUSHPOP, PUSH三三 籠統(tǒng)數(shù)據(jù)類型籠統(tǒng)數(shù)據(jù)類型 n一個籠統(tǒng)數(shù)據(jù)類型包括：一個籠統(tǒng)數(shù)據(jù)類型包括：n數(shù)據(jù)對象的一個集合；數(shù)據(jù)對象的一個集合；n作用于這些數(shù)據(jù)對象的籠統(tǒng)運算的集合；作用于這些數(shù)據(jù)對象的籠統(tǒng)運算的集合；n這種類型對象的封裝，即，除了運用類型中所這種類型對象的封裝，即，除了運用類型中所定義的運算外，用戶不能對這些對象進展操作。定義的運算外，用戶不能對這些對象進展操作。n程序設(shè)計言語對籠統(tǒng)數(shù)據(jù)類型的支持程序設(shè)計言語對籠統(tǒng)數(shù)據(jù)類型的支持nAda言語經(jīng)過程序包言語經(jīng)過程序包package提供了數(shù)據(jù)提供了數(shù)據(jù)封裝的支持封裝的支持nSmal

21、ltalk、C+和和Java言語那么經(jīng)過類言語那么經(jīng)過類Class對籠統(tǒng)數(shù)據(jù)類型提供支持。對籠統(tǒng)數(shù)據(jù)類型提供支持。 2.2.4 2.2.4 語句與控制構(gòu)造語句與控制構(gòu)造一表達式一表達式表達式由運算量也稱操作數(shù)，即數(shù)據(jù)援用表達式由運算量也稱操作數(shù)，即數(shù)據(jù)援用或函數(shù)調(diào)用和算符操作符組成?；蚝瘮?shù)調(diào)用和算符操作符組成。方式：中綴、前綴、后綴方式：中綴、前綴、后綴 X X* *Y -A PY -A P表達式構(gòu)成規(guī)那么表達式構(gòu)成規(guī)那么算符的優(yōu)先次序算符的優(yōu)先次序n普通的規(guī)定普通的規(guī)定nPASCALPASCAL：左結(jié)合：左結(jié)合A+B+C=(A+B)+CA+B+C=(A+B)+CnFORTRANFORTRAN

22、：對于滿足左、右結(jié)合的算符可：對于滿足左、右結(jié)合的算符可任取一種，如任取一種，如A+B+CA+B+C就可以處置成就可以處置成(A+B)+C(A+B)+C，也可以處置成，也可以處置成A+(B+C)A+(B+C)。n留意兩點：留意兩點：n代數(shù)性質(zhì)能援用到什么程度視詳細的言代數(shù)性質(zhì)能援用到什么程度視詳細的言語不同而不同；語不同而不同；n在數(shù)學(xué)上成立的代數(shù)性質(zhì)在計算機上未在數(shù)學(xué)上成立的代數(shù)性質(zhì)在計算機上未必完全成立。必完全成立。二語句二語句n賦值語句：賦值語句：n A := B A := B n名字左值：該名字代表的那個單元地址名字左值：該名字代表的那個單元地址稱為該名字的左值。稱為該名字的左值。(

23、(所代表的存貯單元的所代表的存貯單元的地址地址) )n右值：一個名字的值稱為該名字的右值。右值：一個名字的值稱為該名字的右值。( (所代表的存貯單元的內(nèi)容所代表的存貯單元的內(nèi)容) )n控制語句：控制語句： l無條件轉(zhuǎn)移語句無條件轉(zhuǎn)移語句 l goto Ll條件語句條件語句 l if B then S l if B then S1 else S2l循環(huán)語句循環(huán)語句 l while B do Sl repeat S until Bl for i:=E1 step E2 until E3 do Sl過程調(diào)用語句過程調(diào)用語句l call P(X1, X2, . ,Xn)l前往語句前往語句 l retu

24、rn (E) return (E)n闡明語句：定義各種不同數(shù)據(jù)類型的變量闡明語句：定義各種不同數(shù)據(jù)類型的變量或運算，定義名字的性質(zhì)?；蜻\算，定義名字的性質(zhì)。簡單句和復(fù)合句簡單句和復(fù)合句n簡單句：不包含其他語句成分的根本句簡單句：不包含其他語句成分的根本句n復(fù)合句：句中有句的語句復(fù)合句：句中有句的語句2.3 2.3 程序文語的語法描畫程序文語的語法描畫 n幾個概念幾個概念: :n思索一個有窮思索一個有窮 字母表字母表 字符集字符集n其中每一個元素稱為一個字符其中每一個元素稱為一個字符n上的字上的字( (也叫字符串也叫字符串) ) 是指由是指由中的字中的字符所構(gòu)成的一個有窮序列符所構(gòu)成的一個有窮序

25、列n不包含任何字符的序列稱為空字，記為不包含任何字符的序列稱為空字，記為n用用* *表示表示上的一切字的全體上的一切字的全體, ,包含空字包含空字n例如例如: : 設(shè)設(shè) =a =a， b b，那么，那么 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.n*的子集的子集U和和V的銜接積定義為的銜接積定義為nUV | U & V nV本身的本身的 n次積記為次積記為nVn=VVVn規(guī)定規(guī)定V0=，令，令n V*=V0V1V2V3 n稱稱V*是是V的閉包的閉包;n記記 VVV* ，稱，稱V+是是V的正規(guī)閉包。的正規(guī)閉包。2.3.1 2.3.1

26、 上下文無關(guān)文法上下文無關(guān)文法n文法：文法： 描畫言語的語法構(gòu)造的方式規(guī)那么描畫言語的語法構(gòu)造的方式規(guī)那么nHe gave me a book.He gave me a book.n n n n n n He Hen me men book bookn a an 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)文法的定義： n一個上下文無關(guān)文法一個上下文無關(guān)文法G G是一個四元式是一個四元式n G=(VT

27、G=(VT，VNVN，S S，P)P)，其中，其中nVTVT：終結(jié)符集合：終結(jié)符集合( (非空非空) )nVNVN：非終結(jié)符集合：非終結(jié)符集合( (非空非空) )，且，且VT VT VN=VN=nS S：文法的開場符號，：文法的開場符號，S SVNVNnP P：產(chǎn)生式集合：產(chǎn)生式集合( (有限有限) )，每個產(chǎn)生式方式，每個產(chǎn)生式方式為為nP P， P PVNVN， (VT (VT VN) VN)* *n開場符開場符S S至少必需在某個產(chǎn)生式的左部出至少必需在某個產(chǎn)生式的左部出現(xiàn)一次?，F(xiàn)一次。n例，定義只含例，定義只含+，*的算術(shù)表達式的文法的算術(shù)表達式的文法n G=， 其中，其中，P由以下產(chǎn)

28、生式組成：由以下產(chǎn)生式組成：nE inE E+EnE E*EnE (E)n幾點規(guī)定：幾點規(guī)定：n“ 也可以用也可以用“:=表示，表示， 這種表示稱為這種表示稱為巴科斯范式巴科斯范式(BNF)n P 1 nP 2 可縮寫為可縮寫為 P 1|2|n n nP nn 其中，其中，“|讀成讀成“或，稱為或，稱為P的一個候選式。的一個候選式。n表示一個文法時，通常只給出開場符號和產(chǎn)表示一個文法時，通常只給出開場符號和產(chǎn)生式，如上例，可表示為：生式，如上例，可表示為：nG(E)： E i | E+E | E*E | (E)n定義：稱定義：稱A直接推出直接推出，即，即nAn 僅當(dāng)僅當(dāng)A 是一個產(chǎn)生式，是一個

29、產(chǎn)生式，n 且且， (VT VN)* 。n假設(shè)假設(shè)1 2 n，那么我們稱，那么我們稱這個序列是從這個序列是從1到到n的一個推導(dǎo)。假設(shè)的一個推導(dǎo)。假設(shè)存在一個從存在一個從1到到n的推導(dǎo)，那么稱的推導(dǎo)，那么稱1可以推導(dǎo)出可以推導(dǎo)出n 。n例：對文法例：對文法(1)nE (E) (E+E) (i+E) (i+i)n通常，用通常，用 表示：從表示：從1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過一步或假設(shè)干步，可以推出一步或假設(shè)干步，可以推出n n。n1n*1 用用 表示：從表示：從1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過0 0步步或假設(shè)干步，可以推出或假設(shè)干步，可以推出n n。* 所以所以 ： 即即 或或*S ,|)(*TV SGL

30、q定義：假定定義：假定G G是一個文法，是一個文法，S S 是它的開場符號。是它的開場符號。假設(shè)假設(shè) ，那么，那么稱是一個句型。僅含終稱是一個句型。僅含終結(jié)符號的句型是一個句子。文法結(jié)符號的句型是一個句子。文法G G所產(chǎn)生的句子所產(chǎn)生的句子的全體是一個言語，將它記為的全體是一個言語，將它記為 L(G)L(G)。n例：例： (i*i+i)是文法是文法(1)的一個句子。的一個句子。n E (E) (E+E) (E*E+E) (i*E+E) n (i*i+E) (i*i+i)n E，(E)，(E*E+E)，(i*i+i)是句型。是句型。n例：文法例：文法G1(S)：nS ABnA aA|anB bB

31、|bnG1(S)的言語的言語?nL(G1)=ambn|m，n0q例：文法例：文法G2(A)：qA c|AbqG2(A)的言語的言語?qL(G2)=c，cb，cbb，q以以c開頭，后繼假設(shè)干個開頭，后繼假設(shè)干個bq例：給出產(chǎn)生言語為例：給出產(chǎn)生言語為anbn|n1的文法的文法。q G3(S)：q S aSbq S abq例：給出產(chǎn)生言語為例：給出產(chǎn)生言語為ambn|1nm2n的文法。的文法。q G4(S)：q S aSb | aaSbq S ab | aab n從一個句型到另一個句型的推導(dǎo)往往不獨從一個句型到另一個句型的推導(dǎo)往往不獨一。一。n E+Ei+Ei+i E+EE+ii+in最左推導(dǎo)：任

32、何一步最左推導(dǎo)：任何一步 都是對都是對中中的最左非終結(jié)符進展交換。的最左非終結(jié)符進展交換。n 最右推導(dǎo)：任何一步最右推導(dǎo)：任何一步 都是對都是對中中的最右非終結(jié)符進展交換。的最右非終結(jié)符進展交換。2.3.2 2.3.2 語法樹與二義性語法樹與二義性n用一張圖表示一個句型的推導(dǎo)用一張圖表示一個句型的推導(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(E*i+i)i+i)(i*i+i) 一棵語法樹是不同推導(dǎo)過程的共性籠

33、統(tǒng)。一棵語法樹是不同推導(dǎo)過程的共性籠統(tǒng)。n假設(shè)運用最左假設(shè)運用最左( (右右) )推導(dǎo)，那么一個最左推導(dǎo)，那么一個最左( (右右) )推導(dǎo)與語法樹一一對應(yīng)。推導(dǎo)與語法樹一一對應(yīng)。n一個句型能否只對應(yīng)獨一一棵語法樹？一個句型能否只對應(yīng)獨一一棵語法樹？Ei+*()EiiEEEEE+*()EiEEiiEEn定義：假設(shè)一個文法存在某個句子對應(yīng)兩定義：假設(shè)一個文法存在某個句子對應(yīng)兩顆不同的語法樹，那么說這個文法是二義顆不同的語法樹，那么說這個文法是二義的。的。nG(E)： E i|E+E|E*E|(E) 是二義文法。是二義文法。n言語的二義性：一個言語是二義性的，假言語的二義性：一個言語是二義性的，假設(shè)

34、對它不存在無二義性的文法。設(shè)對它不存在無二義性的文法。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) (i*i+T) (i*i+F) (i*i+i)思索句子思索句子(i*i+i)n描畫程序設(shè)計