高級(jí)程序設(shè)計(jì)語(yǔ)言原理課件

語(yǔ)言設(shè)計(jì)問(wèn)題早期的語(yǔ)言設(shè)計(jì)需使程式能高效地運(yùn)行於昂貴的硬體上，因此，早期語(yǔ)言總以翻譯成高效的機(jī)器碼為目標(biāo)，既使程式難以書(shū)寫(xiě)?，F(xiàn)在，硬體價(jià)格下降、軟體價(jià)格上升，更強(qiáng)調(diào)程式容易書(shū)寫(xiě)，即使慢點(diǎn)也可。例如，ML的類(lèi)型特性、C++的類(lèi)、Ada的Package均在執(zhí)行速度上有代價(jià)，但對(duì)保證程式正確性有幫助。開(kāi)發(fā)語(yǔ)言時(shí)，有三個(gè)影響語(yǔ)言設(shè)計(jì)的主要因素：電腦本身在電腦上支持語(yǔ)言的執(zhí)行模型，即虛擬電腦語(yǔ)言所實(shí)現(xiàn)的計(jì)算模型2.1電腦的結(jié)構(gòu)和操作一個(gè)電腦是能夠存儲(chǔ)和執(zhí)行程式的數(shù)據(jù)結(jié)構(gòu)和演算法的集成集合。電腦可構(gòu)造為實(shí)際的物理設(shè)備，用導(dǎo)線(xiàn)、積體電路、電路板等。此即實(shí)際電腦或稱(chēng)硬體電腦。電腦構(gòu)造為軟體，用運(yùn)行於其他電腦上的程式。此即軟體仿真電腦。程式設(shè)計(jì)語(yǔ)言的實(shí)現(xiàn)是通過(guò)一個(gè)翻譯器，將以語(yǔ)言書(shū)寫(xiě)的程式翻譯為機(jī)器語(yǔ)言程式（可為某電腦直接執(zhí)行，可以是硬體電腦，也可以為軟硬參雜的虛擬機(jī)）。一個(gè)電腦包含6個(gè)主要部件，它們緊密地對(duì)應(yīng)於程式設(shè)計(jì)語(yǔ)言的主要方面。1、數(shù)據(jù)：電腦必須提供各種基本資料項(xiàng)目和操作的數(shù)據(jù)結(jié)構(gòu)。2、基本操作：必須提供對(duì)運(yùn)算元據(jù)有用的基本操作集。3、順序控制：必須提供控制基本操作執(zhí)行順序的機(jī)制。4、數(shù)據(jù)訪(fǎng)問(wèn)：必須提供控制向操作的執(zhí)行供給數(shù)據(jù)的機(jī)制。5、存儲(chǔ)管理：必須提供控制程式和數(shù)據(jù)存儲(chǔ)分配的機(jī)制。6、操作環(huán)境：必須提供與包圍程式和被處理數(shù)據(jù)的外部環(huán)境通訊的機(jī)制。電腦硬體一個(gè)典型的傳統(tǒng)電腦組織如下：包括程式和被處理的數(shù)據(jù)操作主存和高速緩存中的數(shù)據(jù)在主存和外部環(huán)境間傳遞程式或數(shù)據(jù)完成處理工作取機(jī)器指令解碼調(diào)用指定的基本操作，以指定的運(yùn)算元作為輸入數(shù)據(jù)有三個(gè)主要的存貯部件：主存，高速寄存和外部檔。主存：組織為線(xiàn)性位串，可分為定長(zhǎng)的字（32或64）或8位位元組。寄存器：字長(zhǎng)度的位串，可能有特殊的子域可直接訪(fǎng)問(wèn)，可存數(shù)據(jù)或主存地址。外部檔：存在盤(pán)、帶或CD-ROM上，按記錄劃分，記錄是位或位元組的序列。一個(gè)電腦有被硬體基本操作直接操作的固有數(shù)據(jù)類(lèi)型。一般有：整數(shù)、單精確度實(shí)數(shù)（浮點(diǎn)數(shù)）、定長(zhǎng)字串、定長(zhǎng)位串等。除了明顯的硬體數(shù)據(jù)元素外，程式（也有固有的內(nèi)部表示，稱(chēng)為機(jī)器語(yǔ)言表示）也是一種數(shù)據(jù)形式。機(jī)器語(yǔ)言程式可構(gòu)造為存儲(chǔ)位置的序列，每個(gè)包含一或多條指令，每條包括操作碼和若干運(yùn)算元（指示）。操作電腦必須包含有一個(gè)固有的基本操作集，通常和機(jī)器語(yǔ)言指令中操作碼一一對(duì)應(yīng)。典型的操作集包括在固有數(shù)值類(lèi)型上的基本算術(shù)操作。測(cè)試資料項(xiàng)目各種性質(zhì)的基本操作。訪(fǎng)問(wèn)和修改資料項(xiàng)目的基本操作。控制I/O設(shè)備的基本操作。順序控制的基本操作。傳統(tǒng)的機(jī)器是CISC，complexinstructionsetcomputers.新近發(fā)展的是RISC，reducedinstructionsetcomputers.更少的基本指令，更簡(jiǎn)單的內(nèi)部邏輯。順序控制程式地址寄存器（位置計(jì)數(shù)器）的內(nèi)容決定了下一條將執(zhí)行的指令，即包含了下條指令的地址。某些基本操作允許修改程式寄存器，從而傳遞控制到程式的其他部分。解釋器實(shí)際地使用程式地址寄存器並指導(dǎo)操作序列。解釋器是電腦操作的中心，其週期動(dòng)作如圖所示：數(shù)據(jù)訪(fǎng)問(wèn)除了操作碼外，每個(gè)機(jī)器指令必須指明所需的運(yùn)算元（必須在主存或寄存器中）電腦必須結(jié)合指定運(yùn)算元的手段和從給定運(yùn)算元指示器檢索運(yùn)算元的機(jī)制。同時(shí)，操作的結(jié)果也必須存儲(chǔ)在指定的位置。傳統(tǒng)的存儲(chǔ)控制機(jī)制是為存儲(chǔ)位置設(shè)定整數(shù)地址，提供操作從給定地址的位置檢索內(nèi)容和存儲(chǔ)新值。寄存器也賦以整數(shù)地址。存儲(chǔ)管理機(jī)器設(shè)計(jì)的一個(gè)驅(qū)動(dòng)原則是保持所有電腦資源盡可能多地被使用，中心衝突是：CPU中的操作是納秒級(jí)（一個(gè)操作10—50ns）訪(fǎng)問(wèn)主存是是微秒級(jí)（0.1~0.2微秒，100—200ns）外部數(shù)據(jù)操作是毫秒級(jí)（15—30毫秒）這樣在內(nèi)外速度間相差1000,000倍。為了平衡速度差異，各種存儲(chǔ)管理機(jī)制是必須的。1、在最簡(jiǎn)單的設(shè)計(jì)（如低價(jià)PC）中，只有簡(jiǎn)單的存儲(chǔ)管理設(shè)施。程式和數(shù)據(jù)執(zhí)行時(shí)駐留記憶體，在一個(gè)時(shí)刻只有一個(gè)程式準(zhǔn)備執(zhí)行。雖然CPU必須等待數(shù)據(jù)，它也是價(jià)格有效的，因?yàn)椴恍杓尤敫郊佑搀w。2、為加速外部數(shù)據(jù)訪(fǎng)問(wèn)和CPU間的平衡，操作系統(tǒng)常使用多道程序設(shè)計(jì)，當(dāng)?shù)却撩肴プx數(shù)據(jù)時(shí)，電腦將執(zhí)行另一個(gè)程式。為了保證多個(gè)程式同時(shí)駐留主存，通常有硬體設(shè)施負(fù)責(zé)頁(yè)面查找或動(dòng)態(tài)程式重定位，頁(yè)面查找通過(guò)預(yù)測(cè)進(jìn)行，預(yù)測(cè)在最近將來(lái)最可能使用的頁(yè)面，將其放入主存。如在主存，則程式執(zhí)行，否則，出現(xiàn)頁(yè)間錯(cuò)，操作系統(tǒng)將從外存中讀取所需頁(yè)，同時(shí)執(zhí)行別的程式。3、為加速主存和CPU間的不平衡，常使用Cache記憶體（小的高速數(shù)據(jù)存儲(chǔ)）。Cache可允許電腦操作，好象主存具有和CPU相同速度，通常是1K到256K位元組，32K的Cache，可達(dá)到95%的選中率。操作環(huán)境電腦的操作環(huán)境通常包括週邊記憶體和I/O設(shè)備，這些設(shè)備表示了電腦的外部世界，和電腦的任何通訊必須通過(guò)它們。操作環(huán)境中通常有硬體的不同，如：高速存儲(chǔ)（擴(kuò)展記憶體），中速存儲(chǔ)（磁片），低速存儲(chǔ)（磁帶）和I/O設(shè)備。各種電腦體系結(jié)構(gòu)電腦硬體的組織有多種形式，上面的討論是基於VonNeumann體系結(jié)構(gòu)。VonNeumann體系結(jié)構(gòu)：命名來(lái)源於數(shù)學(xué)家JohnvonNeumann，他在40年代開(kāi)發(fā)這個(gè)初始設(shè)計(jì)，作為ENIAC電腦設(shè)計(jì)的一部分，現(xiàn)今電腦仍屬此體系結(jié)構(gòu)。多處理器：VonNeumann設(shè)計(jì)的最大問(wèn)題是外部數(shù)據(jù)設(shè)備的慢速和CPU寄存器高速間的矛盾。解決方案之一是在指定系統(tǒng)中使用多個(gè)CPU，這樣的多處理系統(tǒng)已使用了30多年，通過(guò)幾個(gè)相對(duì)不昂貴的CPU的粘合，再加上單一的主存、磁片、磁帶等，得到一個(gè)高效系統(tǒng)。操作系統(tǒng)將不同程式運(yùn)行於不同CPU上，從而整個(gè)性能得到改善。語(yǔ)言和系統(tǒng)設(shè)計(jì)正在演化，使得能夠書(shū)寫(xiě)程式在多個(gè)電腦上執(zhí)行並相互通訊。電腦狀態(tài)對(duì)電腦靜態(tài)組織的瞭解只是一個(gè)部分，全面瞭解則涉及電腦在程式執(zhí)行時(shí)的動(dòng)態(tài)操作，包括：執(zhí)行開(kāi)始時(shí)各存儲(chǔ)部件的內(nèi)容，操作執(zhí)行順序。執(zhí)行進(jìn)行時(shí)如何修改各種數(shù)據(jù)部件，程式執(zhí)行的最後結(jié)果等。通常對(duì)電腦動(dòng)態(tài)行為的觀(guān)察是通過(guò)電腦狀態(tài)（執(zhí)行過(guò)程中某點(diǎn)主存、寄存器和外存的內(nèi)容決定）的概念。程式的執(zhí)行體現(xiàn)為一系列狀態(tài)的變化初始狀態(tài)通過(guò)一系列狀態(tài)變遷（從當(dāng)前狀態(tài)通過(guò)存貯內(nèi)容的修改進(jìn)入新的狀態(tài)），得到最終狀態(tài)。如果我們可以預(yù)測(cè)狀態(tài)變遷序列，則可以聲稱(chēng)瞭解了電腦的動(dòng)態(tài)行為。固件電腦如前定義，電腦=演算法集+數(shù)據(jù)結(jié)構(gòu)集 可執(zhí)行程式表示為電腦的機(jī)器語(yǔ)言程式通常認(rèn)為電腦操作在相當(dāng)?shù)图?jí)的機(jī)器語(yǔ)言之上，具有簡(jiǎn)單的指令格式。然而，機(jī)器語(yǔ)言並不一定限制到低級(jí)。可以選擇任何程式設(shè)計(jì)語(yǔ)言，精確地刻劃數(shù)據(jù)結(jié)構(gòu)集和定義程式執(zhí)行規(guī)則的演算法，這樣該電腦的“機(jī)器語(yǔ)言”就是該高級(jí)語(yǔ)言。每個(gè)程式定義了電腦的初態(tài)，程式執(zhí)行的規(guī)則定義了程式執(zhí)行過(guò)程中狀態(tài)的變遷序列，程式執(zhí)行結(jié)果由程式執(zhí)行完成後電腦的終態(tài)決定。給定一個(gè)精確的電腦定義，總是可能將其用硬體實(shí)現(xiàn)，從而可使電腦的機(jī)器語(yǔ)言為C、Ada、或其他高級(jí)語(yǔ)言。如此考慮的一個(gè)重要的基本原則是：任何精確定義的演算法或數(shù)據(jù)結(jié)構(gòu)可以用硬體實(shí)現(xiàn)。電腦簡(jiǎn)單地是演算法和數(shù)據(jù)結(jié)構(gòu)的集合，我們可以假定其硬體實(shí)現(xiàn)是可能的，不管其複雜度和相應(yīng)的機(jī)器語(yǔ)言。實(shí)際的電腦通常有相當(dāng)?shù)图?jí)的機(jī)器語(yǔ)言。高級(jí)語(yǔ)言作為機(jī)器語(yǔ)言會(huì)使機(jī)器非常複雜，具應(yīng)用靈活性較差。一個(gè)具有低級(jí)通用指令集和簡(jiǎn)單的、無(wú)結(jié)構(gòu)的主存和寄存器的電腦可以被編程為相當(dāng)廣範(fàn)圍的高效電腦。一個(gè)常用的選擇（相對(duì)於電腦的嚴(yán)格硬體實(shí)現(xiàn)）是固件電腦，由運(yùn)行在特殊的微可偏程硬體電腦上運(yùn)行的微程式來(lái)仿真。這種電腦的機(jī)器語(yǔ)言是絕對(duì)低級(jí)的微指令集，用微指令集可編碼得到微程式，微程式將仿真所希望的電腦的操作，並定義瞭解釋週期和各種基本操作。通常微程式本身駐留在特殊的只讀記憶體中，由宿主機(jī)硬體高速執(zhí)行，這種電腦在執(zhí)行速度上和硬體直接實(shí)現(xiàn)電腦無(wú)太大差別。電腦的微程式仿真有時(shí)可稱(chēng)為emulation（仿真），該電腦稱(chēng)為虛擬機(jī)，因?yàn)闄C(jī)器本身並不存在。翻譯器和軟體仿真電腦理論上，有可能直接構(gòu)造硬體或固件電腦，運(yùn)行任何特殊的程式設(shè)計(jì)語(yǔ)言，但構(gòu)造這樣的電腦並不經(jīng)濟(jì)?，F(xiàn)實(shí)的考慮是實(shí)際電腦採(cǎi)用低級(jí)機(jī)器語(yǔ)言（基於速度、靈活性和價(jià)格考慮），編程仍以高級(jí)語(yǔ)言進(jìn)行。語(yǔ)言實(shí)現(xiàn)者面臨的任務(wù)是如何使高級(jí)語(yǔ)言程式執(zhí)行在實(shí)際電腦上，不管其機(jī)器語(yǔ)言。這個(gè)實(shí)現(xiàn)問(wèn)題有兩個(gè)基本方案。1、翻譯（編譯）高級(jí)語(yǔ)言程式→翻譯器→等價(jià)的機(jī)器語(yǔ)言程式→硬體直接執(zhí)行源語(yǔ)言→目標(biāo)語(yǔ)言幾種特殊類(lèi)型的翻譯器：A、彙編器目標(biāo)語(yǔ)言：實(shí)際電腦的機(jī)器語(yǔ)言源語(yǔ)言：組合語(yǔ)言，機(jī)器語(yǔ)言的符號(hào)表示大多數(shù)指令是一對(duì)一的翻譯B、編譯器目標(biāo)語(yǔ)言：彙編和機(jī)器語(yǔ)言源語(yǔ)言：高級(jí)語(yǔ)言C、裝配器或連接編輯器（loader/linkeditor）目標(biāo)語(yǔ)言：實(shí)際的機(jī)器代碼源語(yǔ)言：幾乎相同於機(jī)器代碼，通常包含可重定位的機(jī)器語(yǔ)言程式和數(shù)據(jù)表（刻劃可重定位代碼為變成真正可執(zhí)行所必須修改的地方）D、預(yù)處理器或宏處理器源語(yǔ)言：某種高級(jí)語(yǔ)言的擴(kuò)展形式目標(biāo)語(yǔ)言：同樣語(yǔ)言的標(biāo)準(zhǔn)形式。通常進(jìn)行宏替換。高級(jí)源語(yǔ)言到可執(zhí)行機(jī)器語(yǔ)言的翻譯通常涉及多個(gè)翻譯步驟，有時(shí)，編譯本本身也涉及多遍（多步），如：先產(chǎn)生某種中間形式。2、軟體仿真（軟體解釋?zhuān)┪覀兛梢酝ㄟ^(guò)運(yùn)行在另一臺(tái)宿主機(jī)上的程式仿真一臺(tái)電腦，其機(jī)器語(yǔ)言為高級(jí)語(yǔ)言。用宿主機(jī)的機(jī)器語(yǔ)言構(gòu)造一個(gè)程式集（表達(dá)高級(jí)語(yǔ)言執(zhí)行必需的演算法和數(shù)據(jù)結(jié)構(gòu)），即用軟體構(gòu)造運(yùn)行於宿主機(jī)上的高級(jí)語(yǔ)言電腦，稱(chēng)為高級(jí)語(yǔ)言電腦在宿主機(jī)上的軟體仿真（或軟體解釋?zhuān)７抡骐娔X接受高級(jí)語(yǔ)言程式作為輸入，主仿真器程式完成解釋演算法（解碼並執(zhí)行語(yǔ)言），最後從程式產(chǎn)生輸出。軟體仿真和翻譯的不同：均以高級(jí)語(yǔ)言程式為輸入，但是，翻譯為目標(biāo)碼後再運(yùn)行於實(shí)際電腦上仿真電腦直接執(zhí)行輸入程式翻譯器以物理輸入順序處理程式語(yǔ)句，每個(gè)語(yǔ)句只處理一次。仿真器以邏輯控制流處理程式，可能重複處理某些語(yǔ)句而完全忽略其他語(yǔ)句。純粹的翻譯和純粹的仿真形成兩個(gè)極端全翻譯是很少的，除了輸入語(yǔ)言和輸出語(yǔ)言非常相似，如組合語(yǔ)言。全仿真也非常少，除了操作系統(tǒng)控制語(yǔ)言或互動(dòng)式語(yǔ)言情形。通常語(yǔ)言實(shí)現(xiàn)是二者的結(jié)合。如圖所示。翻譯和仿真各有不同優(yōu)點(diǎn)有的程式結(jié)構(gòu)最好翻譯成更簡(jiǎn)單的形式，——如迴圈中語(yǔ)句多次執(zhí)行，翻譯可省去解碼時(shí)間。有的方面最好保持原有形式，在執(zhí)行時(shí)根據(jù)需要處理。翻譯的主要缺點(diǎn)是失去了關(guān)於程式的一些資訊。單個(gè)的高級(jí)語(yǔ)言語(yǔ)句比單條機(jī)器語(yǔ)言指令含有更多資訊。仿真的優(yōu)缺點(diǎn)基本正好相反。不需要太多的空間來(lái)存儲(chǔ)代碼序列的多份拷貝。但解碼代價(jià)高。通常，如源語(yǔ)言結(jié)構(gòu)在目標(biāo)語(yǔ)言中有直接表示，則代碼擴(kuò)展不太嚴(yán)重，可採(cǎi)用翻譯。其他情形，可採(cǎi)用仿真。是否程式執(zhí)行時(shí)的基本表示為實(shí)際機(jī)器的機(jī)器語(yǔ)言，形成了語(yǔ)言劃分的基礎(chǔ)。1、編譯型語(yǔ)言。如：C、C++、Fortran、Ada等源語(yǔ)言翻成機(jī)器碼，仿真僅限於一些運(yùn)行支持例程（用於仿真源語(yǔ)言中和機(jī)器語(yǔ)言沒(méi)有緊密類(lèi)似的基本操作）。通過(guò)硬體解釋器，可實(shí)現(xiàn)更快的程式執(zhí)行。當(dāng)然，也可能有的部分仍?huà)?cǎi)用軟體仿真，如數(shù)據(jù)控制結(jié)構(gòu)和存儲(chǔ)管理。2、解釋型語(yǔ)言。如：LISP、ML、Prolog、Smalltalk等翻譯器不是產(chǎn)生機(jī)器代碼，而是產(chǎn)生某種中間形式，比源語(yǔ)言更易執(zhí)行。然後使用軟體解釋器對(duì)中間代碼進(jìn)行執(zhí)行。通常執(zhí)行慢，也需要對(duì)基本操作、存儲(chǔ)管理和其他語(yǔ)言特性的仿真，這類(lèi)語(yǔ)言翻譯器很簡(jiǎn)單，更多的複雜性在軟體仿真。2.2虛擬電腦和綁定時(shí)間電腦的構(gòu)造方式1、通過(guò)硬體實(shí)現(xiàn)，直接使用物理設(shè)備2、固件實(shí)現(xiàn)，在合適的硬體電腦上使用微程式設(shè)計(jì)3、軟體仿真，在宿主機(jī)上用某種語(yǔ)言實(shí)現(xiàn)4、上述技術(shù)的組合，各自選擇合適的實(shí)現(xiàn)方式當(dāng)一個(gè)程式設(shè)計(jì)語(yǔ)言被實(shí)現(xiàn)，程式執(zhí)行時(shí)使用的運(yùn)行時(shí)數(shù)據(jù)結(jié)構(gòu)和演算法定義了一個(gè)電腦。類(lèi)似電腦的固件實(shí)現(xiàn)，我們稱(chēng)其為由語(yǔ)言實(shí)現(xiàn)定義的虛擬電腦。該虛擬機(jī)的機(jī)器語(yǔ)言是該語(yǔ)言的翻譯器產(chǎn)生的可執(zhí)行程式（形式：對(duì)編譯是實(shí)際的機(jī)器碼形式；對(duì)解釋是某種任意結(jié)構(gòu)）；其數(shù)據(jù)結(jié)構(gòu)是程式運(yùn)行時(shí)使用的運(yùn)行時(shí)數(shù)據(jù)結(jié)構(gòu)；基本操作是那些運(yùn)行時(shí)實(shí)際可執(zhí)行的；順序控制、數(shù)據(jù)控制和存貯管理結(jié)構(gòu)也是那些運(yùn)行時(shí)使用的，不管其是用軟體、硬體或微程式表示。語(yǔ)法和語(yǔ)義語(yǔ)法：程式看起來(lái)象什麼。語(yǔ)法規(guī)則規(guī)定了如何書(shū)寫(xiě)語(yǔ)句、聲明和其他語(yǔ)言結(jié)構(gòu)。語(yǔ)義：對(duì)各種語(yǔ)法結(jié)構(gòu)賦予的含義。在語(yǔ)言手冊(cè)和其他語(yǔ)言描述中，通常圍繞語(yǔ)言中的各種語(yǔ)法結(jié)構(gòu)組織語(yǔ)言描述。典型地，給出語(yǔ)法（對(duì)一個(gè)語(yǔ)言結(jié)構(gòu)，如語(yǔ)句、聲明），然後給出語(yǔ)義，BNF是主要的語(yǔ)法記號(hào)體系。本書(shū)的組織方式略有不同，圍繞和虛擬機(jī)相關(guān)聯(lián)的結(jié)構(gòu)來(lái)組織，這種風(fēng)格用用在虛擬機(jī)中的數(shù)據(jù)結(jié)構(gòu)和操作來(lái)描述語(yǔ)言的語(yǔ)義。有時(shí)，這些數(shù)據(jù)結(jié)構(gòu)和操作是直接和語(yǔ)言語(yǔ)法中的特殊結(jié)構(gòu)相關(guān)聯(lián)的，而通常，這種聯(lián)繫並不是太直接。如：Pascal虛擬機(jī)中可能在程式執(zhí)行中使用向量，而向量結(jié)構(gòu)是在聲明中直接給出的；然而，虛擬機(jī)也可能有其他不能在程式中直接可見(jiàn)數(shù)據(jù)結(jié)構(gòu)，如副程式“活躍記錄”的中心棧。這些“隱藏”的虛擬機(jī)結(jié)構(gòu)和那些直接對(duì)應(yīng)程式員寫(xiě)在程式中的某些東西的“可見(jiàn)”結(jié)構(gòu)一樣，對(duì)更好地瞭解語(yǔ)言同等重要。因此，這裏的討論是圍繞在虛擬機(jī)中看到的結(jié)構(gòu)，而不僅僅是語(yǔ)法元素來(lái)進(jìn)行的。一個(gè)特殊的虛擬機(jī)元素可能在程式中沒(méi)有語(yǔ)法表示；可被單個(gè)語(yǔ)法元素直接表示；可被幾個(gè)分開(kāi)的語(yǔ)法元素表示（由翻譯器合起來(lái)產(chǎn)生一個(gè)虛擬機(jī)元素）。虛擬機(jī)和語(yǔ)言實(shí)現(xiàn)如果語(yǔ)言用它們的虛擬機(jī)來(lái)定義，使得每個(gè)語(yǔ)言和一個(gè)共同理解的虛擬機(jī)相關(guān)聯(lián)，則使用虛擬機(jī)來(lái)描述語(yǔ)言的語(yǔ)義是直接的。然而，語(yǔ)言定義通常是個(gè)體地對(duì)每個(gè)語(yǔ)法結(jié)構(gòu)給出語(yǔ)義，語(yǔ)言定義僅隱含地刻劃了一個(gè)虛擬機(jī)。語(yǔ)言在不同電腦上的每次實(shí)現(xiàn)，實(shí)現(xiàn)者都會(huì)從語(yǔ)言定義中看到略微（或非常）不同的虛擬機(jī)。同一語(yǔ)言的兩個(gè)不同實(shí)現(xiàn)，可能使用不同的數(shù)據(jù)結(jié)構(gòu)和操作集合（特別是在語(yǔ)法中隱藏的部分）。每個(gè)實(shí)現(xiàn)者有很大自由度確定自己的虛擬機(jī)結(jié)構(gòu)，這些是他的語(yǔ)言實(shí)現(xiàn)的基礎(chǔ)。當(dāng)語(yǔ)言在一特定電腦上實(shí)現(xiàn)時(shí)，實(shí)現(xiàn)者首先確定表示語(yǔ)言的語(yǔ)義解釋的虛擬機(jī)，然後通過(guò)基本電腦提供的軟、硬體元素來(lái)構(gòu)造虛擬機(jī)。語(yǔ)言實(shí)現(xiàn)的組織和結(jié)構(gòu)由實(shí)現(xiàn)者的許多細(xì)微決策確定，需考慮電腦各種軟、硬體設(shè)施和使用代價(jià)。例：虛擬機(jī)如有整數(shù)加和平方根操作，則整數(shù)加可直接用硬體提供的整數(shù)加來(lái)實(shí)現(xiàn)，平方根可用軟體仿真，使用一個(gè)副程式。整數(shù)變數(shù)x可直接用存儲(chǔ)位置實(shí)現(xiàn)，該位置存放x的值；也可帶有標(biāo)記，由標(biāo)記和指針（擴(kuò)向存取x值的位置）構(gòu)成）。實(shí)現(xiàn)者還需確定什麼通過(guò)翻譯處理？什麼在執(zhí)行中解決？通常，如果在程式翻譯並建立運(yùn)行時(shí)結(jié)構(gòu)的過(guò)程中，採(cǎi)用了某些動(dòng)作，則可以使用一個(gè)特定的表示虛擬機(jī)數(shù)據(jù)結(jié)構(gòu)或操作的方式。如果實(shí)現(xiàn)者略去這些動(dòng)作而簡(jiǎn)化翻譯器，則不同的運(yùn)行時(shí)表示可能是必須的。三個(gè)因素導(dǎo)致相同語(yǔ)言的不同實(shí)現(xiàn)1、實(shí)現(xiàn)者虛擬機(jī)概念的不同（隱含在語(yǔ)言定義中）2、宿主機(jī)提供的設(shè)施的不同3、實(shí)現(xiàn)者如何用宿主機(jī)提供的設(shè)施仿真虛擬機(jī)元素的選擇和如何去構(gòu)造翻譯器支持這些虛擬機(jī)選擇的不同。電腦層次程式員以某種高級(jí)語(yǔ)言編程使用的虛擬機(jī)事實(shí)上形成了一個(gè)虛擬電腦層次。底層：實(shí)際的硬體電腦。通常程式員很少直接使用這個(gè)電腦，一般地，硬體機(jī)被一個(gè)或多個(gè)軟體層（或微程式）變換成一個(gè)虛擬機(jī)，它可能和硬體機(jī)有很大不同。二層：由稱(chēng)為操作系統(tǒng)的例程集合定義的虛擬機(jī)（如微程式形成第二層，那麼這也可稱(chēng)為第三層）。典型地，OS提供了一系列新的操作和數(shù)據(jù)結(jié)構(gòu)的仿真（這不是由硬體直接提供的）。如：外部檔結(jié)構(gòu)或檔管理原語(yǔ)。OS也從OS定義的虛擬機(jī)上刪去了某些硬體原語(yǔ)，使得它們不能由操作系統(tǒng)用戶(hù)直接訪(fǎng)問(wèn)。如：關(guān)於I/O、錯(cuò)誤監(jiān)測(cè)、多道程序設(shè)計(jì)和多道處理的硬體原語(yǔ)。OS定義的虛擬機(jī)通常就是高級(jí)語(yǔ)言實(shí)現(xiàn)者使用的機(jī)器。三層：語(yǔ)言實(shí)現(xiàn)者提供了一個(gè)新的軟體層，運(yùn)行於OS虛擬機(jī)上，仿真高級(jí)語(yǔ)言虛擬機(jī)的操作；也提供了翻譯器：將用戶(hù)程式翻譯成語(yǔ)言定義虛擬機(jī)的機(jī)器語(yǔ)言。四層：高級(jí)語(yǔ)言定義的虛擬機(jī)並不是層次的最後一層。實(shí)際上，程式員編制的程式形成了新的一層虛擬機(jī)。那麼，什麼是這個(gè)程式員定義的軟體仿真虛擬機(jī)的機(jī)器語(yǔ)言呢？（這個(gè)程式的輸入數(shù)據(jù)將由這個(gè)機(jī)器語(yǔ)言構(gòu)成或?qū)懗桑Ｒ坏┏淌絾T建立了一個(gè)程式，必須有一個(gè)“程式”在該程式定義的虛擬機(jī)上運(yùn)行，這個(gè)“程式”通過(guò)選擇合適的輸入數(shù)據(jù)集合而寫(xiě)成。這個(gè)概念之所以難於理解，是因?yàn)閷?duì)很多程式而言，輸入數(shù)據(jù)非常簡(jiǎn)單，僅僅可稱(chēng)為最平凡的程式設(shè)計(jì)語(yǔ)言。如：排序程式的機(jī)器語(yǔ)言可認(rèn)為是整數(shù)集，即以一定格式構(gòu)成的整數(shù)表為程式。然而，明顯的是：每一個(gè)在我們上述層次上構(gòu)造較低層次的程式員必須記住這個(gè)觀(guān)點(diǎn)，因?yàn)樵诿恳粚訕?gòu)造的程式和數(shù)據(jù)結(jié)構(gòu)事實(shí)上表示了下一層程式員編程使用的虛擬機(jī)的仿真。上面討論中一個(gè)隱含的中心概念是：程式和數(shù)據(jù)是等價(jià)的。我們習(xí)慣於在編程中將對(duì)象區(qū)分為“程式”和“數(shù)據(jù)”，這通常是一種有用的直覺(jué)的區(qū)分，但如上所討論，這種區(qū)分是一種表面性的。在某語(yǔ)境中的程式可能在另外的語(yǔ)境中變成數(shù)據(jù)。如：我們寫(xiě)Pascal程式，但對(duì)Pascal編譯器來(lái)說(shuō)，該程式是被輸入處理的數(shù)據(jù)，其輸出是機(jī)器語(yǔ)言程式。如果觀(guān)察程式的執(zhí)行，你會(huì)發(fā)現(xiàn)它又是執(zhí)行電腦中解釋器的數(shù)據(jù)。我們總是將某程式的輸入等價(jià)為將被處理的數(shù)據(jù)或?qū)⒈粓?zhí)行的程式。進(jìn)一步考慮這個(gè)問(wèn)題（等價(jià)性）。如：在C、Fortran語(yǔ)言中，表示可執(zhí)行程式的存儲(chǔ)空間通常是和其數(shù)據(jù)空間分開(kāi)的。但在LISP和Prolog中，則沒(méi)有不同，程式和數(shù)據(jù)是混合的，只有執(zhí)行過(guò)程可將其區(qū)分開(kāi)來(lái)。綁定和綁定時(shí)間不嚴(yán)格地說(shuō)，一個(gè)程式元素到某特定特徵或性質(zhì)的綁定，僅是從一個(gè)可能性質(zhì)的集合中性質(zhì)的簡(jiǎn)單選擇。決定這個(gè)選擇的程式陳述或處理的時(shí)間稱(chēng)為性質(zhì)對(duì)元素的綁定時(shí)間。語(yǔ)言中有不同的綁定和不同的綁定時(shí)間。綁定時(shí)間的類(lèi)型對(duì)綁定類(lèi)型沒(méi)有簡(jiǎn)單的分類(lèi)，但可區(qū)分出一些主要的綁定時(shí)間。這裏，我們基於一個(gè)基本假設(shè)：程式的處理總是先翻譯，後執(zhí)行。1、執(zhí)行時(shí)（運(yùn)行時(shí)）很多綁定是在程式執(zhí)行過(guò)程中完成的。如：變數(shù)到值的綁定，變數(shù)到特定存儲(chǔ)位置的綁定（在很多語(yǔ)言中）。進(jìn)一步可分為：a.進(jìn)入副程式或塊時(shí)。大多數(shù)語(yǔ)言中，重要的綁定只限制發(fā)生在執(zhí)行中進(jìn)入副程式或塊時(shí)，如C、Fortran中形參到實(shí)參、以及形參到特定存儲(chǔ)位置的綁定。b.在執(zhí)行中的任意點(diǎn)。某些綁定可以發(fā)生在程式執(zhí)行中的任意點(diǎn)，如：變數(shù)通過(guò)賦值到值的綁定，以及在LISP、ML中，名字到存儲(chǔ)位置的綁定。2、翻譯時(shí)（編譯時(shí)）綁定，可進(jìn)而分為三種：a.程式員選定的綁定寫(xiě)程式時(shí)，程式員有很多關(guān)於變數(shù)名、變數(shù)類(lèi)型、程式語(yǔ)句結(jié)構(gòu)等選擇的決定，這些決定代表了翻譯的綁定，語(yǔ)言翻譯器使用這些綁定確定目標(biāo)程式的最終形式。b.翻譯器選擇的綁定有些綁定由翻譯器決定，沒(méi)有直接的程式員規(guī)約。如：數(shù)據(jù)對(duì)象在為某過(guò)程分配的存儲(chǔ)區(qū)域中的相對(duì)位置（程式員不知道也不關(guān)心），數(shù)組如何存儲(chǔ)，數(shù)組描述子如何創(chuàng)建等。不同的語(yǔ)言實(shí)現(xiàn)可能以不同方式提供這些特性。c.裝配器選定的綁定（鏈接時(shí)）程式通常包含幾個(gè)子程式，這些副程式被合併為一個(gè)可執(zhí)行程式。翻譯器決定變數(shù)到每個(gè)副程式中存儲(chǔ)地址的綁定，這些存儲(chǔ)必須被分配物理機(jī)中的實(shí)際地址。3、語(yǔ)言實(shí)現(xiàn)時(shí)語(yǔ)言定義的某些方面可能對(duì)所有運(yùn)行於同一語(yǔ)言實(shí)現(xiàn)上的程式均是相同的，但可能由於語(yǔ)言實(shí)現(xiàn)不同而不相同。如：通常和數(shù)的表示以及算術(shù)操作的表示相關(guān)的細(xì)節(jié)由底層硬體機(jī)進(jìn)行算術(shù)的方式確定。以某語(yǔ)言編寫(xiě)的程式，如果使用了在實(shí)現(xiàn)時(shí)固定的特性，則不一定可以運(yùn)行在該語(yǔ)言的另一實(shí)現(xiàn)上，也可能有不同執(zhí)行結(jié)果。4、語(yǔ)言定義時(shí)語(yǔ)言的大多數(shù)結(jié)構(gòu)是在語(yǔ)言定義時(shí)固定的（對(duì)程式員寫(xiě)程式時(shí)可用的規(guī)約）。如：對(duì)程式員可以使用的選擇語(yǔ)句形式、數(shù)據(jù)結(jié)構(gòu)類(lèi)型、程式結(jié)構(gòu)等?？紤]下麵簡(jiǎn)單例子：X:=X+10，假定該語(yǔ)言為L(zhǎng)，則需考慮的綁定和綁字時(shí)間如下：1、變數(shù)X的可能類(lèi)型的集合變數(shù)X在語(yǔ)句中通常和某類(lèi)型相關(guān)聯(lián)，如實(shí)數(shù)、整數(shù)、布爾，X的允許類(lèi)型集合通常在語(yǔ)言定義時(shí)固定，如類(lèi)型只能是：實(shí)數(shù)，整數(shù)，布爾，集合，字元等。此外，語(yǔ)言可能允許程式定義新類(lèi)型，此時(shí)X的類(lèi)型綁定在翻譯時(shí)固定。2、X的類(lèi)型通常在翻譯時(shí)固定，通過(guò)顯式的聲明語(yǔ)句，如：FloatX。有些語(yǔ)言，如Smalltalk、Prolog，類(lèi)型綁定在運(yùn)行時(shí)完成（無(wú)類(lèi)型、弱類(lèi)型語(yǔ)言）。3、變數(shù)X的可能值的集合如X類(lèi)型為real，則其值集為實(shí)數(shù)，真實(shí)集應(yīng)為定義語(yǔ)言的虛擬機(jī)可表示和操作的實(shí)數(shù)，通常是可方便地在硬體機(jī)上表示和操作的實(shí)數(shù)。這樣，X的可能值集在語(yǔ)言實(shí)現(xiàn)時(shí)確定，也可能是在裝載時(shí)根據(jù)執(zhí)行程式的硬體機(jī)確定。4、變數(shù)X的值在執(zhí)行中某點(diǎn)，一特定值被約束到X。通常值是在執(zhí)行時(shí)通過(guò)對(duì)X的賦值而確定的。5、常量10的表示整數(shù)10的表示作為程式中的常量，使用串‘10’；執(zhí)行時(shí)，表示為位串。程式中十進(jìn)位的選擇通常在語(yǔ)言定義時(shí)決定（10也可能為2#的2），而特殊位串的選擇是語(yǔ)言實(shí)現(xiàn)時(shí)決定。6、操作符+的性質(zhì)符號(hào)+代表加法是在語(yǔ)言定義時(shí)確定。然而，+可以被重載（實(shí)數(shù)、整數(shù)、複數(shù)加等，根據(jù)語(yǔ)境確定）。在編譯型語(yǔ)言中，在編譯時(shí)確定，通常根據(jù)運(yùn)算元類(lèi)型判定。+的詳細(xì)定義依賴(lài)於底層硬體機(jī)。如X=2^49，則X+10可能在某一機(jī)器上沒(méi)有定義，因此，+的定義是在語(yǔ)言實(shí)現(xiàn)時(shí)確定，根據(jù)底層硬體機(jī)的定義。這樣：+表示加法在語(yǔ)言定義時(shí)定，每個(gè)加法操作在語(yǔ)言實(shí)現(xiàn)時(shí)定，符號(hào)+被綁定到特定加法操作是在翻譯時(shí)，每個(gè)特定加法對(duì)特定運(yùn)算元的值在運(yùn)行時(shí)定。綁定時(shí)間的重要性。在下面語(yǔ)言的分析和比較中，很多不同是由於綁定時(shí)間的不同。一定經(jīng)常不斷問(wèn)的問(wèn)題是：翻譯時(shí)做，還是執(zhí)行時(shí)做？語(yǔ)言中許多重要而微妙的不同是由於綁定時(shí)間的不同。例如：幾乎每個(gè)語(yǔ)言均允許數(shù)作為數(shù)據(jù)，並允許在其上的算術(shù)操作，但並不是每個(gè)語(yǔ)言均適合涉及大量算術(shù)編程問(wèn)題。ML和Fortran，均允許建立和運(yùn)算元值的數(shù)組，但ML不適合於求解需大數(shù)組和大量算術(shù)的問(wèn)題，而Fortran是合適的。原因：ML中，程式中大多數(shù)綁定是在執(zhí)行時(shí)，需要大量執(zhí)行時(shí)間來(lái)創(chuàng)建和消除綁定。Fortran中，大多數(shù)綁定是在編譯時(shí)，相同綁定的大部分在編譯時(shí)做一次，很少的工作在運(yùn)行時(shí)完成，因此，執(zhí)行更為高效。反過(guò)來(lái)，為什麼Fortran不適合於處理串，而ML更容易？原因也在於綁定時(shí)間。Fortran中大多數(shù)綁定在翻譯時(shí)完成，即在輸入數(shù)據(jù)被知道前，這樣它對(duì)執(zhí)行時(shí)有不同數(shù)據(jù)形式的情況不太合適，F(xiàn)ortran中串的大小和變數(shù)類(lèi)型需在編譯時(shí)確定。ML可在執(zhí)行中延遲到輸入數(shù)據(jù)已被檢查，且綁定已確定時(shí)，才確定大小和類(lèi)型。這兩種不同綁定分為早期綁定（early）和晚期綁定（late）。二者的優(yōu)、缺點(diǎn)圍繞的衝突是：效率和靈活性，如二者均需考慮，則應(yīng)提供選擇的靈活性，如Ada。綁定時(shí)間和語(yǔ)言實(shí)現(xiàn)語(yǔ)言定義通常允許指定綁定時(shí)間。 一個(gè)語(yǔ)言被設(shè)計(jì)使得某特定綁定可在，如翻譯時(shí)，完成。但實(shí)際的綁定時(shí)間只能在語(yǔ)言實(shí)現(xiàn)時(shí)決定。如：Pascal設(shè)計(jì)為允許變數(shù)類(lèi)型在編譯時(shí)確定，但某種實(shí)現(xiàn)可以允許在執(zhí)行時(shí)作類(lèi)型檢查。通常，一個(gè)語(yǔ)言設(shè)計(jì)指定綁定可能發(fā)生的最早時(shí)間。但很多實(shí)現(xiàn)事實(shí)上延遲這些綁定。然而，通常同一語(yǔ)言的大多數(shù)實(shí)現(xiàn)在相同時(shí)間完成大多數(shù)和綁定。如果一個(gè)語(yǔ)言設(shè)計(jì)為允許編譯時(shí)綁定，則延遲綁定將導(dǎo)致低效，還不一定取得太多的靈活恬。需要注意的是，通常語(yǔ)言中很小的變化會(huì)導(dǎo)致綁定時(shí)間的大變化，如：Fortran90允許遞歸，就修改了很多重要特性的綁定時(shí)間，因?yàn)榻壎〞r(shí)間是實(shí)現(xiàn)依賴(lài)的。2.3語(yǔ)言範(fàn)型前面討論了實(shí)際的電腦環(huán)境，它包含程式的翻譯後目標(biāo)碼，以及提供運(yùn)行時(shí)數(shù)據(jù)存儲(chǔ)和操作的虛擬機(jī)（為了目標(biāo)碼的執(zhí)行）。下麵將討論語(yǔ)言支持的計(jì)算模型（程式如何執(zhí)行？語(yǔ)言提供什麼種類(lèi)的結(jié)構(gòu)？）通常，不同語(yǔ)言的擁護(hù)者聚在一起，爭(zhēng)論的問(wèn)題常是：數(shù)組聲明的形式（C、Fortran中各不同）解釋和編譯的價(jià)值，等。然而，這些不同對(duì)語(yǔ)言間的差異並無(wú)本質(zhì)影響，語(yǔ)法上的不同只反映了設(shè)計(jì)者的希望，對(duì)寫(xiě)成的程式也無(wú)多大影響。有四種基本的計(jì)算模型：1、命令型語(yǔ)言（Imperativelanguage）也稱(chēng)過(guò)程型（procedural）、命令驅(qū)動(dòng)的、或面向語(yǔ)句的。其基本概念是機(jī)器狀態(tài)，程式由一組語(yǔ)句構(gòu)成，每各語(yǔ)句的執(zhí)行，將使得解釋器改變某些存儲(chǔ)位置的值，進(jìn)入新?tīng)顟B(tài)。程式形式一般為：statement1;statement2;…如圖示，記憶體包含一組盒子，語(yǔ)句的執(zhí)行（如將兩個(gè)變數(shù)相加而得到第三個(gè)變數(shù)）可被表示為訪(fǎng)問(wèn)存儲(chǔ)位置，以某種方式組合這些值，將結(jié)果存到新的位置。程式的開(kāi)發(fā)涉及建造連續(xù)的、要到達(dá)最終答案所需的機(jī)器狀態(tài)。即，建立連續(xù)的機(jī)器狀態(tài)，最終達(dá)到結(jié)果。大多數(shù)傳統(tǒng)語(yǔ)言?huà)?cǎi)用這種模型，遵循傳統(tǒng)電腦的結(jié)構(gòu)，順序地執(zhí)行指令。2、作用型語(yǔ)言（applicative）另一種看待語(yǔ)言完成的計(jì)算的視角是：看程式所表示的功能，而不是程式執(zhí)行時(shí)的狀態(tài)變化。我們只觀(guān)察希望的結(jié)果，而不是可用的數(shù)據(jù)。即不關(guān)心機(jī)器為得到結(jié)果所經(jīng)過(guò)的狀態(tài)順序。這樣問(wèn)題就變成：這個(gè)函數(shù)（功能）是什麼？它通過(guò)訪(fǎng)問(wèn)初始變數(shù)集，而被作用到初始機(jī)器狀態(tài)，以特殊方式組合，得到結(jié)果。程式開(kāi)發(fā)：以已有函數(shù)為基礎(chǔ)開(kāi)發(fā)新的複雜函數(shù)，最終的函數(shù)作用將得到結(jié)果。程式執(zhí)行：連續(xù)的函數(shù)變換，f1(f2(f3(……))。通常也稱(chēng)函數(shù)式語(yǔ)言。引用透明性是一個(gè)主要特徵。3、基於規(guī)則的語(yǔ)言（邏輯型語(yǔ)言）檢查當(dāng)前條件，當(dāng)其得到滿(mǎn)足時(shí)，執(zhí)行合適的動(dòng)作。如圖25，使用過(guò)濾集作用到數(shù)據(jù)存儲(chǔ)上以使能狀態(tài)變化。其執(zhí)行類(lèi)似命令式語(yǔ)言，但語(yǔ)句不是順序的，使能條件將決定執(zhí)行順序。使能條件1→動(dòng)作1使能條件2→動(dòng)作2┋使能條件n→動(dòng)作nProlog語(yǔ)言?huà)?cǎi)用這種範(fàn)型。其他如決策表的業(yè)務(wù)應(yīng)用也是一種基於規(guī)則的程式設(shè)計(jì)。4、OO語(yǔ)言當(dāng)前最重要、流行的計(jì)算模型。建立複雜數(shù)據(jù)對(duì)象，限定該對(duì)象上的操作集合，並封裝在一起。複雜對(duì)象是簡(jiǎn)單對(duì)象的擴(kuò)展，繼承簡(jiǎn)單對(duì)象的性質(zhì)。實(shí)際上使用了其他兩種計(jì)算模型的優(yōu)點(diǎn)，具體數(shù)據(jù)對(duì)象——有命令型語(yǔ)言的效率，限定功能類(lèi)到具體數(shù)據(jù)對(duì)象——應(yīng)用型模型的靈活性和可靠性。計(jì)算模型概論前面的討論，我們使用“支持”，而不是“實(shí)現(xiàn)”某計(jì)算模型。語(yǔ)言的使用依賴(lài)於程式員。 命令型語(yǔ)言適合面向語(yǔ)句的程式設(shè)計(jì)，但也可以用LISP、Prolog寫(xiě)出實(shí)質(zhì)上順序執(zhí)行並完成相同功能的程式。用C語(yǔ)言也可以寫(xiě)出具有函數(shù)調(diào)用的程式——作用型。歷史上：命令型語(yǔ)言最早廣泛使用，一直佔(zhàn)據(jù)統(tǒng)治地位。70—80年代，作用型語(yǔ)言提供了驗(yàn)證和證明程式正確的好方式。圖2.6（a）無(wú)結(jié)構(gòu)的流程圖。程式?jīng)]有明顯的結(jié)構(gòu)。圖2.6（b）結(jié)構(gòu)化圖，可分為4個(gè)功能函數(shù)，因此，也可算作用型，有4個(gè)函數(shù)。第三章語(yǔ)言翻譯3.1語(yǔ)言的語(yǔ)法語(yǔ)法：?jiǎn)卧~作為語(yǔ)句中元素的顯示它們之間關(guān)係的佈局。描述了構(gòu)成有效程式的符號(hào)序列。如C中，x=y+z是有效的符號(hào)序列，而xy+－則不是。語(yǔ)法提供了理解程式需要的有意義的資訊。也提供了大量根源程式到目標(biāo)程式翻譯所需的資訊。單靠語(yǔ)法並不足以無(wú)二義地刻劃語(yǔ)句的結(jié)構(gòu)。如：x=2.45+3.67，語(yǔ)法並不能告訴我們x是否被聲明或是否聲明為實(shí)數(shù)。x=5,6或6.12均是可能的。因此，對(duì)語(yǔ)言的完整描述單靠語(yǔ)法結(jié)構(gòu)是不夠的，還需涉及語(yǔ)義。如：聲明的使用、操作、順序控制和引用環(huán)境等影響變數(shù)，並不總是由語(yǔ)法決定。雖然如此，語(yǔ)法仍是語(yǔ)言描述中的重要屬性?，F(xiàn)在，語(yǔ)法描述已是一個(gè)解決了的問(wèn)題，根源程式的語(yǔ)法理解階段是相當(dāng)機(jī)械的，YACC等工具可自動(dòng)生成給定程式的語(yǔ)法描述。一般語(yǔ)法準(zhǔn)則語(yǔ)法的主要目的是為程式員和語(yǔ)言處理器間通訊提供一套注記方法。而特殊語(yǔ)法結(jié)構(gòu)的選擇被限制於特殊的資訊項(xiàng)通訊。例如：某特定變數(shù)有類(lèi)型實(shí)數(shù)，可以用多種方式表達(dá)。可以是顯示聲明或隱含的命名約定，等。語(yǔ)法細(xì)節(jié)的選擇大部分是基於第二準(zhǔn)則，如可讀性，它和通訊的主要目標(biāo)無(wú)關(guān)。有很多二級(jí)準(zhǔn)則，通常可按其目標(biāo)分類(lèi)，分為：易讀、易寫(xiě)、易翻譯、無(wú)二義等目標(biāo)。這些目標(biāo)間有時(shí)會(huì)有衝突。易讀性（Readabitity）程式是易讀的，如果程式表示的演算法和數(shù)據(jù)的結(jié)構(gòu)可從程式文本的檢查明顯瞭解。一個(gè)易讀的程式，通常稱(chēng)為自文檔的（不需其他用於理解的輔助文檔）。增加易讀性的方式：自然的語(yǔ)句格式、結(jié)構(gòu)化語(yǔ)句、關(guān)鍵字和噪音字的自由使用、嵌入式注釋機(jī)制、不限長(zhǎng)識(shí)別字，記憶操作符、自由域格式、完全的數(shù)據(jù)聲明等。易讀性並不能由語(yǔ)言設(shè)計(jì)保證，最好的設(shè)計(jì)也可能由於糟糕的編程而破壞。當(dāng)然，語(yǔ)法設(shè)計(jì)也可能使最有意識(shí)的程式員寫(xiě)出難理解的程式，如APL。COBOL強(qiáng)調(diào)易讀，但其代價(jià)是犧牲了易寫(xiě)和易翻譯。增加易讀性—語(yǔ)法不同應(yīng)反映語(yǔ)義不同，做相似事的程式結(jié)構(gòu)是相似的。做不同事的程式其結(jié)構(gòu)需有明顯不同。語(yǔ)言如只提供了少數(shù)不同語(yǔ)法結(jié)構(gòu)，通常導(dǎo)致程式易讀性差。如APL，SNOBOL4等，只提供一種語(yǔ)句格式，賦值、副程式調(diào)用、簡(jiǎn)單GOTO、副程式返回，多路條件分支、及其它常見(jiàn)程式結(jié)構(gòu)的差異只能通過(guò)個(gè)別操作子的不同來(lái)反應(yīng)。易寫(xiě)性易寫(xiě)性（使用簡(jiǎn)明的、規(guī)則的語(yǔ)法結(jié)構(gòu)）通常和易讀性（冗餘結(jié)構(gòu)是有幫助的）相衝突。隱含的語(yǔ)法約定允許聲明和操作不需刻劃，從而使程式更短、更易寫(xiě)，但不易讀。其他特性對(duì)兩個(gè)目標(biāo)均有增強(qiáng)：如結(jié)構(gòu)化語(yǔ)句、簡(jiǎn)單自然語(yǔ)句格式、記憶操作符、未限制標(biāo)記符等通常使程式易寫(xiě)，通過(guò)允許在程式中直接表示問(wèn)題的演算法和數(shù)據(jù)的自然結(jié)構(gòu)。語(yǔ)法稱(chēng)為冗餘的，如果以多種方式傳達(dá)同樣的資訊。有些冗餘性有用的，因它允許程式易讀，並允許翻譯時(shí)錯(cuò)誤檢測(cè)。缺點(diǎn)是不易寫(xiě)。大多數(shù)缺省規(guī)則（針對(duì)語(yǔ)言結(jié)構(gòu)含義）試圖減少冗餘，通過(guò)刪去某些顯式的含義陳述，因?yàn)檫@些含義可從語(yǔ)境中導(dǎo)出。例，F(xiàn)ortran中約定，I-N打頭的變數(shù)為整型，其他為實(shí)數(shù)，這樣不需聲明，但缺點(diǎn)是有副作用，如：拼寫(xiě)錯(cuò)誤不能被編譯器檢測(cè)到，例如：INDEX被寫(xiě)成INDX→則變成新變數(shù)。易驗(yàn)證性和易讀、易寫(xiě)相關(guān)的概念是程式正確性或程式驗(yàn)證。多年經(jīng)驗(yàn)表明，理解每條程式語(yǔ)言語(yǔ)句是容易的，創(chuàng)建正確程式的整個(gè)過(guò)程卻是困難的。因此，需有技術(shù)，使得能數(shù)學(xué)地證明程式是正確的。易翻譯性即易於翻譯成可執(zhí)行形式。易讀性和易寫(xiě)性是面向程式員的需要。易翻譯性（關(guān)鍵是結(jié)構(gòu)的正則性）是面向翻譯器（處理被寫(xiě)成的程式）的需要。如LISP程式，不易讀、也不易寫(xiě)、但易於翻譯，主要由於其語(yǔ)法簡(jiǎn)單且正則。當(dāng)特殊語(yǔ)法結(jié)構(gòu)增加，將導(dǎo)致翻譯困難，如COBOL，允許大量的語(yǔ)句和聲明形式。沒(méi)有含混性含混性是語(yǔ)言設(shè)計(jì)中的一個(gè)中心問(wèn)題。一個(gè)語(yǔ)言定義理想地為每個(gè)語(yǔ)法結(jié)構(gòu)提供唯一的意義。而含混性結(jié)構(gòu)允許兩個(gè)或多個(gè)不同解釋。通常不是由個(gè)體程式元素的結(jié)構(gòu)產(chǎn)生，而是由於不同結(jié)構(gòu)的交迭。例如：ifBooleanexpthenstatement1elsestatement2.IfBooleanexpthenstatement1當(dāng)兩種形式組合時(shí)，有可能出現(xiàn)二義情況。Fortran中，A（I，J）可能是數(shù)組元素，也可能是函數(shù)調(diào)用。事實(shí)上，上面提到的含混在語(yǔ)言中均有解決方案。條件語(yǔ)句的兩種不同解釋?zhuān)豪阂蚪M合而形成的懸空else：IfBooleanexp1thenifBooleanexp2thenstat1elsestat2Algol解決方案：改變語(yǔ)法，引入分界符begin…end。Ada解決方案：每個(gè)if語(yǔ)句必須以endif分界符結(jié)尾。C和Pascal解決方案：從二義結(jié)構(gòu)中任選一種解釋。對(duì)本例而言，最後的else總是和最近的then配對(duì)。FORTRAN中函數(shù)調(diào)用和數(shù)組引用的二義性由規(guī)則解決：A(I,J)被視為函數(shù)調(diào)用，如果沒(méi)有數(shù)組A的聲明。但這個(gè)假定只能在程式裝載、鏈接時(shí)被檢查。Pascal中區(qū)分二者的方法是使用不同的括弧，如：[…]用於界定數(shù)組參數(shù)，(…)用於界定函數(shù)調(diào)用的參數(shù)。語(yǔ)言的語(yǔ)法元素語(yǔ)言的語(yǔ)法風(fēng)格由各種基本語(yǔ)法元素的選取所決定。字元集字元集的選擇是語(yǔ)言設(shè)計(jì)的第一件事。已有一些標(biāo)準(zhǔn)字元集，如：ASCII碼。通常是選擇一個(gè)標(biāo)準(zhǔn)的字元集。 但也有不標(biāo)準(zhǔn)的，如APL。字元集的選擇對(duì)確定可被用於語(yǔ)言實(shí)現(xiàn)的I/O設(shè)備的類(lèi)型是非常重要的。如：C的字元集可用於大多數(shù)I/O設(shè)備。而APL的字元集則不能直接用於大多數(shù)I/O設(shè)備。通常用8位來(lái)表示字元（60年代早期用6位），這似乎是足夠的。但是，隨著電腦產(chǎn)業(yè)的國(guó)際化進(jìn)程，可能16位表示是必需的（可有65536個(gè)字元）。識(shí)別字字和數(shù)字串，以字母開(kāi)頭——常用的選擇。也可能使用特殊字元，如用.或-來(lái)改善易讀性和長(zhǎng)度限制。操作符符號(hào)+，-，*，/表示基本演算法操作。通常原操作可完全使用特殊符號(hào)。當(dāng)然，也可以使用識(shí)別字來(lái)表示原操作，如LISP中的PLUS、TIMES。大多數(shù)語(yǔ)言?huà)?cǎi)用二者的組合。關(guān)鍵字和保留字關(guān)鍵字——用於語(yǔ)句語(yǔ)法中固定部分的識(shí)別字。保留字——不能被程式員使用的關(guān)鍵字。大多數(shù)語(yǔ)言使用保留字以改善翻譯器的錯(cuò)誤檢測(cè)能力，使語(yǔ)法分析更為容易。雜訊字可選的字，被插入語(yǔ)句中以改善易讀性。如：COBOL中Go語(yǔ)句可寫(xiě)為GOTO注釋是文檔中的重要部分，幾種注釋方式：1、分別的注釋行，F(xiàn)ortran2、特殊標(biāo)誌界定，/**/，界定字元丟失可能導(dǎo)致大面積出錯(cuò)。3、在行中任意地方開(kāi)始，但在行末結(jié)束，如C++的//空白（空格）語(yǔ)言中常使用空白規(guī)則，通常都是作為分隔符號(hào)。 也有的語(yǔ)言中空格有其他用途。界定符（分界符）和括弧用於標(biāo)記語(yǔ)法單位的開(kāi)始和結(jié)束括弧是一對(duì)分界符。自由和固定域格式自由域——語(yǔ)句可寫(xiě)在任何地方固定域——在輸入行中通過(guò)位置來(lái)傳遞資訊。Fortran是典型例子。當(dāng)前固定域越來(lái)越少。運(yùn)算式訪(fǎng)問(wèn)程式中數(shù)據(jù)對(duì)象並反回值，是基本的語(yǔ)法建築塊。在命令型語(yǔ)言中，運(yùn)算式形成基本操作，狀態(tài)被語(yǔ)句所改變。在作用型語(yǔ)言中，運(yùn)算式形成了驅(qū)動(dòng)程式執(zhí)行的基本順序控制。語(yǔ)句是命令型語(yǔ)言中最主要的語(yǔ)法部件。語(yǔ)句的語(yǔ)法對(duì)語(yǔ)言整體的正則性、易讀性和易寫(xiě)性有著關(guān)鍵影響。有的語(yǔ)言?huà)?cǎi)用單一語(yǔ)句格式，強(qiáng)調(diào)正則性；而其他語(yǔ)言對(duì)不同語(yǔ)句類(lèi)型使用不同語(yǔ)法，著重於易讀性。語(yǔ)句結(jié)構(gòu)中的一個(gè)更重要的差異是：結(jié)構(gòu)性（或嵌套）語(yǔ)句和簡(jiǎn)單語(yǔ)句。程式——副程式結(jié)構(gòu)分開(kāi)的副程式定義Fortran中， 每個(gè)副程式定義被處理為分開(kāi)的語(yǔ)法單元，每個(gè)副程式被分別編譯，被編譯程序在裝載時(shí)鏈接。這種組織方式主要是針對(duì)這樣一種情況：每個(gè)副程式均需含所有數(shù)據(jù)元素的完整數(shù)據(jù)聲明，即使是對(duì)那些在COMMON塊中的或與其它副程式共用的數(shù)據(jù)。需要這些聲明主要是由於分開(kāi)編譯的需要?；镜母背淌絾卧渺侗硎就ǔＬ峁┫嚓P(guān)功能的結(jié)構(gòu)。分開(kāi)的數(shù)據(jù)定義把所有操作於給定數(shù)據(jù)對(duì)象之上的操作組合在一起，如C++中類(lèi)。主要是基於數(shù)據(jù)抽象的原則。嵌套的副程式定義如PASCAL，副程式定義在主程序中作為聲明出現(xiàn)，副程式本身又可含有其他副程式定義。其目標(biāo)是強(qiáng)調(diào)結(jié)構(gòu)化的語(yǔ)句，但事實(shí)上產(chǎn)生了不同用途。結(jié)構(gòu)化語(yǔ)句的引入主要是為演算法結(jié)構(gòu)的常見(jiàn)的層次劃分提供一種自然的注記方式，但嵌套子程式定義為編譯時(shí)定義的副程式提供了非局部的作用環(huán)境。從而允許靜態(tài)類(lèi)型檢查，和有效的可執(zhí)行代碼的生成。沒(méi)有副程式定義的嵌套，則必須為每個(gè)在副程式定義中的非局部變數(shù)提供聲明，或?qū)⑺蟹蔷植恳玫念?lèi)型檢查推遲到運(yùn)行時(shí)。嵌套的另一好處是作用域管理。允許副程式名具有較少的作用域。

