高級程序設(shè)計語言原理課件

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

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

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

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

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