代數編譯器

代數編譯器，是指計算機代數系統的編譯器。

計算機代數系統（Computer Algebra System, CAS）是集大整數運算和符號運算於一體的計算平台。實現一個功能強大的CAS，關鍵和核心在於其編譯器的設計和實現。

隨著計算機的進一步普及和人工智慧等新興科研領域的發展，國外許多機構紛紛開始關注運用計算機進行代數運算，由此發展出一批功能強大的計算機代數系統，它們中的典型代表就是Maple和Mathematica。

基本介紹

• 中文名：代數編譯器
• 外文名：CAS compiler
• 作用：源語言處理
• 基本結構：詞法分析器、解析器、主控器等
• 輔助設施：虛擬機、解釋器
• 套用系統：計算機代數系統

功能作用

在傳統的計算機代數系統軟體中，對用戶的命令處理，大多是採用如圖1所示的流程。

圖1 用戶命令處理流程

在整個處理過程中，編譯器構成了整個系統的核心，傳統編譯器除了負責處理源語言的識別、翻譯和相關的檢查之外，還要完成大整數處理、符號處理以及記憶體管理等多項功能，並對每種功能生成對應的目標指令。而處於系統底層、對編譯器起支撐作用的解釋器和虛擬機往往只被設計為編譯器的輔助設施，在系統功能級上處於次要地位。這種設計方式造成了CAS編譯器規模龐大、結構複雜，使得CAS編譯器的開發變得異常困難和艱巨，同時整個CAS的維護和擴展也受到了限制。

改進方式

與上述介紹的CAS的編譯器的設計相比，本文提出的設計思路在於：編譯器並不是把所有的功能都集中在一起實現，它只是負責對源語言進行計算語言學方面的處理，而將符號計算和大整數運算的功能下放到虛擬機上去實現。其中，虛擬機是基於Linux下的GiNaC符號計算包來設計和實現的，把整個編譯器稱為新型編譯器，以區別於普通的CAS編譯器。

GiNaC是由德國Christian Bauer等人於2000年開發出的一個基於Linux的開放源碼的符號計算包，最初被用於進行量子物理計算。

下文以現今流行的計算機代數系統Maple的程式語言（簡稱Maple程式語言）為背景，逐步說明新型編譯器的設計和實現過程。

新型代數編譯器

基本結構

新型編譯器可以由8個模組組成，分別是：詞法分析器，語法分析器，語義分析器，代碼生成器，解析器，表格管理，差錯管理，主控器。各模組之間的關係如圖2所示。

圖2 新型代數編譯器的結構

各模組的功能如下：

(1)詞法分析器：編譯器首先要能讀入字元，並能產生源語言的最小單位——詞，因此需要一個詞法分析器。它的主要功能是掃描程式字元，按照語言的詞法規則，識別出各類單詞符號並輸出，同時進行詞法檢查。

(2)語法分析器：在詞法分析的基礎上，按照語法規則，從單詞串中識別出各類語法成分，同時進行語法檢查。語法分析的目的是為語義分析和代碼生成做準備的。

(3)語義分析器：源語言經過語法分析後只能得到一棵符合語法要求的語法樹，它所包含的運算信息、類型信息和定義信息只是局部的。而對於一種語言的處理，更重要的是知道它是否符合該語言定義的語義規則。尤其對於類型採用隱式定義和傳遞的CAS程式語言，更需要進行語義上的分析。這個工作是在語義分析器中完成的。語義分析器主要完成類型檢查、控制流檢查、唯一性檢查和定義處理。

(4)代碼生成器：如一段原始碼在經過上述3個模組分析後，都沒有發現任何錯誤，即被認為是有效的。那么就可由代碼生成器將它轉換成能被虛擬機理解和執行的目標指令。

(5)解析器：解釋執行目標指令。

(6)表格管理：提供編譯和解釋執行過程中存儲各種信息的場所，並具有對信息進行修改，檢索和查詢的管理功能。

(7)出錯管理：用戶輸入的源語言並不能保證每次都是完全正確的。診查出各類錯誤並準確定位出錯的位置，同時報告錯誤的性質是出錯管理模組的主要功能。它通過一次編譯儘可能地找出所有的錯誤，並具備一定的錯誤糾正能力。

(8)主控器：主要是為了協助各個處理模組之間的信息交流和控制；同時也作為與外界互動的接口，接收用戶信息和反饋處理結果。

虛擬機的設計

編譯器是直接和硬體打交道的，每個編譯器都對應一個目標機，而目標機就是編譯器所針對的具體機器。由於不可能為每台具體的機器都設計一個專用的編譯器，因此引入了虛擬機的概念。虛擬機是指：通過對具體機器進行一定的模擬和抽象而產生虛擬的目標機。在通常的編譯器設計中，採用虛擬機主要是為了提高程式的可移植性；但在新型編譯器設計中，主要是為了實現特定的功能，如大整數的表示和符號運算的實現等。