分開(kāi)的介面定義FORTRAN的結(jié)構(gòu)允許分開(kāi)副程式的非常容易的編譯，但缺點(diǎn)是不同副程式共用的數(shù)據(jù)可能有不同的定義，而這種不同是編譯器在編譯時(shí)無(wú)法檢測(cè)到的。PASCAL允許編譯器訪(fǎng)問(wèn)所有這樣的定義以幫助發(fā)現(xiàn)錯(cuò)誤，缺點(diǎn)是全部程式，即使其有上千條語(yǔ)句，必須在每次修改後重新編譯。結(jié)合上面的技術(shù)可以改善編譯行為。程式實(shí)現(xiàn)由幾個(gè)相互交互的副程式構(gòu)成，這些部件稱(chēng)為模組，將被連接在一起以創(chuàng)建可執(zhí)行程式，但每次只有修改的模組被重編譯。而在一個(gè)部件中的過(guò)程間傳送的數(shù)據(jù)必須具有公共聲明，從而允許編譯器的高效檢查。為了在分開(kāi)的編譯模組間傳遞數(shù)據(jù)，引入了規(guī)約部件，如C中.h檔。Ada中的Package（介面定義規(guī)約+實(shí)現(xiàn)體）。數(shù)據(jù)描述和可執(zhí)行語(yǔ)句分離COBOL包含了早期的部件結(jié)構(gòu)形式。在COBOL中，所有副程式的數(shù)據(jù)聲明和可執(zhí)行語(yǔ)句被分入不同的程式中，即數(shù)據(jù)段和過(guò)程段，而用環(huán)境段包含關(guān)於外部操作環(huán)境的聲明。一個(gè)程式的過(guò)程段被組織為子單元，以對(duì)應(yīng)副程式體，但所有數(shù)據(jù)對(duì)所有副程式均是全局的，沒(méi)有東西對(duì)應(yīng)於通常副程式中的局部數(shù)據(jù)。中心化數(shù)據(jù)段的優(yōu)點(diǎn)是：強(qiáng)迫形成數(shù)據(jù)格式和過(guò)程段中演算法的邏輯獨(dú)立性，數(shù)據(jù)結(jié)構(gòu)的細(xì)小修改可只修改數(shù)據(jù)段而不需修改過(guò)程段。同時(shí)將數(shù)據(jù)描述搜集到一個(gè)地方，而不是散佈在副程式中也是方便的方式。這適合於大量數(shù)據(jù)的處理。在某種意義是，資料庫(kù)應(yīng)用是這種形式的擴(kuò)展。未分離的副程式定義不分開(kāi)主程序和副程式語(yǔ)句，如SNOBOL4中，程式是一個(gè)語(yǔ)句表。副程式間沒(méi)有語(yǔ)法分隔，函數(shù)調(diào)用開(kāi)始新的副程式執(zhí)行，返回語(yǔ)句結(jié)束該副程式。程式作為是動(dòng)態(tài)的。事實(shí)上，任意語(yǔ)句可以同時(shí)是主程序的一部分，也可以是副程式的一部分。這體現(xiàn)在該語(yǔ)句可在主程序的執(zhí)行中某點(diǎn)被執(zhí)行，而後又在某副程式的執(zhí)行中某點(diǎn)被執(zhí)行。這種混沌結(jié)構(gòu)僅僅對(duì)允許運(yùn)行時(shí)翻譯和相對(duì)簡(jiǎn)單的新語(yǔ)句和副程式執(zhí)行機(jī)制具有價(jià)值。BASIC簡(jiǎn)單的語(yǔ)法，和前述設(shè)計(jì)目標(biāo)均有衝突。主要面向非科學(xué)家用戶(hù)。3.2翻譯的階段邏輯上，翻譯可分為兩個(gè)主要部分（輸入根源程式的分析，可執(zhí)行目標(biāo)程式的綜合），兩個(gè)階段又可細(xì)分。大多數(shù)翻譯器的中這些邏輯階段不是可以明確劃分開(kāi)的，而是混合在一起使得分析和綜合交替進(jìn)行（通常逐條語(yǔ)句進(jìn)行）。編譯器通常對(duì)根源程式掃描兩遍第一遍將程式分解為部件並從程式中導(dǎo)出資訊。第二遍根據(jù)這些收集的資訊生成目標(biāo)程式。如果編譯速度是重要的考慮（如教學(xué)用編譯器），一遍掃描是常用方式，在程式被分析時(shí)，立即被翻譯為目標(biāo)代碼。如果執(zhí)行速度是重要考慮，三遍甚至更多遍掃描也是可能的。第一遍分析根源程式。第二遍使用各種定義好的優(yōu)化演算法將根源程式重寫(xiě)為更多效的形式。第三遍生成目標(biāo)代碼。根源程式的分析語(yǔ)法分析將根源程式字元流分隔、分組，成為一些基本的構(gòu)成成分，如： 識(shí)別字、分界符、操作符、數(shù)、關(guān)鍵字、噪音字、空白、注釋等。這些稱(chēng)為語(yǔ)法項(xiàng)，Token。語(yǔ)法分析（parsing）標(biāo)識(shí)大的程式結(jié)構(gòu)（語(yǔ)句，聲明、運(yùn)算式等）（基於前面得到的Token）。通常語(yǔ)法分析和語(yǔ)義分析交替進(jìn)行（使用棧作為通訊工具）。語(yǔ)法分析器向棧中輸入各種語(yǔ)法單元元素，語(yǔ)義分析器檢索並處理。需要高效的語(yǔ)法分析技術(shù)，主要基於形式化文法的應(yīng)用。語(yǔ)義分析——翻譯的中心階段處理語(yǔ)法分析器識(shí)別的語(yǔ)法結(jié)構(gòu)，並開(kāi)始形成可執(zhí)行目標(biāo)碼的結(jié)構(gòu)，語(yǔ)義分析是分析和綜合間的橋樑。這階段的工作包括一些重要工作，如符號(hào)表維護(hù)、大多數(shù)錯(cuò)誤檢測(cè)，宏擴(kuò)展以及編譯時(shí)語(yǔ)句的執(zhí)行。在簡(jiǎn)單情況下，語(yǔ)義分析器直接生成可執(zhí)行代碼，但大多數(shù)情況下，是產(chǎn)生最終可執(zhí)行程式的某種內(nèi)部格式，然後被優(yōu)化處理。語(yǔ)義分析器可分為一些小的語(yǔ)義分析器，各自處理一特殊類(lèi)型的程式結(jié)構(gòu)。它們之間通過(guò)存放在各種數(shù)據(jù)結(jié)構(gòu)、特別是中心符號(hào)表中的資訊而進(jìn)行交互。常見(jiàn)的語(yǔ)法分析功能：1、符號(hào)表維護(hù)符號(hào)表（最早由詞法分析形成）含有對(duì)程式中不同識(shí)別字的表項(xiàng)（不僅含識(shí)別字，還包含涉及識(shí)別字屬性的附加數(shù)據(jù)，如：識(shí)別字類(lèi)型，值類(lèi)型，引用環(huán)境等。）語(yǔ)義分析器在處理聲明、副程式頭、語(yǔ)句等時(shí)，填入相關(guān)資訊。編譯型語(yǔ)言的符號(hào)表在翻譯結(jié)構(gòu)後通常丟棄。但有的語(yǔ)言在執(zhí)行時(shí)仍保留，如：允許運(yùn)行時(shí)創(chuàng)建新識(shí)別字的語(yǔ)言（ML、LISP等，符號(hào)表是運(yùn)行時(shí)的中心數(shù)據(jù)結(jié)構(gòu)），以及輔助調(diào)試（dbx使用運(yùn)行時(shí)符號(hào)表來(lái)調(diào)試C程式）。2、隱含資訊的插入在根源程式中，有的資訊經(jīng)常是隱含的，必須在低級(jí)目標(biāo)程式中顯式化。這類(lèi)隱含資訊包括：一些缺省約定資訊，類(lèi)型推導(dǎo)資訊等。3、錯(cuò)誤檢測(cè)語(yǔ)法和語(yǔ)義分析器必須能夠處理不正確的和正確的程式。語(yǔ)法分析器可能會(huì)接受到和當(dāng)時(shí)語(yǔ)境不相容的詞法項(xiàng)，如：運(yùn)算式中出現(xiàn)分界符，語(yǔ)句序列中出現(xiàn)聲明等。更微妙的錯(cuò)誤有：實(shí)數(shù)變數(shù)出現(xiàn)在需要整數(shù)的地方，對(duì)聲明只有二維的數(shù)組出現(xiàn)三維下標(biāo)引用等。屬語(yǔ)義錯(cuò)。語(yǔ)義分析器不僅需要能夠識(shí)別這樣的錯(cuò)誤並產(chǎn)生適當(dāng)?shù)某鲥e(cuò)消息，還必須能夠在大多數(shù)情況下，確定合適的方式以繼續(xù)剩餘程式的語(yǔ)法分析工作。4、宏處理和編譯時(shí)操作並非所有語(yǔ)言具有宏特徵和編譯時(shí)操作。但如果具備，通常在語(yǔ)義分析中處理。語(yǔ)義分析器必須識(shí)別宏調(diào)用並處理宏替換。通常，該任務(wù)需要中斷詞法和語(yǔ)法處理，而讓它們?nèi)ヌ幚砗牦w中的字元流。另一個(gè)方法是宏體可能已預(yù)先被部分翻譯，語(yǔ)義分析器可以直接處理，在繼續(xù)根源程式分析前插入適當(dāng)?shù)哪繕?biāo)碼並建立合適的表項(xiàng)。用於控制翻譯。編譯時(shí)操作是在翻譯中完成的操作，用於控制根源程式的翻譯。C中提供了大量這樣的操作。如：#define允許常量或運(yùn)算式在程式被編譯前計(jì)值。#ifdef允許不同的代碼序列被編譯，根據(jù)某些變數(shù)的存在與否。這些設(shè)施允許程式員修改被編譯的語(yǔ)句序列。目標(biāo)程式的綜合翻譯的最後階段是根據(jù)語(yǔ)義分析的結(jié)果，構(gòu)造可執(zhí)行程式。優(yōu)化語(yǔ)義分析器通常以某種中間形式來(lái)產(chǎn)生可執(zhí)行程式，中間形式可以是操作符和運(yùn)算元的串，也可以是操作符和運(yùn)算元序列的表。在代碼生成前，對(duì)中間形式進(jìn)行優(yōu)化處理是必要的。代碼生成在中間形式被優(yōu)化後，必須產(chǎn)生最後的輸出結(jié)果：可執(zhí)行程式。它可能是組合語(yǔ)言語(yǔ)句、機(jī)器代碼序列或其他目標(biāo)形式。它可能能夠直接執(zhí)行，也可能需要鏈接裝載後才可執(zhí)行。連接和裝載形成最終可運(yùn)行程式。3.3形式翻譯模型編譯器理論的語(yǔ)法識(shí)別部分是相當(dāng)標(biāo)準(zhǔn)的，通?；渡舷挛臒o(wú)關(guān)理論。語(yǔ)言語(yǔ)法的形式定義通常稱(chēng)為文法（grammar）一個(gè)文法由一個(gè)規(guī)則集合組成，規(guī)則被稱(chēng)為產(chǎn)生式，刻劃了形成允許程式的字元序列。一個(gè)形式文法是用嚴(yán)格定義的記號(hào)體系刻劃的文法。編譯技術(shù)中常用兩類(lèi)文法。BNF文法（上下無(wú)關(guān)文法）正則文法BNF文法Backus-NaurForm。JohnBackus開(kāi)發(fā)，用於Algol語(yǔ)言的語(yǔ)法定義。PeterNaur是開(kāi)發(fā)Algol委員會(huì)的主席。幾乎同時(shí)，語(yǔ)言學(xué)家NoamChomsky設(shè)計(jì)了上下文無(wú)關(guān)文法來(lái)定義自然語(yǔ)言的語(yǔ)法。在能力上，二者是等價(jià)的，差異只是符號(hào)體系不同。語(yǔ)法BNF文法包含一個(gè)BNF文法規(guī)則的有限集合，它定義了一個(gè)語(yǔ)言。語(yǔ)法僅僅涉及形式而不涉及含義，一個(gè)語(yǔ)言從語(yǔ)法上考慮，由一個(gè)語(yǔ)法正確的程式集合構(gòu)成，每個(gè)程式只簡(jiǎn)單地是一個(gè)字元序列。語(yǔ)法正確的程式不一定有語(yǔ)義，即可能不一定計(jì)算出什麼結(jié)果，甚至沒(méi)有結(jié)果。不考慮語(yǔ)義，語(yǔ)言是任意有限字串的集合，這些字元選自某固定符號(hào)集。因此，下麵均為語(yǔ)言1、所有C中賦值語(yǔ)句的集合2、所有C程式的集合3、所有LISP原子的集合4、a、b.構(gòu)成的序列的集合，所有a在所有b之前。語(yǔ)言可包含有限的串集合，也可能包含無(wú)限的串集合?？紤]上面例子，可發(fā)現(xiàn)用自然語(yǔ)言描述語(yǔ)言帶來(lái)了一些問(wèn)題，如：4例中，b是否是語(yǔ)言的成員？是否串上必須有a？因此，描述並不完整。解決這個(gè)問(wèn)題的方法：給出形式的數(shù)學(xué)規(guī)則集合，準(zhǔn)確地確定語(yǔ)言中的串是什麼？最簡(jiǎn)單的文法規(guī)則是列出有限語(yǔ)言的所有元素，如：<digit>:=0|1|2|3…8|9這裏<digit>表示一個(gè)非終結(jié)符或語(yǔ)法範(fàn)疇，0－9為終結(jié)符。一旦定義了基本的語(yǔ)法非終結(jié)符集合，可以構(gòu)造更複雜的串，如：<conditionalstatement>::=If<Booleanexp>then<statement>else<statement>|if<Booleanexp>then<statement>規(guī)則定義的非終結(jié)符可本身被用在規(guī)則中，從而形成遞歸規(guī)則。<unsignedinteger>::=<digit>|<unsignedinteger><digit>一個(gè)更複雜的文法，定義一組簡(jiǎn)單賦值語(yǔ)句。語(yǔ)法分析樹(shù)（parsetree）給定文法，可使用單替換規(guī)則生成語(yǔ)言的串。如：下麵文法生成平衡的括弧序列：S→SS|（S）|（）一個(gè)推導(dǎo)過(guò)程：S→（S）→（SS）→（（）S）→（（）（））推導(dǎo)中的每個(gè)項(xiàng)稱(chēng)為語(yǔ)句形式。語(yǔ)言是語(yǔ)句形式的集合，每個(gè)語(yǔ)句形式只含有終結(jié)符，並可從文法的初始符號(hào)推導(dǎo)出來(lái)。為了確定是否一給定串是一個(gè)文法定義的語(yǔ)言的語(yǔ)法合格程式。我們必須使用文法規(guī)則去構(gòu)造串的語(yǔ)法分析，如成果地分析，則是該語(yǔ)言的程式。賦值語(yǔ)句W=Y*(U+V)的語(yǔ)法分析樹(shù)：BNF文法將一個(gè)結(jié)構(gòu)賦給語(yǔ)言中的每個(gè)串。注意，被賦的結(jié)構(gòu)實(shí)質(zhì)上是一棵樹(shù)，這是由於BNF文法的限制。樹(shù)的葉節(jié)點(diǎn)是單個(gè)字元或詞法項(xiàng)，中間的分叉點(diǎn)是一個(gè)語(yǔ)法範(fàn)疇，由非終結(jié)符標(biāo)記，根節(jié)點(diǎn)是表示整個(gè)語(yǔ)言的非終結(jié)符。分析樹(shù)為程式提供了大部分的直覺(jué)的語(yǔ)義結(jié)構(gòu)。同樣的語(yǔ)言可被很多不同文法定義，如圖3.5定義的語(yǔ)言和圖3.3是一樣的。不能用BNF文法定義的語(yǔ)法是那些涉及上下文依賴(lài)的語(yǔ)法，如：如下限制不能用BNF刻劃。同樣的識(shí)別字不能在相同塊中聲明兩次。每個(gè)識(shí)別字必須聲明在包括其使用點(diǎn)的塊中。一個(gè)用二維聲明的數(shù)組不能用三個(gè)下標(biāo)引用。此類(lèi)限制必須用對(duì)顯式化BNF的補(bǔ)遺來(lái)定義。賦值語(yǔ)句的另一個(gè)BNF定義：含混性（二義性）多義性通常是文法中的問(wèn)題，而不一定是語(yǔ)言的問(wèn)題。如：G1：S→SS|0|1具有二義性，如圖3.6所示。如果對(duì)給定語(yǔ)言的每個(gè)文法均是含混的，則稱(chēng)語(yǔ)言是固有含混的。然而上面G1文法描述的語(yǔ)言不是含混的，因?yàn)榭梢詾樗鼘?xiě)出不含混的文法。

