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

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

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

G2：T→0T|1T|0|1BNF記號(hào)法的擴(kuò)展BNF文法比較簡單，但用於描述語言卻有諸多不便。將其適當(dāng)擴(kuò)展後更易用。可選性元素用[……]表示。選擇用|表示。重複用{……}*表示。圖3.7給出了簡單賦值語句的擴(kuò)展BNF文法。語法圖也稱鐵道圖，是擴(kuò)展BNF的圖形表示。圖3.7中的描述可用圖3.8等價(jià)表示。有限狀態(tài)自動(dòng)機(jī)語言由Token構(gòu)成，Token具有簡單的結(jié)構(gòu)。這裏主要給出識(shí)別Token的機(jī)器模型，有限狀態(tài)自動(dòng)機(jī)或狀態(tài)機(jī)。這是一種有效的識(shí)別Token的工具，只要知道當(dāng)前所處狀態(tài)，就可以確定現(xiàn)有輸入是否為Token的一部分。圖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è)開始狀態(tài)，一個(gè)或多個(gè)終態(tài)，以及一組從狀態(tài)到狀態(tài)的變遷。任何串，只要能使機(jī)器從初態(tài)到終態(tài)（通過一系列變遷），則該串為機(jī)器所接受。圖3.10，識(shí)別帶符號(hào)整數(shù)。非確定型有限自動(dòng)機(jī)確定型FSA——對其每個(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è)變遷接受來自輸入符號(hào)集的一個(gè)元素。非確定性是指：從一個(gè)狀態(tài)有多個(gè)具有相同標(biāo)記的弧線連出，從而必須作出選擇。一個(gè)串稱為可接受的，如果存在從初始結(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)算式是語言定義的另一種形式，等價(jià)於FSA和正則文法。定義：1、單個(gè)終結(jié)符是正而運(yùn)算式2、如a、b是正則運(yùn)算式，則a

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

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