計(jì)算科學(xué)導(dǎo)論課件第三章

程序設(shè)計(jì)語(yǔ)言與軟件開發(fā)方法學(xué)程序設(shè)計(jì)語(yǔ)言的發(fā)展形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)義學(xué)程序設(shè)計(jì)方法學(xué)計(jì)算語(yǔ)言學(xué)軟件開發(fā)方法學(xué)

程序設(shè)計(jì)語(yǔ)言的發(fā)展算法、過程與程序機(jī)器指令與機(jī)器語(yǔ)言匯編語(yǔ)言與匯編程序高級(jí)語(yǔ)言與編譯程序MAS與超級(jí)語(yǔ)言

返回算法、過程與程序算法:一個(gè)有窮規(guī)則的集合，其中之規(guī)則確定了一個(gè)解決某一特定類型問題的運(yùn)算序列。算法的特性:有窮性、確定性、輸入、輸出和能行性。過程:一個(gè)有窮規(guī)則的集合，其中之規(guī)則確定了一個(gè)解決某一特定類型問題的運(yùn)算序列。過程的特性:確定性、輸入、輸出和能行性。程序:是具有特殊功能的指令序列。程序設(shè)計(jì):編寫程序的過程。返回機(jī)器指令與機(jī)器語(yǔ)言機(jī)器指令的格式:機(jī)器指令的分類:1控制指令;2算術(shù)運(yùn)算指令;3邏輯運(yùn)算指令;4移位操作指令;5傳送操作指令;6輸入輸出指令。機(jī)器語(yǔ)言:機(jī)器指令系統(tǒng):機(jī)器語(yǔ)言程序機(jī)器指令的實(shí)現(xiàn):微指令與微程序RISC:精簡(jiǎn)指令系統(tǒng)計(jì)算機(jī)返回操作碼地址碼匯編語(yǔ)言與匯編程序程序的可讀性匯編指令:用英文字母和一些符號(hào)對(duì)機(jī)器語(yǔ)言指令和存儲(chǔ)空間及數(shù)據(jù)進(jìn)行編碼，為0、1串進(jìn)行命名所得到的指令。操作符:add(加法)mul(無符號(hào)乘法)idiv(有符號(hào)除法)neg(求補(bǔ))xchg(交換)test(邏輯比較)jmp(無條件轉(zhuǎn)移)匯編語(yǔ)言程序匯編程序機(jī)器語(yǔ)言程序匯編語(yǔ)言的好處:使得程序設(shè)計(jì)人員從原來記憶0、1串的煩惱中解放出來，變按二進(jìn)制數(shù)字與地址空間的存取與操作為按名存取與操作。返回

高級(jí)語(yǔ)言與編譯程序高級(jí)語(yǔ)言的語(yǔ)句：把人們利用機(jī)器語(yǔ)言或匯編語(yǔ)言編程時(shí)所用數(shù)據(jù)的邏輯結(jié)構(gòu)，和對(duì)數(shù)據(jù)進(jìn)行處理時(shí)的操作序列的邏輯結(jié)構(gòu)，歸納抽象為數(shù)據(jù)類型和語(yǔ)句，利用英文字母、數(shù)字和一些符號(hào)通過一定規(guī)則（語(yǔ)法）對(duì)其編碼，所用編碼的自然語(yǔ)言含義與對(duì)應(yīng)邏輯結(jié)構(gòu)的意義盡量接近。例如：ifabthenx:=aelsex:=b

；高級(jí)語(yǔ)言程序編譯程序機(jī)器語(yǔ)言程序高級(jí)語(yǔ)言分類對(duì)高級(jí)語(yǔ)言多態(tài)性的反思