G2：T→0T|1T|0|1BNF記號(hào)法的擴(kuò)展BNF文法比較簡(jiǎn)單，但用於描述語(yǔ)言卻有諸多不便。將其適當(dāng)擴(kuò)展後更易用?？蛇x性元素用[……]表示。選擇用|表示。重複用{……}*表示。圖3.7給出了簡(jiǎn)單賦值語(yǔ)句的擴(kuò)展BNF文法。語(yǔ)法圖也稱(chēng)鐵道圖，是擴(kuò)展BNF的圖形表示。圖3.7中的描述可用圖3.8等價(jià)表示。有限狀態(tài)自動(dòng)機(jī)語(yǔ)言由Token構(gòu)成，Token具有簡(jiǎn)單的結(jié)構(gòu)。這裏主要給出識(shí)別Token的機(jī)器模型，有限狀態(tài)自動(dòng)機(jī)或狀態(tài)機(jī)。這是一種有效的識(shí)別Token的工具，只要知道當(dāng)前所處狀態(tài)，就可以確定現(xiàn)有輸入是否為T(mén)oken的一部分。圖3.9，F(xiàn)SA，識(shí)別奇數(shù)個(gè)1構(gòu)成的串。輸入100101的機(jī)器操作如下處理：輸入 當(dāng)前狀態(tài) 接受串否？Null A no1 B yes10 B yes100 B yes1001 A no10010 A no100101 A yes通常，F(xiàn)SA有一個(gè)開(kāi)始狀態(tài)，一個(gè)或多個(gè)終態(tài)，以及一組從狀態(tài)到狀態(tài)的變遷。任何串，只要能使機(jī)器從初態(tài)到終態(tài)（通過(guò)一系列變遷），則該串為機(jī)器所接受。圖3.10，識(shí)別帶符號(hào)整數(shù)。非確定型有限自動(dòng)機(jī)確定型FSA——對(duì)其每個(gè)狀態(tài)，每個(gè)輸入符號(hào)，有唯一的變遷到相同或不同狀態(tài)。非確定型FSA具有：1、一個(gè)狀態(tài)集合2、一個(gè)初始狀態(tài)3、一個(gè)終止態(tài)集合4、一個(gè)輸入符號(hào)集合5、一個(gè)從狀態(tài)到狀態(tài)的變遷集合，每個(gè)變遷接受來(lái)自輸入符號(hào)集的一個(gè)元素。非確定性是指：從一個(gè)狀態(tài)有多個(gè)具有相同標(biāo)記的弧線(xiàn)連出，從而必須作出選擇。一個(gè)串稱(chēng)為可接受的，如果存在從初始結(jié)點(diǎn)到終止結(jié)點(diǎn)之一的路徑，即使其他路徑可能不能到達(dá)某終態(tài)。正則文法是BNF文法的特例，等價(jià)於FSA，形式為：<nontrerminals>::=<terminal><nonterminal>|<terminal>例：A→0A|1A|0產(chǎn)生以0為結(jié)尾的01串。正則運(yùn)算式正則運(yùn)算式是語(yǔ)言定義的另一種形式，等價(jià)於FSA和正則文法。定義：1、單個(gè)終結(jié)符是正而運(yùn)算式2、如a、b是正則運(yùn)算式，則a

