高级程序设计语言原理课件

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

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

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

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

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