返回高級(jí)語(yǔ)言分類過程型語(yǔ)言認(rèn)為計(jì)算機(jī)所解決的問題是由一個(gè)個(gè)小問題的順次解決而解決的，把解決各個(gè)問題的動(dòng)作及所參加的成員，抽象為操作（語(yǔ)句）和數(shù)據(jù)。前期高級(jí)語(yǔ)言大多是過程型的。常見的有：FORTRAN,ALGOL60,COBOL,BASIC,PASCAL,C,ADA等。函數(shù)型語(yǔ)言認(rèn)為計(jì)算機(jī)所解決的問題是從一個(gè)域到另一個(gè)域的函數(shù)映射，把要解決的問題劃分成一個(gè)個(gè)相關(guān)成員的集合和集合間的函數(shù)關(guān)系。典型代表如LISP邏輯型語(yǔ)言認(rèn)為計(jì)算機(jī)所解決的問題是由已知事實(shí)及一定規(guī)則進(jìn)行邏輯推理得到一定結(jié)論，把要解決的問題描述為一系列事實(shí)與規(guī)則的集合。典型代表PROLOG對(duì)象型語(yǔ)言認(rèn)為計(jì)算機(jī)要解決的問題是參與問題的所有個(gè)體及個(gè)體間的相互作用的結(jié)果，把問題描述為表述個(gè)體的對(duì)象集合及個(gè)體間相互作用的消息集合，典型代表如SMALLTALK，C++,JAVA等。返回對(duì)高級(jí)語(yǔ)言多態(tài)性的反思計(jì)算機(jī)高級(jí)語(yǔ)言雖然種類繁多，但它的產(chǎn)生與發(fā)展也受到兩方面的限制，其一是實(shí)現(xiàn)它的物理機(jī)器原理等價(jià)性的限制；其二是它所抽象與表術(shù)的現(xiàn)實(shí)世界同一性的限制。所以會(huì)出現(xiàn)過程型、函數(shù)型、邏輯型和對(duì)象型等高級(jí)語(yǔ)言，是因?yàn)楝F(xiàn)實(shí)世界在不同領(lǐng)域以不同的表現(xiàn)形式為主，以其它表現(xiàn)形式為輔；還因?yàn)槿藗儗?duì)于現(xiàn)實(shí)世界認(rèn)識(shí)的主觀性與片面性。

返回MAS與超級(jí)語(yǔ)言把用高級(jí)語(yǔ)言解決某問題而設(shè)計(jì)的一個(gè)完整的程序作為整體抽象為一個(gè)Agent，把由多個(gè)Agent通過交互作用而形成的整體稱為多Agent系統(tǒng)（Multi-AgentSystem,簡(jiǎn)稱MAS），把描述MAS中各Agent的組成成份及各Agent間相互作用規(guī)則的程序設(shè)計(jì)語(yǔ)言稱為超級(jí)語(yǔ)言。程序設(shè)計(jì)語(yǔ)言的發(fā)展目標(biāo)一是為了提高數(shù)據(jù)表示的抽象程度，如過程、對(duì)象類、Agent類等，二是為了提高程序編制的自動(dòng)化程度，如指令、語(yǔ)句，規(guī)劃和目標(biāo)等。返回

語(yǔ)言及其組成自然語(yǔ)言：音義結(jié)合的符號(hào)系統(tǒng)。程序設(shè)計(jì)語(yǔ)言：碼義結(jié)合的符號(hào)系統(tǒng)。形式語(yǔ)言：一個(gè)符號(hào)選自某個(gè)字母表的字符串集合。詞法：它規(guī)定了什么樣的符號(hào)組成的字符序列或空間排列是這個(gè)語(yǔ)言合法的單詞（或字）。文法：是關(guān)于用語(yǔ)言的單詞構(gòu)成短語(yǔ)、句子和篇章的規(guī)則，在此基礎(chǔ)上可以形成各種句子和文章。語(yǔ)法：由詞法和文法構(gòu)成。語(yǔ)義：就是指單詞、短語(yǔ)、句子和文章的意義或含義。如“上馬”的語(yǔ)義語(yǔ)用：是指在一定的語(yǔ)言環(huán)境中語(yǔ)言和它的使用者之間的關(guān)系。語(yǔ)境：語(yǔ)言的使用環(huán)境。返回形式語(yǔ)言與自動(dòng)機(jī)語(yǔ)言及其組成：語(yǔ)法與巴科斯范式：轉(zhuǎn)換生成語(yǔ)言學(xué)理論：語(yǔ)言可以通過字母表和表上定義的一組語(yǔ)法規(guī)則經(jīng)演繹過程生成。喬姆斯基語(yǔ)言與自動(dòng)機(jī)的等價(jià)性：語(yǔ)言也是一種計(jì)算模型,它在計(jì)算機(jī)裸機(jī)系統(tǒng)與人的思維、描述方式之間架起了一座溝通的橋梁,只是在描述、刻畫、表達(dá)計(jì)算時(shí)所處層面和方便程度不同而已。

