基于編譯原理的四則混合運算器的實現

摘要：計算機只能執行機器代碼，只有專業程序人員才能較好地使用此類語言。因此編譯程序已成為計算機系統的最重要的系統程序之一。本文主要通過對四則混合計算器的軟件的設計分析講述了編譯程序的工作過程及具體實現。

關鍵詞：四則混合計算器；詞法分析；語法分析；LR分析；語義分析

中圖分類號：TP312 文獻標識碼：A文章編號：1009-3044(2008)15-2pppp-0c

Four Items of Commixture Arithmetic Device Realization

QIN Fei-zhou

(Academy of Physics and Electricity Information，University of Ningxia，Yinchuan 750021，China)

Abstract:The computer can only carry out the machine code，only specialized procedure personnel could use this kind of language well.So the compiler has already become one of the most important systematic procedures of the computer system. Mainly through mix to four fundamental rules design of software of calculator is it tell working course and concrete to realize of compiler to analyse this text.

Key words:The four fundamental operations of arithmetic blends a calculator;Lexical analysis;Grammatical analysis;LR analysis;Semantic analysis

我們每個人都使用過計算器，專用的計算器都是一個現成的器件，是由運算芯片完成運算功能的。而且只能進行單純的加、減、乘、除運算，不能進行四則混合運算。那么如何用計算機來實現一個四則混合計算器呢？用計算機來實現一個四則混合計算器，也就是用編寫程序（即軟件）的方法來實現。

1 編寫四則混合計算器的意義

所謂的編譯程序是指這樣的一種程序，它能夠把某一種語言程序（稱為源語言程序）轉換成另一種語言程序（稱為目標語言程序），而后者與前者在邏輯上是等價的。四則混合計算器的輸入是一個由字符組成的表達式（源程序），如果這個表達式是合法的，則輸出是這個表達式的計算結果（目標代碼）；否則輸出錯誤信息。因此四則混合計算器是一個典型的編譯程序。

編譯原理是計算機軟件專業的一門重要的專業必修課。盡管編譯過程與外文書刊的翻譯工作過程比較類似，但由于編譯程序所翻譯的畢竟不是自然語言，必然有其自身特性，因而學生普遍認為這門課程是專業課中比較難于學習的。即使學習了編譯原理這門課，大多數學生也不可能就開發出一個編譯程序。事實上，許多從事計算機專業的人士也未能編寫出一個完整的編譯系統。而編制四則混合運算的計算器，就等價于編寫一個小的編譯系統，而且又具有可實現性，因此，把這個題目作為編譯原理學習的一個測驗題目是非常適合的。

2 現有編譯程序的類型及特點

現有的編譯程序通常有兩大類：一類是翻譯，另一類是解釋。所謂翻譯，是指在計算機中放置一個能為計算機直接執行的翻譯程序，它以某一種程序設計語言（源語言）所編寫的程序（源程序）作為翻譯或加工的對象，當計算機執行翻譯程序時，就將它翻譯為與之等價的另一種語言目標語言的程序（目標程序）。如C編譯程序就是一種翻譯程序，它的源語言和目標語言分別是相應的C語言和機器語言。解釋程序也是以源程序作為它的輸入，它與編譯的主要區別是在解釋程序的執行過程中不產生目標程序，而是邊解釋邊執行源程序本身，例如FoxPro語言。

3 四則混合計算器程序的邏輯結構

編譯程序完成從源程序到目標程序的翻譯工作，是一個復雜的過程。典型的編譯過程可包括詞法分析、語法分析、語義分析、中間代碼生成、代碼優化、目標代碼生成六個階段和表格管理與出錯處理兩部分。從概念上來講，一個編譯程序的整個工作過程是劃分成階段進行的，每個階段將源程序的一種表示形式轉換成另一種表示形式，各個階段進行的操作在邏輯上是緊密連接在一起的。

由于四則混合計算主要目標是計算出表達式結果，因此編譯階段可以設計為下圖所示：

3.1 詞法分析程序

詞法分析程序又可稱為掃描器，它掃描源程序，并進行分析，將源程序轉換為便于編譯程序其余部分進行處理的內部格式。對于四則混合運算而言，可以將詞法分析程序的預定形式設計為形如（字符，值）的二元式。

3.2 語法分析程序

語法分析是編譯程序的核心部分，語法分析的作用是識別由詞法分析所給出的單詞符號序列是否是給定文法的正確句子（程序）。目前語法分析常用的方法的有自頂向下分析和自底向上的分析兩大類。我對四則混合運算的語法分析采用了自底向上的分析法中的LR(1)分析法。自頂向上分析法的關鍵問題是在分析過程中如何確定句柄。LR(K)分析法正是給出一種能根據當前分析棧中的符號串（通常以狀態表示）和向右順序查看輸入串的K個（K ≥0）符號就能唯一地確定分析器的動作是移進還是歸約。LR語法分析器是由三部分組成：

(1)總控程序，也可以稱為驅動程序，對于所有的LR分析器的總控程序都是相同的。功能就是自左至右地依次掃描輸入符號串的各個符號，并根據當前分析棧中所存放的符號的狀態及當前正在掃描的輸入符號，檢索分析表并按其指示完成相應的分析動作。

(2)分析棧，包括符號棧和狀態棧兩個棧。