b,ab,(a),a*也是正則運(yùn)算式。3、除1、2外，沒(méi)有其他是正則運(yùn)算式?？梢杂谜齽t運(yùn)算式來(lái)表示任何用正則文法或FSA定義的語(yǔ)言，雖然將任意FSA轉(zhuǎn)換為正則運(yùn)算式並不總是明顯的。下麵兩圖為到FSA的轉(zhuǎn)換：壓棧自動(dòng)機(jī)PushdownAutomataPDA是類(lèi)似於FSA的抽象模型機(jī)，等價(jià)於BNF文法，它具有有限個(gè)狀態(tài)，有一個(gè)下壓棧，其移動(dòng)規(guī)劃如下：1、讀輸入符號(hào)，並讀棧項(xiàng)符號(hào)2、基於兩個(gè)輸入，機(jī)器進(jìn)入一個(gè)新?tīng)顟B(tài)，並寫(xiě)0個(gè)或多個(gè)符號(hào)在棧頂。3、如果棧空，則串被接受（或PDA處?kù)督K態(tài)）易於看出PDA比FSA具有更強(qiáng)大的能力。如：anbn不能被FSA識(shí)別，但可以被PDA識(shí)別。PDA接受的語(yǔ)言等價(jià)於上下文無(wú)關(guān)語(yǔ)言?？紤]產(chǎn)生串的最左推導(dǎo)的過(guò)程，在這種情形，語(yǔ)句形式存放在棧中，PDA的操作如下：1、如棧頂是終結(jié)符，將其和下一輸入比較，如相同，則彈出棧。如不相匹配，則出錯(cuò)。2、如棧頂是非終結(jié)符X，用串а替代X，а是產(chǎn)生式X→а的右端。這樣PDA模擬了上下文無(wú)關(guān)文法的最左推導(dǎo)，這種構(gòu)造實(shí)際上形成了一個(gè)非確定型PDA，等價(jià)於對(duì)應(yīng)的BNF文法。在第二步中，可能有多個(gè)X→α樣式的規(guī)則，規(guī)則的選用需人來(lái)選擇。確定型PDA和非確定型PDA間關(guān)係，P94-95的回文例子。確定型PDA等價(jià)於LR（K）文法，對(duì)實(shí)際的編譯器設(shè)計(jì)是非常重要的。高效的語(yǔ)法分析演算法文法描述語(yǔ)言是自頂向下，而語(yǔ)法分析則是自底向上，從個(gè)體字元開(kāi)始。一般的分析策略：每種類(lèi)型的形式文法總是和某類(lèi)型的自動(dòng)機(jī)緊密相關(guān)。自動(dòng)機(jī)是一種抽象機(jī)，讀一個(gè)輸入帶，產(chǎn)生一個(gè)輸出帶。然而，BNF文法可能是含混的，因此，自動(dòng)機(jī)必須是非確定的。非確定型壓棧機(jī)能識(shí)別任何上下文無(wú)關(guān)文法，通過(guò)使用猜測(cè)策略。對(duì)語(yǔ)言翻譯而言，不需猜測(cè)的確定型自動(dòng)機(jī)是需要的。對(duì)正則文法，總有對(duì)應(yīng)的確定型自動(dòng)機(jī)。對(duì)BNF文法則沒(méi)有，除非文法無(wú)二義並滿(mǎn)足某些其他限制。對(duì)無(wú)二義BNF文法，已找到直接的語(yǔ)法分析技術(shù)。最早的技術(shù)是遞歸下降法。主要的進(jìn)展是Knuth的LR文法（lefttorightparsingalgorithms），可描述所有可用確定型壓棧機(jī)識(shí)別的BNF文法。LR（1）——為了確定分析決策，只需向前看一個(gè)符號(hào)。SLR——simpleLR，LR的子類(lèi)LALR——lookaheadLRLL——自頂向下技術(shù)，是遞歸下降的推廣語(yǔ)義建模語(yǔ)言的手冊(cè)必須定義語(yǔ)言中每個(gè)結(jié)構(gòu)的含義，包括單獨(dú)結(jié)構(gòu)的含義以及和其他結(jié)構(gòu)組合時(shí)的含義。語(yǔ)言提供了不同結(jié)構(gòu)，用戶(hù)（為了寫(xiě)正確的程式，預(yù)測(cè)語(yǔ)句的執(zhí)行效果）和實(shí)現(xiàn)者（正確地實(shí)現(xiàn)語(yǔ)言）需要這些結(jié)構(gòu)的精確定義。大多數(shù)語(yǔ)言中，形式文法用於定義語(yǔ)法，一段文字或例子用於定義語(yǔ)義，但定義是不精確的，有二義性，不同作者可能有不同理解。語(yǔ)義定義問(wèn)題還是理論研究的目標(biāo)，但至今沒(méi)有令人滿(mǎn)意的解答。已有各種形式方法用於語(yǔ)義定義。文法模型對(duì)定義語(yǔ)言的BNF文法進(jìn)行擴(kuò)展，給出程式的語(yǔ)法分析樹(shù)，從樹(shù)中抽取出附加資訊。屬性文法便是抽取附加資訊的一種方式。命令或操作模型定義程式如何在某虛擬機(jī)上執(zhí)行。通常描述為一自動(dòng)機(jī)，但比語(yǔ)法用的簡(jiǎn)單自動(dòng)機(jī)遠(yuǎn)為複雜。自動(dòng)機(jī)有內(nèi)部狀態(tài)——對(duì)應(yīng)程式執(zhí)行時(shí)的內(nèi)部狀態(tài)，包括所有變數(shù)的值、執(zhí)行程式本身、以及各種系統(tǒng)定義的數(shù)據(jù)結(jié)構(gòu)。一組形式定義的操作用於刻劃自動(dòng)機(jī)內(nèi)部狀態(tài)如何改變。此外還需定義程式文本如何翻譯成自動(dòng)機(jī)的初始狀態(tài)。語(yǔ)言的操作定義對(duì)語(yǔ)言如何實(shí)際執(zhí)行給出了相當(dāng)直接的抽象。也可能提出一個(gè)更抽象的模型，作為語(yǔ)言的軟體解釋的基礎(chǔ)。70年代的VDL（ViennaDefinitionLanguage）是一個(gè)操作方法。它擴(kuò)展語(yǔ)法分析樹(shù)以包含機(jī)器解釋器。計(jì)算的狀態(tài)是程式樹(shù)加上描述機(jī)器中所有數(shù)據(jù)的樹(shù)。每條語(yǔ)句的執(zhí)行使樹(shù)的狀態(tài)發(fā)生變化。作用型模型試圖直接構(gòu)造每個(gè)程式的功能的定義，採(cǎi)用層次式的構(gòu)造方式。程式中每個(gè)基本的或程式員定義的操作代表一個(gè)數(shù)學(xué)函數(shù)。語(yǔ)言的程式控制結(jié)構(gòu)用於將這些函數(shù)複合為更大的序列，代表運(yùn)算式和語(yǔ)言。語(yǔ)句序列和條件分叉表示為個(gè)體函數(shù)構(gòu)造而成的函數(shù)。迴圈通常表示為遞歸函數(shù)。最終，為整個(gè)程式導(dǎo)出一個(gè)完整的功能模型（函數(shù)模型），指稱(chēng)語(yǔ)義歸於此類(lèi)。公理模型使用謂詞演算，每個(gè)語(yǔ)法結(jié)構(gòu)的語(yǔ)義被描述為公理或推導(dǎo)規(guī)則，用於導(dǎo)出結(jié)構(gòu)的執(zhí)行效果。從一個(gè)初始假設(shè)開(kāi)始，假設(shè)輸入變數(shù)滿(mǎn)足一定的約束，在程式語(yǔ)句執(zhí)行後，使用公理和推導(dǎo)規(guī)則來(lái)推導(dǎo)其他變數(shù)值需滿(mǎn)足的限制，最終，程式的結(jié)果被證明滿(mǎn)足希望的約束（描述了它們的值和輸入值的關(guān)係）。如Hoare的公理語(yǔ)義。規(guī)約模型描述實(shí)現(xiàn)程式的各個(gè)函數(shù)的關(guān)係，只要我們可以證明一個(gè)實(shí)現(xiàn)符合任意兩個(gè)函數(shù)間的關(guān)係，則稱(chēng)實(shí)現(xiàn)相對(duì)於規(guī)約是正確的。代數(shù)數(shù)據(jù)類(lèi)型是形式規(guī)約的一種形式。例如：實(shí)現(xiàn)棧的程式，S表示棧，則有公理，pop(push(S,x))=S任何一個(gè)實(shí)現(xiàn)如果能保持這種關(guān)係，則稱(chēng)是棧的正確實(shí)現(xiàn)。上述各種形式語(yǔ)義模型各有優(yōu)點(diǎn)，但均不能稱(chēng)為完全實(shí)用的和適用的，各有其適合範(fàn)圍。屬性文法這是最早的開(kāi)發(fā)語(yǔ)義模型的工作之一。其思想是對(duì)分析樹(shù)中的每個(gè)結(jié)點(diǎn)關(guān)聯(lián)一個(gè)函數(shù)，從而給出結(jié)點(diǎn)的語(yǔ)義內(nèi)容。屬性文法的創(chuàng)建是通過(guò)加函數(shù)（屬性）到文法中的每一條規(guī)則。繼承屬性是一個(gè)函數(shù)，它將樹(shù)中非終結(jié)符值和樹(shù)中更高層的非終結(jié)符值相關(guān)聯(lián)。換言之，任何規(guī)則右端的非終結(jié)符的函數(shù)值是左端非終結(jié)符的函數(shù)。綜合屬性是一個(gè)函數(shù)，它將左端非終結(jié)符和右端非終結(jié)符的值相關(guān)聯(lián)，這些屬性在樹(shù)中向上傳遞資訊，即從樹(shù)中下層資訊進(jìn)行“綜合”。例：考慮算術(shù)運(yùn)算式的簡(jiǎn)單文法。E→T|E+TT→P|T×PP→I|(E)其語(yǔ)義通過(guò)文法中非終結(jié)符間的關(guān)係集合定義。如：下麵函數(shù)生成該文法生成的任意運(yùn)算式的值：產(chǎn)生式 屬性E→E+T Value(E1)=V(E2)+V(T)E→T V(E)=V(T)T→T×P V(T1)=V(T2)×V(P)T→P V(T)=V(P)P→I V(P)=數(shù)I的值P→(E) V（P）=V（E）下圖是一個(gè)屬性樹(shù)，它給出了運(yùn)算式2+4×（1+2）值屬性文法可用於在語(yǔ)法樹(shù)中傳遞語(yǔ)義資訊。例如，聲明資訊可以通過(guò)語(yǔ)言的聲明產(chǎn)生式收集。沿樹(shù)向下傳的符號(hào)表資訊可用於生成運(yùn)算式代碼。下麵屬性可加到非終結(jié)符<decl>和<declaration>來(lái)創(chuàng)建一個(gè)程式中聲明的名字集合。產(chǎn)生式 屬性<declaration>::=<decl><declaration> decl_set(declaration1)=declaname(decl)∪decl_set(declaration2)<declaration>::=<decl> decl_set(declaration)=decl-name(decl)<decl>::=declarex decl-name(decl)=x(decl)::=declarey decl-name(decl)=y(decl)::=declarez decl-name(decl)=z這是綜合屬性，包含程式中聲明的名字集合。該屬性可以沿樹(shù)向下傳遞，成為繼承屬性，用於正確地生成數(shù)據(jù)的代碼。第四章數(shù)據(jù)類(lèi)型任何程式，不管以何種語(yǔ)言寫(xiě)成，均可以視為刻劃了一個(gè)操作集合。並將以一定順序作用到一定數(shù)據(jù)上。語(yǔ)言的基本不同在於：允許的數(shù)據(jù)類(lèi)型、允許的操作類(lèi)型、以及控制操作順序的機(jī)制。下麵章節(jié)將圍繞這些方面展開(kāi)。4.1類(lèi)型和對(duì)象的性質(zhì)數(shù)據(jù)對(duì)象、變數(shù)和常量電腦的數(shù)據(jù)存儲(chǔ)在結(jié)構(gòu)上是簡(jiǎn)單的，通常是由位串構(gòu)成的位元組。而語(yǔ)言虛擬機(jī)的數(shù)據(jù)存儲(chǔ)則有更複雜的組織，如：數(shù)組、棧、數(shù)、字串、以及其他存在於程式執(zhí)行中不同點(diǎn)的數(shù)據(jù)。我們稱(chēng)虛擬機(jī)上一個(gè)或多個(gè)數(shù)據(jù)片斷運(yùn)行時(shí)的組合為數(shù)據(jù)對(duì)象。在程式運(yùn)行中，存在許多不同類(lèi)型的不同數(shù)據(jù)對(duì)象。這些對(duì)象及其相互關(guān)係在運(yùn)行時(shí)動(dòng)態(tài)變化。有些數(shù)據(jù)對(duì)象是程式員定義的，如變數(shù)、常量、數(shù)組、檔等。程式員通過(guò)聲明和語(yǔ)句顯式地創(chuàng)建和操作它們。有些數(shù)據(jù)對(duì)象是系統(tǒng)定義的，不可為程式員直接訪(fǎng)問(wèn)。如：運(yùn)行時(shí)存儲(chǔ)棧、副程式啟動(dòng)記錄、檔緩衝、自由空間列表等。這些數(shù)據(jù)對(duì)象在運(yùn)行需要時(shí)自動(dòng)產(chǎn)生，不需要時(shí)刪除。數(shù)據(jù)對(duì)象表示了數(shù)據(jù)值的一個(gè)容器，是值被存放和檢索的地方，而數(shù)據(jù)值是在記憶體中以一種特定的位模式表示。數(shù)據(jù)對(duì)象和數(shù)據(jù)值在大多數(shù)語(yǔ)言中均是明確區(qū)分的，如圖4.1所示。每個(gè)數(shù)據(jù)對(duì)象有生命期，在生命期內(nèi)可用來(lái)存放數(shù)據(jù)值。數(shù)據(jù)對(duì)象可分為簡(jiǎn)單數(shù)據(jù)對(duì)象和數(shù)據(jù)結(jié)構(gòu)——其他數(shù)據(jù)對(duì)象的聚集。數(shù)據(jù)對(duì)象在其生命期中涉及各種綁定，雖然其屬性不變，但綁定可動(dòng)態(tài)改變。重要的屬性和綁定有：1、類(lèi)型通常在程式翻譯時(shí)，關(guān)聯(lián)數(shù)據(jù)對(duì)象和它可能的取值集合。2、位置通常不由程式員規(guī)定，而是系統(tǒng)存儲(chǔ)管理負(fù)責(zé)。3、值由賦值操作完成綁定。4、名通常在聲明時(shí)完成綁定，但可被子程式調(diào)用和返回修改5、部件通常用指針值相連，可通過(guò)指針的修改而變動(dòng)。變數(shù)和常量程式員通過(guò)變數(shù)顯式地定義和命名數(shù)據(jù)對(duì)象。一個(gè)簡(jiǎn)單的變數(shù)是有名字的簡(jiǎn)單數(shù)據(jù)對(duì)象，通過(guò)賦值修改變數(shù)值。常量是具有名字的數(shù)據(jù)對(duì)象，其值在其生命期內(nèi)永久不變。一個(gè)文字（或文字常量）是一個(gè)常量，其名是其值的書(shū)寫(xiě)表示，如21表示值為21的整數(shù)常量。程式員定義的常量——其名字由程式員指定。常量的綁定由編譯器完成。如C語(yǔ)言中，#defineMAX20語(yǔ)句MAX=4是非法的。永久性Persistence現(xiàn)今大多數(shù)程式仍是採(cǎi)用批處理模式，即1、將程式裝入記憶體2、適當(dāng)?shù)耐獠繑?shù)據(jù)被準(zhǔn)備給程式所用。3、將相關(guān)輸入數(shù)據(jù)讀入程式中變數(shù)，變數(shù)被操作，然後結(jié)果數(shù)據(jù)被寫(xiě)回外部數(shù)據(jù)格式。4、程式終止。程式中變數(shù)的生命期由程式的執(zhí)行時(shí)間所確定。然而，數(shù)據(jù)的生命期經(jīng)常超出程式的單次執(zhí)行，這種數(shù)據(jù)稱(chēng)為永久的，在程式的多次執(zhí)行間存在。具有永久特性的語(yǔ)言對(duì)書(shū)寫(xiě)基於事務(wù)的系統(tǒng)更為高效。檔系統(tǒng)可以解決永久性問(wèn)題。數(shù)據(jù)類(lèi)型一個(gè)數(shù)據(jù)類(lèi)型是一類(lèi)數(shù)據(jù)對(duì)象加上創(chuàng)建及操作它們的一組操作。每個(gè)語(yǔ)言有一個(gè)基本數(shù)據(jù)類(lèi)型集合，是語(yǔ)言固有的。有的語(yǔ)言還提供了設(shè)施允許程式員定義新數(shù)據(jù)類(lèi)型。有的新語(yǔ)言還允許類(lèi)型本身被語(yǔ)言操作（高階能力）。數(shù)據(jù)類(lèi)型的規(guī)約包括：1、區(qū)分該類(lèi)型的數(shù)據(jù)對(duì)象的屬性2、該類(lèi)型數(shù)據(jù)對(duì)象可具有的值3、定義該類(lèi)型數(shù)據(jù)對(duì)象可能處理的操作例如：數(shù)組數(shù)據(jù)類(lèi)型的規(guī)約屬性：維數(shù)、每維的下標(biāo)範(fàn)圍、元素的數(shù)據(jù)類(lèi)型等。值：形成數(shù)值元素有效值的數(shù)的集合。操作：選擇個(gè)體數(shù)組元素、創(chuàng)建數(shù)組、改變數(shù)組形狀，訪(fǎng)問(wèn)下標(biāo)上下界、完成數(shù)組間的算術(shù)操作等。數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)包括：1、存儲(chǔ)表示：用於在電腦記憶體中表示數(shù)據(jù)對(duì)象。2、數(shù)據(jù)類(lèi)型操作被以特殊的演算法或過(guò)程表示的方式，這些演算法和過(guò)程操縱數(shù)據(jù)對(duì)象的存儲(chǔ)表示。數(shù)據(jù)類(lèi)型的規(guī)約大致可對(duì)應(yīng)虛擬機(jī)中該類(lèi)型定義部分的規(guī)約。而數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)定義了那些虛擬機(jī)部分基於更基本的低層結(jié)構(gòu)的仿真，低層結(jié)構(gòu)可以直接是硬體，也可以是有操作系統(tǒng)或微代碼定義的軟、硬體組合。從語(yǔ)法表示來(lái)看，規(guī)約和實(shí)現(xiàn)大部分獨(dú)立於特定的語(yǔ)法形式。屬性：表示為聲明或類(lèi)型定義值：表示為文字或定義的常量操作：可由特殊的符號(hào)、固有過(guò)程或函數(shù)、或隱含地通過(guò)其他語(yǔ)言元素的特殊組合來(lái)調(diào)用。特定的語(yǔ)法表示並沒(méi)什麼不同，但程式語(yǔ)法中提供的資訊被用於確定各種屬性的綁定時(shí)間，從而允許翻譯器建立高效的存儲(chǔ)表示或完成類(lèi)型檢查?；荆ê?jiǎn)單）數(shù)據(jù)類(lèi)型的規(guī)約簡(jiǎn)單數(shù)據(jù)對(duì)象包含單個(gè)數(shù)據(jù)值，這類(lèi)數(shù)據(jù)對(duì)象稱(chēng)為基本數(shù)據(jù)類(lèi)型。雖然不同的語(yǔ)言有不同的基本類(lèi)型集合，但整數(shù)、實(shí)數(shù)、字元、布爾、枚舉、指針等基本都是有的。但各自精確的規(guī)約對(duì)不同語(yǔ)言會(huì)有差異。屬性對(duì)象的基本屬性（如類(lèi)型和名字）通常在生命期中是不變的。有的屬性可存放在描述子中，作為數(shù)據(jù)對(duì)象的一部分在運(yùn)行時(shí)出現(xiàn)。有的屬性只用於確定其存儲(chǔ)表示，在執(zhí)行中不顯式地出現(xiàn)。屬性值和數(shù)據(jù)對(duì)象的值是不同的。值數(shù)據(jù)對(duì)象的類(lèi)型確定了它可包含的可能值集，但在執(zhí)行中任一點(diǎn)，只包含一個(gè)來(lái)自該集合的單值?；緮?shù)據(jù)類(lèi)型定義的值集通常是有序集，有最小值和最大值。操作確定數(shù)據(jù)對(duì)象被處理的方式。操作可能是原操作，也可是用戶(hù)定義操作，本章強(qiáng)調(diào)語(yǔ)言固有的原操作。操作是一個(gè)數(shù)學(xué)函數(shù)，對(duì)一給定輸入?yún)?shù)，有定義的、唯一確定的結(jié)果。每個(gè)操作有作用域，值域。操作的動(dòng)作定義了對(duì)給定參數(shù)的結(jié)果。演算法可用於刻劃操作的動(dòng)作，但其他規(guī)約也是可以的。如可用乘法表來(lái)刻劃乘法的動(dòng)作。操作的基調(diào)（signature）——定義了操作的作用域中參數(shù)的數(shù)量、順序和類(lèi)型，以及結(jié)果值域的順序和類(lèi)型。數(shù)學(xué)記號(hào)：OP：type1×type2×…typen