返回語(yǔ)法與巴科斯范式自然語(yǔ)言的語(yǔ)法結(jié)構(gòu)：〈句子〉〈名詞短語(yǔ)〉〈動(dòng)詞短語(yǔ)〉〈名詞短語(yǔ)〉〈形容詞〉〈名詞短語(yǔ)〉〈名詞短語(yǔ)〉〈名詞〉〈名詞〉boy〈形容詞〉little……程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)：〈表達(dá)式〉〈表達(dá)式〉+〈表達(dá)式〉〈表達(dá)式〉〈表達(dá)式〉*〈表達(dá)式〉〈表達(dá)式〉（〈表達(dá)式〉）〈表達(dá)式〉id……形式語(yǔ)言的語(yǔ)法結(jié)構(gòu)：返回形式語(yǔ)言的語(yǔ)法結(jié)構(gòu)上下文無關(guān)文法：CFG=（V，T，P，S），其中：

V：變?cè)挠懈F集合；

T：終極符的有窮集合，VT=0；

P：產(chǎn)生式的有窮集合，每個(gè)產(chǎn)生式的形式是A，A是變?cè)?，是（VT）*中的符號(hào)串；

S：是開始變?cè)＠樱篊FG

=（{E}，{+，*，（，），id}，P，E），其中P為：EE+EEE*EE（E）Eid……巴科斯—瑙爾范式（BNF）

返回

形式語(yǔ)義學(xué)自然語(yǔ)言：語(yǔ)法、語(yǔ)義、語(yǔ)用、語(yǔ)境與本質(zhì)條件子句與條件語(yǔ)句嵌套的語(yǔ)義問題：

條件子句：ifBthenS；

條件語(yǔ)句：ifBthenS1else

S2；

條件子句與條件語(yǔ)句嵌套：

ifB1thenifB2thenS1else

S2；

條件子句與條件語(yǔ)句嵌套的兩種語(yǔ)義解釋：1.ifB1then(ifB2thenS1else

S2)；2.ifB1then(ifB2thenS1)else

S2；形式語(yǔ)義（學(xué)）：就是指用形式化的方法對(duì)語(yǔ)言成分語(yǔ)義的描述（研究）。語(yǔ)義的四種描述方法

返回語(yǔ)義的四種描述方法程序語(yǔ)義（功能）的形式描述：{Q}P{R}其中：

P：表示一程序；

Q：P的前斷言，表示P執(zhí)行前的狀態(tài)（指影響P運(yùn)行的所有組成成份的狀態(tài)）必須滿足的條件；

R：P的后斷言，表示P執(zhí)行后的狀態(tài)必須滿足的條件。

例如：

{Q：得到10元錢}P：S1；S2；……；Sn；{R：打回一瓶酒}程序語(yǔ)義的四種描述方法

返回語(yǔ)義的四種描述方法（續(xù)）操作語(yǔ)義：用抽象機(jī)的基本動(dòng)作對(duì)語(yǔ)言中語(yǔ)句的語(yǔ)義進(jìn)行描述的方法。即把{Q}P{R}中的S1；S2；…；Sn用抽象機(jī)的基本動(dòng)作O1；O2；…；Om進(jìn)行描述,以證明P完成了其功能{Q，R}。指稱語(yǔ)義：用基本定值函數(shù)對(duì)語(yǔ)言中語(yǔ)句的語(yǔ)義進(jìn)行描述的方法。即把{Q}P{R}中的S1；S2；…；Sn用基本定值函數(shù)f1；f2；…；fm進(jìn)行描述，以證明P完成了其功能{Q，R}。公理語(yǔ)義：用基本公理和推導(dǎo)規(guī)則對(duì)語(yǔ)言中語(yǔ)句的語(yǔ)義進(jìn)行描述的方法。即從基本公理{Q1}S1{R1}；{Q2}S2{R2}；…；{Qn}Sn{Rn}出發(fā)，利用推導(dǎo)規(guī)則，以證明P完成了其功能{Q，R}。代數(shù)語(yǔ)義：用基本代數(shù)規(guī)則對(duì)語(yǔ)言中語(yǔ)句的語(yǔ)義進(jìn)行描述的方法。即把{Q}P{R}中的S1；S2；…；Sn用基本代數(shù)規(guī)則R1；R2；…；Rm進(jìn)行描述，以證明P完成了其功能{Q，R}。四種描述方法的等價(jià)性問題返回程序設(shè)計(jì)方法學(xué)程序理論：程序的結(jié)構(gòu)，程序的正確性，程序的運(yùn)行效率等。程序設(shè)計(jì)方法：自頂向下，自底向上，結(jié)構(gòu)化，程序推導(dǎo)，程序變換，面向?qū)ο?，面向函?shù)，面向邏輯等。程序設(shè)計(jì)技術(shù)：程序驗(yàn)證技術(shù)，程序重用技術(shù)，約束程序設(shè)計(jì)技術(shù)，并發(fā)程序設(shè)計(jì)技術(shù)等。返回程序的結(jié)構(gòu)程序的整體結(jié)構(gòu)程序的數(shù)據(jù)結(jié)構(gòu)程序的控制結(jié)構(gòu)：

