簡介：面向?qū)ο蟪绦蛟O(shè)計,、,第二章面向?qū)ο蟮姆治雠c設(shè)計,學習目標,1確定系統(tǒng)中的對象2確定對象的屬性及操作3測試對象的有效性4區(qū)分對象和類5了解面向?qū)ο蟮木幊毯瓦^程化編程之間的區(qū)別6了解封裝的主要好處7了解軟件開發(fā)的主要步驟,我們可以把生活所在的真實世界（REALWORLD）當作是由許多大小不同的對象所組成的。對象可以是有生命的個體，比如一個人或一只鳥。,,對象,對象,對象也可以是無生命的個體，比如一輛汽車或一臺計算機。對象也可以是一個抽象的概念，如天氣的變化或鼠標所產(chǎn)生的事件。,,,對象的基本概念,客觀世界的組成對象；對象之間的相互關(guān)系；對象對象是系統(tǒng)中用來描述客觀事物的一個實體，它是構(gòu)成系統(tǒng)的一個基本單位。一個對象由一組屬性和操作組成。動態(tài)觀點對象的操作就是對象的行為,對象的特征,對象有兩個特征屬性和行為如一個人有他的身高或體重作屬性，有他的行為如唱歌、打球、騎摩托車、開汽車。一條狗有它的顏色作屬性，有它的行為，如搖尾巴或跳躍。一臺電視機有它的外形、尺寸和顏色，有它的行為，如開、關(guān)，接收信號，轉(zhuǎn)換頻道，調(diào)節(jié)音量。,,,汽車對象,以汽車為例，我們可定義其屬性與方法如,課程中通過下面的案例來學習面向?qū)ο蟮姆治雠c設(shè)計原理。,案例研究,公司名稱DIRECTCLOTHING公司業(yè)務包括1、按月生成產(chǎn)品目錄2、客戶通過電話、網(wǎng)絡和傳真訂購3、隨時檢查訂購項的庫存情況4、公司接受支票和信用卡付款,定義系統(tǒng)的對象1、對象屬性對象的特征2、對象操作所能執(zhí)行的任務,面向?qū)ο蟾攀?找出問題描述領(lǐng)域中的主要名詞對象可能是簡單的或復雜的（襯衣，銀行）真實的或概念的（銀行出納員，帳戶）對象有屬性顏色，尺寸操作（下訂單，取消訂單）,第一步確定對象,對象找到了,屬性是對象的狀態(tài)特征可以是數(shù)據(jù)或其它對象對ORDER對象來說，可能包括ORDERID和ITEMS操作是對象執(zhí)行的動作可以是對象做出的或施加給對象的動作對ORDER對象來說，可能是PLACE和CANCEL,第二步確定對象屬性和操作,第三步對象建模,屬性類型,與問題域的相關(guān)性對象是否在問題陳述的界限之內(nèi)系統(tǒng)是否必須有此對象才能完成任務在用戶與系統(tǒng)的交互中是否必須有此對象獨立存在性屬性和操作,第四步測試對象,面向?qū)ο蠓治鲂〗Y(jié),找出問題域中的對象，及其屬性和操作步驟1、列出有關(guān)的對象（名詞）2、列出這些對象的屬性和操作3、為對象設(shè)置合理的屬性和操作4、應用第四步的3條評判規(guī)則檢驗對象的有效性,練習,ANOBJECTORIENTEDDESIGNFORAJAVAAPPLICATIONTHATTRACKSSOCCERSCORESTHEPROGRAMSHOULDTRACKTHENUMBEROFGOALSEACHPLAYERSCORESINEACHGAMEWHATTEAMSTHEPLAYERSPLAYFORANDWHATSEASONTHEGAMESWEREPLAYIN,什么是類是同種對象的集合與抽象,,類（CLASS）,類與對象關(guān)系,面向?qū)ο蟪绦蛟O(shè)計的重點是類的設(shè)計，而不是對象的設(shè)計。,,類與對象的關(guān)系類?對象抽象定義實例電視機?一臺長虹電視機學生?軟件學院05級學生小強,實例對象（INSTANCE）,汽車類有些共同的屬性（汽缸排氣量，排檔數(shù)，顏色，輪胎數(shù)）和行為（換檔，開燈，開冷氣），但每一臺汽車個別的狀態(tài)及方法可不同于且獨立于其他汽車。你的汽車只是這世界中許多汽車中的一個。我們就稱你的汽車是汽車類中的一個實例對象（INSTANCE）。,,面向?qū)ο笈c面向過程,公共數(shù)據(jù),算法＋數(shù)據(jù)結(jié)構(gòu),,,對象＋消息,比較,結(jié)構(gòu)化程序設(shè)計對應的典型的計算機語言,例如C面向操作的函數(shù)方法是程序的基本單位面向?qū)ο蟪绦蛟O(shè)計對應的典型的計算機語言,例如JAVA面向?qū)ο驩BJECT的類CLASS是程序的基本單位方法函數(shù)被封裝在類中數(shù)據(jù)也常常被封裝在類中,,示例過程化和面向?qū)ο髢煞N方法的比較,幾個編程小組在設(shè)計一個進銷存系統(tǒng)其中，一個小組編寫處理貨物和庫存的程序，一個小組編寫處理訂單的程序,面向過程,面向?qū)ο?,OO的真正意義,OO的真正意義是使得軟件開發(fā)接近人類的正常思維，將許多原來由人完成的工作交給機器去完成機器語言匯編語言高級語言面向過程面向模塊面向?qū)ο驩O包括一套比較完整的方法，程序設(shè)計只是其中一個環(huán)節(jié)。面向?qū)ο蟮姆治雒嫦驅(qū)ο蟮脑O(shè)計面向?qū)ο蟮某绦蛟O(shè)計代碼重用,,,,,小結(jié),JAVA程序是由一個個類定義組成的編寫JAVA程序的過程是從現(xiàn)實世界中抽象出JAVA可實現(xiàn)的類，并用合適的語句定義它的過程這個定義過程包括1、對類中各種屬性和方法的定義2、創(chuàng)建類的對象3、類間的各種關(guān)系和接口的定義,什么是面向?qū)ο竺嫦驅(qū)ο笫且环N程序設(shè)計規(guī)范,其基本思想是使用對象、類、繼承、封裝、多態(tài)等基本概念來進行程序設(shè)計。,OOP三大特性封裝、繼承與多態(tài),封裝（ENCAPSULATION）封裝是一種信息隱藏技術(shù)。是指將數(shù)據(jù)和基于數(shù)據(jù)的操作封裝在一起，數(shù)據(jù)被保護在內(nèi)部，系統(tǒng)的其他部分只有通過在數(shù)據(jù)外面的被授權(quán)的操作才能夠進行交互，目的在于將類使用者CLASSUSER和類設(shè)計者CLASSCREATOR分開。在面向?qū)ο蟮木幊讨?，用類來封裝相關(guān)的數(shù)據(jù)和方法，保證了數(shù)據(jù)的安全和系統(tǒng)的嚴密性。,,,,,,,,,倉庫,,,,屬性,操作,價格表,物品,賬單，電話,等等,提供物品，賬單等等,考慮一個倉庫，外部只能通過管理員獲取物品。,,抽象,封裝的優(yōu)點隱藏類的實現(xiàn)細節(jié),實現(xiàn)了信息的隱藏及安全性；提高了程序的模塊化，且易于維護；具體實現(xiàn)是編寫該類的人控制的,讓使用者只能通過事先定制好的方法來訪問數(shù)據(jù)，可以方便地加入控制邏輯，限制對屬性的不合理操作,封裝的汽車實現(xiàn)細節(jié)隱藏在車蓋下；駕駛員不必知道汽車是怎樣工作的汽車的部分零件改變或更換，駕駛員不必改變對汽車的駕駛,,交通工具,JAVA僅支持單繼承,優(yōu)點使程序結(jié)構(gòu)清晰，減少了編碼和維護的工作量，子類可以使用父類所提供的方法，實現(xiàn)了代碼的復用。,CLASSTHISCLASSEXTENDSSUPERCLASS{}現(xiàn)以下圖來說明,繼承,繼承,,,多態(tài)用同一個名字調(diào)用實現(xiàn)不同操作的方法方式1父類和子類之間的同名方法（覆蓋子類方法的名稱和參數(shù)與父類方法的名稱和參數(shù)相同，在執(zhí)行過程中，子類的方法將覆蓋父類的方法）方式2同一類中參數(shù)不同的同名方法（重載不是子類對父類同名方法的重新定義，而是類對自身已有的同名方法的重新定義。重載方法的參數(shù)必須不同，或者是參數(shù)個數(shù)不同，或者是參數(shù)類型不同）使用方便，且降低了維護和編程量,覆蓋CLASSA{PUBLICINTX,YAINTA,INTB{XAYB}PUBLICVOIDDISPLAY{INTZZXYSYSTEMOUTPRINTLN“ADD”Z}}CLASSBEXTENDSA{BINTA,INTB{SUPERA,B}PUBLICVOIDDISPLAY{INTZZXYSYSTEMOUTPRINTLN“PRODUCT”Z}},CLASSABEXTENDSB{ABINTX,INTY{SUPERX,Y}PUBLICSTATICVOIDMAINSTRINGARGS{ANUM1NEWA4,10BNUM2NEWB4,10ABNUM3NEWAB4,10NUM1DISPLAYNUM2DISPLAYNUM3DISPLAY}},重載CLASSMETHODOVERLOADING{VOIDRECEIVEINTI{SYSTEMOUTPRINTLN“一個整數(shù)”SYSTEMOUTPRINTLN“I”I}VOIDRECEIVEINTX,INTY{SYSTEMOUTPRINTLN“兩個整數(shù)”SYSTEMOUTPRINTLN“X”X”Y”Y}VOIDRECEIVEDOUBLED{SYSTEMOUTPRINTLN“一個浮點數(shù)”SYSTEMOUTPRINTLN“D”D}VOIDRECEIVESTRINGS{SYSTEMOUTPRINTLN“一個字符串”SYSTEMOUTPRINTLN“S”S}},PUBLICCLASSMETHODOVERLOADINGTEST{PUBLICSTATICVOIDMAINSTRINGARGS{METHODOVERLOADINGMONEWMETHODOVERLOADINGMORECEIVE1MORECEIVE2,3MORECEIVE1256MORECEIVE“HELLO”}},面向?qū)ο蟮娜筇卣?1封裝將數(shù)據(jù)成員（DATAMEMBER）和屬于此數(shù)據(jù)的操作方法（OPERATINGMETHOD），放在同一個實體中。2繼承父類定義一些通用的屬性與行為，其子類可以使用。3多態(tài)在同一個類中可有許多同名的方法，但其參數(shù)個數(shù)與參數(shù)類型不同，而且操作過程與返回值也可能會不同。,（1）模塊化（2）信息隱藏,（1）實現(xiàn)代碼復用（2）簡化設(shè)計過程,解決其他語言中不能重名的問題,以前編寫的操作可以在其他工程中再次使用，可提高開發(fā)效率，縮短開發(fā)周期,復用,,面向?qū)ο筌浖_發(fā)過程（軟件生命周期）,1、搜集和分析要求2、設(shè)計系統(tǒng)3、為系統(tǒng)編寫代碼4、測試系統(tǒng)的所有方面5、讓客戶和用戶測試系統(tǒng)6、維護系統(tǒng),
下載積分： 6 賞幣
上傳時間：2024-01-06
頁數(shù)： 49
大?。?2.87(MB)
子文件數(shù)：
簡介：第二章高級語言及其語法描述,第二章高級語言及其語法描述,本章概述高級語言的結(jié)構(gòu)和主要的共同特征，并介紹程序語言的語法描述方法。要學習和構(gòu)造編譯程序，理解和定義高級語言是必不可少的。21程序語言的定義任何語言實現(xiàn)的基礎(chǔ)是語言的定義。在定義方面，編譯程序研制者與一般用戶有所不同，他們對那些構(gòu)造允許出現(xiàn)更感興趣。即使一時不能看出某種構(gòu)造的實際應用，或者判斷實現(xiàn)該結(jié)構(gòu)會導致嚴重的困難，但仍必須嚴格根據(jù)語言的定義實現(xiàn)它。程序語言主要由語法和語義兩方面定義。,第二章高級語言及其語法描述,,211語法任何語言程序都可以看成是一定字符集（稱為字母表）上的字符串（有限序列）。但是什么樣的字符串才算是一個合適的程序呢所謂一個語言的語法是指這樣的一組規(guī)則，用它可以形成和產(chǎn)生一個合適的程序。這些規(guī)則一部分稱為詞法規(guī)則，另一部分能稱為語法規(guī)則（或產(chǎn)生規(guī)則）。,第二章高級語言及其語法描述,,注意這里提到三個概念A一個程序只是用一個有限字符集作為字母表；B詞法規(guī)則是指單詞符號的形成規(guī)則。單詞符號一般包括各類型的常數(shù)、標識符、基本字、算符和界符等。C語言的語法規(guī)則規(guī)定了如何從單詞符號形成更大的結(jié)構(gòu)（即語法單位），換言之，語法規(guī)則是語法單位的形成規(guī)則。一般程序語言的語法單位有表達式、語句、分程序、函數(shù)、過程和程序等。,第二章高級語言及其語法描述,,212語義對于一個語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義。這就是語義問題。語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意義。我們采用的方法為基于屬性文法的語法制導翻譯方法。,第二章高級語言及其語法描述,,一個程序語言的基本功能是描述數(shù)據(jù)和對數(shù)據(jù)的運算。所謂程序，從本質(zhì)上來說是描述一定數(shù)據(jù)的處理過程。在現(xiàn)今的程序語言中，一個程序大體可以視為下面所示的層次結(jié)構(gòu),,,,,程序,,子程序,或,分程序,,語句,,表達式,,數(shù)據(jù)引用,算符,函數(shù)調(diào)用,,,,,第二章高級語言及其語法描述,,自上而下看上述層次結(jié)構(gòu)頂端是程序本身，他是一個完整的執(zhí)行單位。一個程序通常是由若干個子程序或分程序組成的，他們常常含有自己的數(shù)據(jù)（局部名）。子程序或分程序是由于語句組成的。而組成語句的成分是個種類型的表達式。表達式是描述數(shù)據(jù)運算的基本結(jié)構(gòu)，它通常含有數(shù)據(jù)引用、算符和函數(shù)調(diào)用。,第二章高級語言及其語法描述,,自下而上看上述層次結(jié)構(gòu)我們希望通過對下層成分的了解掌握上層成分，從而掌握整個程序。在學習編譯原理的過程中特別注意程序語言的每個組成成分都有（抽象的）邏輯和計算機實現(xiàn)兩方面的意義。當從數(shù)學上考慮每一個組成成分時，我們注重它的邏輯意義，當從計算機這個角度來看時，我們注重他在機內(nèi)的表示和實現(xiàn)的可能性與效率。,第二章高級語言及其語法描述,,22高級語言的一般特性221高級語言的分類；A強制式語言過程式語言（命令驅(qū)動、面向語句，如PASCALC等）B應用式語言函數(shù)式語言（如LISP）C基于規(guī)則的語言邏輯型設(shè)計語言（如PROLOG）D面向?qū)ο笳Z言支持封裝、多態(tài)、繼承222幾種程序的典型結(jié)構(gòu)；,第二章高級語言及其語法描述,,FORTRANMAINENDSUBROUTINESUB1ENDSUBROUTINESUBNEND,一FORTRAN一個FORTRAN程序有一個主程序段和若干個（可以是0個）輔助程序段組成。如右側(cè)）,第二章高級語言及其語法描述,,輔助程序段可以是子程序、函數(shù)段或數(shù)據(jù)。每程序段由一系列說明語句和執(zhí)行語句組成。各程序段可以獨立編輯。這對模塊設(shè)計甚為方便。一個FORTRAN程序個程序段所定義的各種名字通常是彼此獨立的。同一個標識符在不同的程序段中一般都可以代表不同的名字，即代表不同的存儲單元，個程序段對它們的引用或賦值是彼此無關(guān)的。但是，不同程序段里的同名公用塊（COMMONBLOCK卻代表同一個存儲區(qū)域。因此，出現(xiàn)在COMMON語句中的名字所代表的單元在其他程序塊中也可以引用。所以說，公用區(qū)具有全局性。不出現(xiàn)在COMMON中的名字所代表的單元具有局部性。,第二章高級語言及其語法描述,,二PASCALPASCAL是一個允許子程序嵌套定義的語言。一個PASCAL程序可以看作是操作系統(tǒng)調(diào)用的一個子程序，而子程序中又可以定義別的子程序。,PROGRAMMAINPROCEDUREP1PROCEDUREP11BEGINENDBEGINENDPROCEDUREP2BEGINENDBEGINEND,第二章高級語言及其語法描述,,PASCAL這種嵌套結(jié)構(gòu)中允許同一標識符在不同的子程序段中表示不同的名字。關(guān)于名字的作用域的規(guī)定是A一個在子程序B1中說明的名字X只在B1中有效（局部于B1）。B如果B2是B1的一個內(nèi)層子程序，且B2中對標識符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對X重新作了說明，那么，B2中對X的任何引用都是指重新說明過的這個X。,第二章高級語言及其語法描述,,223數(shù)據(jù)類型與操作；一個數(shù)據(jù)類型通常包括以下三種要素A用于區(qū)別這種類型的數(shù)據(jù)對象的屬性B這種類型的數(shù)據(jù)對象可以具有的值C可以作用于這種類型數(shù)據(jù)對象的操作一、初等數(shù)據(jù)類型常見的初等數(shù)據(jù)類型有A數(shù)值數(shù)據(jù)B邏輯數(shù)據(jù)C字符數(shù)據(jù)D指針類型,第二章高級語言及其語法描述,,指針是指這樣一種類型的數(shù)據(jù)，他們的值指向另一些數(shù)據(jù)。一般意義是，假定P是一個指針，PADDRX意味著P將指向X，或說P的值將是變量X的地址。有些語言用P↑表示指針P的內(nèi)容。在PADDRX的情況下，如令P↑03，則意味著X的值是03,第二章高級語言及其語法描述,,用計算機術(shù)語來說，名字可以看成是代表一個抽象的存儲單元，這個單元可包含一位、一字節(jié)、一字或相繼的許多個字。而這個單元的內(nèi)容則認為是此名字的值。名字的值就是它所表示的對象。此外，我們還必須指出名字的屬性。一個名字的屬性包括類型和作用域。名字的類型決定了它能具有什么樣的值，值在計算機內(nèi)的表示方式，以及對他能施加什么運算。名字的作用域規(guī)定了他的值存在范圍。,第二章高級語言及其語法描述,,二、數(shù)據(jù)結(jié)構(gòu)許多程序語言提供了一種由初級數(shù)據(jù)定義復雜數(shù)據(jù)的手段。下面我們將概述其中常見的定義方式A數(shù)組從邏輯上說，一個數(shù)組是由同一類型數(shù)據(jù)所組成的某種N維矩形結(jié)構(gòu)。沿著每一維的距離稱為一個下標。數(shù)組的每個元素是矩形結(jié)構(gòu)中的一個點，它的位置可通過給出每維的下標來確定。,第二章高級語言及其語法描述,,數(shù)組的每個元素（也稱為下標變量）是由數(shù)組名連同各維的下標值命名的。如A（I1,I2,IN）。根據(jù)數(shù)組的類型，每個數(shù)組元素在計算機中占有同樣大小的存儲空間。如果一個數(shù)組所需的存儲空間大小在編譯時就已知道則稱此數(shù)組是一個確定數(shù)組；否則稱為可變數(shù)組。,第二章高級語言及其語法描述,,數(shù)組的存儲表示有多種形式，最簡單的一種是把整個數(shù)組按行（或按列）存放在一片連續(xù)存儲區(qū)中。數(shù)組元素的地址計算和數(shù)組的存儲方式密切相關(guān)。關(guān)于數(shù)組元素的地址計算公式，數(shù)據(jù)結(jié)構(gòu)教材中有詳細的介紹。編譯程序要做的就是實現(xiàn)地址計算公式，使數(shù)組元素得到正確的引用。在編譯過程中，當碰到數(shù)組說明時，必須把數(shù)組的有關(guān)的信息記錄在一個“內(nèi)情向量”之中，以便以后計算數(shù)組元素的地址時引用這些信息。每個數(shù)組的內(nèi)情向量必須包括維數(shù)，各維的上下限，首地址，以及數(shù)組元素的類型等。,第二章高級語言及其語法描述,,B記錄從邏輯上說，記錄結(jié)構(gòu)是由已知類型的數(shù)據(jù)組合起來的一種結(jié)構(gòu)。記錄結(jié)構(gòu)是許多程序語言的一類重要的數(shù)據(jù)結(jié)構(gòu)。不同語言定義記錄結(jié)構(gòu)的方式也不同。如PASCAL語言采用下面形式定義記錄CARDRECORDNAMEARRAY120OFCHARAGEINTEGERMARRIEDBOOLEANEND,第二章高級語言及其語法描述,,這說明定義了一個記錄CARD它是一個含有三個分量的記錄結(jié)構(gòu)NAME,字符數(shù)組；AGE,整型量；MARRIED,布爾量。記錄結(jié)構(gòu)的每個分量（域）所需占用的存儲單元（字節(jié)）數(shù)，成為該域的長度。當知道一個記錄的地址后，通過每個域的長度就可算出個域的地址，因為我們?nèi)菀淄瞥雒總€域相對于記錄結(jié)構(gòu)起點的相對數(shù)OFFSET此域之前各域長度的總和。,第二章高級語言及其語法描述,,如就CARD而言，NAME,AGE,MARRIED的相對數(shù)OFFSET分別為0、20、24。于是，假定CARD的首地址為A，那么，CARDNAME地址為ACARDAGE地址為A20CARDMARRIED地址為A24,第二章高級語言及其語法描述,,224語句與控制結(jié)構(gòu)一、表達式一個表達式是由運算量（亦稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。對于大多數(shù)程序語言來說，表達式的形成規(guī)則可概括為（1）變量（包括下標變量）、常數(shù)是表達式；（2）若E1、E2為表達式，Θ為二元算符，則E1ΘE2為表達式；（3）若E為表達式，Θ為一元算符，則ΘE為表達式；（4）若E為表達式，則（E是表達式。,第二章高級語言及其語法描述,,在多數(shù)語言中算術(shù)算符和邏輯算符的優(yōu)先順序一般規(guī)定如下乘冪（或↑）一元負（）乘、除（，/，÷）加、減（，）關(guān)系符（,,非（﹁，NOT,或NOT與（∧，S→ASB|AB,第二章高級語言及其語法描述,,為了對句子結(jié)構(gòu)進行確定性分析，我們往往只考慮最左推導或最右推導。所謂最左推導是指任何一步???都是對?中的最左非終結(jié)符進行替換的。同樣，可定義最右推導。,第二章高級語言及其語法描述,,232語法分析樹與二義性前面我們提到過可以用一張圖表示一個句型的推導，這種表示稱為語法分析樹，或簡稱語法樹。語法樹的根結(jié)由開始符號所標記。隨著推導的展開，當某個非終結(jié)符被它的某個候選式所替換時，這個非終結(jié)符的相應結(jié)就產(chǎn)生了下一代新結(jié)。每個新結(jié)和其父親結(jié)間都有一條連線。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的端末結(jié)自左至右排列起來就是一個句型。,第二章高級語言及其語法描述,例如對于文法（21關(guān)于（III的推導形成語法樹如圖22,,,,圖22語法樹,第二章高級語言及其語法描述,,一個句型是否只對應唯一的一棵語法樹呢也就是說它是否只有唯一的一個最左（最右推導呢不盡然。如文法21,關(guān)于（III就存在一個與22非常不同的推導E??E?EE?IE?IEE?IIE?III其對應語法樹,,第二章高級語言及其語法描述,,圖22與圖23的不同之處在于從第二代三代過渡開始。對于前者，我們選用規(guī)則E→EE,而后者我們選用E→EE。這里不是同代兄弟生兒子的先后次序的不同而是生什么兒子的不同，后面的這個不同是本質(zhì)上的的差異。這意味著我們可以用兩種完全不同的辦法產(chǎn)生同一個句子。,第二章高級語言及其語法描述,,如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。也就是說，若一個文法存在某個句子，它有兩個不同的最左（最右推導，則這個文法是法是二義的。最后，作為描述程序語言的上下文無關(guān)文法，我們對它有幾點限制。（1）文法中不含任何下面形式的產(chǎn)生式P→P因為這種產(chǎn)生式除了產(chǎn)生二義性外沒有任何用處。,第二章高級語言及其語法描述,,（2）每個非終結(jié)符P必須有用處。這一方面意味著，必須存在含P的句型；也就是，從開始符號出發(fā)，存在推導S??P?另一方面意味著，必須存在終結(jié)符串??VT,使得P??；也就是，對于P不存在永不終結(jié)的回路。我們以后所討論的文法均假定滿足上述兩條件。,第二章高級語言及其語法描述,,233形式語言鳥瞰喬姆斯基把文法分為四種類型即0型、1型、2型、3型。0行強于1型，1行強于2型，2型強于3型。這幾文法的差別在于對產(chǎn)生式施加不同的限制。我們說GVT,VN,S,?是一個0型文法，如果它的每個產(chǎn)生式???是這樣的結(jié)構(gòu)??VN?VT且至少有一個非終結(jié)符，而??VN?VT。0型文法也稱短語文法。,第二章高級語言及其語法描述,,如果對0型文法分別施加以下的第I條限制，則我們就得到第I型文法1G的任何產(chǎn)生式???均滿足|?|≤|?|（其中|?|和|?|分別為?和?的長度；僅S??例外，但S不得出現(xiàn)在任何產(chǎn)生式的右部。2）G的任何產(chǎn)生式為A??,A?VN,??VN?VT。3G的任何產(chǎn)生式為A??B或A??，其中??VT，A、B?VN。其中1型文法也稱上下文有關(guān)文法。這種文法意味著，對非終結(jié)符進行替換式務必考慮上下文并且一般不允許替換成空串?。,第二章高級語言及其語法描述,,2型文法也稱上下文無關(guān)文法，注意其語言定義G的任何產(chǎn)生式為A→Β，A∈VN，Β∈（VN∪VT表明凡出現(xiàn)在產(chǎn)生式左邊的符號都是非終結(jié)符。3型文法也稱右線性文法。3型文法還有另一種形式，稱左線性文法一個文法G為左線性文法，如果G的任何產(chǎn)生式為A→B?或A→?，其中?∈VT,A、B∈VN由于3型文法等價于正規(guī)式所以也稱正規(guī)文法。,第二章高級語言及其語法描述,例題與習題解答,例21試構(gòu)造生成語言L{ANBNCI|N?1,I?0}的文法解GZZ?ABA?AAB|ABB?CB|?例22已知語言L{ANBBN|N?1},寫出產(chǎn)生L的文法。,,,第二章高級語言及其語法描述,,解GSS?AABA?AAB|B例23已知文法G{A,B,C},{A,B,C},A,P其中產(chǎn)生式P由以下組成A?ABCA?ABBCBB?BBBC?CBCCBC?CBAC?AABAC?AA問此文法表式的語言是什么,第二章高級語言及其語法描述,,解由于A為開始符。由于A?ABBC?ABBC?ABCBCC?ACBBCC?AABBCC語言為{ANBNCN,N0}例24試構(gòu)造語言L{ANBNCI|N1,I0}的文法。解GZZ?ABA?AAB|ABB?CB|?,第二章高級語言及其語法描述,,例25試寫一文法，使其描述的語言LG是能被5整除的整數(shù)集合。解GZZ?|A0|5A?0|1|2|3|4|5|6|7|8|9|AA例26已知語言L{X|X?{A,B,C},且X重復排列是對稱的（AABCBAA,AABBAA,等寫出該語言的文法。解GZZ?AZA|BZB|CZC|A|B|C|?,
下載積分： 6 賞幣
上傳時間：2024-01-06
頁數(shù)： 53
大?。?0.24(MB)
子文件數(shù)：