type—也稱(chēng)為函數(shù)原形操作有單元、二元和多元。動(dòng)作的精確規(guī)約需要比參數(shù)類(lèi)型更多的資訊。特別地，參數(shù)類(lèi)型的存儲(chǔ)表示通常確定那些參數(shù)如何被操作，如：二進(jìn)位數(shù)的乘法和10進(jìn)制數(shù)的乘法有很大不同。這樣，在操作的規(guī)約中，常給出動(dòng)作的非形式的描述。一旦參數(shù)的存儲(chǔ)表示確定，動(dòng)作的精確規(guī)約是操作實(shí)現(xiàn)的一部分。有時(shí)難於確定操作的精確規(guī)約為數(shù)學(xué)函數(shù)，有四個(gè)主要因素。1、操作對(duì)某些輸入無(wú)定義。2、隱含的參數(shù)——操作會(huì)訪(fǎng)問(wèn)其他隱含參數(shù)（全局變數(shù)；非局部變數(shù)）。3、副作用（隱含結(jié)果）——可能修改其他數(shù)據(jù)對(duì)象。4、自我修改（歷史敏感性）——操作修改自己的內(nèi)部結(jié)構(gòu)、或是執(zhí)行中保持的局部數(shù)據(jù)、或是代碼。操作的結(jié)果還依賴(lài)於歷史調(diào)用。例：亂數(shù)產(chǎn)生器。LISP中可自我修改代碼。子類(lèi)型指一個(gè)類(lèi)型是某大類(lèi)的一部分（子類(lèi)型——超類(lèi)型）如：PSCAL中的子域機(jī)制，OO中的繼承機(jī)制。但從理論角度看，子類(lèi)型有嚴(yán)格定義：凡是超類(lèi)型對(duì)象可存在的地方（可承受的操作），子類(lèi)型對(duì)象同樣適用，子類(lèi)型對(duì)象繼承超類(lèi)型對(duì)象的行為。基本數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)存儲(chǔ)表示基本類(lèi)型的存儲(chǔ)受低層電腦的影響很大。如：整數(shù)或?qū)崝?shù)幾乎就是在低層硬體中使用的數(shù)的整數(shù)或浮點(diǎn)數(shù)表示。對(duì)字元值，硬體或OS字元碼被使用?；纠碛桑喝缡褂糜搀w存儲(chǔ)表示，則該類(lèi)型數(shù)據(jù)基本操作可以用硬體提供的基本操作實(shí)現(xiàn)。否則，將使用軟體仿真，從而帶來(lái)效率損失?；緮?shù)據(jù)類(lèi)型的屬性被類(lèi)似地處理。1、為了效率，很多語(yǔ)言設(shè)計(jì)為屬性由編譯器確定。屬性本身並不存放在運(yùn)行時(shí)存儲(chǔ)表示中——存儲(chǔ)表示通常直接使用硬體，如：C、Fortran、Pascal等。2、數(shù)據(jù)對(duì)象的屬性可存放在描述子中作為