1、順序：S1；S2；；Sn

2、選擇：ifBthenS1else

S2endif3、循環(huán)：loopBdoSendloop

返回程序的控制結(jié)構(gòu)

程序的整體結(jié)構(gòu)Ｃ語(yǔ)言程序的總體結(jié)構(gòu)

一個(gè)完整的Ｃ語(yǔ)言程序，是由一個(gè)main()函數(shù)（又稱主函數(shù)）和若干個(gè)其它函數(shù)結(jié)合而成的，或僅由一個(gè)main()函數(shù)構(gòu)成[例1]僅由main()函數(shù)構(gòu)成的Ｃ語(yǔ)言程序。main(){printf(“ThisisaCprogram.\n”);}程序運(yùn)行結(jié)果：

ThisisaCprogram.Ｃ語(yǔ)言程序的總體結(jié)構(gòu)[例2]由main()函數(shù)和1個(gè)其它函數(shù)max()構(gòu)成的Ｃ語(yǔ)言程序。int

max(intx,inty){return(x>y?x:y);}main(){intnum1,num2;

printf(“Inputthefirstintegernumber:”);

scanf(“%d”,&num1);

printf(“Inputthesecondintegernumber:”);

scanf(“%d”,&num2);

printf(“max=%d\n”,max(num1,num2));}程序運(yùn)行情況：

Inputthefirstintegernumber:6←┘Inputthesecondintegernumber:9←┘max=9函數(shù)的一般結(jié)構(gòu)任何函數(shù)都是由函數(shù)說明和函數(shù)體兩部分組成：

[函數(shù)類型]函數(shù)名(函數(shù)參數(shù)表)函數(shù)說明部分

{說明語(yǔ)句部分；執(zhí)行語(yǔ)句部分；函數(shù)體部分

}函數(shù)參數(shù)表的格式為：

數(shù)據(jù)類型形參[,數(shù)據(jù)類型形參2……]例如，函數(shù)max()說明部分如下：

函數(shù)類型函數(shù)名函數(shù)參數(shù)表

↓↓↓

intmax(intx,inty)函數(shù)體一般由說明語(yǔ)句和可執(zhí)行語(yǔ)句兩部分構(gòu)成：（1）說明語(yǔ)句部分說明語(yǔ)句部分由變量定義、自定義類型定義、自定義函數(shù)說明、外部變量說明等組成。（2）可執(zhí)行語(yǔ)句main(){intnum1,num2;變量定義部分

printf(“Inputthefirstintegernumber:”);

scanf(“%d”,&num1);

printf(“Inputthesecondintegernumber:”);可執(zhí)行語(yǔ)句部分函數(shù)體

scanf(“%d”,&num2);

printf(“max=%d\n”,max(num1,num2));}函數(shù)體程序的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)(Data)：一切能夠由計(jì)算機(jī)接受和處理的對(duì)象。數(shù)據(jù)元素(Dataelement)：是數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體加以考慮和處理。數(shù)據(jù)項(xiàng)(Dataitem)：是數(shù)據(jù)的不可分割的最小單位，在有些場(chǎng)合下，數(shù)據(jù)項(xiàng)又稱為字段或域。數(shù)據(jù)結(jié)構(gòu)(Datastructure)：數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。例:數(shù)組