一、基本思想

虛擬機的設計是基於以下兩個基本思想：

(1)為了源程式的可移植性編譯器依功能可以分為前端和後端。前端主要進行源語言文法處理，後端可以看作目標機的運行。從前端到後端的信息流是源語言結構的處理形式，而從後端到前端則為目標機運行的信息。二者的接口是通過虛擬機來實現的，它能夠將源語言中的各種結構映射到虛擬機的偽操作上。使用虛擬機可以使前端與後端相對獨立，這意味著如果需要將一個編譯器移植到另一台新的機器上，只需根據具體的硬體情況重新開發該編譯器的後端，就可針對不同的後端產生不同形式的目標代碼。而前端只需作少量的修改甚至不作修改。這樣就最大可能地增強了源程式的可移植性。

(2)為了支持特殊的數據結構新型編譯器處理符號計算和大整數計算的能力很大程度上來自虛擬機的支持。在虛擬機中，採用特殊的數據結構來存儲和表示那種突破常規計算機字長的整數，並賦予它們加、減、乘、模等基本運算；同時通過重新定義基本數據類型，使它具有封裝符號計算的功能。這樣，使最小的數據類型都支持符號計算，然後在此基礎上實現更複雜的數據類型，顯然這些複雜的數據類型也同樣支持符號運算。用這樣的方式進行設計，使得編譯器的前端可以把“符號”作為一種基本數據類型來操作，就像整型、浮點類型一樣，而無須考慮它的存儲、表示和運算。

上述的第(1)個思想的實現使得相同的Maple原始碼，即可以在Windows下的計算機代數系統Maple中運行，也可以在Linux下的新型編譯器中解釋執行。第(2)個思想的實現可以確保編譯器前端在整個設計和實現的過程中只關注與語言文法有關的功能，而無須考慮符號和大整數的存儲和表示，這樣就大大降低了編譯器設計的規模和複雜度。同時編譯器功能的下放也有利於系統的維護和擴展，使得整個後端更趨向於結構化和模組化。

圖3 新型編譯器的層次圖

圖3展示了新型編譯器的層次圖，以及和一般CAS編譯器層次圖的對比，從中可以看出二者的編譯器和虛擬機在功能設計上的區別。

二、基本數據結構

根據上述的設計思想，新型編譯器的虛擬機在具體實現上定義了6個暫存器和兩個存儲器，以及3種指令格式的指令系統，如圖4所示。

PC記錄的是當前執行的指令序號；

圖4 虛擬機結構

IR存放的是當前執行的指令；

T存放著數據存儲器當前工作棧的棧頂位置；

BX存放著當前工作棧的棧底位置（基地址）。

指令存儲器用來存放生成的虛擬機指令，它體現了源程式對數據的處理過程。數據存儲器存放著程式運行過程中的所有數據，包括全局數據、局部數據和臨時數據。

3種指令格式是自定義的，分別是二運算元指令、一運算元指令和無運算元指令，採用直接方式和間接定址兩種定址方式。

新型編譯器的虛擬機採用的是棧式管理，以更好地支持程式的遞歸調用和多層定義。每當進入一個函式塊（外層的主程式也可看作一個函式），它就在數據存儲器中建立一塊棧單元作為當前工作棧，並將有關的信息填入，這些信息包括：靜態鏈，動態鏈，返址，局部參數等。同時初始化局部變數單元和形式參數單元，並修改暫存器T與BX的值以指向正確的單元位置。

在實現過程中，虛擬機的所有數據單元全部採用經過封裝後的類型。把封裝大整數表示和運算後的類型定義為numeric類型，然後在此numeric類型的基礎上封裝符號計算能力進一步得到ex類型，再用此ex類型去定義向量、矩陣、列表等比較複雜的類型。這種方法把大整數計算能力和符號計算能力擴展到了各個運算類型，使得各運算類型都支持大整數計算和符號計算。同時，在整個虛擬機運轉過程中，可以根據需要實時地判斷和轉換類型，以保證參與運算的類型相互匹配。

上述虛擬機的構建方式使得從上層編譯器的角度來看，它底層是一台可以進行大整數運算和符號運算的目標機，從而實現了CAS兩大功能的下放和編譯器設計複雜性的降低。

說明的那樣，以GiNaC作為基礎，在此基礎上來建造虛擬機；在虛擬機內部實現系統對大整數和符號計算的處理以及必要的記憶體管理；然後在此基礎上架設用於識別語言文法的編譯器和提供友好互動的用戶界面。這樣就構建了一個完整的計算機代數系統。