(3)分析表，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將也不同。分析又表由狀態轉換表（GOTO）和動作表（ACTION）兩個部分組成，它們都可用二維數組表示。GOTO（S，A）=j，A為非終結符，表明前一動作是用關于A的產生式歸約的，當前面臨非終結符A應移入符號棧，j移入狀態棧。ACTION（Si，a）規定了棧頂狀態為Si時遇到輸入符號a應執行的動作，動作有4種可能：

移入：讀入下一個輸入符號并把它入符號棧。

歸約：當棧頂的部分連續符號串形成一個句柄時，對此句柄進行歸約，把形成句柄的符號串替換為相應的非終結符號。

接受：當總控程序發現棧頂除了棧底標志符號#之外僅有識別符號，而輸入也已達到右端標志符號#時，因而識別出輸入符號串是一個句子時，執行接受動作而結束識別工作。

報錯：當識別程序察覺一個錯誤，因此輸入符號串不是句子而無法繼續識別工作時，調用一個出錯處理子程序進行處理或停止。

為了簡化工作，只考慮整數的四則混合計算，表達式構造文法如下：

G=（VN，VT，P，E），其中VN={E，T，F}，VT={+，-，*，/，(，)，d}，

P={E→E+T|E-T|E*T|E/T|T，T→T*F|F，F→Fd|d}

對文法進行擴展并編號如下：

構造分析表是一個難度很大的工作，是由手工完成的，這里不再描述它的構造過程，直接給出構造好的分析表。

分析表中元素（狀態i，符號a）=Rj， 表示狀態棧的棧頂狀態i遇到終結符號a，則用編號為j產生式進行歸約；元素（狀態i，符號a）=Sj，表示狀態棧的棧頂狀態i遇到終結符號a，，轉移到狀態j；

元素（狀態i，A）=j，表示表明前一動作是用關于A的產生式歸約的，當前面臨非終結符A應移入符號棧，

j移入狀態棧；表格中空白為出錯處理。

3.3 語法分析程序

在語法分析過程中，隨著分析的步步進展，根據每個產生式所對應的語義子程序進行翻譯的方法進行翻譯的辦法叫作語法制導翻譯。語法制導翻譯的具體實現途徑可以與語法分析結合起來，擴充LR的分析棧，增加一個語義棧，用于存放分析過程中每個符號的語義。同時把LR分析的能力擴大，使它不僅執行語法分析任務，且能在用某個產生式進行歸約的同時調用相應的語義子程序，完成相應的語義動作。

四則混合計算文法所對應的語義動作如下：

產生式語義動作

(0)S→E print(E.val)

(1)E→T E.val=T.val

(2)E→E+T E.val=E.val+T.val

(3)E→E-T E.val=E.val-T.val

(4)T→F T.val=F.val

(5)T→T*F T.val=T.val*F.val

(6)T→T/F T.val=T.val/F.val

(7)F→d F.val=d.val

(8)F2→F1dF2.val=F1.val*10+d

(9)F→(E)F.val=E.val

以表達式（13+2）*4/2-5為例說明語法分析的同時結合語義分析，語法分析是判斷該表達是否合法，如果合法則在語法分析結束時得出語義，即得出該表達式的運算結果。表中狀態加下劃線的表示一個狀態，如10表示狀態10。

3.4 表格管理程序

在編譯過程中，需要經常收集、記錄或查詢源程序中所出現的各種量的有關信息。為此，編譯程序需要建立或持有一批不同用途的表格。四則混合計算器的表格有語義表，LR（1）分析表，這兩張表是事先設計好，并存儲在計算機中的，所以只需要編制查表的程序。

3.5 出錯處理程序

程序人員在編寫程序時，錯誤是難免的。四則混合計算器的出錯主要是所輸入表達式的非法，也就是上面LR分析表中空白元素的地方。如果分析到空白處，則給用戶提供“表達式輸入錯誤”的信息。

4 四則混合計算器軟件的具體實現

(1)對于分析棧，可用順序棧這一數據結構，并相應編寫置空棧、判棧空、入棧、出棧的功能函數。其中的三個棧可以申請三個全局變量進行存儲。

(2)表格的建立和查找

由于四則混合計算程序的兩張表格都是事先設計好的，因此可用兩個全局常量來進行存儲。可用結構化數組作為數據結構。對于查找可以設計一個函數完成該功能。

(3)對于輸入串用一字符串變量進行存儲。設計一個界面用于接收表達式的輸入及計算結果的輸出。

(4)語法分析及語義分析可以編寫在一起，用一個主函數完成。歸約和移入也可以用功能功能模塊分別完成，由于語義分析只是在歸約時進行，因此語義分析可以設計與產生式編號相一致的語義子程序完成。

參考文獻：

[1]陳火旺，錢家驊，孫永強.程序設計語言編譯原理.國防工業出版社，1983.

[2]杜淑敏，王永寧.編譯程序設計原理.北京大學出版社，1986.

[3]鄭茂松.編譯程序中代碼生成研究的現狀.計算機工程與應用，1982.1.

[4]呂映芝，張素琴，蔣維杜.編譯原理.清華大學出版社，1988.2.

[5]蔣立源，編譯原理.西北大學出版社，1984.4.

[6]唐策善，李龍澍，黃劉生.數據結構.高等教育出版社，1985.1.

[7]譚浩強.C程序設計（第2版）.清華大學出版社，2003.

收稿日期：2008-02-19

作者簡介：秦飛舟（1972-），女，江蘇泰興人，講師，學士，主要研究領域為：數據庫和網絡方向的教學及軟件開發。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”