返回?cái)?shù)組數(shù)組是由一些單元組成的，每個(gè)單元對(duì)應(yīng)著一組下標(biāo)值和一個(gè)數(shù)組元素。n維數(shù)組的每個(gè)單元對(duì)應(yīng)n個(gè)下標(biāo)值。數(shù)組元素可以是基本數(shù)據(jù)類型，如整數(shù)型、實(shí)數(shù)型、字符型等，也可以是有多個(gè)數(shù)據(jù)項(xiàng)的一種結(jié)構(gòu)。同一數(shù)組中各個(gè)元素必須是同一數(shù)據(jù)類型，每個(gè)數(shù)組元素都占有相同數(shù)量的存儲(chǔ)單元，才能用下標(biāo)來唯一的確定數(shù)組中的元素。例：[23,56,900,85,67,53,146]

1234567返回計(jì)算語(yǔ)言學(xué)是計(jì)算科學(xué)與語(yǔ)言學(xué)的一個(gè)交叉學(xué)科，其主要任務(wù)是運(yùn)用數(shù)學(xué)和計(jì)算科學(xué)的理論與技術(shù)研究語(yǔ)言學(xué)的基本規(guī)律。直接應(yīng)用：開發(fā)自然語(yǔ)言理解系統(tǒng)和機(jī)器翻譯軟件。理論工具：本體與主體理論，形式語(yǔ)言與自動(dòng)機(jī)理論，數(shù)理邏輯與形式語(yǔ)義學(xué)。研究難點(diǎn)：語(yǔ)義與語(yǔ)境、語(yǔ)用的關(guān)系語(yǔ)言多義性的幾個(gè)例子

現(xiàn)狀與出路

返回計(jì)算語(yǔ)言學(xué)語(yǔ)言多義性的幾個(gè)例子（一）例1

“他的老師當(dāng)?shù)煤谩！钡亩嗔x性。A、他的傳授文化、技術(shù)的身分擔(dān)任的好。B、他的（某位）老師把知識(shí)、技能傳授得好。C、他的（所有）老師把知識(shí)、技能傳授得好。D、他的（某位）老師家庭主婦的身分擔(dān)任的好。E、他的（某位）老師人大代表的身分擔(dān)任的好。

例2語(yǔ)言多義性的幾個(gè)例子（二）例2

“調(diào)個(gè)過兒還是一樣”——呂叔湘文集A、在家里，我對(duì)兒媳像閨女一樣，兒媳對(duì)我也像親媽一樣。B、在家里，我對(duì)兒媳像親媽一樣，兒媳對(duì)我也像閨女一樣。C、在家里，我對(duì)兒媳像親媽對(duì)閨女一樣，兒媳對(duì)我也像閨女對(duì)親媽一樣。D、在家里，我對(duì)兒媳像親媽對(duì)閨女一樣，兒媳對(duì)我也像閨女對(duì)親媽一樣。例3語(yǔ)言多義性的幾個(gè)例子（三）例3

語(yǔ)音處理的困難—同音字詞的語(yǔ)義。A、家家愛加佳，加佳進(jìn)家家B、加佳愛家家，家家進(jìn)加佳C、加佳愛家家，加佳進(jìn)家家D、家家愛加佳，家家進(jìn)加佳

例四神奇圖片返回計(jì)算語(yǔ)言學(xué)現(xiàn)狀與出路

1

數(shù)理統(tǒng)計(jì)方法：語(yǔ)料庫(kù)，模糊性與特殊語(yǔ)言現(xiàn)象

2

數(shù)理邏輯與形式語(yǔ)義學(xué)：陸汝占，漢語(yǔ)計(jì)算語(yǔ)義學(xué)

3

計(jì)算語(yǔ)義學(xué)模型：形式語(yǔ)言與自動(dòng)機(jī)理論

4

語(yǔ)言的本質(zhì)：本體與主體理論返回軟件開發(fā)方法學(xué)軟件及其分類軟件的開發(fā)軟件開發(fā)方法學(xué)研究范疇軟件開發(fā)方法學(xué)發(fā)展方向：1、軟件開發(fā)環(huán)境的研究：計(jì)算機(jī)輔助軟件工程（CASE）和形式化軟件開發(fā)方法2、分布式和并行軟件開發(fā)方法學(xué)：MAS（多代理系統(tǒng)），語(yǔ)義Web，WebService，AORBCO

返回軟件及其分類軟件：是對(duì)事先編